[OS] File System - Management of Data Blocks

William Stallings의 『Operating Systems, Internals and Design Principles (9th Ed.)』 을 토대로 작성하였음.

👑 Data Blocks

파일 시스템의 구성 요소 중 실제 데이터가 저장되는 블록인 data block이 있다.

파일을 저장하기 위해서는 이러한 데이터 블록에 공간을 할당해야 하며, 파일 시스템은 할당 가능한 공간을

추적하고 관리해야 한다. 데이터 블록의 할당 방법에는 다양한 방식이 존재한다.

💡 연속 할당 (Contiguous allocation)

파일 생성 시, 파일의 전체 크기에 맞는 연속된 공간을 배정하는 방법이다.

FCB 또는 File allocation table에 파일의 시작 블록 번호와 파일의 길이가 저장되며,

이 정보를 통해 파일의 내용을 읽고 쓸 때 필요한 블록 위치를 확인한다.

장점

• 임의의 블록에 직접 접근이 가능하다. 연속된 블록에 저장하므로 파일 내 특정 블록의
  접근이 가능하며, 이는 데이터 접근 속도를 높인다.

• 파일이 연속된 블록에 저장되어 손상 가능성이 줄어들고, 복구 및 백업 시에도 유리할 수 있다. (안전성 ↑)

단점

• 하지만, 연속적인 공간을 사용하므로, 파일 크기 증가가 어렵다.

• 또한, 파일의 생성 및 삭제가 반복되면 연속된 빈 공간이 부족해져 외부 단편화를 초래한다.
  즉, 공간 활용도가 떨어지며, 외부 단편화 해결을 위한 디스크 압축 등의 오버헤드가 발생한다.

정리

연속 할당은 데이터 접근 속도가 빠르고, 구조가 단순하지만, 파일 크기의 동적 증가와

외부 단편화 문제로 인해 현대 파일 시스템에서는 자주 사용되지 않는다.

💡 연결 할당 (Linked allocation = Chained allocation)

연결 할당은 블록들을 개별적으로 할당하고, 각 블록이 다음 블록을 가리키는 포인터를 포함하는 구조이다.

자료구조의 Linked List와 유사하게 동작하며, non-contiguous 할당 방법 중 하나이다.

파일의 각 데이터 블록이 개별적으로 할당되며, 연속 할당처럼 FCB 또는 File allocation table에

시작 블록 번호와 파일의 길이를 기록한다.

장점

• 파일의 크기를 동적으로 증가시키는 데 문제가 없다.

• 블록들이 개별적으로 할당되므로, 연속된 빈 공간을 필요로 하지 않아 외부 단편화가 발생하지 않는다.

단점

• 포인터를 따라가야 하므로, 특정 블록으로의 직접 접근이 불가능하다.

• 블록들이 디스크 상에 흩어져 있을 수 있어, 디스크 접근 속도가 느리다.

• 각 블록들이 포인터로 연결되어 있어, 포인터 손상 시 전체 파일 접근이 어려워진다. (안전성 ↓)

정리

연결 할당은 파일 크기 변경이 빈번하고, 외부 단편화를 피하고자 할 때 유용하지만,

데이터 접근 속도와 안전성 문제로 인해 제한적인 환경에서 사용된다.

💡 색인 할당 (Indexed allocation)

색인 할당은 Index block이라 불리는 별도의 블록을 사용하여 파일의 블록들을 직접적으로

참조하는 방법이다. 각 파일은 별도의 인덱스 블록을 가지며, 이 블록은 해당 파일의 모든 데이터 블록에

대한 포인터(주소)를 저장하고 있다.

장점

• 인덱스 블록을 통해 파일의 모든 블록에 직접 접근이 가능하다.

• 파일의 데이터 블록들이 연속적으로 저장될 필요가 없기 때문에 외부 단편화가 발생하지 않는다.

• 파일의 크기를 증가시키는 데 연속적인 공간이 필요하지 않으므로 문제가 없다.

단점

• 파일의 데이터 블록들이 분산되어 저장되므로, 여러 데이터 블록에 접근할 때 디스크 헤드가 많이
  움직여야 하며, 이로 인해 접근 속도가 느려질 수 있다.

• 인덱스 블록의 손상 시에 파일 전체를 읽을 수 없게 될 수 있다.
  하지만, 각 데이터 블록이 직접적으로 연결되지는 않기 때문에 연결 할당 방식보다는 안전성이 높다.

정리

Indexed allocation 방식은 파일을 구성하는 각 데이터 블록에 대한 인덱스 블록을 사용하여 파일을

관리한다. 이 방식은 직접 접근을 가능하게 하고 외부 단편화를 방지하지만, 디스크 접근 속도가 느릴 수

있으며, 데이터 블록들이 분산되어 저장되기 때문에 지역성의 원리를 반영하지 않는다.

파일 크기 증가에 유연하게 대처할 수 있는 장점이 있으며, 데이터 안전성은 중간 정도 수준이다.

👑 Free-Space Management

파일 시스템에서 디스크의 빈 공간을 효율적으로 관리하기 위해 다양한 방법이 존재한다.

각 방법은 성능, 효율성, 구현 측면에서 장단점을 가지고 있다.

💡 Counting

파일 할당 방식에서의 Contiguous allocation 방식과 유사한 방법을 사용한다.

free-block list의 각 엔트리는 디스크 주소와 개수로 이루어져 있다. 각 엔트리는 첫 번째

free-block의 주소와, 첫 블록 이후 연속적으로 존재하는 빈 블록의 수를 가지고 있다.

즉, x번 블록부터 n개가 비어 있다. 와 같은 방식으로 저장한다.

각 엔트리가 두 가지 정보를 가지고 있기 때문에, 다른 방식에 비해 한 엔트리가 더 많은 공간을

차지한다. 하지만, 연속된 빈 블록들을 하나의 엔트리로 관리하기 때문에 전체 free-block list의

길이는 더 짧아진다는 이점이 있다.

💡 Linked list (free list)

파일 할당 방식에서의 Linked allocation 방식과 유사하다.

모든 빈 블록을 연결 리스트로 연결하며, 각 빈 블록은 다음 빈 블록의 주소를 포함한다.

공간의 낭비가 없다는 장점이 있지만, 빈 공간을 찾거나 할당할 경우 디스크 접근 속도가 느려

성능이 좋지 않다는 단점이 있다.

💡 Grouping

파일 할당 방식에서의 Indexed allocation 방식과 유사하다.

각 그룹은 일정한 개수의 빈 블록을 포함하며, 다음 그룹의 주소를 가진다.

각 그룹이 n개의 빈 블록으로 이루어진다고 가정하면, 처음 n - 1개의 블록들에는

빈 블록들의 주소가 저장되며, 이 주소들은 오름차순으로 정렬되어 있다. 그 다음 마지막

블록에는 다음 그룹의 블록들의 주소를 담고 있다. 이러한 방식을 통해 빠르게 빈 블록들의

주소들을 빠르게 찾아낼 수 있다.

💡 Bit Vector (Bit Map)

각 디스크 블록에 대해 1bit의 정보를 사용하여 해당 블록이 사용 중인지 빈 블록인지를 표시한다.

장점

• 간단하고 직관적이다.

• 연속된 빈 블록을 빠르게 찾을 수 있다.

단점

• 비트맵이 메인 메모리에 전부 올라가 있지 않는다면, 디스크에서 필요한 부분을 불러와야 하는데
  이는 오버헤드를 발생시키며, 성능을 저하시킨다. 하지만, 대규모 디스크의 경우 비트맵 역시
  큰 공간을 차지하기 때문에 메인 메모리에 모두 유지시키는 것은 비효율적이다.

• 큰 디스크에서는 비트 벡터 자체가 많은 메모리를 차지한다.

$ Disk\;size = 2^{40}\;bytes, \qquad block\;size = 2^{12}\;bytes$ 라고 가정하면,
디스크에는 총 $ 2^{40}\;/\;2^{12} = 2^{28} $ 개의 블록이 있다.

비트맵은 디스크의 각 블록을 표현하는 비트를 가지고 있으므로,
비트맵의 크기는 블록의 수와 동일하며, 따라서 비트맵은 총 $ 2^{28}\;bits $ 를 가진다.

$ 2^{28}\;bits = 2^{25}\;bytes = 2^{15}\;Kbytes = 2^{5}\;Mbytes = 8K $
비트맵의 크기는 디스크의 크기와 블록의 크기에 따라 큰 공간을 차지할 수 있다.