File System

 

이 포스트는 서울대학교의 '운영체제의 기초' 강의를 개인 학습용으로 작성한 포스트입니다.

 

 

 

File and Directory

File

이름이 있고 disk에 있는 byte Sequence의 모임

User 입장에서는 byte sequence, OS 입장에서는 block sequence

 

File descriptor (I-node)

파일의 내용에 접근하기 위해 필요한 메타 데이터들을 저장하는 자료구조

보통 빠르게 접근하기 위해 main memory에 복사함

 

* File descriptor를 특정 영역에 모아두면 성능저하 발생 -> spread하게 둠

 

 

Directory

이름과 file descriptor index를 저장한 data content

UNIX에서는 file과 다를바 없음

 

 

Symbolic link : 이름을 mapping함

Hard link : I-number를 mapping함

 

* I-number는 volume 단위로 부여하기 때문에 같은 volume내에 있어야 hard link 가능

 

 

File System

주요 기능

1. 원하는 data에 read/write 할 수 있도록 함

2. Logical resource name을 Physical address로 변환 (Namespace)

 

View on File

User : file name + bye offset

Kernel : Inode + logical block #

Device Driver : physical block #

Device : drive #, cylinder #, head #, sector #

 

Linux case

 

 

 

File Structure

Linked file

장점 : 쉽게 확장 가능, no fragmentation problem

단점 : random access 사실상 불가, 많은 seek

 

 

Indexed file

Index table을 통해 access함

장점 : Sequential, Random access 모두 쉬움

단점 : maximum file size가 제한됨

 

 

* Bit map을 이용한 디스크 free block 관리 : block free/allocate 되어있는지 알아내는 array, String search를 사용해 연속적인 사용 가능한 block 찾을 수 있음

 

* 연속적인 공간을 할당하는 것이 좋음 : 많이 할당하기 위해 90% 이상으로 디스크를 사용하지 않도록 함

 

 

Disk Space Management

File system의 issues

1. Disk space management

2. Naming

3. Protection

4. Reliability (recovery)

 

 

Disk space allocation policy

1. Contiguous allocation

장점 : simple, sequential/random 모두 access 쉬움, 작은 seeks

단점 : 극심한 fragmentation

2. Block-based allocation

장점 : 유용한 disk space사용

단점 : sequential access 많은 seeks, metadata 읽는데 seeks

3. Extent-based allocation : block을 그룹으로 묶어 연관있는 것들을 같은 sylinder에 둠

장점 : optimized disk seek patterns

단점 : random access에는 안좋음

 

 

Evolution of UNIX File Systems

발전 역사

1. S5FS (System V file system)

2. FFS (UFS, Berkeley fast file system)

3. NFS (Network file system)

4. VFS (Virtual file system)

5. Log-structured file system

 

 

S5FS (System V file system)

volume당 file system 1개 존재

Boot area : 부팅시 실행되는 프로그램인 boot loader가 저장, 사용되지 않는다면 empty

Super block : file system에 대한 모든 메타데이터들

Inode list : Inode들의 array들

Data blocks

 

S5FS 문제점

Inode와 Data block간 물리적 거리가 멀어서 과도한 seek operation 발생

할당/해제를 반복할수록 free block이 산재하게 되어 sequential block읽을 때 과도한 seek operation 발생

Super block이 한곳에 있어서 손상되면 file system 사용할 수 없음 (single copy)

 

 

FFS

Cylinder group : 인접한 cylinder를 group화함 (같은 directory는 같은 cylinder group 되도록)

Superblock copy 만들어 놓음

Symbolic link 지원

 

* rotdelay : 다음 섹터 주소를 계산하는 시간을 계산하여 sector를 떨어트려 놓음 

               (계산하는 동안 지나가지 않음)

 

FFS 문제점

Sequential read 여전히 오래 걸림

Crash가 일어났을 때 recovery 오래 걸림

(fsck : file system check - inconsistency 확인하는 명령어)

 

 

Log-structured file system

모든 file system의 변화를 log file로 append함

crash일어나면 log를 통해 복구함

 

LFS design considerations

What to log

Redo & Undo log

Garbage collection

Group commit : 어느 시기에 log 취합하여 정규화시킴

Retrieval

 

 

Disk Scheduling

Seek time을 최소화하기 위해 I/O scheduler가 담당

 

1. FIFO

2. SSTF (Shortest seek time first) : 제일 가까운거 부터, starvation 생길 수 있음

3. Scan : elavator처럼 한 방에 쭉가면서 중간에 걸리는 operation 처리

4. Circular scan : 양 쪽도 fair하게 하기 위해 한 방향으로만 처리함