---

File Systems Implementation

Allocation of File Data in Disk

1. Contiguous Allocation

• 장점

  Fast I/O
  - 한번의 seek/rotation으로 많은 바이트 transfer
  - Realtime file용으로, 또는 이미 run 중이던 process의 swapping용
  Direct access(=random access) 가능

• 단점

  External fragmentation
  File grow가 어려움
  - File 생성 시 얼마나 큰 hole을 배당할 것인가?
  - Grow 가능 vs 낭비 (internal fragmentation)

2. Linked Allocation

• 장점

  External fragmentation 발생 X

• 단점

  No random access
  Reliability 문제
  - 한 sector가 고장나 pointer가 유실되면 많은 부분을 잃음
  Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
  - 512 bytes/sector, 4 bytes/pointer

• 변형
  File-allocation table (FAT) : 포인터를 별도의 위치에 보관하여 reliability와 공간 효율성 문제 해결

3. Indexed Allocation

• 장점

  External fragmentation 발생 X
  Direct access 가능

• 단점

  Small file의 경우 공간 낭비 (실제로 많은 file들이 small)
  Too large file의 경우 하나의 block으로 index를 저장하기에 부족
  해결 방안 : linked-scheme, multil-level index

UNIX 파일 시스템의 구조

• Boot block : 부팅에 필요한 정보 (bootstrap loader)

• Super block : 파일 시스템에 관한 총체적인 정보

• Inode : 파일 이름을 제외한 파일의 모든 메타 데이터 저장

• Data block : 파일의 실제 내용 보관

FAT 파일 시스템의 구조

• Boot block에는 어떤 파일 시스템과 마찬가지로 부팅에 필요한 정보를 담고있다.

• 메타데이터의 일부(위치정보만)를 FAT에 보관하고 있다.

• 나머지 메타데이터는 디렉토리에 담겨있다.

• 직접 접근이 가능.

• 포인터 하나가 유실되더라도(bad sector) FAT에 내용이 있기 때문에(Data block과 FAT block의 분리) reliability 개선

• Linked Allocation의 단점 극복

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

• Counting

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

Directory Implementation

• Linear list

  <file name, file의 metadata>의 list
  구현이 간단한 장점
  디릭토리 내에 파일이 있는지 찾기 위해서는 linear search 필요 (time-consuming)

• Hash Table

  Linear list + Hashing
  Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
  Search time을 없앰
  Collision 발생 가능성
  

• File의 metadata의 보관 위치

  디렉토리 내에 직접 보관
  디렉토리에는 포인터를 두고 다른 곳에 보관(EX.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-Mapping I/O

  File의 일부를 virtual memory에 mapping 시킴
  매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함

• Buffer Cache

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

• Unified Buffer Cache

  최근의 OS에서는 기존의 buffer cache가 page cache에 통합

사용자 프로그램이 file을 접근하는 방식은 2가지 인터페이스

• Read-Write System Call

  cache에 있는 내용을 copy해서 process 공간에 전달
  운영체제의 중재

• Memory-Mapped I/O

  Copy가 아니라 mapping
  memory에 올라온 file의 내용은 시스템콜을 하지 않고 자신이 CPU를 가지고 있으면서 직접 접근할 수 있기 때문에 빠르다는 장점.
  buffer cache를 mapping하기 때문에 또 다른 mapping이 들어와서 share하게 되면 일관성 문제가 생긴다는 단점.