[운영체제] 파일 할당 File Allocation

운영체제 커리큘럼  1. 프로세스 관리 2. 메인 메모리 관리 3. 파일 시스템

컴퓨터 시스템 자원 관리

•   CPU : 프로세스 관리 (CPU 스케쥴링, 프로세스 동기화)
•   주기억장치 : 메인 메모리 관리 (페이징, 가상 메모리)
•   보조기억장치 : 파일 시스템

 

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

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

  - Sector size = 512 bytes, cf.Block size

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

  - 디스크 = 블록들의 pool

-> 어떻게 파일마다 free block을 할당할까? 

-> 하드디스크 용량 낭비 없도록, 파일 탐색 및 읽는 시간도 고려해야한다.

 

 

 

파일 이란? 사용자가 작성한 서로 관련 있는 레코드의 집합체를 말한다.

프로그램 구성의 기본 단위가 되며, 보조기억장치에 저장된다. 파일마다 이름, 위치, 크기, 작성 시기 등 여러가지 속성을 가지고있다.

 

파일 시스템이란?

파일의 저장, 액세스, 공유, 보호 등 보조기억장치에서의 파일을 관리하는 파일 관리 기술을 말한다.

 

 

1. 파일 할당 방법

파일 할당 방법은 크게 연속, 연결, 색인 할당 방법이 있다.

1) 연속 할당 Contiguous Allocation

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

 

장점은

디스크 헤더의 이동 최소화한다는 점이다. 연속해서 블록을 할당했기 때문에 헤더를 옮기지 않아도 읽을 수 있다. 그러므로 빠른 I/O 성능을 낼 수 있다.

이 방법은  동영상, 음악, VOD 등에 적합하다.

 

연속 할당 방법은 순차 접근으로 읽을 수도 있고(squential access 순차 접근), 특정 부분을 바로 읽을 수도 있다. (direct access 직접 접근)

 

연속 할당 방법은 위와같은 장점이 있으나 단점때문에 더이상 사용하지 않는다.

 

단점은

외부 단편화로 인한 디스크 공간 낭비이다.

메모리 관리에서 First-fit에서의 문제와 유사하다. 파일이 삭제되면 hole이 생성된다. 파일 생성과 삭제를 반복하면 곳곳에 hole이 생성된다. 새로운 파일을 hole들에 어떻게 할당할 것인가?

Compaction을 통해 hole을 한곳에 모을 수 있지만 시간이 오래걸린다.(80년대 초창기 MS-DOS) 

 

또한, 파일 생성 당시에는 크기를 정확히 알 수 없기에 어느 hole에 저장할지 정하기 어렵다는 점이다. 파일의 크기는 커질수도, 작아질 수도 있기 때문에 hole 배치로는 저장이 불가한 경우 문제는 더욱 심각해진다.

 

 

2) 연결 할당 Linked Allocation

연속 할당의 외부 단편화 문제를 개선한 방법이 연결 할당이다.

 

연결 할당은 자료구조에서 Linked List라고 생각하면 쉽다.

파일은 데이터 블록들의 linked list이며, 파일 디렉토리(directory)는 제일 처음 블록을 가리킨다.

각 블록은 포인터 저장을 위한 4byte 또는 그 이상의 저장공간으로 소모한다.

 

연결 할당의 단점은 오직 순서대로만 읽을 수 있다는 점이다. (Only Sequential Aeccss). Direct Access가 불가하다.

그리고 신뢰성이 낮다는 점이다. 포인터가 도중에 끊기면 그 다음 데이터들은 전부 접근 불가능하다는 문제가있다.

또한 헤더의 움직임이 계속해서다른 떨어진 블록들을 탐색해야하기 때문에 읽는 속도가 매우 느리다.

+ 포인터 보관 위한 공간 손실

 

 

* FAT 파일 시스템

: 연결 할당의 문제를 개선하기 위해 FAT 파일 시스템(File Allocation Table) 이 탄생했다.

포인터들을 모은 테이블(FAT)를 별도 블록에 저장한다. FAT 손실 복구를 위해 이중 저장한다.

이를 통해 Direct Access도 가능하다.

 

FAT에 16bit를 할당하면 FAT16이고(포인터 수가 2^16개 = 64000개 용량 작은 디스크에 사용) , 32 bit를 할당하면 FAT32이다.

(플러피 디스크는 FAT 12bit를 할당해 FAT12를 사용했다. 2^12=4096)

FAT 파일 시스템은 MS-DOS, OS/2, Windows 등에서 사용한다.

 

 

 

3) 색인 할당 Indxed Allocation

색일 할당은 파일 당 한 개의 인덱스 블록을 두어 포인터 모음을 저장하는 방식이다.

연결 할당은 링크드 리스트이므로 다음 블록의 주소를 저장했고, 색인 할당은 블록 주소를 인덱스에 저장한다는 차이가 있다. 

 

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

 

장점은

Direct Access가 가능하다는 점과 외부 단편화가 없다는 것이다.

 

단점은

인덱스 블록 할당에 따른 저장 공간 손실이다. (내부 단편화)

1 byte짜리 작은 파일을 저장하는데에도 데이터 1블록과 인덱스 1블록이 필요하다.

 

또한, 파일의 최대 크기가 정해진다는 한계가있다. 인덱스 블록 하나로 큰 파일을 모두 기록할 수 없기때문이다.

1 블록 = 512 byte = 4 byte * 128 인덱스
512 * 128 = 64 KB

1 블록 = 1 KB = 4 byte * 256 인덱스
1 * 256 = 256 KB

 

 

이런 한계를 해결하기 위해 여러 방법 이있다. 대표적으로 Linked, Multilevel Index, Combined 방식이 있다.

• Linked : 인덱스 블록의 마지막 부분이 다른 인덱스 블록을 가리키는 방식
•  Multilevel Index : 인덱스를 트리 모양으로 엮는 방식
• Combined : 위 둘을 혼합한 방식

 

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