11. 파일 시스템 구현
Allocation of File Data in Disk
- Contiguous Allocation
- Linked Allocation
- Indexed Allocation
Contiguous Allocation
연속 할당 - 하나의 파일이 디스크 상에서 연속되도록 저장하는 방법
- 단점
external fragmentation
file 크기가 커지는 것에 제약 - 미리 할당 (internal fragmentation) - 장점
Fast I/O - 한번의 seek으로 많은 바이트 transfer → realtime file
Direct access (=random access) 가능
Linked Allocation
파일이 빈 공간에 아무 곳이나 들어가고 그 다음 파일의 위치 가리킴
- 장점
external fragmentation 발생하지 않음 - 단점
Direct access 불가능
Reliability 문제 - 한 sector가 유실되면 다음 부분을 잃어버림
Pointer를 위한 공간이 block의 일부가 되어 공간 효율성 떨어짐 - 변형
File-allocation table (FAT) 파일 시스템
포인터를 별도의 위치에 보관하여 reliability와 공간 효율성 문제 해결
Indexed Allocation
디렉토리에서 먼저 인덱스 블록을 가리킴
인덱스 블록에 파일의 위치 정보 나열
- 장점
external fragmentation 발생하지 않음
Direct access 가능 - 단점
Small file의 경우 공간 낭비
너무 큰 파일의 경우 하나의 block이 인덱스를 모두 저장하기에 부족함
- 해결 방안
linked scheme, multi-level index
Unix File System
- Boot block - 부팅에 필요한 정보 (bootstrap loader)
- Super block - 파일 시스템에 관한 총체적인 정보
- Inode list - 파일 이름을 제외한 파일의 모든 메타 데이터
- Data block - 파일의 실제 내용(파일 이름 포함)
FAT File System
- Boot block
- FAT - 파일의 메타데이터의 일부 (위치정보만)
배열의 크기 = Data block의 개수
다음 가리키는 블록의 위치 저장 - Root directory
- Data block - 파일의 메타데이터
Free-Space Management
- Bit map or bit vector
각 블록별로 bit를 둠 - 비어있는 블록 0, 할당된 블록 1
부가적인 공간 필요, 연속적인 free block 찾는데 효과적 - Linked List
비어있는 블록 linked list로 연결
공간 낭비 X, 연속적인 가용 공간 찾기 어려움 - Grouping
첫 번째 free block이 n개의 pointer 가짐
n-1개의 포인터는 free data block, 마지막 포인터는 n개의 pointer 가짐 - Counting
(first free block, # of contiguous free blocks)
Directory Implementation
- Linear list
<file name, file의 metadata>의 list
구현 간단, 디렉토리 내에 파일이 있는지 찾기 위해서 linear search 필요 - Hash Table
linear list + hashing
hash table - file name을 linear list의 위치로 바꿈
search time 없앰, collision 발생 가능 - File metadata의 보관 위치
디렉토리 내에 직접 보관
디렉토리에 포인터를 두고 다른 곳에 보관 (inode, FAT) - Long file name의 지원
list에서 각 entry 일반적으로 고정 크기
file name이 고정 크기 entry 길이보다 길어지는 경우 entry 마지막 부분에 이름 뒷부분이 위치한 곳 포인터 둠
VFS and NFS
- VFS (Virtual File System)
서로 다른 다양한 파일 시스템에 동일한 시스템 콜 인터페이스를 통해 접근할 수 있게 해주는 OS layer - NFS (Network File System)
분산 시스템에서 네트워크를 통해 파일 공유하는 대표적인 방법
Page Cache and Buffer Cache
- Page Cache - Virtual memory 관점에서의 caching
- Memory-Mapped I/O
- Buffer Cache - File system 관점에서의 caching
- Unified Buffer Cache - 기존의 buffer cache가 page cache에 통합됨
