파일 할당 (File Allocation)

컴퓨터 시스템 자원 중 CPU는 프로세스 관리를 맡으며 세부적으로 CPU 스케쥴링, 프로세스 동기화 등의 작업을 진행한다. 주기억장치는 메인 메모리를 관리하며 세부적으로 페이징, 가상 메모리 관리 등을 맡는다. 보조기억장치는 파일 시스템 관리를 맡는다.

보조기억장치는 다른 말로 하드디스크라고도 한다.

하드디스크는 다음과 같이 구성되어있다.

플래터 (Platter)

실제 데이터를 기록하는 원판이다. 하드디스크에는 여러개의 Platter가 있으며 앞뒤로 사용할 수 있다. Platter는 여러개의 Track으로 구성된다.

트랙 (Track)

Platter의 동심원을 이루는 하나의 영역이다.

섹터 (Sector)

하나의 Track을 여러개로 나눈 영역이다. 일반적으로 512bytes의 크기를 갖는다. 여러개를 하나로 묶어서 사용한다.

실린더 (Cylinder)

하나의 Cylinder는 모든 Platter에서 같은 Track 위치의 집합이다. 마치 하나의 원통을 이루는 듯하여 실린더라는 이름이 붙었다.

블록 (Block)

섹터를 여러개를 하나로 묶어서 사용한다고 했는데, 하나의 섹터 묶음을 블록 (Block)이라고 한다.

디스크는 비어있는 블록들의 집합이다. (Pool of Free Blocks)

운영체제는 파일에게 디스크의 블록들을 필요한 만큼 할당해줘야한다. 어떻게 할당해줄까?

연속 할당 (Contiguos Allocation)

각 파일에 대해 디스크 상의 연속된 블록을 할당하는 방법이다.

연속된 블록을 할당하므로 디스크 헤더의 이동이 최소화된다. 따라서 I/O의 성능이 빨라진다.

예전의 IBM VM/CMS에서 사용했으며 동영상, 음악, VOD 등에 적합하다.

연속할당은 파일을 순차적으로 읽을 수 있고 (순차접근 : Sequential Access), 특정 부분을 바로 읽을 수도 있다. (직접접근 : Direct Access)

하지만 연속 할당은 현재는 거의 사용하지 않는 방법이다.

파일을 할당하고 지우고 하다보면 중간 중간에 빈 공간 (Hole)이 생긴다. 연속 할당은 말 그대로 연속된 공간을 찾아야하기 때문에 애매하게 비어있는 공간은 무시하고 다른 공간을 찾아간다. 이렇게되면 외부 단편화 문제가 발생하고 디스크 공간의 낭비가 심해진다. 물론 Compaction을 통해 해결할 수 있지만 시간이 오래 걸린다.

또한 연속할당은 파일을 생성할 때 이 파일의 크기를 알 수 없다는 점이다. 따라서 파일을 어느 정도로 연속된 hole에 배치할 것인지를 정하기가 어렵다. 왜냐하면 파일은 사용하면 사용할수록 그 크기가 계속 증가할 수 있다. 따라서 기존에 배치했던 영역만으로는 부족해질 수 있다. 이를 계속 연속적으로 추가 할당해나갈 수 있지만, 빈 공간이 없다면? 더이상 할당해줄 수가 없다.

연결 할당 (Linked Allocation)

연결 할당은 자료구조 중 연결 리스트 (Linked List)와 비슷한 방식으로 할당한다.

각 블록의 마지막에 주소를 저장하는 포인터 공간을 만든다. 이 공간의 크기는 4bytes정도이다. 연결 할당은 임의의 블록을 첫 블록으로 설정하고 포인터 공간에 그 다음 블록의 주소를 저장한다. 이를 연결이라고 표현한다. 이렇게 연결해나가다가 마지막 블록의 포인터 공간에는 끝임을 나타내는 값을 저장한다.

이처럼 연결 할당은 비어있는 임의의 블록을 첫 블록으로 설정하고, 파일이 커지면 다른 블록을 할당받고 연결해주면 되기 때문에 외부 단편화가 발생하지 않는다. 즉, 디스크의 낭비가 없다.

하지만 연결할당은 직접접근 (Direct Access)이 불가능하다. 파일 블록이 모두 흩어져있기 때문에 시작 블록만 가지고는 원하는 위치에 Direct로 Access 할 수 없다. 대신 순차접근은 가능하다.

연결할당은 포인터를 저장하기 위해 4bytes 이상의 데이터가 무조건 손실된다. 또한 이 포인터가 끊어지면 그 다음 블록으로의 접근이 불가능하므로 신뢰성이 낮다. 마지막으로 블록이 모두 흩어져있으므로 그만큼 헤더의 움직임이 많아지고 성능에 악영향을 미친다. 따라서 속도가 느리다.

FAT (File Allocation Table) 시스템

이러한 문제점을 개선해서 나온 방식이 FAT 파일 시스템이다.

포인터들만 모아놓은 테이블 (FAT)을 별도의 블록에 저장해놓는다. 또한 FAT가 손실될 때 복구하기 위해 이중 저장을 실시한다.

FAT의 인덱스는 전체 디스크의 블록 번호를 의미한다. 각 인덱스에는 해당 블록과 연결된 그 다음 블록의 번호가 저장되어있다.

FAT를 한번만 읽으면 파일에 직접 접근이 가능하다. 하지만 접근만 빠를 뿐 실제 블록을 읽는 속도는 마찬가지로 느리다. 왜냐하면 결국에는 흩어져있는 블록을 찾아 디스크 헤더가 계속 움직여야하기 때문이다.

FAT 테이블은 일반적으로 32bit의 크기를 사용한다. (FAT32) 그 외에도 bit 크기에 따라 FAT16, FAT12 등이 있다.

색인 할당 (Indexed Allocation)

연결 할당과 마찬가지로 데이터를 랜덤한 블록에 저장하지만 할당된 블록의 번호 (포인터)를 또 다른 블록에 저장한다. 이러한 블록을 인덱스 블록이라고 한다. 즉, 인덱스 블록은 포인터의 모음이라고 볼 수 있다.

색인 할당은 디렉토리 정보가 다른 할당과 다른데, 시작 블록 번호를 저장하는 것이 아니라 인덱스 블록 번호를 저장한다.

색인 할당은 연결 할당과 마찬가지로 Direct Access가 가능하고 외부 단편화가 없다.

하지만 인덱스 블록 할당에 따른 저장 공간의 손실이 발생한다. 예를 들어서 1byte 파일을 저장하기 위해 데이터 1블록과 인덱스 1블록을 위한 저장공간이 필요하다.

이를 해결하기 위한 방법은 Linked, Multilevel Index, Combined 등이 있다.

• Linked : 하나의 색인 블록은 통상적으로 한 디스크 블록이다. 파일의 크기가 크면 여러 개의 색인 블록들을 연결 시킨다.

• Multilevel : 첫 번째 수준의 색인 블록은 여러 개의 두 번째 수준 색인 블록들에 대한 포인터들을 가진다. 두 번째 수준의 색인 블록은 실제 자료 블록들을 가리킨다. 이러한 방법은 파일의 크기에 따라 세 번째 또는 네 번째 수준으로까지 계속 된다. 한 블록의 크기가 4096 바이트라면 1024개의 4바이트 포인터를 한 색인 블록에서 저장할 수 있다, 2단계 색인 기법을 쓰면 1048576개의 자료 블록을 가질 수있으며 이는 파일 크기 4GB까지 저장 가능하다.

• Combined : Linked + Multilevel의 기법이다. 디렉토리 내의 색인 블록이 15개의포인터를 갖는다. 이 포인터들의 처음 12개는 직접 블록(direct block)을 가리킨다. 그 다음 3개의 포인터는 간접 블록(indirect block)의 주소로서첫 번째 포인터는 단일 간접 블록(single-level indirect block)을 통하여 간접적으로파일의 블록을 찾을 수 있으며 두 번째 포인터는 이중 간접 블록 (double-level indirectblock), 마지막 포인터는 삼중 간접 블록(triple indirect block)을통하여 간접적으로 파일의 블록을 찾는 형식이다. 이는 다단계 색인 기법을 확장한 것이다.