50_디스크 자유 공간 관리(Free-Space Management)

50_디스크 자유 공간 관리(Free-Space Management)

 

디스크의 공간은 제한되어 있기 때문에 삭제된 파일들일 차지하던 공간을 새로운 파일들을 위하여 다시 재사용하여야 한다. 시스템은 이러한 자유 공간을 리스트로 유지하고 관리한다.

 

디스크는 자유 공간 리스트에 디스크의 모든 자유 블록들을 등록 한다. 새로운 파일을 만들려면 자유 공간 리스트를 탐색하여 새로운 파일을 위한 공간을 할당 받아야 한다. 할당 된 공간은 자유 리스트로부터 삭제 된다.

 

자유 공간 관리를 위해서 꼭 리스트 형태로만 구현될 필요는 없다. 관리를 위해 사용되는 다양한 방법을 알아 보자.

 

[비트 벡터(Bit Vector)]

자유 공간 리스트는 흔히 비트 맵(bit map) 또는 비트 벡터(bit vector)로써 구현 된다. 여기서 각 블록은 1비트로 표현된다. 만약에 블록이 자유로우면 그 비트는 1이 되고 만약 블록이 할당되어 있다면 그 비트는 0이 된다.

 

예를 들어 디스크의 블록들 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, 27이 비어 있고 나머지 블록은 할당되어 있다고 가정 할 때 그 자유 공간 비트맵은 다음과 같다.

 

001111001111110001100000011100000…

 

이 방법의 큰 이점은 첫 번째 자유 블록 또는 n개의 연속된 자유 블록들을 찾는 일이 간편하고 효율적이다. Apple Macintosh 운영체제는 디스크 공간 할당을 위해 비트 벡터 기법을 사용한다. Macintosh 운영체제는 비트 맵의 각 워드를 순차적으로 검사하여 0이 아닌 워드를 찾고 그 워드에서 첫 번째 1비트를 찾는다. 블록번호는 다음과 같이 계산 한다.

 

(워드의 비트 수) * (값이 0인 워드 수) + 첫 번째 1비트의 오프셋

 

비트 벡터는 그 전체가 주 메모리 내에 존재하지 않으면 비효율적이 된다.

 

[연결 리스트 (Linked List)]

모든 자유 디스크 블록들을 함께 연결시키는 것인데 첫 번째 자유 블록은 다음 자유 블록을 가리키는 포인터를 가진다. 두 번째 자유 블록은 다음 자유 블록의 포인터를 가지고 계속 그런 방법으로 구현 된다.

 

 

시스템은 첫 번째 자유 블록에 대한 포인터를 디스크의 특정 위치에 두고 메모리에 캐싱하여 사용 한다.

 

자유 리스트를 순회 하려면 매번 디스크를 접근해야 하므로 효율적이지 못하나 자유 리스트는 순회는 자주 발생하지 않는다. 통상 운영체제는 단순히 파일에 할당할 하나의 자유 블록이 필요하며 자유 리스트의 첫 블록을 사용할 수 있다.

 

 

 

[그룹핑(Grouping)]

자유 리스트 방식의 변형으로 첫 번째 자유 블록 내에 n 개의 블록 주소를 저장하는 방법이다. 이 중 처음 n -1 개는 실제로 비어 있는 블록의 주소이다. 그러나 마지막 1개는 자신과 마찬가지로 n-1 개의 빈 블록 주소를 가지고 있는 자유 블록을 가리킨다.

 

이 방법은 연결 리스트 방법과는 달리 다수 개의 자유 블록 주소들을 쉽게 찾을 수 있다는 점이 장점이다.

 

[계수 (Counting)]

프로그램들이 매우 자주(여러 연속된) 블록들을 할당하고(여러 연속된) 블록들을 반환 한다는 사실에 착안한 것으로 특히 연속 할당 알고리즘이나 클러스터링을 통해 공간을 할당 할 경우 유용하다.

 

모든 블록을 일일이 추적할 필요가 없이 연속된 자유 블록의 첫 번째 블록의 주소와 연속된 블록의 계수(count)만 유지하면 보다 효율적이다. 따라서 자유 공간 리스트의 각 항은 하나의 디스크 주소와 블록의 개수로 구성 된다.

 

[참고자료]

Operating System Concepts / 홍릉과학출판사