[OS] 파일 할당

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

 

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

 

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

 

위 그림은 하드디스크 구조이다.

• Platter : 실제 데이터를 기록하는 자성을 가진 원판이다. platter는 그림과 같이 여러개가 존재하고 앞뒤로 사용할 수 있다. 한 platter는 여러개의 track으로 이뤄져있다.
• Track : platter의 동심원을 이루는 하나의 영역이다.
• Sector : 하나의 track을 여러개로 나눈 영역을 sector라고 한다. sector size는 일반적으로 512bytes이며 주로 여러개를 묶어 사용한다.
• Cylinder : 한 cylinder는 모든 platter에서 같은 track 위치의 집합을 말한다.

앞서 sector는 여러개로 묶어 사용한다 했는데 이를 블록(block)이라 한다. 하드디스크는 블록 단위로 읽고 쓰기 때문에 block device라고 불리기도 한다.

하드디스크가 블록 단위로 읽고 쓰는 것을 확인할 수 있는 간단한 방법은 메모장 프로그램에서 알파벳 a만을 적고 저장해보자. a는 character로 1byte 크기를 갖는데, 실제 저장된 텍스트 파일의 속성을 확인하면 디스크에 4KB(하나의 block size)가 할당되는 것을 확인할 수 있다. (실제 디스크 할당 크기는 운영체제마다 다르다.) 따라서 디스크는 비어있는 블록들의 집합이라 볼 수 있다.

 

파일 할당

1. 연속 할당(Contiguous Allocation)

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

앞선 예제로 연속 수행을 하면 위 그림과 같이 할당된다. 연속 할당의 장접은 디스크 헤더의 이동을 최소화할 수 있어 I/O 성능을 높일 수 있다. 이 방식은 예전의 IBM에서 사용하던 방법이며 주로 동영상, 음악, VOD 등에 적합하다.

또한, 연속 할당에는 두 가지 특징이 있다.

• 순차 접근(Sequential Access)이 가능하다.
  • 이는 말그대로 순서대로 파일을 읽을 수 있다는 의미이다.
• 직접 접근(Direct Access)이 가능하다.
  • 운영체제는 파일의 정보를 디렉토리라는 테이블에 저장한다. 디렉토리에서 사용자가 접근가능한 정보는 파일의 이름, 크기, 날짜 등이 있고 운영체제 내부에서 접근하는 정보는 해당 파일의 시작 블록 번호와 같은 것이 있다. 예를 들어 위 예제의 f1 파일의 디렉토리 정보는 아래와 같다.

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

 

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

 

연속 할당은 현재는 거의 사용하지 않는 방식이다. 큰 단점이 존재하기 때문이다. 파일을 할당하고 지우고를 반복하다보면 중간에 빈공간(hole)이 생기는데 연속 할당은 연속된 공간을 찾아야 하기 때문에 이전 메인 메모리 할당에서 살펴본것과 같이 외부 단편화가 발생한다.

외부 단편화로 인해 디스크 공간의 낭비가 매우 심해진다. 이전 메모리 할당에서 외부 단편화로 인해 메모리의 약 1/3을 낭비한다고 했는데 디스크 연속 할당도 마찬가지이다.

 

또 다른 문제는 파일을 저장할 때 실제 크기를 알 수 없다. 특히 계속해서 사용하는 파일의 경우 크기가 증가 할 수 있기 때문에 이를 지속해서 연속적으로 할당하기에는 매우 부적절하다.

2. 연결 할당(Linked Allocation)

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

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

 

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

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

 

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

 

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

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

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

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

 

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

 

FAT의 각 인덱스 크기는 전체 블록의 개수를 저장할 만큼의 크기를 가지고 있어야 하는데 현재는 일반적으로 32bit 크기를 사용한다. 이를 FAT32라고 부른다.

3. 색인 할당(Indexed Allocation)

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

 

예) block size = 1byte, f1 = 5bytes, f2 = 2bytes

 

 

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/4bytes(포인터크기) = 128개이다. 즉 파일의 최대 크기는 (128개) 512bytes = 64KB로 아주 작은 크기이다. 블록 크기가 1KB이라 하더라도 최대 인덱스 개수는 256(1000/4)개이고 최대 파일의 크기는 256KB이다. 이를 해결하기 위한 여러 가지 방법이 있다.

 

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

 

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

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