[운영체제(OS)] 14-2) 파일을 저장장치 공간에 할당

---

<파일을 저장장치 공간에 할당하는 방법>

1. 연속 할당(Contiguous Allocation)

: 각 파일이 저장장치 내에서 연속적인 공간을 차지하도록 요구합니다. 한 파일의 연속 할당은 첫 번째 블록 주소와 블록 단위의 길이로 정의됩니다.

 

<장점>

• 순차 접근과 직접 접근 두가지 모두 지원할 수 있습니다.
  • 순차 접근 : 파일 시스템은 가장 최근에 참조된 주소를 기억하고 있다가 필요할 때 다음 블록을 읽어들임
  • 직접 접근 : 블록 b에서 시작하는 파일의 i번째 블록에 접근하기 위해 블록 b+i에 접근

<단점>

• 파일의 가용 공간을 찾기 어렵습니다.
• 파일을 위해 어느 정도의 공간을 줄지 결정하는게 어렵습니다.
• 너무 작은 공간을 할당해줬을 경우, 다음과 같은 방법을 사용합니다.
  • 확장이 안 될 경우 사용자에게 오류 메시지를 출력하고 프로그램을 종료시킴
  • 보다 큰 공간을 찾아 파일을 복사한 다음 이전 공간을 비움 : 사용자에게 알리지는 않지만 시스템이 점점 느려집니다.

이런 단점을 최소화하기 위해 운영체제는 어느 정도의 연속된 공간만 초기에 할당하고, 양이 충분하지 않을 때는 추후 n개의 연속된 공간을 단위(extent)로 할당합니다.

 

2. 연결 할당(Linked Allocation)

: 연속 할당의 모든 문제를 해결합니다. 파일은 저장장치 블록의 연결 리스트 형태로 저장되고, 이 블록들은 장치 내에 흩어져 저장됩니다. 디렉토리는 파일의 첫 번째와 마지막 블록 포인터를 가지고 있고, 각 블록은 다음 블록을 가리키는 포인터를 포함합니다.

 

<장점>

• 외부 파편화가 없고, 모든 블록의 크기가 같기 때문에 가용 공간 리스트의 어떤 가용 블록을 이용해도 무방합니다.
• 파일 생성 시 생성할 파일의 크기가 미리 고정되지 않아도 됩니다.
• 파일은 계속해서 커질 수 있으며, 디스크 공간을 주기적으로 밀집화할 필요가 없습니다.

<단점>

• 순차적 접근 방식에만 효과적이고, 직접 접근 방식에는 비효율적입니다.
• 포인터들을 위한 메모리 공간이 필요합니다.
• 각 블록이 전체 장치에 흩어져서 연결되기 때문에, 사고로 하나의 포인터를 잃어버리면 모든 데이터를 잃게 되므로 신뢰성 문제가 있습니다.

 

* 파일 할당 테이블(FAT. file allocation table) : 연결 할당의 변형된 방식입니다. 파일 할당 테이블은 각 블록마다 한 개의 항목을 가지고 있고, 이 항목은 디스크 블록 번호를 인덱스로 가지고 있습니다. 디렉토리 항목은 각 파일의 첫 번째 블록 번홀르 가리키고, 그 블록 번호를 가지고 FAT 테이블에 가면 그 항목은 다음 블록 번호를 가리킵니다. 마지막 블록의 테이블 항은 파일의 끝을 나타내는 특수한 값을 가집니다.

 

3. 색인 할당(Indexed Allocation)

: 색인 할당은 모든 포인터들을 하나의 색인 블록으로 관리합니다. 각 파일은 저장장치 블록 주소를 모아둔 배열인 색인(index) 블록을 가지며, 색인 블록의 i번째 항목은 파일의 i번째 블록을 가리킵니다. 파일이 생성될 때 인덱스 블록의 모든 포인터는 null로 설정됩니다. 

 

<장점>

• 외부 파편화없이 직접 접근을 지원합니다.

<단점>

• 공간 낭비를 하는 문제가 있습니다. 색인 블록의 포인터 오버헤드는 일반 연결 할당의 포인터 오버헤드보다 큽니다. 또, 색인 할당을 사용하면 하나 또는 두 개의 포인터만 null이 아니어도 전체 색인 블록을 할당해야 합니다.

모든 파일에는 색인 블록이 있어야 해서 최대한 색인 블록을 작게 만들고 싶은데, 색인 블록이 너무 작으면 큰 파일에 대해 충분한 포인터를 보유할 수 없습니다. 이 문제를 처리하는 기법에 다음과 같은 3가지 기법이 있습니다.

1) 연결 기법(linked scheme) : 파일의 크기가 크면 여러 개의 색인 블록을 연결합니다.

2) 다중 수준 색인(multilevel index) : 연결 기법의 변형으로, 여러 개의 두 번째 수준 색인 블록들의 집합을 가리키기 위해 첫 번째 수준의 색인 블록을 사용하고, 파일의 크기에 따라 세번째, 네번째 수준으로 계속됩니다.

3) 결합 기법(combined scheme) : inode에 색인 블록을 15개 포인터를 유지합니다. 이 포인터들의 처음 12개는 직접 블록을 가리키는데, 파일의 데이터를 저장하고 있는 블록들의 주소를 저장합니다. 그 다음 3개의 포인터는 간접 블록을 가리키며, 각각 단일 간접 블록(single indirect block. 데이터가 아니라 데이터를 저장하고 있는 블록의 주소를 저장), 이중 간접 블록(double indirect block. 실제 데이터 블록을 가리키는 포인터를 저장하는 블록의 주소를 저장), 삼중 간접 블록(triple indirect block)의 주소를 저장합니다.

---

<가용 공간의 관리>

새로운 파일을 만들기 위해서는 가용 공간 리스트를 탐색하여 새로운 파일을 위한 공간을 할당받아야 합니다. 가용 공간 리스트는 명칭과는 달리 반드시 리스트 형태로 구현될 필요는 없습니다.

 

1. 비트 벡트

: 가용 공간 리스트는 흔히 비트맵 또는 비트 벡터로 구현되며, 각 블록은 1비트로 표현됩니다. 블록이 비어있으면 1비트, 할당되어 있으면 0비트 입니다.

 

2. 연결 리스트(Linked List)

: 모든 가용 블록들을 함께 연결하는 것으로, 첫 번째 가용 블록은 다음 가용 블록을 가리키는 포인터를 가지는 식으로 이어지며, 첫 번째 가용 블록에 대한 포인터는 별도의 장소에 보관합니다.

 

3. 그룹핑(Grouping)

: 가용 리스트 방식의 변형으로, 첫 번째 가용 블록 내에 n개의 블록 주소를 저장하는 방법입니다. 이 중 처음 n-1개는 실제로 비어있는 블록의 주소이고, 마지막 1개는 자신과 마찬가지로 n-1개의 빈 블록 주소를 가지고 있는 가용 블록을 가리킵니다. 연결 리스트와 달리 다수의 가용 블록 주소들을 쉽게 찾을 수 있다는 장점이 있습니다.

 

4. 계수(Counting)

: 모든 블록을 일일이 추적할 필요 없이 연속된 가용 블록의 첫 번째 블록의 주소와 연속된 블록의 개수만 유지하는 방식입니다. 가용 공간 리스트의 각 항은 하나의 장치 주소와 블록의 개수로 구성됩니다.

 

5. 공간맵(Space Maps)

: 가용 공간 리스트가 비트맵으로 구현되어있으면 비트맵은 할당과 반환 시에 매번 수정이 되어야해서 비효율적일 수 있습니다. 이러한 입출력을 최소화하기 위해 ZFS 파일 시스템(예시)은 장치의 공간을 관리 가능한 크기로 나누기 위해 메타슬랩을 생성합니다. 각 메타슬랩은 연관된 공간맵을 가지고 있는데, 공간맵은 할당과 반환의 모든 블록 활동을 계수 형식으로 기록해두었다가 메타슬랩으로부터 공간을 할당하거나 반환하려고 할 때 이를 반영합니다.

 

6. 사용하지 않는 블록을 트림(TRIMing Unused Blocks)

: 파일 시스템이 페이지가 비어있고 페이지를 포함하는 블록이 완전히 비어있는 경우 TRIM(또는 unallocate)이 필요합니다. 이 기법을 사용하면 장치가 가득 차기 전에 가비지 수집 및 삭제 단계를 수행해서 장치가 보다 일관된 성능을 제공할 수 있습니다.