[Operating Systems] File Systems

파일은 Secondary storage에 저장하는 논리적인 최소 단위이다. 
즉 사용자 입장에서 보면 이름 붙여진 sequence of bytes이고,
파일 시스템 입장에선 disk block의 콜렉션이다.

파일 시스템이 하는 일은 사용자 측면에서 파일을 바라보고 이름으로 접근하면 그것을 디스크 블락으로 나타내 주는 것이다.
파일 시스템은 disk와 같은 secondary storage에 있으며 데이터를 저장하고 가져오는 것을 쉽게 해준다.

파일은 ADT이며 그것에 대응하는 오퍼레이션들을 가진다.
디렉토리는 특수한 파일로써 파일들을 포함하는데 디렉토리에 속하는 파일을 접근할때 search해야 하는 문제가 발생하므로
OS는 Open File table을 관리하고 파일을 오픈할 경우 그 table의 인덱스를 이용해 바로 파일의 operation을 이용할 수 있도록 한다.

이러한 디렉토리들을 효율적으로 Naming과 Grouping이 가능하도록 어떻게 구조를 설정할 것인가에 대해 여러가지 방법이 있다.
첫째로 Single Level Directory이다. 

 그림과 같이 하나의 디렉토리에 모든 파일들을 관리한다.
따라서 사용자별로 같은 이름을 사용할 수 없는 문제, 파일들을 그루핑 하는 문제들이 있다.

그래서 나온 것이 아래와 같은 Two-level directory이다. 

 
사용자별로 디렉토리를 관리할 수 있도록 해서 naming 문제를 해결한다. 하지만 grouping 문제는 여전히 존재하며 다른 사용자 간에 같은 파일을 가질 수 없는 문제가 있다.

다음은 tree-structured directory이다. 

 이 구조에서는 search도 효율적으로 할 수 있으며 Grouping capability도 존재한다. 또한 이 트리구조에서는 current directory라는 개념이 존재하여 디렉토리 간 이동할 수 있다.
하지만 하나의 파일이 하나만을 가리키기 때문에 하나의 파일을 여러개가 동시에 접근할 수 없게 된다.

따라서 shared file과 subdirectories가 가능하도록 한 것이 acyclic graph directories 구조이다.

 여기에서 생길수 있는 문제로는 하나의 파일을 삭제하였을 때 그 파일을 공유하고 있던 다른 파일에서 생길 수 있는 dangling pointer 문제인데 backpointer를 적용하여 해결할 수 있다.


파일 시스템은 사용되기 전에 mount 되어야 한다.
그리고 각각의 파일들은 권한을 가지고 권한에 따라 가능한 operation을 정의할 수 있다.

여기까지는 파일 시스템을 이루는 파일에 대한 주 설명이며 이제부터는 파일 시스템에 대해 본격적으로 알아보자.

파일 시스템은 어떠한 파티션이 있을때 해당 파티션을 부팅하기 위한 boot control block과 그 파티션에 대한 정보를 담고 있는 partition control block 을 가진다. 그리고 파일들을 관리하기 위해 앞에서 언급하였던 디렉토리 구조를 가지고 파일마다 File Control Block을 가진다.
여기서 partition control block은 파일 시스템의 metadata, file control block은 file의 metadata라고 볼 수 있다.
일반적인 유닉스 계열의 운영체제에서는 FCB가 i-node 형태로 나타나어진다.

프로세스들이 파일을 접근할 때는 각각의 프로세스는 위에서 언급한 open file descriptor table을 가지고 그것을 통해 접근하며, 또한 os는 시스템에 한개 존재하는 global file descriptor table을 가지고 있어서 각각 프로세스의 open file table은 global open file table을 이용하여 접근하게 된다.

파일 시스템은 논리적 기본 단위인 파일을 생성하면 해당 파일에 대해 물리적 기본 단위인 블록들을 할당하며 파일을 삭제하게 되면 기존에 할당된 블록들을 해제한다. 그러한 과정에서 필요한 것이 빈 블록들을 관리하는 Free space Management이다. 

첫 번째 방법은 bit map (or bit vector)이다. 각각의 블록을 비트로 표현하며 데이터가 있으면 1, 없으면 0으로 표현한다. 
이 방법은 bit map을 메모리에 보관해야 하기 때문에 비효율적이다.
따라서 Linked list를 이용하여 Free block끼리 링크드 리스트로 연결하여 관리하기도 한다. 

이런 Free block들을 할당하는 방법으로 contiguous allocation, linked allocation, indexed allocation 방법들이 있다.
첫째로 연속 할당 방법은 인접한 free block들을 할당하는 것이다.
장점은 시작 위치와 크기만 가지면 되기 때문에 구현하기 쉬우며 random access가 가능하다는 것일테지만
단점으로는 external fragmentation이 생길 수 있으며 파일의 크기는 동적으로 변하는데 그것에 유연하게 대처할 수 없는 것이다.
둘째 방법은 linked allocation 방법이다. 각 파일의 시작 블록만을 가지며 각각의 블록들은 블록 내에 링크를 가지고 링크를 따라 연결된다. 공간 활용도 잘 할수가 있으며 external fragmentation 문제도 해결되지만 random access가 불가능하다는 단점이 있다.
이러한 할당 테이블을 가지고 각각의 파일에 해당하는 블록들은 서로 링크로 연결되는 파일 시스템이 FAT(File Allocation Table) 파일 시스템이다.
세번째 방법은 indexed allocation 방법이다. 이것은 하나의 block을 지정하여 그것을 index block으로 두고 그 index block에 모든 블록들에 대한 포인터를 저장하고 접근한다. 이 방법에서는 포인터로 접근하므로 external fragmentation도 해결할 수 있고 모든 엔트리를 인덱스 블록에 저장하기 때문에 random access도 가능하다는 장점이 있다.
하지만 파일의 크기가 커질 경우 index block의 오버헤드가 생길 수 있는데 그 문제는 가상 메모리의 hierarchical 페이지 테이블 처럼 indirect block을 두어 해결할 수 있다. 그 예로 Unix File System에서는 여러개의 direct block과 각각 하나씩의 single direct, double direct 그리고 triple direct를 두어 파일을 블록에 저장하고 FCB인 inode에 해당 정보들을 보관하여 아래와 같이 파일을 관리한다. NTFS가 이 방식을 이용한다.

그리고 파일시스템에서도 또한 locality를 이용하여 buffer cache를 이용해 자주 사용되는 block들을 저장해 둔다. 하지만 memory mapped I/O를 하는 경우에는 page cache로 TLB가 사용되기 때문에 캐쉬를 두번 사용하는 문제가 생길 수 있다.
따라서 memory mapped I/O와 File I/O를 구분하지 않는 Unified Buffer Cache를 사용하여 캐시 간의 data inconsistency 문제와 더블 캐싱 문제를 해결할 수 있다.