7-3. 파일 할당 방법

1. 파일 할당 방법의 개요

파일 시스템은 디스크 공간을 효율적으로 관리하고, 사용자가 파일을 저장하고 검색할 수 있도록 하는 핵심적인 역할을 수행합니다. 파일 할당 방법은 이러한 파일들을 디스크 상의 블록에 어떻게 저장할 것인지 결정하는 전략을 의미합니다. 이러한 전략은 파일 접근 속도, 디스크 공간 사용 효율성, 그리고 파일 시스템의 복잡성에 큰 영향을 미칩니다. 다양한 할당 방법이 존재하며, 각 방법은 고유한 장단점을 가지고 있습니다.

파일 할당 방법을 이해하는 것은 파일 시스템의 성능을 최적화하고, 잠재적인 문제를 해결하는 데 필수적입니다. 예를 들어, 특정 할당 방법은 디스크 조각화를 유발하여 파일 접근 속도를 느리게 만들 수 있습니다. 다른 방법은 파일의 크기에 제한을 둘 수 있습니다. 이러한 특성을 이해하면, 특정 사용 사례에 가장 적합한 파일 시스템을 선택하거나, 파일 시스템 설정을 조정할 수 있습니다.

2. 연속 할당 (Contiguous Allocation)

연속 할당은 파일의 모든 데이터를 디스크 상의 연속된 블록에 저장하는 가장 간단한 할당 방법입니다. 파일이 생성될 때, 파일 시스템은 해당 파일에 필요한 만큼의 연속적인 블록을 디스크에서 찾고, 이 블록들에 파일을 저장합니다.

1) 장점

• 단순함: 구현이 가장 간단하며, 파일 시스템 설계가 용이합니다.
• 빠른 접근: 파일의 모든 데이터가 연속적으로 저장되어 있기 때문에, 파일의 어느 부분에나 빠르게 접근할 수 있습니다. 파일의 i번째 블록에 접근하려면, 시작 블록 주소에 i * 블록 크기를 더하면 됩니다. 따라서, 임의 접근(random access)이 매우 효율적입니다.
• 최소한의 헤드 움직임: 파일의 데이터를 순차적으로 읽을 때, 디스크 헤드의 움직임이 최소화되어 읽기 성능이 향상됩니다.

2) 단점

• 외부 단편화: 디스크 공간이 작은 조각으로 나뉘어 파일을 저장할 공간이 부족해지는 "외부 단편화" 문제가 발생합니다. 이는 디스크 공간을 비효율적으로 사용하게 만들고, 새로운 파일을 저장할 수 없는 상황을 초래할 수 있습니다.
• 크기 결정의 어려움: 파일을 생성할 때, 파일의 크기를 미리 알아야 합니다. 만약 파일의 크기가 예상보다 커지면, 파일을 저장할 연속된 공간을 찾을 수 없어서, 파일의 크기를 늘리거나, 새로운 공간에 전체 파일을 복사해야 하는 비효율적인 상황이 발생합니다.
• 파일 삭제 후 빈 공간 관리: 파일을 삭제하면, 해당 파일이 차지했던 공간이 비게 됩니다. 이 공간을 다시 사용하려면, 파일 시스템은 빈 공간을 추적하고 관리해야 합니다.

3. 연결 할당 (Linked Allocation)

연결 할당은 파일의 각 블록을 임의의 위치에 저장하고, 각 블록이 다음 블록의 주소를 포함하는 방식으로 파일을 관리합니다. 마치 연결 리스트와 유사하게, 각 블록은 다음 블록을 가리키는 포인터를 가지고 있습니다.

1) 장점

• 외부 단편화 문제 해결: 파일이 연속된 블록에 저장될 필요가 없으므로, 외부 단편화 문제가 발생하지 않습니다. 사용 가능한 모든 블록을 활용할 수 있습니다.
• 파일 크기 동적 증가: 파일의 크기를 동적으로 늘릴 수 있습니다. 파일에 데이터를 추가할 때마다, 새로운 블록을 할당하고, 이전 블록의 포인터를 갱신하면 됩니다.
• 디스크 공간 낭비 최소화: 파일의 크기를 미리 알 필요가 없으므로, 파일이 차지하는 디스크 공간을 효율적으로 사용할 수 있습니다.

2) 단점

• 임의 접근의 비효율성: 파일의 i번째 블록에 접근하려면, 첫 번째 블록부터 i-1개의 블록을 따라가야 하므로, 임의 접근이 느립니다.
• 포인터 오버헤드: 각 블록은 다음 블록의 주소를 저장해야 하므로, 추가적인 공간(포인터)을 사용합니다.
• 신뢰성 문제: 블록 중 하나라도 손상되면, 해당 블록 이후의 파일 데이터에 접근할 수 없게 됩니다.
• 저장 공간 낭비: 각 블록이 다음 블록의 주소를 저장해야 하기 때문에, 블록 크기가 작을수록 포인터가 차지하는 공간의 비율이 높아져 공간 낭비가 발생할 수 있습니다.

4. 색인 할당 (Indexed Allocation)

색인 할당은 파일의 각 블록에 대한 정보를 별도의 색인 블록에 저장하는 방법입니다. 색인 블록은 파일의 각 데이터 블록의 주소를 포함하는 포인터의 배열입니다.

1) 장점

• 임의 접근의 효율성: 색인 블록에 모든 블록의 주소가 저장되어 있으므로, 파일의 어느 블록에나 빠르게 접근할 수 있습니다.
• 외부 단편화 문제 해결: 파일이 연속된 블록에 저장될 필요가 없으므로, 외부 단편화 문제가 발생하지 않습니다.
• 파일 크기 유연성: 연결 할당과 유사하게, 파일의 크기를 동적으로 늘릴 수 있습니다. 색인 블록의 포인터 배열에 새로운 블록의 주소를 추가하기만 하면 됩니다.

2) 단점

• 색인 블록 오버헤드: 각 파일마다 색인 블록을 유지해야 하므로, 색인 블록을 저장하기 위한 공간이 필요합니다.
• 색인 블록 크기 제한: 색인 블록의 크기에 따라 파일의 최대 크기가 제한될 수 있습니다. 만약 파일의 크기가 색인 블록이 저장할 수 있는 블록 수를 초과하면, 여러 개의 색인 블록(예: 다중 레벨 색인)을 사용해야 합니다. 이는 구현을 복잡하게 만들 수 있습니다.
• 성능 저하 가능성: 색인 블록을 읽는 데 추가적인 입출력 작업이 필요할 수 있습니다. (그러나 대부분의 경우, 색인 블록은 메모리에 캐시됩니다.)

3) 색인 할당의 확장: 다중 레벨 색인 (Multi-level Indexing)

색인 할당의 주요 단점 중 하나는 단일 색인 블록의 크기에 따라 파일의 최대 크기가 제한된다는 것입니다. 다중 레벨 색인은 이러한 제한을 극복하기 위해 설계되었습니다. 다중 레벨 색인은 색인 블록 자체가 다른 색인 블록을 가리키는 포인터를 포함합니다.

예를 들어, 단일 레벨 색인에서 색인 블록은 데이터 블록의 주소를 직접 가리킵니다. 이중 레벨 색인에서는 최상위 색인 블록이 중간 레벨 색인 블록을 가리키고, 중간 레벨 색인 블록이 데이터 블록을 가리킵니다. 삼중 레벨 색인은 최상위, 중간, 하위 레벨 색인 블록을 사용합니다. 이러한 계층 구조를 통해 파일 시스템은 더 큰 파일을 지원할 수 있습니다.

다중 레벨 색인은 임의 접근 성능을 유지하면서 파일 크기 제한을 완화하지만, 색인 블록의 계층 구조가 깊어질수록 파일 접근에 필요한 입출력 횟수가 증가하여 성능이 저하될 수 있습니다.

5. 할당 방법 비교

6. 결론

파일 할당 방법은 파일 시스템의 성능, 효율성, 그리고 유연성에 큰 영향을 미칩니다. 연속 할당은 단순하고 빠른 접근 속도를 제공하지만, 외부 단편화 문제를 겪습니다. 연결 할당은 외부 단편화를 해결하지만, 임의 접근 속도가 느립니다. 색인 할당은 임의 접근과 외부 단편화 방지 사이의 균형을 제공하며, 다중 레벨 색인과 같은 확장성을 통해 파일 크기 제한을 극복할 수 있습니다.

어떤 할당 방법을 선택할지는 응용 프로그램의 요구 사항과 사용 환경에 따라 달라집니다. 예를 들어, 대용량 파일에 대한 임의 접근이 빈번하게 필요한 경우에는 색인 할당 또는 다중 레벨 색인이 적합할 수 있습니다. 반면, 간단한 시스템에서는 연속 할당이 구현하기 더 쉽고, 성능 측면에서도 유리할 수 있습니다. 파일 시스템 설계자는 이러한 다양한 요소를 고려하여 최적의 파일 할당 방법을 선택해야 합니다.