11장 File Systems Implementation

reference: kocw의 반효경 교수님 강의와 권진욱 교수님 강의(대학 정규 수업)
수업을 듣고나서 강의 교재를 타이핑하고 필기한 부분을 추가적으로 정리하였습니다.
웹뷰에서 toc를 제공합니다.
github의 md 파일로 보는 게 편하시다면, 여기로 이동해주시면 됩니다.

---

-> 실제 어떻게 구현되어 있는가?

*교수님의 한마디: computer science에서 공통의 화두는 최적화! Optimization이다. (비용은 적게, 효율은 좋게-속도는 빠르게, 공간 활용은 적게 등)

01 Allocation of File Data in Disk

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

01-1 Contiguous Allocation

count라는 파일은 0에서 시작하여 길이가 2 - 2개의 block을 차지하는 파일이다.

• 장점
  • fast I/O
    • 한 번의 seek/rotation 시 많은 바이트 transfer
      • HDD에서 헤드가 탐색하는 것을 seek, 원판이 돌아가는 것을 rotation이라고 말함.
    • realtime file 용으로, 혹은 이미 실행 중이던 프로세스의 swapping 용
  • direct access (= random access) 가능 - 정보가 연결되어 있으니까 바로 접근 가능하다.
• 단점
  • external fragmentation (저장하지 못하는 hole-빈 공간 발생)
  • file grow가 어려움
    • file 생성 시 얼마나 큰 hole을 배당할 것인가?
    • grow 가능하지만 낭비 (파일 크기가 커질 것을 대비해서 미리 할당 → internal fragmentation)

참고로, 외부 조각은 아무도 사용하지 않아 누군가에게 할당될 수 있는 공간을 의미하고, 내부 조각은 이미 할당이 됐는데 아직 사용하지 않는 공간을 의미한다.

01-2 Linked Allocation

jeep 파일은 9번에서 시작해서 25번에서 끝난다는 것을 표시해두었다.

9번지에 다음 데이터는 16번지에 있다고 써져있다.

• 장점
  • external fragmentation 발생 X
• 단점
  • No direct access (= no random access) - 같은 파일 내에서 열번째 데이터에 직접 접근할 수 없음
  • seek 시 많은 시간 소요
  • reliability 문제
    • 중간에 하나의 섹터가 bad sector 되면 (쉽게 말해 고장, pointer 유실) 그 뒷 부분은 모두 잃음
  • 포인터를 위한 공간이 block의 일부가 되어 공간 효율성이 떨어짐
    • 보통 한 섹터는 512 bytes (그림에서 한 개의 번지)로 구성되는데 마지막 4 bytes에 다음 블럭을 위한 포인터를 저장함으로써 508 bytes만 저장할 수 있는 상황 → 1%가 항상 손해 (큰 값이다!)

변형: FAT(File-Allocation Table) 파일 시스템

• 포인터를 별도의 위치에 보관하여 reliability와 공간 효율성 문제 해결
• MS-DOS와 OS/2에서 사용
  • 참고로, MS-DOS에서 FAT → winFAT32 → NTFS 로 개선시켜 사용한다.

01-3 Indexed Allocation

index란? 목록

jeep란 파일을 구성하는 리스트들이 19번지 block에 들어있다.

19번지에 가보니, 첫번째는 9번지, 두번째는 16번지, ... 와 같이 목록을 알려준다.

• 장점
  • external fragmentation 발생 X
  • direct access 가능
• 단점
  • 파일이 굉장히 작은 경우에도 공간 낭비 (실제로 많은 파일들이 굉장히 작음)
    • 인덱스를 위한 블록 + 실제 데이터를 저장하기 위한 블록
  • 굉장히too 큰large 파일의 경우 하나의 인덱스 블록으로 모두 표현 불가능
    • 해결 방안
    1. linked scheme : 마지막에 또 다른 인덱스 블록의 위치를 가리킴
    2. multi-level index : 인덱스가 또 다른 인덱스 블록을 가리킴

02 UNIX와 MS-DOS의 파일 시스템 구조

02-1 UNIX(Linux) 파일 시스템 구조

• Boot block
  • 부팅에 필요한 정보 (bootstrap loader)
  • 어떠한 파일 시스템이라도 0번 블록이 boot block
• Super block
  • 파일 시스템에 관한 총체적인 정보
    • 어디가 빈 공간인지, 어디까지가 inode list인지 등
• Inode (중요!)
  • 파일 하나 당 inode 하나 할당
  • 파일 이름을 제외한 파일의 모든 메타데이터 저장 (파일 이름은 data block에 저장)
  • direct blocks는 바로 data block의 데이터를 가르키고, single indirect는 index 1개를 가지고, double은 index를 2단으로 갖는다.
• Data block
  • 파일의 실제 내용을 보관
  • directory file
    • (파일 이름, inode 번호)

02-2 MS-DOS 파일 시스템 구조

ms-dos와 windows 계열

차이점: FAT과 Root directory

• Root directory는 말 그대로 C:, D: 을 의미한다.
• FAT: File Allocation Table
  • FAT은 linked allocation을 조금 변형한 것이다.
  • linked allocation에서는 중간에 하나의 섹터가 bad sector 되면 그 뒤에 있는 파일들을 읽지 못한다거나 포인터의 저장으로 공간 효율성이 낮아지는 단점이 있었다. 다음 블록의 위치 정보를 디렉토리 파일에 저장하지 않고 FAT에 저장해둠으로써 이러한 단점을 해결하고 direct access 또한 가능하다.

03 Free-Space Management

첫번째 방법: Bit map or bit vector

• 해당 블록이 사용중인지 아닌지를 비트로 표현
  • bit[i] = 0 : block[i] free
  • bit[i] = 1 : block[i] occupied
• 장점: 연속적인 n개의 free block 을 찾는 데 효과적
• 단점: bit map은 부가적인 공간을 필요로 함

두번째 방법: Linked list

• 모든 free block 들을 링크로 연결
• 장점: 공간 낭비가 없음
• 단점: 연속적인 가용공간(빈공간)을 찾기는 어려움

세번째 방법: Grouping

• indexed list 방법의 변형

• 

  • 첫번째 free block이 n개의 pointer를 가짐
  • n-1 pointer (0, 1, ... , n-1)는 free data block을 가리킴
  • 마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐

네번째 방법: Counting

• 프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안
• (first free block, # of contiguous free blocks) 정보를 유지
  • ex) (31, 5) 31번지 block부터 5개의 free block 있음
• 연속적인 free block 을 찾는데 효과적

04 Directory Implementation

모든 방법은 trade off (장점이 있으면 단점이 있고)

기준: performance(성능-속도포함)/저장공간/비용

• Linear list
  •   

    

  • <file name, file의 metadata>의 리스트
  • 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요
  • 구현이 간단하지만 시간이 오래 걸려 비효율적
• Hash Table

  • 

  • linear list + hashing
  • file name을 이 파일의 linear list 위치로 바꾸어줌
  • search time을 없애서 효율적이지만 해시 특징 상 collision 발생 가능
• File의 metadata 보관 위치
  • 디렉토리 내 직접 보관하거나
  • 디렉토리에는 포인터를 두고 다른 곳에 보관할 수 있다.
    • ex) inode, FAT 등
• Long file name의 지원
  • <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정된 크기
  • 파일 이름이 엔트리 길이보다 길어지는 경우 엔트리 마지막 부분에 포인터를 두는 방법

    • 

  • 이름의 나머지 부분은 동일한 디렉토리 파일 일부에 존재

    • 

05 VFS and NFS

VFS (Virtual File System)

• 서로 다른 다양한 file system에 동일한 시스템콜 인터페이스를 통해 접근할 수 있게 해주는 OS의 layer
• 다양한 file system (HDD, CDROM, NTFS 등) 어디에 저장되든 상관없이 파일 위치만 제대로 알려주면 접근할 수 있다.

NFS (Network File System)

• 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다
• 즉 네트워크를 통해 연결된 다른 파일 시스템에 접근하도록 해준다
• NFS는 분산 환경에서의 대표적인 파일 공유 방법이다
• 파일 위치만 제대로 알려주면 네트워크를 타고 다른 서버에 요청해서 원하는 파일을 얻을 수 있다. ex) google drive -> network drive

06 Page Cache and Buffer Cache

Page Cache

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

Buffer Cache

• 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
• 파일 사용의 locality 활용 (특정 부분만 집중적으로 쓰는 집중성 활용)
  • 한 번 읽어온 block에 대한 후속 요청 시 디스크에 접근하지 않고 buffer cache에서 즉시 전달
• 모든 프로세스가 공용으로 사용
• replacement algorithm 필요 (LRU, LFU 등)

 

결론은, Unified Buffer Cache !!!

• 최근 OS에서는 기존의 buffer cache가 page cache에 통합됨 (둘의 동작이 비슷함)
• 즉 buffer cache도 페이지 단위로 관리

잠깐, Memory-Mapped I/O란?

• File의 일부을 virtual memory 영역에 mapping시킴
• 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함
• 즉, read, write 등의 시스템콜을 사용하는 것이 아닌 메모리에다가 읽고 씀

정리

과거에는 page cache가 중간에 있었다. memory-mapped I/O 요청 시, paging이 먼저 돌아가고 그 중 파일 관련 부분은 buffer cache를 통하도록 작동했다.

하지만 이제는 page caching이 통합되어 두 요청 모두 buffer cache를 이용하도록 한다.

이렇게 하면 일관된 접근 방법이 되기 때문에 버그 가능성이 줄어들고 buffer cache 성능에만 집중하면 되기 때문에 훨씬 효율적인 시스템이 만들어졌다.