[OS] File System(2) - Implementation

File System은 Interface와 Implementation으로 나뉠 수 있다. 

저번 포스팅에선 User와 File System 간의 상호작용을 위한 "Interface"를 다뤘다면, 

이번 포스팅에선 실제 내부적으로 어떻게 구현되는지 "Implementation"에서 다뤄볼 것이다. 

 

Main Memory와 Disk간의 데이터 교환 단위는 "Block"인데, 

File System은 Disk에서 "Sequence of Block"으로 표현된다.

 

각 "Block"은 하나 이상의 Sector로 구성된다. 

 

Disk에는 MetaData와 File Data가 저장되어야 한다.

Unix에선 inode(MetaData)를 위한 공간과 File Data를 위한 공간이 따로 할당되어 있다. 

inode의 경우 사이즈가 동일 하지만, File Data의 경우 사이즈가 동일하지 않다. 

따라서, File Data를 할당하는 방법에 대한 이슈가 존재한다. 

 

 

File Data Allocation Methods

Continous Allocation 

같은 File이라면, File Data를 Disk내에 연속적인 Block으로 할당하는 방식이다. 

따라서, Start Location과 Length에 대한 정보가 필요하다. 

이는 Sequential Access와 Random Access를 간단하게 구현이 가능하다. 

 

하지만, Externel Fragmentation 문제가 발생할 수 있다. 

예를 들어, 2개의 block이 남았지만 3개의 block이 필요한 경우,
해당 공간을 사용하지 못하게 된다. 

또한, File의 크기를 확장시키기 어렵다는 단점이 있다. 

 

Linked Allocation 

각 File Data를 Disk Block의 Linked List로 저장하는 방식이다. 

장점

Linked List방식이기 때문에, 연속적으로 할당될 필요가 없다. 

따라서 Externel Fragmentation 문제가 발생하지 않는다.

 

단점

Linked Allocation은 다음과 같은 단점이 존재한다. 

우선, 중간의 한 Block이 고장난다면,

그 뒤에 있는 데이터는 접근할 수 없게 된다. 

 

또한, 특정 index로 접근할 수 없기 때문에 Random Access는 불가능하다. 

 

FAT File System

MS-DOS에서 사용하는 방식으로

FAT File System을 추가하여 Linked Allocation 방식의 단점을 보완하였다. 

 

Linked Allocation에선 한 Block이 고장 나면 뒤에 있는 Block은 접근하지 못한다는 단점이 존재했다.  

FAT File System은 Pointer를 따로 저장하여 Block이 고장 나도 뒤에 Block에는 접근 가능할 수 있게 해준다. 

 

Indexed Allocation 

"Indexed Allocation" 방식에선,

Pointer를 저장하는 "Index Block"을 따로 할당한다. 

장점

index Block을 통해 Random Access가 가능해지게 되었으며,

Externel Fragmentation이 발생하지 않는다.

 

단점 

File마다 하나의 Index Block이 할당된다. 

하지만, 실제 File은 규모가 작은 File이 많은데 

Block하나의 규모의 File이라도

Index Block까지 할당되어 2개의 Block이 할당된다.

즉, Disk 공간이 낭비된다. 

 

또한, File이 클 경우 Index Block안에 모든 Index를 정보를 저장하지 못하는 경우도 발생한다. 

 

Multi-level Index

이는 Unix에서 사용하는 방식이다.

"Direct Block"은 실제 File Data의 Block을 가리킨다.

반면, "Indirect Block"은 실제 File Data가 아닌 다른 Index Block을 가리킨다. 

이러한 구조를 통해 File의 Size가 크더라도 적절한 Index Block을 할당할 수 있다. 

 

 

Free Space Management

새로운 File을 만들기 위해 Disk에는 "빈 Block"을 탐색하여 할당할 수 있어야 한다. 

따라서 "Free Space MangeMent"는

File System에서 사용가능한 공간(빈 Block)을 관리한다.

 

Bit Map (Bit Vector)

Bit Map은 해당 block이 할당되어 있으면 1, 반대의 경우는 0을 저장한다.

이는 연속적인 빈 Block을 찾기에는 효율적이지만, 

Bit Map이라는 추가적인 공간이 필요하다.

 

Linked List

Free Block들을 링크로 연결하는 방식이다.

첫 번째 Free Block에 대한 Pointer는 별도의 장소에 보관한다.

Bit Map과 다르게 추가적인 공간이 필요하진 않지만, 

연속적인 공간을 찾기 어렵다는 단점이 있다.

 

Grouping

Linked List방식의 변형 방식으로, n개의 Block으로 그룹화하여 연결한다.

따라서, 그룹 내의 하나의 Block은 다음 그룹의 Pointer를 저장하고,

나머지 n-1개의 Block은 Free Block을 가리킨다.

 

 

Directory Implementation

Directory는 저번 포스팅에서 언급했듯이, 

File의 일종으로 File들의 Metadata를 저장하고 관리하는 특수한 파일이다. 

 

이러한 Directory를 구현하는 방법에는 2가지가 있다. 

Linear List

"Linear List"는

Directory내의 File들의 정보를 <name, Metadata> 형태의 List로 저장한다.

 

구현이 단순하다는 이점이 있지만, 

특정 File을 찾기 위해선 순차적으로 찾아야 하기 때문에 시간이 소모된다. 

 

Hash Table

"Hash Table"은

File Name을 해쉬 함수를 적용한 결과에 해당하는 Entry에 MetaData를 저장하는 방식이다.

 

따라서, 특정 File을 찾기 위해선 Hash 값의 Entry로 접근하기 때문에

순차적인 탐색이 필요 없어진다.

 

하지만, Hash를 사용하기 때문에 Collision이 발생할 수 있다.

 

 

Performance

File System의 Performance를 증가시키기 위해선 다음과 같은 것들이 고려되어야 한다. 

Seek Time을 줄이기 위해 Data Block과 MetaData Block이 가까워야 한다. 

 

또한, "Last Access Time"와 같은 특정  MetaData는

Read & Write작업이 자주 이루어지기 때문에

유용성과 성능을 잘 비교하여 특정 MetaData를 유지할지 말지 고려해야 한다. 

 

Buffer Cache

File에 Access할 때마다, Disk와 Memory간의 데이터가 이동하는데, 

이러한 I/O작업은 엄청난 OverHead를 일으킨다. 

 

따라서, 최근에 접근한 데이터에 다시 접근한다는 "Temporal Locality"에 따라 Buffer Cache를 추가한다.

Buffer Cache에는 최근에 사용된 Block을 저장함으로써, 

Disk Access하는 빈도를 줄일 수 있다.

 

Recovery

이러한 Buffer Cache를 사용하는 것은 Data Inconsistency문제가 발생할 수 있다. 

예를 들어, System Crash로 인해 Buffer Cache의 데이터에 저장되지 않는 경우가 있다.

만약 해당 데이터가 Directory나 MetaData라면 문제는 더욱 커질 것이다. 

 

이를 해결하기 위해 여러 가지 방법이 있다. 

 

첫 번째는 UNIX의 fsck(Consistency Checker)이다. 

Directory의 Data와 Disk의 Block을 비교하여, 일관성에 문제가 있는 경우 수정한다. 

이는 시스템이 비정상적으로 종료되거나, 예기치 않는 동작이 발생한 경우 사용된다. 

 

두 번째는 중요한 MetaData에 대한 Synchronous Write이다. 

 

세 번째는 Journaling이다.

변경 사항을 Log로 남기는 것으로, 해당 Log는 Data Inconsistency를 해결하는데 사용할 수 있다. 

 

또한, System Program을 사용하여

Disk로부터 다른 Storage Device로 Data를 백업한다. 

Disk나 File에 문제가 발생할 경우 백업을 통해 복구한다.

 

 

References

Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』