[운영체제] 데이터 블록(Data Block)의 관리

 

 

파일 시스템에서의 Data Blcok

 

파일에서는 Block이라고 하는 것을 저장단위로 사용한다.

이 Block 하나의 크기는 4096바이트이다. 

 

디스크에서 파일을 저장할 때, Block을 무작위로 저장하지는 않는다. 어떻게 배치하느냐에 따라 그 전략이 달라진다.

우선, 지금은 잘 사용하지 않는 _Contiguous Allocation_에 대해 알아보자.

 

 

 

 

Contiguous Allocation

 

이름을 보고 유추할 수 있듯이, _Contiguous Allocation_방식은 파일을 저장할 때 연속적으로 Block을 배치한다.

이 방식을 사용하면 File Allocation Table을 사용하는데, 여기에 파일의 시작 Block과 Block의 길이를 저장한다. 물론 파일의 FCB에서도 파일의 시작 Block과 Block의 길이 정보를 같이 저장한다.

 

 

 

하지만, 이 방식을 굉장히 좋지 못한데 그 이유는 크게 두 가지다.

 

첫 번째로, _external fragmentation_이 발생한다.

fragmentation은 데이터가 연속적으로 저장됨으로 인해 부분적으로 빈 공간이 발생하는 것을 말한다. 이때 각 파일의 외부 공간에 대해서 fragmentation이 발생하는 것을  _external fragmentation_이라고 한다.

 

파일 내부에서 발생하는 fragmentation은 internal fragmentation이라고 한다.

 

두 번째는 파일 크기를 늘리기가 힘들다는 것이다.

각각의 파일들은 연속적으로 자리를 차지하고 있다. 그렇기 때문에 fragmentation에서는 부분적으로 공간을 늘릴 수는 있으나, 원하는 만큼 크게 늘리진 못한다. 만약 옮기고 싶다면 전체를 복사해서 새로운 공간에 할당해야 하기 때문에 시간도 굉장히 많이 든다.

 

위와 같은 단점들로 인해 Contiguous Allocation은 사용하지 않는다.

 

 

 

 

 

Chained Allocation(Linked Allocation)

 

 

이 방식은 Linked List를 사용하는 방법으로 생각하면 쉽다.

각 Block이 그다음 Block의 참조를 가진다. 따라서 _external fragmentaion_과 같은 문제는 없어진다.

 

하지만 이렇게 참조를 기반으로 연결되어 있다는 특성 때문에 또 다른 문제가 발생한다.

먼저, Block을 탐색하다가 중간에 참조가 끊어지면 그 뒤에 있는 Block은 읽지 못한다. 또한 하나의 파일 안에서 특정 블록에 대해 바로 접근하는 _direct access_가 불가능하다.

 

이러한 문제를 해결하기 위해 나온 것이 _indexed allocation_이다.

 

 

 

 

 

 

 

Indexed Allocation

 

 

_index allocation_은 여러 Block 중 임의로 하나를 파일의 인덱스를 관리하는 Block으로 만드는 방식이다.

이 방식으로 사용하면, 해당 Block은 파일을 구성하는 다른 Block들에 대한 정보를 순서대로 지니고 있게 된다.

 

즉, _Direct Access_가 가능하고, _Fragmentation_도 없다.

 

 

 

 

 

Free-Space Management

 

 

빈 공간을 관리하는 방법에도 여러 종류가 있다.

 

 

counting

 

counting 방식은 간단하게 시작 Block 번호와 해당 Block으로 부터 얼마만큼 Free Block인지 세는 방법이다.

 

 

 

 

 

Linked List (free list)

 

 

앞서 파일을 관리하는 방식 중, Chained allocation과 굉장히 유사하다.

마찬가지로 Free Block 들을 Linked List로 관리하여 공간을 관리한다.

 

이때, 새로운 Free Block을 할당하기 위해서 맨 앞의 head 값을 사용하기 때문에 할당은 간단하다.

하지만, 여전히 하나의 Block의 참조가 끊키면 다른 Block들도 다 못 사용하기 때문에 좋지 않다.

 

 

 

 

 

 

Grouping

 

이 방식은 앞선 Indexed Allocation 방식과 유사하다.

임의의 Block이 Free Block들에 대해 관리하는 방식이다.

 

하지만 Free Block들이 적지는 않다. 고작 4096바이트 밖에 되지 않고, 하나의 Free Block을 기록하기 위해 4바이트를 사용하여 총 1024개의 Free Block을 적을 수 있을 텐데, 어떻게 많은 Free Block을 관리할 수 있을까?

 

이는 바로 Grouping에서 사용하는 특수한 저장 방식으로 해결 가능하다.

 

 

 

초기에 Free Block들을 관리하기 위해 Super Block List에 모든 Free Block 정보를 넣는다. 여기 안에서 하나씩 꺼내서 각각의 Free Block들을 할당하는데, 만약 Free Block들이 너무 많아진다면 마지막으로 저장한 Free Block으로 이동하여 새롭게 Free Block을 저장한다.

 

위의 예시에서는 109번이 마지막으로 저장되므로 109번 Block으로 가서 다시 처음부터 Free Block을 저장한다.

 

 

사용하는 것도 마찬가지다.

109번 Block앞의 모든 Block을 전부 사용했다면 109번 Block을 Free Block에서 Block으로 할당하기 위해, 109번 Block 안에 있던 모든 정보를 Super Block List로 전부 이동시킨다.

 

 

 

 

 

Bit-vector

 

마지막으로 Bit-vector 방식인데, 이 방식은 모든 Block 들에 대해 Free Block은 1로, 할당된 Block은 0으로 두는 방식이다.

개념적으로는 아주 간단하고 좋은 방식이나 모든 Block들을 저장하는데 8K disk Block이 필요하다.