[Chapter 6] 개념 이해를 위한 운영체제 [파일 시스템 - 빈 공간 관리]

파일의 내용을 저장하기 위해서는 보조 기억장치의 빈 공간을 파악하고 빈공간을 할당하는 기법이 필요하다. 

 

빈 공간 관리

파일 시스템은 새로운 파일을 생성하기 위하여 보조 기억장치의 빈 공간의 크기와 위치를 관리해야 한다. 이러한 빈 공간을 관리하는 기법은 보조 기억장치의 용량에 따라 다르다.

1. 비트 맵
   • 보조 기억장치의 빈 공간을 관리하기 위하여 모든 블록에 해당하는 비트맵 혹은 비트 백터를 유지하고 각 블록의 사용 여부를 비트 단위로 표시하는 가장 간단한 기법이다. 만약 보조 기억장치의 해당 블록이 사용중이면 '1' 아니면 '0'으로 표시한다.
   • ex) 20개의 블록으로 구성된 디스크에서 블록 번호 0, 1, 2, 10, 11, 15, 16, 17이 사용중이고 나머지 블록은 비어있을 경우 비트맵의 내용은 111000000011000111000이 될 것이다.
   • 파일 시스템은 보조 기억장치의 빈 공간을 신속하게 파악하기 위하여 비트 맵ㅇ틔 내용을 메모리에 적재하여 사용한다. 따라서 이 기법은 구현이 용이하고 순차 파일과 같이 여러 개의 연속적인 빈 공간을 요구할 경우 매우 효과정이다. 
   • 용량이 큰 보조 기억장치의 빈 공간 관리에는 부적합하기 때문에 주로 마이크로 컴퓨터와 같이 용량이 작은 보조 기억장치의 빈 공간 관리에 사용되고 있다.
2. 연결 리스트
   • 보조 기억장치의 모든 빈 공간을 연결하는 연결 리스트(linked list) 구조로 관리하는 기법이다. 모든 빈 공간은 다음 빈 공간을 연결하기 위한 포인터를 가지고 있다.
   • 파일 시스템은 보조 기억장치의 빈 공간을 신속하게 파악하기 위하여 첫 번째 빈 공간과 마지막 빈 공간을 가리키는 포인터를 메모리에 유지한다. 따라서 이 기법은 빈 공간을 가리키는 포인터를 메모리에 유지한다.
   • 보조 기억장치의 용량에 관계없이 적용할 수 있다. 그러나 다음 빈 공간을 탐색하거나 새로운 빈 공간이 추가될 경우 보조 기억장치를 접근해야하기 때문에 오버헤드가 발생하는데 이러한 오버헤드를 개선하기 위한 방법으로 계수(counting)와 그룹핑(grouping)기법이 있다.
   • 계수 기법은 보조 기억장치의 빈 공간이 연속적으로 존재할 경우 첫 번째 빈 공간의 주소와 연속된 빈 공간들의 계수를 지정함으로써 다음 빈 공간의 탐색 시간을 최소화하는 것이다. 그러나 불연속적으로 존재하는 빈 공간들을 포인터로 연결한다. 반면 그룹핑 기법은 첫 번째 빈 공간에 빈 공간들의 주소를 지정함으로써 다수의 빈 공간을 한 번에 탐색할 수 있도록 한다. 
   • 빈 공간의 수가 너무 많아 첫 번째 빈 공간이 부족할 경우 또 다른 빈 공간을 포인터로 연결하여 나머지 빈 공간들의 주소가 지정하는 연결 리스트 구조이다.

연결 리스트를 이용한 빈 공간 관리

빈 공간 할당

파일 시스템은 새로운 파일을 생성하기 위하여 보조 기억장치의 빈 공간의 크기와 위치를 확인한 후 빈 공간을 할당해여 한다. 임의의 파일 내용을 저장하기 위한 보조 기억장치의 빈 공간 할당 기법은 가변 분할 다중 프로그래밍에서 메모리 할당 기법과 유사하다. 보조 기억장치의 빈 공간 할당 기법은 보조 기억장치의 특성과 파일의 접근 방식에 따라 다르지만 일반적으로 연속 할당(contiguous allocation)과 불연속 할당(noncontiguous allocation)이 있다.

 

• 연속 할당
  • 연속 할당은 파일을 구성하는 레코드들을 보조 기억장치의 인접된 공간에 연속적으로 할당하는 기법이다.

연속 할당(contiguous allocation)

보조 기억장치의 빈 공간을 연속적으로 할당할 경우 파일 시스템은 각 파일에 대한 보조 기억장치의 시작 주소와 길이에 대한 정보를 디렉토리에 유지함으로써 파일의 내용을 쉽게 접근할 수 있도록 한다.

파일을 구성하는 레코드들을 보조 기억장치에 불연속적으로 할당하는 기법보다 훨씬 빠르게 접근할 수 있다.

보조 기억장치의 빈 공간을 연속적으로 할당할 경우 시간이 지남에 따라 파일 생성과 삭제 작업이 반복되면서 보조 기억장치의 외부 단편화 현상이 발생하게 된다. 이를 해결하기 위해서는 주기적으로 보조 기억장치의 빈 공간들을 합병 혹은 집약시켜야 하는 오버헤드가 있다.

• 불연속 할당
  • 불연속 할당은 연속 할당에 의한 단편화 현상을 근본적으로 해결하기 위하여 파일을 구성하는 레코드들을 보조 기억장치의 임의의 빈 공간에 불연속적으로 할당하는 기법으로써 연결 리스트(linked list)와 색인 블록(index block)을 이용한 방법이 있다.

• 연결 리스트 방법
  • 연결 리스트를 이용한 불연속 할당 기법은 파일을 구성하는 레코드들을 보조 기억장치의 임의의 빈 공간에 불연속적으로 할당하고 각각의 레코드는 다음 레코드를 연결하기 위한 포인터를 유지한다. 
  • 하나의 파일을 구성하는 레코드들이 보조 기억장치에 저장된 형태는 포인터에 의한 연결 리스트(linked list) 구조이다.
  • 보조 기억장치의 빈 공간을 연결 리스트를 이용하여 불연속적으로 할당할 경우 파일 시스템은 파일의 내용을 접근하기 위하여 각 파일에 대한 보조 기억장치의 시작과 끝 주소에 대한 정보만을 디렉토리에 유지하면 된다.

연결 리스트를 이용한 불연속 할당

• 디렉토리 구조가 간단하며 파일 수정에 의한 레코드의 추가는 물론 삽입 및 삭제 작업이 용이하다. 
• 모든 레코드들이 포인터에 의해 보조 기억장치에 불연속적으로 연결되어 있기 때문에 임의의 레코드를 접근하기 위해서는 첫 번째 레코드가 저장된 시작 주소에서부터 찾아가야 한다. 따라서 파일 접근을 위한 탐색 시간이 많이 걸리게 된다. 
• 모든 레코드들은 다음 레코드가 저장된 주소를 지정하기 위한 포인터를 유지해야 하기 때문에 실제 사용자가 필요로 하는 데이터를 저장할 수 있는 공간이 그만큼 줄어드는 단점이 있다.

• 색인 블록 방법
  • 색인 블록을 이용한 불연속 할당 기법은 파일을 구성하는 레코드들을 보조 기억장치의 임의의 빈 공간에 불연속적으로 할당하고 각각의 파일은 색인 블록(index block)을 유지한다. 색인 블록은 그 파일을 구성하는 모든 레코드들이 저장된 보조 기억 장치의 주소를 가리키는 포인터를 가지고 있다.
  • 하나의 색ㅇ틴 블록이 부족할 경우에는 임의의 빈 공간을 할당하여 또 다른 색인 블록으로 지정하고 색인 블록까리는 포인터로 연결한다. 따라서 파일을 구성하는 레코드들은 색인(indexed) 구조이고 색인 블록들은 연결 리스트(linked list) 구조이다.

색인 블록을 이용한 불연속 할당

보조 기억장치의 빈 공간을 색인 블록을 이용한 불연속적으로 할당할 경우 파일 시스템은 파일의 내용을 접근하기 위하여 각 파일에 대한 색인 블록의 시작 주소에 대한 정보만을 디렉토리에 유지하면 된다. 

디렉토리 구조가 간단하며 임의의 레코드를 접근하기 위하여 보조 기억장치의 주소를 빠르게 탐색할 수 있다.

모든 파일마다 색인 블록을 유지해야 하기 때문에 실제 사용자가 필요로 하는 데이터를 저장할 수 있는 공간이 그만큼 줄어들고 파일 수정에 의한 레코드 삽입 및 삭제 시 색인 블록을 수정해야 하는 번거로움이 있다. 색인 블록들끼리는 포인터로 연결되어 있기 때문에 연결 리스트 구조에 의한 단점이 존재한다.

---

Reference

개념 이해를 위한 운영체제