File Systems Implementation

직접 접근이 가능한 매체라 하더라도 data를 어떻게 관리하느냐에 따라서 순차 접근만 허용하는 경우도 있고 직접 접근이 가능한 경우도 있다.

Allocation of File Data in DIsk

: 디스크 내부를 동일한 크기의 sector 단위로 나누어 저장

• Contiguous Allocation (Array)

  • 하나의 file이 디스크 상에 연속해서 저장됨
    • 오른쪽 표 directory에 metadata는 파일명, 시작점, 길이
    • 단점
      : 외부 단편화
      : File grow가 어려움, 미리 할당 해놓으면 내부 단편화
    • 장점
      : 빠른 I/O에 효과적, 한번의 seek/rotation으로 많은 바이트 transfer
      : Direct access(Random access) 가능

• Linked Allocation (Linked List)

  • Linked list를 이용해 sector들을 연결
    • directory에 파일의 시작점, 끝점
    • 단점
      1. 직접 접근이 되지 않음
      2. 한 sector가 고장나 pointer가 유실되면 많은 부분을 잃음(Reliability)
      3. pointer를 위한 공간이 block의 일부가 되어 공간 효율성 떨어짐
      (512 bytes/sector, 4 bytes/pointer)
    • 장점
      : 외부 단편화 발생 안함
    • 변형
      : File Allocation Table (FAT) 파일 시스템
      -> 포인터를 별도의 위치에 보관하여 relaibility와 공간효율성 문제 해결

• Indexed Allocation

  • 파일마다 데이터가 들어있는 index들이 담긴 index block을 할당
    • 장점
      1. 외부 단편화가 일어나지 않음
      2. 직접 접근 가능
    • 단점
      1. 작은 파일의 경우 공간 낭비
      2. 너무 큰 파일의 경우 한 block으로 index를 저장하기에 부족
         : linked scheme(마지막에는 다른 index블럭을 가리킴),
         multi-level index(다른 index블럭들을 가리키는 index블럭)으로 해결

UNIX 파일 시스템

• Boot block
  부팅에 필요한 정보(bootstrap loader)
  모든 파일 시스템에서 Boot block은 항상 맨 앞에 있음
• Superblock
  파일 시스템에 관한 총체적인 정보를 담고 있다.
• Inode list
  파일 이름을 제외한 파일의 모든 메타 데이터를 저장
  directory file에는 file name, inode number
• Data block
  파일의 실제 내용을 보관

FAT File System (File Allocation Table)

Linked allocation의 변형, file allocation table(FAT)를 추가
Data block 갯수만큼의 FAT에는 다음 block의 번호가 저장되어있음

• 직접 접근 가능
• bad sector가 생겨도 FAT를 참조해 복구 가능

Free-Space Management

• bitmap 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 block을 가리킴
    • 마지막 pointer가 가리키는 block은 또 다시 n개의 pointer를 가짐

• Counting

  • 프로그램들이 종종 여러 연속적인 block을 할당하고 반납한다는 성질에 착안
  • (first free block, # of contiguous free blocks)를 유지

Directory Implementation

• Linear list

  

  • <file name, file의 metadata>의 list
  • 구현이 간단
  • directory 내에 파일이 있는지 찾기 위해서는 linear search 필요

• Hash Table

  

  • linear list + hashing
  • hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
  • search time을 없앰
  • hash collision 발생 가능

• File metadata의 보관 위치

  1. 디렉토리 내에 직접 보관
  2. 디렉토리에는 포인터를 두고 다른 곳에 보관
     • inode, FAT 등

• Long file name의 지원

  

  • <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정크기
  • file name이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
  • 이름의 나머지 부분은 동일한 directory file의 일부에 존재

VFS and NFS

• Virtual File System (VFS)

  • 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 OS Layer

• Network File System (NFS)

  • 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
  • NFS는 분산 환경에서의 대표적인 파일 공유 방법임

Page Cache and Buffer Cache

• Page Cache

  • Virtual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어
  • Memory-Mapped I/O를 쓰는 경우 file의 I/O에서도 page cache 사용

• Memory-mapped I/O

  • File의 일부를 virtual memory에 mapping 시킴
  • mapping 시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함
  • 이미 mapping이 되어있는 내용에 대해서는 커널의 도움을 받지 않고 직접 읽고 쓸 수 있다는 장점

• Buffer Cache

  • File system을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
  • 한번 읽어온 block에 대한 후속 요청시 buffer cache에서 즉시 전달 (locality)
  • 모든 프로세스가 공용으로 사용
  • Replacement algorithm 사용 (LRU, LFU 등)

• Unified Buffer Cache

  • 최근의 OS에서는 기존의 buffer cache가 page cache에 통합됨
  • 똑같이 page 단위로 관리하면서 필요할 때마다 파일 입출력을 위한 공간 혹은 프로세스의 주소공간으로 할당해서 사용