22. File system Implementation

Allocation of File Data in Disk

• Contiguous Allocation
  • 단점
    • external fragmentation
    • File grow가 어려움
      • file 생성 시 얼마나 큰 hole을 배당할 것인가?
      • grow 가능 vs 낭비(internal fragmentation)
  • 장점
    • Fast I/O
      • 한번의 seek/rotation으로 많은 바이트 transfer
      • Realtime file용으로 또는 이미 run 중이던 process의 swapping용으로
    • Direct access(=random access) 가능
• Linked Allocation
  • 장점
    • External fragmentation 없음
  • 단점
    • Direct access(직접 접근) 불가능
    • No random access
    • Reliabilty 문제
      • 한 sector가 고장나 pointer가 유실되면 많은 부분을 잃음
    • Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
      • 512 bytes/sector, 4 bytes/sector
  • 변형
    • File-allocation table(FAT) 파일 시스템
      •  포인터를 별도의 위치에 보관하여 reliablity와 공간효율성 문제 해결
• Indexed Allocation
  • 장점
    • External fragmentation이 발생하지 않음
    • random access 가능
  • 단점
    • small file의 경우 공간 낭비(실제로 많은 file들이 small)
    • Too Large file의 경우 하나의 block으로 index를 저장하기에 부족
      • 해결 방안
        • linked scheme
        • multil-level index

 UNIX 파일 시스템의 구조

• 유닉스 파일 시스템의 중요 개념
  • Boot block
    • 부팅에 필요한 정보 (bootstrap loader)
  • Superblock
    • 파일 시스템에 관한 총체적인 정보를 담고 있다.
  • Inode
    • 파일 이름을 제외한 파일의 모든 메타 데이터를 저장
  • Data block
    • 파일의 실제 내용들을 보관

Fat File System

 

Free-Space Management

• Bit map or bit vector
  
  • Bit map은 부가적인 공간을 필요로 함
  • 연속적인 n개의 free block을 찾는데 도움이 됨
• Linked list
  • 모든 free block들을 링크로 연결(free list)
  • 연속적인 가용공간을 찾는 것은 쉽지 않다.
  • 공간의 낭비가 없다
• Grouping
  • linked list 방법의 변형
  • 첫번째 free block이 n개의 pointer를 가짐
    • n-1 pointer는 free data blcok을 가리킴
    • 마지막 pointer가 가리키는 block은 또다시 n pointer를 가짐
• Counting
  • 프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안
  • first free block, # of contiguouse free blocks 을 유지