File-System Implementation

File System Structure

memory와 mass storage 간의 I/O 전송은 block 단위로 수행됨

File system은 disk에 있음

Locial file system은 metadata 정보를 관리
File Control Block(FCB)는 파일의 정보를 포함

File organization module은 파일과 논리 블록을 인지

Basic file system은 device driver한테 명령을 내림
logical block address기반으로 명령을 내림
memory buffer와 cache도 관리

Device drvier(IO controller)는 I/O control layer에 있는 I/O device를 관리

File System Operations

On-disk Structure

file space가 보관함

Boot control block은 OS 부팅에 필요한 정보 포함
Volume control block은 불륨의 상세정보를 포함
Directory structure는 파일을 구성
File control block은 파일에 대한 많은 상세정보를 포함

In-memory Structure

OS가 관리함
Mount table은 mount 정보를 저장
Directory structure cache는 최근에 접근한 디렉토리의 디렉토리 정보를 저장
System-wide open-file table은 각 파일에 대한 FCB의 copy를 저장
Per-process open-file table은 System-wide open-file table의 적절한 entry에 대한 포인터를 저장

Allocation Method

Contiguous Allocation Method

연속적인 블럭으로 파일이 배치됨

모든 경우에 대해 좋은 성능임
시작 지점과 길이만 필요하니 간단함

fragmentation이 발생가능함

extent를 통해 fragmentation을 좀 줄일 수 있음

Linked Allocation Method

각 파일이 블록의 연결 리스트이며 0포인터로 끝

compaction과 fragementation이 없음

Reliability가 부족(link하나가 깨지면 뒤가 다 깨짐)
블록 놓는게 많은 I/O와 디스크 검색을 요함

FAT(File Allocation Table)
각 블록마다 하나의 엔트리를 가지며 block 번호로 인덱싱됨

Indexed Allocation Method

각 파일이 data block에 대한 포인터의 고유한 index block을 가짐

Performance of Allocation Methods

Contiguous는 sequential 이랑 random에 좋음
Linked는 sequential에 좋은데 random에 안좋음

Indexed는 좀 복잡함
single block access는 index block read 후 data block read를 요해서 2번 읽는 문제가 있음
Clustering을 통해 처리량과 오버헤드를 줄일 수 있음

Free-Space Management

파일 시스템은 사용 가능한 block/cluster를 추적하기 위해 free-space list를 유지함

Bit vector or bit map

첫 번째 free block의 블록 번호 계산
(단어당 비트 수) * (0값 단어의 수) + 첫 번째 비트의 오프
연속 파일을 쉽게 얻을 수 있음

Page Cache

Page cache는 virtual memory과 address를 사용하여 disk block 대신 page를 캐시

Memory mapped I/O는 page cache를 씀
Routine I/O는 buffer cache를 씀

Unified Buffer Cache

Unified Buffer Cache는 동일한 page cache를 사용해서 메모리 매핑 페이지와 일반 파일 시스템 I/O를 모두 캐시하여 이중 캐시를 방지

Log Structured File Systems

Log structured (or journaling) file systems은 각 메타데이터 업데이트를 transaction으로써 파일에 기록
transaction이 로그에 기록되면 커밋으로 간주하지만 아직 파일 시스템에 업데이트가 안 되었을 수도 있음
로그는 파일 구조에 비동기적으로 쓰임
파일 시스템이 충돌하더라도 로그에 남아 있는 모든 transaction을 계속 수행해야 함