[운영체제] 11. File System Implementation

[이론] Allocation of File Data in Disk

disk에 파일을 저장할 때는 동일한 크기의 sector(logical block)로 나누어서 저장

 

1) contiguous allocation

2) linked allocation

3) indexed allocation

 

1) Contiguous allocation

하나의 file이 disk 상에 연속해서 저장되는 방법

* 장점

1) 빠른 I/O

- HDD는 disk head의 이동 시간이 긴 편인데, 연속 할당을 쓰면 한 번의 seek/rotation으로 많은 양의 data transfer 가능

- process의 swap area로도 쓰임 (임시 저장이기 때문에 공간 효율성보다는 속도 효율성이 좋음)

- real time file용으로 사용 가능 (deadline O)

2) direct access (random access) <-> linked allocation은 불가능

- (start + index)를 통해 원하는 위치에 바로 접근 가능

 

* 단점

중간에 균일하지 않은 크기의 hole이 생김

1) external fragment 발생 가능

연속 할당을 하고 있기 때문에 비어있음에도 활용될 수 없는 조각 발생

2) file grow가 어려움 -> 미리 빈 공간을 확보해놓는 방법 가능

- 그러나 그 이상은 커지지 못하는 문제 발생

- 할당되었지만 당장 사용하지 않는 공간(internal fragmentation) 발생

 

2) linked allocation

연속적이지 않고 빈 위치면 어디든지 들어갈 수 있음 (start, end만 기록)
-1이 나오면 탐색 종료

* 장점

external fragment 발생 X

 

* 단점

- no random access : 순차 접근에 의한 시간 발생

- low reliability : 중간에 bad sector가 발생하면 포인터가 유실되어 뒷부분을 잃을 수 있다

- pointer 공간 차지(bad 공간 효율성) : 한 섹터에 저장될 데이터가 pointer로 인한 용량 부족으로 두 섹터에 저장되는 등의 일이 발생할 수 있다

 

* FAT(File Allocation table)

포인터를 별도의 위치에 보관하여 reliability와 공간 효율성 문제 해결

 

3) indexed allocation

directory에 index block 위치를 표시하고, 해당 block에는 데이터가 저장된 위치 정보들을 저장해둔다

* 장점

- direct access 가능

- no external fragmentation

 

* 단점

- small file의 경우 공간 낭비 (실제로 많은 file들이 small)

- too large file의 경우 하나의 block으로 모든 index를 저장할 수 없다

 

* 해결 방안

1) linked scheme

index block에 실제 파일의 위치를 적다가 마지막에 다음 index block의 위치를 표시

2) multi-level index

index block table과 index block으로 구성 (2단 구성) -> 무조건 2개 이상을 사용하므로 index를 위한 공간 낭비가 있음

 

[실제] UNIX File System의 구조

하나의 partition에 file system을 설치해놓음

1) Boot Block

부팅 시 사용하는 블록으로, 0번 블록에 존재한다. (bootstrap loader)

2) Super Block

파일 시스템에 관한 총체적인 정보를 담고 있다

- 블록의 사용 여부

- Inode list의 범위

- 실제 data block의 위치

3) Inode

- 실제 file system에서는 directory가 metadata를 모두 가지고 있지는 않다 

- UNIX 파일 시스템의 경우 [파일 이름을 제외한 모든 metadata]는 Inode list에 저장된다. (1 index node per file)

- directory는 파일의 이름과 inode의 번호를 저장한다

 

* 파일 위치 저장 방법(Indexed allocation 사용)

- inode의 크기는 고정되어 있음 > 위치 정보를 나타나는 포인터 개수 유한

 

1) 작은 파일

- direct blocks : 대부분의 작은 파일은 이것만으로 나타낼 수 있음

2) 큰 파일

- single indirect : pointer들이 들어있는 index block으로 이어짐

- double indirect : 2단계 index 구조

- triple indirect : 3단계 index 구조

4) Data Block

- file의 실제 내용을 저장 

 

FAT File System

MS에서 처음 만든 file system. 여전히 사용하는 경우도 있음

1) Boot Block

부팅 시 사용하는 블록으로, 0번 블록에 존재한다. (bootstrap loader)

2) FAT

한 블록의 다음 블록의 위치 정보를 저장

- 파일의 metadata의 일부(위치 정보)만 가지고 있음 / 나머지는 directory (file 이름, 소유주, 첫 시작 블록 위치 등)

- linked allocation에서 발생하는 문제 해결 가능

-- 1) reliability : {index, number} = {현 블록 위치, index 블록의 다음 블록 위치}

--- 파일 위치를 담고 있기 때문에 보통 2개의 copy를 둠 -> higher reliability

-- 2) direct access : FAT은 이미 메모리에 올라와 있음 & 중간 위치도 바로 파악 가능

-- 3) pointer 공간을 분리했기 때문에 sector의 모든 저장 공간을 활용할 수 있음 

3) Root directory

4) Data block

 

Free Space Management

비어있는 블록들을 관리하는 방법

1) Bit map / Bit vector

각각의 블록에 0 / 1을 표시하여 할당 여부를 판단

- bit map : 부가적인 공간을 필요로 함

- 연속적인 n개의 free block을 찾는데 효과적(연속 할당을 사용하지 않더라도 disk header의 이동량을 줄이기 위해 연속하게 할당하는 것이 좋기 때문)

 

2) Linked List

- 모든 free block들을 링크로 연결해둔다 (시작 위치)

- 추가적인 공간 낭비가 없지만 연속적인 가용 공간을 찾기 어렵다(실제 사용 낮음)

 

3) Grouping

- linked list 방법의 변형

- 빈 블록은 linked list보다 잘 찾지만, 그래도 연속적인 빈 블록을 찾기는 어렵다

4) Counting

연속적인 빈 블록들을 찾기 위해 {첫 번째 빈 블록의 위치, # 연속된 빈 블록}을 저장

 

Directory Implementation

1) Linear List

<file name, file metadata>의 lisf

(+) 크기가 고정 / 구현 간단

(-) directory 내의 파일 여부를 판단하기 위해서는 linear search가 필요(time-consuming)

 

2) Hash Table

해시 함수를 적용하여 효율적으로 search (no search time)

(-) hash 함수 특성 상 collision 발생 가능

 

3) File의 metadata 보관 위치

1) directory 내에 직접 보관

2) directory에 포인터를 두고 다른 곳에 metadata를 보관 ex) Inode, FAT

 

4) Long file name의 지원

<file name, file metadata>에서 각 entry는 일반적으로 고정된 크기

- file name을 제한하는 것은 비효율적

- file name이 entry 길이보다 길어지는 경우 : entry 마지막 부분에 [이름의 뒷부분이 위치한 곳의 포인터]의 위치를 저장

aaabb -> aaa / bb의 마지막 포인터 저장

 

VFS and NFS

1) VFS (Virtual File System)

사용자를 위해 동일한 system call을 제공하는 system. 주로 개별 파일 시스템 윗 계층에 존재

서로 다른 file system에 대해 [동일한 system call interface(API)]를 통해 접근할 수 있게 해주는 OS의 layer

2) NFS (Network File System)

- 분산 시스템에서의 대표적인 파일 공유 방법 

- 네트워크를 통해 원격으로 파일 접근 요청 -> local 처럼 처리할 수 있다

- client와 server 모두에게 NFS 모듈이 있어야 한다

 

Page Cache and Buffer Cache

1) Page Cache(Page 4KB)

page가 swap area에 내려가 있는지 cache에 올라와 있는지 판별

- virtual memory의 paging system에서 사용하는 page frame -> caching의 관점에서 설명하는 용어

- swap area backing store보다 빠르기 때문에 caching으로 설명

- memory-mapped I/O를 사용하는 경우 file I/O에서도 page cache 사용

- page hit의 경우 파일 접근 시간을 알 수 없기 때문에 replace algo 대신 clock algo 사용

2) Buffer Cache(sector - 512B)

file data가 storage에 있는지 buffer cache에 있는지 판별

- file의 data를 요청했을 때, 사용자 전달에서 끝나는 것이 아니라 OS가 자신의 영역에 data를 저장

- file의 위치와 상관없이 file 접근을 위해서는 system call을 해야 하기 때문에 파일 요청 시간을 알 수 있음

-> replacement algorithm 사용 가능

 

3) Unified Buffer Cache(Page - 4KB)

page cache + buffer cache

- buffer cache와 page cache 공간을 따로 구분하지 않고 합쳐놓은 후, 필요에 따라 page 단위로 할당

(좌) buffer에 있는 data를 page cache에 copy하는 overhead 발생

 

4) Memory-Mapped I/O

system call 없이 memory에 read/write

- [원본] file open 후 read/write system call

1) system call을 통해 disk에 있는 file을 buffer cache로 읽어옴

2) file의 일부를 virtual memory에 mapping

3) 해당 내용을 page cache로 copy : 

> 매핑한 영역에 대한 메모리 접근 연산 = 파일의 입출력 수행과 동일

 

* 만약 mapping만 해놓고 page cache에 copy 안 하면 page fault 발생 -> OS가 handler를 통해 disk로부터 file 가져옴

* I/O는 무조건 system call 필요! but mmp의 경우는 이미 메모리에 올라와 있다면 system call 필요 X

 

프로그램의 실행

1) 실행 파일

* 프로그램은 file system에 실행 파일 형태로 저장되어 있음

> 실행 시 process로 변화

> 독자적인 virtual memory(code, data, stack) 할당

> address translation을 통해 필요한 부분을 Physical memory에 올림

> Physical memory의 공간 부족으로 swap area로 쫓겨나기도 함

 

* code 부분은 read-only로 이미 file system에 실행 file 형태로 저장되어 있다

> 메모리에 올라간 후 쫓겨날 때 swap area로 내려가지 않는다

 

* 실행파일의 code를 실행할 때 loader라는 software가 mmp를 사용한다

> file을 프로그램의 virtual memory (주소) 영역에 mapping 해서 쓰는 대표적인 경우

> 프로그램이 특정 코드에 접근하는데 메모리에 안 올라와 있는 경우 swap area가 아닌 file system에서 가져와야 함

 

2) 데이터 파일

Memory-mapped I/O

page cache(buffer cache)를 논리적 메모리에 직접 mapping 해놓았기 때문에 
다른 process가 이를 share하는 경우 일관성이 깨져 변화가 반영되지 않을 수 있음

* [page fault 시] OS에게 data file의 일부를 process의 주소 공간에 mapping 해달라고 요청해야 함

- 한 번 올려두면 OS의 도움 없이 physical memory로 mapping

- 쫓겨나는 경우 mmap file이기 때문에 swap area가 아닌 file system에 수정된 내용 반영 해야 함

 

* 다른 process가 같은 data file을 mmap한 경우에는 physical memory에서 share한다.

 

Read() system call

copy해서 전달하기 때문에 일관성 문제가 발생하지 않는다 + OS의 중재

* OS는 자신의 buffer cache에서 해당 내용을 읽어옴

> [unified buffer cache] physical memory의 page cache(buffer cache)를 copy해서 process에게 전달