[Linux] Disk Allocation Method

안녕하세요, Einere입니다.

오늘은 Disk allocation method에 대해 알아보겠습니다.

첫번째로, Contiguous Allocation입니다.

이 방식은 disk상에 연속적으로 file block을 할당하는 방식입니다.

만약 특정 file을 append할 때 여유공간이 없다면 충분한 공간이 있는 위치로 이동시킨 뒤 확장합니다.

그리고 원래 자리의 block은 지웁니다.

이렇게 block들을 옮기고 지우는 방식은 copy & paste를 하게 되는데, 그러면 필연적으로 disk access횟수가 늘어나게 되므로 매우 느립니다.

단점으로는, 읽기와 쓰기를 반복하다 보면 곳곳에 조각난 공간이 많이 발생하게 되는데, 이를 external fraction이라고 합니다.

또한 file의 크기는 가변적이므로 필요한 크기를 예측하기 힘들며, 크기가 변할때마다 많은 disk access가 수행되므로 느립니다.

Linked Allocation은 Contiguous Allocation의 단점을 보완한 방식입니다.

file data block이 disk상에서 흩어져 있지만 link를 통해 연결되어 있습니다. (linked list와 유사합니다.)

그리고 마지막 블록의 link에는 끝임을 표시하는 nil(-1)이 저장되어 있습니다.

이 방식 또한 단점이 존재하는데, 바로 linked list의 단점인 sequential access입니다.

즉, 특정 block에 접근하기 위해서는 무조건 첫 block부터 차례대로 접근해야 한다는 것입니다.

따라서 이 방식 또한 느립니다.

그리고 link를 저장하기 위한 추가공간이 필요하므로, 필요한 용량이 커집니다.

위와 같은 단점을 개선하기 위해, FAT(file allocation table)을 도입했습니다.

이 table은 특정 file의 link정보를 저장합니다.

link정보를 따로 저장하므로, disk으 추가 용량이 필요하지 않습니다.

시작 block주소만 알고 있다면 FAT를 탐색하여 이후 block의 주소를 알 수 있습니다.

만약 새로운 block이 추가된다면, 마지막 entry의 값에 추가된 block의 주소를 넣어주면 됩니다.

그러나 table을 위한 공간이 따로 필요한데, 이를 해결하기 위해 main memory의 cache에 해당 table을 저장합니다.

따라서 속도가 빠른 main memory를 우선 탐색하고, 필요한 block address를 구해서 disk에게 IO request를 보내게 됩니다.

마지막으로 Indexed Allocation입니다.

Linked Allocation의 direct access나 random access를 해결하기 위한 방식입니다.

Linked Allocation과는 달리, 하나의 block이 table역할을 하게 됩니다. 이때, 이 block을 index block이라고 합니다.

하지만 file data block이 한두개 정도인 경우라도 무조건 index block을 할당해야 하므로, 공간 낭비가 발생하게 됩니다.

또한 큰 용량의 file을 저장하기 힘들다는 단점이 있습니다.

위와 같은 단점을 해결하기 위해, Multilevel index라는 개념을 도입하게 됩니다.

이 방식은 12개의 direct block과 하나의 single, double, triple indirect block을 가지는 방식입니다.

direct block은 직접적인 data block을 가리키며, indirect block은 index block입니다.

single indirect block은 index block이므로 여러 data block의 link를 가집니다.

double indirect block은 index block의 link를 가지는 index block입니다.

triple indirect block은 index block의 link를 가지는 index block의 link를 가지는 index block입니다.. 헉헉

따라서 한 index block이 256개의 link를 가진다고 가정한다면,

최대 12 + 256 + 256 * 256 + 256 * 256 * 256 = 16843020개의 link를 가질 수 있습니다.

따라서 하나의 block이 512 byte라고 가정하면 8623626240 byte의 크기를 저장할 수 있습니다.