File Allocation

이 글은 KOCW 강좌 중 경성대학교 양희재 교수님의 '운영체제' 강의를 정리한 글입니다.

 

File Allocation

File Allocation

Hard Disk 구조는 아래와 같다.

• platter -> 실제 Data를 기록하는 자성을 가진 원판
• track -> platter의 동심원을 이루는 하나의 영역
• sector -> track을 여러 개로 나눈 영역, 일반적으로 setor의 크기는 512 bytes.
• cylinder -> 모든 platter에서 같은 track 위치의 집합

위에서 sector 여러개를 묶어 block이라고 한다.

Hard Disk는 block 단위로 읽고 쓰기 때문에 Block Device라고도 한다.

비어 있는 block들의 모임으로 볼 수도 있어서 pool of free blocks라고도 한다.

운영체제가 File을 free block에 어떻게 할당할지 알아보려 한다.

Contiguous Allocation

연속 할당은 말그대로 각 file을 연속된 Block에 할당하는 방식이다.

연속된 Block에 위치해 있어 file을 읽을 때 Disk Header의 이동을 최소화할 수 있다.

빠른 I/O 성능을 보여준다.

주로 동영상, 음악, VOD file에 적합하다.

연속 할당은 아래 2가지 특징이 있다.

• Sequential Access(순차 접근) -> 순서대로 file 읽기
• Direct Access(직접 접근)
  • 운영체제는 Directory라는 테이블에 file의 정보 저장(이름, 크기, 날짜, 시작 Block 번호)
  • 시작 Block 번호를 근거로 해서 특정 Block에 바로 접근 가능

빠른 I/O 성능을 보여주지만 단점이 존재한다.

file을 삭제했을 때 hole이 발생한다.

삭제하다 보면 hole들이 생기고 빈 공간의 총량은 크지만 각 hole보다 큰 file을 저장하지 못한다.

외부 단편화가 발생한다.

Compaction으로 hole들을 정리할 수 있지만 시간이 오래 걸린다.

그리고 file 생성 시 크기를 알 수 없다.

file의 크기는 계속 증가할 수 있어서 지속적으로 연속 할당하기에는 부적절하다.

Linked Allocation

연결 할당은 Linked List처럼 Pointer를 이용해서 file을 Block에 저장한다.

file의 Directory 테이블은 제일 처음 Block을 저장한다.

각 Block은 다음 Block 주소를 저장하는 Pointer를 가진다.

Pointer의 크기는 보통 4 bytes 또는 그 이상이다.

file이 커지면 다음 Block을 가리켜주면 된다.

외부 단편화가 없지만 아래와 같은 단점이 존재한다.

• Sequential Access를 해야 한다 -> Direct Access가 불가능
• Pointer 저장을 위한 공간 손실
• 낮은 신뢰성 -> Pointer 끊기면 접근 불가
• 느린 속도 -> Block이 흩어져 있어 Disk Header 움직임 발생

FAT

File Allocation Table File System

연결 할당 방식을 개선하기 위해 나온 방식이다.

FAT는 다음 Block을 가리키는 Pointer들만 따로 Table로 저장하는 방식이다.

이 Table을 별도 Block에 저장해서 Table을 통해 Block에 접근한다.

Table 손실 시 복구를 위해 이중 저장한다.

Direct Access도 가능하다.

FAT는 일반적으로 Memory에 캐싱한다.

Indexed Allocation

색인 할당은 file당 Index Block를 따로 두어 해당 Block Pointer들을 저장한다.

file의 Directory 테이블은 Index Block을 가리킨다.

보통 Unix, Linux 등에서 사용한다.

Direct Access가 가능하고 외부 단편화가 없다.

대신 file당 Index Block을 저장할 공간이 필요하다.

요즘 file 크기가 커서 하나의 Block에 모든 Pointer를 저장하지 못한다.

그래서 아래와 같은 개선된 방식이 생겼다.

• Linked
  • 여러 개의 Index Block을 연결, Block 마지막 부분이 다음 Index Block Pointer
• Multilevel Index
  • 계층을 두는 방식, 마지막 Level에서는 Data Block을, 그 외에는 모두 Index Block을 가리킴
• Combined
  • Linked와 Multilevel Index를 합친 방식, 일부는 Data Block 일부는 Index Block을 가리킴