File Allocation

Disk Sector, Disk Cluster, Disk Block

 

Disk

   - Sector : 자체적으로 주소를 갖고 있는 스토리지 단위이다. 하드디스크의 섹터 크기는 보통 512byte이고, 소프트웨어적으로 접근할 수 있는 가장 작은 단위가 된다.

 

   - Cluster : Sector의 집합으로, 파일을 할당할 수 있는 항당 단위이다. 파일이 할당 될 수 있는 가장 작은 디스크 공간이다.

 

   - Block : 운영체제가 디스크를 접근하는 기본 단위이다. 즉 1개 이상의 섹터를 갖는다. 블록 단위의 크기가 커지면 한번에 참조하는 양이 많아지므로 속도는 빨라지지만, 낭비되는 메모리가 많아 메모리 활용에서는 떨어진 성능을 보인다.

 

Allocate and Free 

 

   - Disk에 파일을 할당하고, 해제하는 방식을 결정한다. 큰 2차원 배열처럼, 하드디스크도 아래 그림처럼 각 블록 크기의 방에 파일을 할당한다는 것을 생각해둬야 이해가 쉽다.

 

Contiguous Allocation

 

   - 연속 할당 방식은 말그래도 블록을 순서대로 사용해서 파일을 저장한다. 디스크 이동을 최소화할 수 있어 속도가 빠르고, 원하는 특정 위치를 직접 읽을 수 있다.

 

   - 문제는 파일을 삭제하고 할당하는 것을 반복하면서, 비어있는 블록이 흩어지게 되고, 이를 모으면 충분한 크기의 저장 공간인데 반해, 연속하지 않아 결국 할당하지 못하는 외부 단편화 문제가 발생한다.

 

File4, File6, File8이 삭제된 이후, 블록 사이즈가 5이상인 파일은 할당될 수 없는 상황

 

Linked Allocation 

 

   - 연결 할당 방식은 연속 할당 방식의 외부 단편화 문제 해결을 위해, 파일을 순서대로가 아닌 흩어진 블록에 저장한다. 블록을 할당할 때 다음 이어질 내용의 블록을 포인터로 가리키는 형식으로 할당을 자유롭게 할 수 있다.

 

   - 특정 위치를 엑세스할 때, 그 위치를 한번에 알 수 없어, 그 순서를 따라 이전 블록들을 모두 참조하여 올라가야만 해당 위치를 엑세스할 수 있다. 또, 같은 이유로 중간의 한 블록만 소실되어도, 이후 포인터를 잃어 다음 순서에 해당하는 모든 블록을 다 손실하게 된다.

 

Linked Allocation

   ** FAT (file allocation table) : 이런 문제를 해결하기 위한 방식으로, 블록 안에서 다음 순서의 블록 포인터를 갖고 있는 것이 아니라, 한 블록에 테이블로 위치 포인터를 저장한다.

 

   - 이 테이블을 읽음으로써 바로 원하는 위치에 엑세스가 가능하므로, 속도가 더 빨라지고, 테이블 블록만 아니라면, 중간의 한 블록을 읽어도 다른 연결된 블록에 영향을 주지 않는다. 테이블 블록의 손실을 피하기 위해, 백업 테이블을 만들어 안전하게 한다.

 

   - MSdos, window에서 사용된다.

 

Indexed Allocation

 

   - 색인 할당 방식은 한 기준 블록(인텍스 블록)에 인덱스를 저장해두고 디렉토리를 이 블록으로 하는 것으로, 외부 단편화를 해결하고, Direct access를 가능하게 한다.

 

   - 문제는 블록 사이즈가 작아, 한 블록 안에서 인덱스를 모두 포함하지 못하는 상황이 발생하고, 이를 모두 표시하기 위해서 인덱스 블록을 늘리고, 연결하다보면, 저장소가 낭비된다는 파일 최대 크기 문제가 발생한다. 이런 문제를 해결하기 위해, Linked index block 방식, multi level 방식, combined 방식이 사용된다.

 

   - LINUX나 UNIX에서 사용된다.    

 

Linked index block

 

Multi level index block

 

Combined index block

 

Example

 

   - FAT / Indexed block

FAT / Indexed block

 

   - 8번째 블록을 엑세스 하는데 각 방식별 읽어야하는 블록의 개수

 

   1. 연속 할당 : 1개

   

   2. 연결 할당 : 8개

 

   3. FAT : 1개  ( table은 장기 기억을 위해, 디스크에 저장해뒀다가, 부팅 시 이를 메모리에 올려 더 빠르게 엑세스한다. 메모리에서 테이블을 읽고 바로 8번째 블록을 찾아 엑세스 한다.)

 

   4. 색인 : 2개 ( 인덱스 블록이 1개일 때를 가정하면, 인덱스 블록과 8번째 블록을 읽으면 된다. 인덱스 블록이 여러개 연결 시 참조 블록의 수는 달라진다.)