File Allocation

보조 기억 장치에 저장되는 파일의 할당에 대해 알아본다.

컴퓨터 시스템 자원 중 가장 중요한 것은 CPU이다. CPU 자원 관리에 대해서는 맨 처음 부분에서 다루었으며 CPU 스케줄링, 프로세스 동기화 등에 대해서 배웠다. CPU 다음으로 중요한 자원은 메인 메모리와 같은 주기억장치이다. 메인 메모리 관리에 대한 주요 이슈는 페이징, 가상 메모리(요구 페이징) 등이 있었다.

CPU, 주기억장치 다음 중요한 컴퓨터 시스템 자원은 하드디스크와 같은 보조기억장치이다. 하드디스크가 데이터를 관리하는 방식은 파일 시스템이다. 파일은 컴퓨터에서 운영체제를 사용해본 사용자라면 매우 익숙한 단어일 것이다. 대표적인 windows 운영체제를 보면 폴더(디렉토리) 내부에 또 다른 폴더 또는 어떠한 파일이 존재한다. 이러한 폴더 및 파일은 트리 구조로 관리할 수 있다.

이번 장에서는 보조기억장치 중 컴퓨터에서 주로 사용하는 하드디스크의 파일이 할당되는 방법에 대해서 살펴볼 것이다.

파일 할당이란

위 그림은 pool of free blocks를 논리적인 그림으로 나타낸 모습이고 블록마다 인덱스 번호를 설정하였다. 블록들이 위와 같이 있을 때 파일을 할당하는 방법은 크게 연속 할당, 연결 할당, 색인 할당 세 가지가 존재한다.

2.1 연속 할당 (Contiguous Allocation)

연속 할당은 말그대로 연속된 블록에 파일을 할당 하는 것이다. 예를 들어, 블록 크기가 1KB이고, 할당할 파일은 f1, f2, f3 3개가 있고 각각의 크기는 5KB, 3KB, 4KB이다.

앞선 예제로 연속 할당을 수행하면 위의 그림과 같은 모습이 나온다.

2.1.1 연속할당의 장점

연속 할당에는 세 가지 특징이 있다.

• 연속 할당의 장점은 디스크 헤더의 이동을 최소화 할 수 있다.
  • I/O 성능을 높일 수 있다. 이 방식은 예전의 IBM에서 사용하던 방법이며 주로 동영상, 음악, VOD 등에 적합하다.
• 순차 접근(Sequential Access)이 가능하다.
  • 이는 말그대로 순서대로 파일을 읽을 수 있다는 의미이다.
• 직접 접근(Direct Access)이 가능하다.
  • 운영체제는 파일의 정보를 디렉토리(directory) 라는 테이블에 저장한다. 디렉토리에서 사용자가 접근가능한 정보는 파일의 이름, 크기, 날짜 등이 있고, 운영체제 내부에서 접근하는 정보는 해당 파일의 시작 블록 번호와 같은 것이 있다. 예를 들어, 위 예제의 f1 파일의 디렉토리 정보는 아래와 같다.

file name: f1
file size: 5 bytes
...
-----------------
block number: 0

연속 할당은 순차적으로 저장되어 있으므로 운영체제는 디렉토리에서 얻은 시작 블록 번호로 원하는 블록에 바로 접근할 수 있다. 예를 들어, 위 예제에서 f1 파일의 3번째 블록에 접근하고 싶다고 가정하자. 운영체제는 f1의 시작 블록 번호가 0번인 것을 알고 있기 때문에 2번 블록에 접근하면 f1의 3번째 블록이라는 것을 알 수 있다.

2.1.2 연속할당의 단점

연속 할당은 현재에는 거의 사용하지 않는 방식인데, 이 방법에는 큰 단점이 존재하기 때문이다.

• 외부 단편화 문제가 발생한다.
  • 파일을 할당하고 지우고를 반복하다보면 중간 중간에 빈 공간(hole)이 생기는데 연속 할당은 연속된 공간을 찾아야 하기 때문에 이전 메인 메모리 할당에서 살펴본 것과 같이 외부 단편화 문제가 발생한다.
  • 외부 단편화로 인해 디스크 공간의 낭비가 매우 심해진다. 이전 메모리 할당에서 외부 단편화로 인해 메모리의 약 1/3을 낭비한다고 하였는데, 디스크의 연속 할당도 같은 낭비가 발생한다.
• 파일을 저장할 때 실제 크기를 알 수 없다.
  • 특히, 계속해서 사용하는 파일의 경우 크기가 계속 증가 할 수 있기 때문에 이를 지속해서 연속적으로 할당하기에는 매우 부적절하다.

2.2 연결 할당 (Linked Allocation)

연결 할당은 연속 할당의 문제점을 해결하기 위해 나온 방법으로, 연속적으로 할당하는 것이 아니라 링크드 리스트(linked list) 와 같은 방식으로 파일을 할당한다

위 그림은 block 크기가 1 byte, 파일 f1의 크기가 5 bytes 일 때 연결 할당을 수행한 모습이다. 각 블록의 마지막에 **주소를 저장하는 포인터 공간(4bytes)**이 존재하며, 여기서 다음 블록을 가리키고 있다. 마지막 블록의 포인터 공간에는 끝임을 나타내는 값이 저장되어 있다.

이러한 파일을 linked list of data blocks 라고 하며, f1의 파일 디렉토리 정보는 아래와 같다.

file name: f1
file size: 5 bytes
...
-----------------
block number: 6

2.2.1 연결할당의 장점

• 위치와 상관없이 할당이 가능하므로 외부 단편화 문제가 없다. (= 디스크 낭비가 없다.)
  • 연결 할당을 사용해서 새로운 파일을 할당할 때는 비어있는 임의의 블록을 첫 블록으로 선택하며, 만약 파일이 커지는 경우 다른 블록을 할당해서 기존의 블록과 연결만 해주면 된다.

2.2.2 연결할당의 단점

하지만, 연결 할당 역시 여러 문제점을 가지고 있다.

• 순차 접근은 가능하지만 직접 접근은 불가능하다.
  • 파일의 블록들은 모두 흩어져 있으므로 시작 블록 번호를 가지고는 원하는 위치의 블록에 바로 접근할 수는 없다.
• 포인터를 저장하는 4 bytes 이상의 손해가 발생한다.
• 낮은 신뢰성
  • 중간 블록의 포인터가 끊어지면 그 이후의 모든 블록에 접근하지 못한다.
• 느린 속도
  • 블록이 모두 흩어져 있으므로 디스크 헤더의 움직임이 그 만큼 많이 발생한다.

2.2.3 FAT(File Allocation Table) 시스템

위 문제점을 개선하기 위해 나온 것이 같은 연결 할당 방식인 FAT(File Allocation Table) 시스템이다. FAT 시스템은 다음 블록으르 가리키는 포인터들만 모아서 하나의 테이블(FAT)을 만들어 한 블록에 저장한다.

위 그림은 앞선 예제의 f1 파일을 FAT 파일 시스템 방식으로 저장한 모습이다. 0번 블록에 저장된 FAT를 보면 테이블의 인덱스는 전체 디스크의 블록 번호이며, 각 인덱스마다 다음 블록 번호를 저장하고 있다.

FAT 시스템을 사용하면 기존의 연결 할당의 문제점 대부분을 해결할 수 있다. FAT를 한 번만 읽으면 직접 접근이 가능하고, FAT만 문제가 없다면 중간 블록에 문제가 생겨도 FAT를 통해 그 다음 블록은 여전히 읽을 수 있다. 그리고 FAT는 일반적으로 메모리 캐싱을 사용하여 블록 위치를 찾는데는 빠르지만 실제 디스크 헤더가 움직는 것은 블록이 흩어져 있으므로 여전히 느리다고 볼 수 있다. 마지막으로 FAT는 매우 중요한 정보이므로 손실 시 복구를 위해 이중 저장을 한다.

FAT의 각 인덱스 크기는 전체 블록의 개수를 저장할 만큼의 크기를 가지고 있어야 하는데, 현재는 일반적으로 32bit 크기를 사용($2^{32}$)한다. 이를 FAT32라고 부른다.(이전에는 FAT16, FAT12 등이 있었다.)

2.3 색인 할당 (Indexed Allocation)

색인 할당 역시 연결 할당과 같이 데이터를 랜덤한 블록 번호에 할당하지만 할당된 블록 번호(포인터)를 하나의 블록에 따로 저장한다. 이러한 블록을 인덱스 블록이라고 부르며, 파일 당 하나의 인덱스 블록이 존재한다. 색인 할당은 디렉토리 정보가 다른 할당과 다른데, 시작 블록 번호를 저장하는 것이 아니라 인덱스 블록 번호를 저장한다.

2.3.1 예제

|block size|f1|f2| |:--------:|::|::| |1byte|5byte|2byte|

file name: f1
file size: 5 bytes
...
-----------------
index block number: 11

file name: f2
file size: 2 bytes
...
-----------------
index block number: 27

그림을 보면, 블록 하나를 지정하여, 파일의 인덱스를 저장하는 인덱스 블록으로 사용한다.

색인 할당은 인덱스 블록에 할당된 블록을 순서대로 저장하기 때문에 직접 접근이 가능하다. 그리고 연속적으로 할당할 필요가 없으므로 외부 단편화 문제 또한 발생하지 않는다. 색인 할당은 Unix/Linux에서 주로 사용한다.

색인 할당의 단점은 작은 크기의 파일인 경우에도 하나의 블록을 인덱스 블록으로 사용하기 때문에 저장 공간이 손실된다. 그리고 하나의 인덱스 블록을 가지고는 크기가 큰 파일을 저장할 수 없다.

예를 들어, 하나의 블록 크기가 512 bytes인 블록은 최대 저장할 수 있는 블록의 인덱스 개수가 512 / 4 bytes(포인터 크기) = 128개이다. 즉 파일의 최대 크기는,

128(인덱스 블록에서 저장할 수 있는 블록의 포인터 개수의 최대값) x 512bytes(블록 하나의 크기) = 64KB

로 아주 작은 크기이다. 블록 크기가 1KB이라 하더라도 최대 인덱스 개수는 256개(1000/4)이고 최대 파일의 크기는 256KB이다.

2.3.2 해결 방법

이를 해결하기 위한 여러 가지 방법이 있다.

2.3.2.1 Linked

이 방식은 인덱스 블록을 여러 개 만들어 연결 할당을 하는 것과 같다. 즉, 각 인덱스 블록의 마지막은 다음 인덱스 블록을 가리키는 포인터가 저장되어 있다.

2.3.2.2 Multilevel index

이 방식은 계층을 두는 방법으로 하나의 인덱스 블록의 모든 포인터가 다른 인덱스 블록을 가리킨다. 만약 이것으로 부족하면 계층을 더 만들어 간다.

2.3.2.3 Combined

이 방식은 Linked와 Multilevel index를 합친 방법으로 한 인덱스 블록의 포인터들은 데이터 블록과 또 다른 인덱스 블록 둘 다 가리킬 수 있다.(리눅스는 combined 방식을 사용한다.)

Reference

KOCW 양희재 교수님 - 운영체제 양희재 교수님 블로그(시험 기출 문제)
codemcd 님의 정리글
세마포 사진
Operating System Concepts, 9th Edition - Abraham Silberschatz