운영체제 시리즈 14. File System Implementation

Allocation of File Data in Disk

디스크에 파일 정보를 어떻게 할당할 것인가를 결정한다.

Contiguous Allocation(연속할당)

연속해서 할당하는 방법이다. 

 

[장점]

- Fast IO : 연속적으로 할당되어 있기 때문에 한 번의 seek 또는 rotation으로 많은 내용을 빠르게 찾을 수 있다. 많은 바이트 transfer용도, realtime file 용도, swapping용도(스와핑은 공간 효율성보다는 속도 효율성이 중요하다) 등으로 사용된다.

- Direct access(Random access)가 가능하다.

 

[단점]

- 외부조각이 발생한다.

- file의 크기를 증가시키는 것이 어렵다. 파일이 커질 것을 대비하여 미리 확보해 놓으면 내부조각이 발생한다.

Linked Allocation

다음 파일의 위치정보를 가지고 있는 방식이다. LinkedList와 비슷하다. 디렉토리에는 파일의 처음 주소와 끝 주소를 정보를 포함한다.

 

[장점]

- 외부조각이 발생하지 않는다.

 

[단점]

- 직접접근(direct access)이 안 된다.

- reliability(신뢰성) 문제가 생길 수 있다. 한 sector가 고장나서 다음 sector에 대한 포인터가 유실되면 많은 부분을 잃게 된다.

- 공간효율성이 떨어진다. 포인터를 위한 공간이 블럭의 일부가 되기 때문이다. 일반적으로 512bytes/sector의 크기가 할당되는데 4bytes/pointer의 크기만큼 포인터에게 할당된다. 실제 디스크와 컴퓨터 내부의 인터페이스가 512bytes 단위라서 포인터까지 합치면 512bytes가 넘어가므로 2 sector가 필요하게 된다.

 

[변형]

FAT(File-Allocation Table) 파일 시스템을 활용하여 포인터를 별도의 위치에 보관하여 reliability 문제와 공간효율성 문제를 해결한다. 

Indexed Allocation

index block을 두어 데이터 블럭을 관리한다. 인덱스 블럭에는 각 데이터의 위치정보가 담겨있다. 4번째 블럭에 접근하고 싶다면 인덱스 블럭의 4번째 인덱스(인덱스 3)에 접근하면 된다. 

 

[장점]

- 외부조각이 발생하지 않는다.

- 직접접근이 가능하다.

 

[단점]

- 작은 파일의 경우 공간이 낭비된다. 아무리 파일이 작아도 최소한 2개의 블럭(인덱스 블럭, 데이터 블럭)이 필요하다. (실제로 많은 파일이 작다.)

- 매우 큰 파일의 경우 하나의 인덱스 블럭으로 저장하기에 부족하여 Linked scheme이나 multi-level index 등으로 해결한다.

유닉스 파일 시스템의 구조

유닉스 파일 시스템에서 어떤 파일 시스템이라도 boot block은 첫번째에 오기로 약속 되어있다.

 

- Boot block : 부팅에 필요한 정보를 담고 있다. (bootstrap loader)

- Super block : 파일 시스템에 대한 총체적인 정보를 담고 있다.

- Inode : 파일 이름을 제외한 모든 메타데이터를 담고 있다.

- Data block : 실제 파일 내용을 담고 있다. 파일의 이름은 직접 가지고 있다.

 

유닉스는 indexed allocation을 약간 변형한 형태로 사용하고 있다. 파일의 크기에 따라 다른 방식으로 위치정보를 표시한다. 매우 작은 파일의 경우에는 direct block으로 표시하며 파일이 커질 수록 single indirect, double ~, triple ~로 표시한다. 한정된 inode에 모든 파일의 위치정보를 가지고 있기 위해서다. 

FAT File System

 

FAT라는 별도의 테이블에 다음 블럭의 정보를 담는다.  data block의 크기가 n이면 FAT의 크기도 n이다. 217번 블럭이 첫번째라면 FAT에서 217번에 가면 655 엔트리 정보를 가진다. 655번에 가면 355의 정보를 가지고 이런식으로 하다가 EOF가 나오면 파일이 끝난다. Linked allocation을 사용하다 FAT이라는 별도의 테이블을 두어 reliability가 개선되었고, random access가 가능하다.

Free-space Management

빈 블럭의 관리방법이다.

Bit map 또는 bit vector

0 : 빈블럭, 1 : 할당된 블럭으로 표기한다. bit map은 부가적인 공간을 필요로 하지만 연속적인 n개의 free-space를 찾는데 효과적이다.

 

참고 블로그

Linked List

모든 free block을 링크드 리스트로 연결한다. 연속적인 가용공간을 찾는 것이 쉽지 않지만 공간의 낭비가 없다. 실제로 쓰기 쉽지 않다고 한다.

Grouping

linked list 방법의 변형방법이다. 첫번째 free block이 n개의 포인터를 가진다. 또 마지막 block이 n개의 포인터를 가져서 연결되어 빈 공간을 나타낸다. 연속적인 빈 블럭을 찾기엔 효과적이지 않다.

 

Counting

프로그램이 종종 여러개의 연속적인 블럭을 사용하고 반납한다는 방법에 착안한 방법이다. 시작되는 빈블럭과 거기서 연속되는 빈블럭의 갯수를 쌍으로 관리한다. (first free block , number of countiguous free blocks)

Directory Implementation

- Linear list : 구현이 간단하지만 파일을 찾기 위해서는 linear search가 필요하다

- Hash table : linear list + hashing의 방법으로 구현한 것이다. 파일 이름을 이 파일의 linear list의 위치로 변경해준다. 따라서 search time을 줄였다. 하지만 충돌(collision)이 발생할 수 있다. 

 

- 파일 메타데이터의 보관 위치 : 디렉토리 내에 직접 보관할 수도 있고, 디렉토리에는 포인터를 두고 다른 곳에 보관할 수도 있다.

- Long file name의 지원 : <file name, file metadata>의 리스트에서 각 엔트리는 일반적으로 고정된 크기를 갖는다. 파일이름이 고정된 엔트리 크기보다 길어지는 경우 엔트리의 마지막 부분에 이름의 뒷 부분이 위치한 곳의 포인터를 둘 수 있다. 크기가 넘어가는 이름의 나머지 부분은 동알한 directory file의 일부분에 존재한다.

VFS and NFS

VFS(Virtual File System)

서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 OS의 layer이다.

NFS(Network File System)

분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다. NFS는 분산 시스템 환경에서의 대표적인 파일 공유 방법이다.

페이지 캐시와 버퍼캐시

Page Cache

virtual memory의 페이징 시스템에서 사용하는 페이지 프레임을 caching의 관점에서 설명하는 용어이다. memory-mapped IO를 사용하는 경우 파일의 IO에서도 페이지 캐시를 사용한다.

Memory-mapped IO

파일을 접근할 때 시스템 콜이 아니라 파일의 일부를 memory에 mapping 시켜놓고 사용하는 것이다. read/write 시스템 콜이 아니라 매핑 시킨 영역에서 메모리 접근 명령어를 가지고 수행하기 때문에 빠른 수행이 가능하다. 

Buffer Cache

파일 시스템을 통한 IO 연슨은 메모리 특정 영역인 buffer cache를 사용한다. 파일의 로컬리티를 사용하여 한 번 읽어온 블럭에 대한 후속 요청은 즉시 캐시된 블럭을 전달한다. 모든 프로세스가 공용으로 사용하여 다른 프로세스가 읽어온 파일을 빠르게 사용이 가능하다. OS가 관리하는 영역이므로 LRU, LFU등의 교체 알고리즘 사용이 가능하다.

Unified buffer cache

최근의 OS에서는 page cache와 buffer cache가 통합되었다.

주의할 점은 페이지 캐시나 버퍼캐시를 맵핑하는 것이기 때문에 일관성 문제가 생길 수 있다는 것이다.

정리

파일 시스템의 수행방식에 대해 정리해보았다. 디스크에 어떻게 할당할 것인지, 빈공간은 어떻게 관리할 것인지 등의 이슈가 있었다. 다른 파일 시스템을 사용할 경우에는 어떤 방식으로 소통해서 가져올 수 있는지에 대한 방안도 있었다. cache를 사용하여 운영체제 입장에서 시스템콜을 줄이고 빠른 수행을 가능할 수 있게 하는 장치도 존재했다.

 

운영체제 시리즈는 반효경 교수님의 운영체제 강의 와 "운영체제와 정보기술의 원리"라는 책을 바탕으로 정리한 내용입니다.