49_파일 할당 방법 (Allocation Method)

49_파일 할당 방법 (Allocation Method)

 

디스크의 직접 접근 특성이 파일의 구현에 융통성을 허용한다. 거의 모든 경우에 하나의 디스크에 여러 파일이 저장되며 이 파일들을 어떻게 디스크 공간에 배치해야 효율적으로 사용할 수 있을지 고민하게 된다. 디스크 공간을 할당 방법과 특성을 살펴 보자.

 

[연속 할당 (Contiguous Allocation)]

연속 할당은 각 파일이 디스크 내에서 연속적인 공간을 차지하도록 요구 한다. 디스크 주소들은 디스크 상에서 선형 순서를 정의 한다. 이러한 순서를 따를 경우 단지 한 작업(job)이 디스크에 접근 한다고 가정하고 블록 b 다음에 블록 b+1을 접근 한다면 통상 헤드의 이동을 요하지 않는다. 헤드의 이동이 필요한 경우는 다음 섹터의 이동할 경우 이다.

 

한 파일의 연속 할당은 디스크 주소와(블록 단위의) 길이로 정의 된다. 파일의 길이가 n블록이고 블록 b에서 시작한다면 이 파일은 블록 b, b+1, b+2 … b+n-1을 차지한다. 각 파일을 위한 디렉토리 항목은 이 파일의 디스크 내 시작 블록 주소와 이 파일의 크기만 표시하면 된다.

 

 

연속적으로 할당된 파일의 접근은 쉽다. 가장 최근 참조된 주소를 기억하고 있다가 필요할 때 다음 블록을 읽어 들이면 된다. 그러나 연속 할당 기법에서 가장 큰 문제는 새로운 파일을 위한 가용 공간을 찾는 일이다. 자유 공간(free space)을 관리하기 위해 선택된 시스템이 이 작업을 담당한다.

 

연속 할당 문제는 일반적인 동적 공간 할당 문제(dynamic storage allocation problem)의 특정 응용으로 볼 수 있다. 이 문제는 자유 공간 (free hole)의 리스트에서 크기 n의 공간을 할당하는 방법에 관한 것이다. 최초 적합(first fit)과 최적 적합(best fit)이 가용 공간 중에서 할당할 공간을 선택하는 가장 일반적인 전략이다. 연속 할당 방법은 모두 외부 단편화(external fragmentation)문제가 발생 한다.

 

연속 할당의 또 다른 문제점은 파일을 위해서 얼마나 많은 공간을 주어야 할지를 결정하는 것이다. 파일이 생성될 때 필요한 공간의 크기를 알아야만 할당 가능하다. 기존의 파일을 복사하는 경우를 제외하곤 파일의 크기를 예측하는 것은 어렵다.

공간을 너무 작게 예약하여 사용하는 경우 파일이 커졌을 때 앞뒤로 다른 데이터로 인해 확장 할 수가 없다. 한 파일에 대한 공간을 미리 알 수 있다고 해도 선할당은 비효율 적이다. 내부 단편화가로 낭비 될 수 있기 때문이다.

 

이러한 단점을 보완하기 위해 많은 운영체제는 어느 정도의 연속된 공간만 초기에 할당하고 그 양이 충분히 크지 않을 때는 추후 n개의 연속된 공간을 단위(extent)로 할당한다. 파일 블록들의 위치는 위치와 블록 수, 다음 단위의 첫 블록에 대한 포인터로 기록된다.

 

 

[연결 할당 (Linked Allocation)]

연결 할당은 연속 할당의 모든 문제를 해결 한다. 연결 할당에서 각 파일은 디스크 블록의 연결 리스트이다. 파일의 디스크 블록들이 디스크 내에 흩어져 있다. 그리고 디렉토리는 파일의 첫 번째와 마지막 블록에 대한 포인터를 가지고 있다.

 

새 파일을 생성하려면 단순히 디렉토리 내의 새로운 항목(entry)을 만든다. 연결 할당의 경우 각 디렉토리 항목은 파일의 첫 디스크 블록에 대한 포인터를 갖고 있다. 이 포인터는 처음에는 빈 파일을 표시하기 위해 nil(연결의 끝에 해당하는 포인터 값) 값으로 초기화된다. 파일 쓰기가 일어나면 자유 공간 관리 시스템은 자유 블록을 할당받아 쓰기를 실행 한 후 파일의 끝에 연결 한다.

 

 

연결 할당의 경우 외부 단편화가 없고 모든 블록들은 크기가 같기 때문에 자유 공간 리스트의 어떠한 자유 블록들을 이용하여도 무방하다. 파일의 크기가 미리 고정될 필요도 없다. 파일은 계속해서 커질 수 있으며 주기적으로 밀집화 할 필요도 없다.

 

하지만 단점도 존재한다. 가장 중요한 단점은 순차적 접근 파일에만 효과적이다. 포인터를 접근할 때마다 디스크 읽기와 몇 번의 탐색이 필요하므로 직접 접근에는 비효율 적이다. 그리고 포인터를 관리하기 위한 추가 공간이 필요하다. 이 문제를 일반적인 해결방법은 블록들을 클러스터(cluster)로 구성하여 클러스터 단위로 할당하는 것이다.

 

또 다른 문제는 신뢰성의 문제인데 포인터를 이용하여 관리하다 보니 포인터를 잃어버리거나 잘못된 포인터 주소를 가지게 되면 결국 모든 자료를 잃게 된다. 이 경우 이중 연결 리스트를 사용하거나 각 블록마다 파일 이름과 상대 블록 번호 등을 저장하는 방법을 같이 쓸 수도 있겠으나 이 기법들은 더 많은 오버헤드를 유발한다.

 

연결 할당의 변형으로 파일 할당 테이블(file Allocation Table, FAT)을 사용하는 것이다. FAT 테이블은 각 디스크 블록마다 한 개의 항목을 가지고 있고 이 항목은 디스크 블록 번호를 색인으로 찾는다.

 

FAT 할당 기법은 FAT가 캐시되지 않으면 상당한 수의 디스크 찾기를 유발 할 수 있다. FAT를 읽기 위해 디스크 헤드를 반드시 파티션의 시작 부분으로 움직여 찾고자 하는 블록의 주소를 알아내야 하고 이어 그 블록이 있는 곳으로 다시 이동해야 한다. 최악의 경우 각 블록을 찾을 때마다 두 번의 이동이 일어나야 한다. 장점은 디스크헤드가 FAT의 정보를 읽어 임의의 블록의 위치를 알아 낼 수 있기 때문에 임의(random) 접근 시간이 개선된다.

 

 

[색인 할당 (Indexed Allocation)]

연결 할당은 연속 할당의 외부 단편화 문제와 파일 크기 문제를 해결하였지만 FAT가 없으면 직접 접근 방식을 지원 할 수가 없다. 색인 할당은 모든 포인터들을 하나의 장소 즉, 색인 블록으로 관리함으로써 이 문제를 해결 한다.

 

각 파일들은 디스크 블록 주소를 모아 놓은 배열인 색인(index) 블록을 가진다. 색인 블록의 i번째 항목은 파일의 i번째 블록을 가리킨다. 디렉토리는 색인 블록의 주소를 가지고 있다. i번째 블록을 읽기 위해서는 색인 블록 항목에 있는 i번째 항목에서 포인터를 얻어서 그 블록을 읽는다. 이 기법은 페이징과 유사하다.

 

 

색인 할당은 추가 공간 요구가 있을 경우 디스크 상의 임의의 자유 공간을 사용할 수 있기 때문에 외부 단편화 없이 직접 접근을 제공 한다. 그러나 색인 할당은 공간의 낭비가 문제이다. 색인 블록의 포인터 오버헤드는 일반적으로 연결 할당의 포인터 오버헤드 보다 크다. 대부분의 파일들은 작으므로 파일들이 대부분 하나 또는 두 개의 블록만으로 구성되어 있는 것이 일반적이다. 이 경우 단지 한 두개의 포인터만 사용되지만 색인을 위해 한 블록이 할당되어야 한다.

 

여기에서는 색인 블록이 얼마나 커야 하는지가 문제 된다. 각 파일들은 하나의 색인 블록을 가지므로 색인 블록의 크기는 가능한 작은 것이 좋다. 만약 색인 블록이 너무 작다면 큰 파일들에 대해서 충분한 공간을 가질 수가 없을 것이다.

 

이러한 문제점을 보완하는 기법은 다음과 같다.

• 연결 기법(Linked scheme) : 하나의 색인 블록은 통상 한 디스크 블록이다. 파일의 크기가 크면 여러 개의 색인 블록들을 연결 시킨다.
• 다단계 색인(Multilevel index) : 첫 번째 수준의 색인 블록은 여러 개의 두 번째 수준 색인 블록들에 대한 포인터들을 가진다. 두 번째 수준의 색인 블록은 실제 자료 블록들을 가리킨다. 이러한 방법은 파일의 크기에 따라 세 번째 또는 네 번째 수준으로까지 계속 된다. 한 블록의 크기가 4096 바이트라면 1024개의 4바이트 포인터를 한 색인 블록에서 저장할 수 있다, 2단계 색인 기법을 쓰면 1048576개의 자료 블록을 가질 수 있으며 이는 파일 크기 4GB까지 저장 가능하다.
• 결합 기법(Combined scheme) : 디렉토리 내의 색인 블록이 15개의 포인터를 갖는다. 이 포인터들의 처음 12개는 직접 블록(direct block)을 가리킨다. 그 다음 3개의 포인터는 간접 블록(indirect block)의 주소로서 첫 번째 포인터는 단일 간접 블록(single-level indirect block)을 통하여 간접적으로 파일의 블록을 찾을 수 있으며 두 번째 포인터는 이중 간접 블록 (double-level indirect block), 마지막 포인터는 삼중 간접 블록(triple indirect block)을 통하여 간접적으로 파일의 블록을 찾는 형식이다. 이는 다단계 색인 기법을 확장한 것이다.

 

색인 할당 기법은 연결 할당과 동일한 성능 문제를 갖는다. 특히 색인 블록은 메모리에 캐시될 수 있지만 자료 블록은 전체 볼륨 파티션 전체에 널리 퍼져 있을 수 있다.

 

 

[참고자료]

Operating System Concepts / 홍릉과학출판사