[운영체제] 11. File System Implementation

kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.

1. Allocation of File Data in Disk

Contiguous Allocation

 

• 단점
  • External fragmentation 
  • File grow가 어려움
    • 파일 생성 시 얼마나 큰 hole을 배당할 것인가?
    • grow 가능 v.s.  낭비(hole을 크게 배당했는데 grow를 안하는 경우 - internal fragmentation 발생, 공간 낭비) 
• 장점
  • Fast I/O
    • 한번의 seek/rotation으로 많은 바이트 transfer 가능 (데이터가 연속으로 있어서)
    • Realtime file용(빠른 I/O가 필요)으로, 또는 이미 run 중이었던 process의 swapping 용(영구저장을 할 필요가 없는 임시저장 용. 공간효율성보다 속도 효율성이 더 중요함)  
  • Direct access 가능

Linked Allocation

• 단점
  • No random access (순차접근으로만 가능)
  • Reliability 문제
    • 한 sector가 고장나 pointer가 유실되면 많은 부분을 잃음
  • Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
    • 512 bytes/sector, 4 bytes/pointer
• 장점
  • External fragmentation 발생 안 함
• 변형: File-Allocation table (FAT). MS DOS와 OS/2에서 사용

Indexed Allocation

• 단점
  • Small file의 경우 공간 낭비(실제로 많은 file들이 small)
  • Too large file의 경우 하나의 block으로 index를 저장하기에 부족
    • 해결방안
      • linked scheme: index block 마지막이 다음 index block을 가리키는 포인터 
      • multi-level index: index를 위한 index 
• 장점
  • External fragmentation이 발생하지 않음
  • Direct access 가능

2. UNIX / MS-DOS

유닉스 파일 시스템의 중요 개념

• Boot block: 부팅에 필요한 정보(bootstrap loader)
• Super block: 파일시스템에 관한 총체적인 정보(어디가 빈 블럭이고 어디가 사용중인 블럭인지에 대한 정보 등)
• Inode: 파일 이름을 제외한 파일의 모든 메타 정보를 저장. (Directory는 파일 이름과 Inode index를 가지고 있음)
• Data block: 파일의 실제 내용을 보관

 

FAT File System(MS-DOS)

 

 

FAT(File Allocation Table)는 다음 block의 위치(pointer)를 저장하는 Linked allocation을 활용함.

FAT를 disk에 2 copy 이상 가짐 -> reliability 문제 개선 & disk block의 512 bytes 모두 활용 가능해 짐 & FAT만 확인해보면 되므로 direct access 가능

3. Free-Space Management

• Bit map or Bit vector
  • bit[i] = 0 -> block[i] free / bit[i] = 1 -> block[i] occupied 
  • Bit map은 부가적인 공간을 필요로 함
  • 연속적인 n개의 free block을 찾는데 효과적
• Linked list
  • 모든 free block들을 링크로 연결 (free list)
  • 연속적인 가용공간을 찾는 것이 어려움 (count logic 필요)
  • 공간의 낭비가 없음
• Grouping
  • linked list 방식의 변형
  • 첫번째 free block이 n개의 pointer를 가짐
    
    • n-1 pointer는 free data block을 가리킴
    • 마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐
  • logic이 복잡, 버그 가능성 ↑
• Counting
  • 프로그램들이 종종 여러개의 연속적인 block을 할당하고 반납한다는 성질에 착안
  • (first free block, # of contiguous free blocks)을 유지
  • 연속적인 free block을 찾기 쉬움

4. Directory Implementation

• Linear list
  • <file name, file의 metadata>의 list
  • 구현이 간단
  • 디렉토리 내의 파일이 있는지 찾기위해서는 linear search 필요 -> time-consuming
• Hash table
  • linear list + hashing
  • Hash table은 file name을 이 파일의 linear list의 위치(index)로 바꿔줌
  • search time을 없앰
  • Collision 발생 가능
• File의 metadata의 보관 위치
  • 디렉토리 내에 직접 보관
  • 디렉토리에는 포인터를 두고 다른 곳에 보관
    • Inode, FAT 등
• Long file name의 지원
  • <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정 크기
  • file name이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
  • 이름의 나머지 부분은 동일한 directory file의 일부에 존재

5. VFS and NFS

• VFS(Virtual File System): 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 OS의 layer
• NFS(Network File System): 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음. NFS는 분산 환경에서의 대표적인 파일 공유 방법

6. 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 시킴
  • 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함
• Buffer cache
  • 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
  • File 사용의 locality 활용
    • 한번 읽어온 block에 대한 후속 요청시 buffer cache에서 즉시 전달
  • 모든 프로세스가 공용으로 사용
  • Replacement algorithm 필요(LRU, LFU 등)
• Unified Buffer cache
  • 최근의 OS에서는 기존의 buffer cache가 page cache에 통합됨