파일 할당(File Allocation)

컴퓨터 시스템 자원 관리

  - CPU : 프로세스 관리 (CPU 스케쥴링, 프로세스 동기화)

  - 주기억장치 : 메인 메모리 관리 (페이징, 가상 메모리)

  - 보조기억장치 : 파일 시스템

 

보조기억장치 (하드디스크)

  - 하드디스크 : track(cylinder), sector

  - Sector size = 512 bytes, cf.Block size

하드디스크의 섹터 사이즈는 보통 512bytes 이며 이 섹터들을 모아 블록 단위로 헤더가 읽는다.

  - 디스크 = pool of free blocks

=> 각각의 파일에 대해 free blcok을 어떻게 할당해줄까?

효과적으로 하드디스크 용량을 관리하는 것과 파일 탐색 및 읽는 시간을 모두 고려해야 한다!

---

1. 파일 할당 방법

1) 연속 할당

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

연속 할당의 장점은 디스크 헤더의 이동을 최소화한다는 것이다. 연속해서 블록을 할당했기 때문에 블록들이 모여있게 되고 헤더가 이를 빨리 읽을 수 있게 된다. 이를 통해 빠른 i/o 성능을 낼 수 있다.

 

연속 할당은 옛날 IBM VM/CMS에서 사용되었다. 동영상, 음악, VOD 등 순차적인 데이터를 빠르게 읽어야할 때 적합한 방식이다.

연속할당은 순차적으로 읽을 수도 있고, (=sequential access 순차 접근)

특정 부분을 바로 읽을 수도 있다. (=direct access 직접 접근) 

 

연속할당의 단점으로는 외부 단편화로 인한 디스크 공간 낭비이다. Compactions을 통해 hole을 모을 수 있지만 시간이 오래 걸린다.(초창기 MS-DOS)또다른 단점으로, 파일 생성 당시에는 이 파일의 크기를 알수 없기에 파일을 어느 hole에 저장할 지 모른다는 점이다.또한, 파일의 크기는 계속 증가할 수 있기 때문에 기존의 hole 배치로는 저장이 불가할 경우 문제는 더욱 심각해진다.　

  　

2) 연결 할당

연속 할당의 외부단편화 문제를 해결하기 위해 나온 방법이 바로 연결 할당이다.

연결 할당은 쉽게 말해 LinkedList 자료구조이다. 파일은 데이터 블록들의 linked list이며, 파일 디렉토리(directory)는 제일 처음 블록을 가리킨다. 각 블록은 포인터 저장을 위한 4byte 또는 그 이상의 저장공간으로 소모한다.

 

연결 할당의 단점으로는 오직 순서대로만 읽을 수 있다는 것이다.(Only sequential access)

그래서 Direct access가 불가하다.

또한, 포인터 저장을 위해 4byte 이상의 메모리 손실이 발생한다.

그리고 낮은 신뢰성, 즉 포인터가 도중에 끊어지면 그 다음의 데이터들은 모조리 접근이 불가하다는 문제가 있으며느린 속도, 헤더의 움직이 계속해서 다른 떨어진 블록들을 탐색해야 되기에 읽는 속도가 굉장히 느리다는 문제가 있다.

 

• 개선 : FAT 파일 시스템

연속 할당의 문제를 개선하기위해 FAT 파일 시스템이 탄생했다.

FAT란 File Allocation Table의 약자로, 포인터들을 모은 테이블(FAT)를 별도 블록에 저장한다. FAT 손실 시 복구를 위해 이중저장한다. 이를 통해 Direct access 도 가능해진다.

FAT는 일반적으로 메모리 캐싱이다.

　

3) 색인 할당

색인 할당은 파일 당 (한 개의) 인덱스 블록을 두어 포인터의 모음을 저장해둔다.

얼핏 보면 연결할당과 비슷하다고 볼 수 있으나, 연결 할당은 링크드리스트이기에 다음 블록의 주소를 저장해둔 것이고, 색인 할당은 아예 처음부터 블록들의 주소를 각각의 인덱스에 저장해둔 것이다.

 

디렉토리에는 인덱스 블록의 주소가 저장된다.

색인 할당 방식은 Unix/Linux 등에서 사용된다.

 

색인 할당의 장점으로는 Direct access가 가능하며, 외부 단편화가 없다는 점이다.그러나, 색인 할당의 단점으로는 인덱스 블록 할당에 따른 저장공간의 손실이 발생한다는 것이다. 예를 들어 1byte의 아주 작은 파일을 저장하기 위해 데이터 1블록 + 인덱스 1블록이 필요하다.

 

또한, 파일의 최대 크기가 정해진다는 것도 색인할당의 큰 단점이다.인덱스 블록 하나만으론 큰 파일을 모두 기록할 수 없기 때문이다!이러한 문제를 해결하기 위한 방법으로 인덱스 블록의 마지막 부분이 다른 인덱스 블록을 가리키도록 하는 Linked 방식,인덱스 블록을 트리 모양으로 엮는 Multilevel Index 방식, 이 둘을 혼합한 Combined 방식 등이 있다.