[OS] File Allocation

 

 

 

파일 할당 (File Allocation)

 

컴퓨터에서 가장 중요한 자원은 cpu > 메인 메모리 > 하드디스크 이다.

• cpu → 프로세스 관리 → cpu 스케쥴링, 프로세스 동기화
• 메인 메모리 → 메인 메모리 관리 → 페이징, 가상 메모리 → demand paging
• 보조기억장치 → 파일 시스템

 

하드디스크를 위, 앞에서 본 모습

 

하드디스크는 글자단위로 자료가 이동하는 키보드와 같은 character device가 아닌 block device이다. 하드디스크에 무언가를 read, write할 땐 블록단위로 읽고 쓴다. 각각의 파일에 대해 free  block을 할당하는 방식은 속도를 추구할 지 용량을 추구할 지에 따라 os 설계자가 결정한다.

 

block = sector의 모음

 

하드디스크에서 track은 sector들로 구성되고 회전한다. 디스크의 헤드는 코일로 감싸져 있고 헤드를 앞뒤로 움직여 전기를 유도해 (자화) 내용을 읽거나 기록한다.

 

Transfer time = 디스크가 회전하면서 해당 내용이 읽혀짐 → 빠르다.

Seek time = 디스크가 원하는 트랙을 찾아 옮김 → 오래 걸린다.

Rotatinoal delay = 한 바퀴 돌고 다시 헤드 밑으로 오는 데 걸리는 시간 → 빠르다.

 

맨 처음 하드디스크는 비어있는 block들로 구성된다.

파일할당은 디스크의 용량을 낭비하지 않고 빨리 읽을 수 있도록 해준다.

 

 

 

ex) 5KB의 파일이 있다고 가정하자

 

1. 연속 할당 (Contiguous Allocation)

디스크 상 연속된 블록을 할당하는 방식이다. → 0번, 1번, 2번,  3번, 4번..(파일 시작 위치 : 0)

 

장점 : 디스크 이동을 최소화할 수 있고 읽고 쓰기가 빠르다. sequential access, direct access 가능

단점 : 디스크 생성, 삭제를 반복하면 hole이 흩어지게 된다. sequential access를 사용하면 외부단편화 문제가 발생해 디스크 공간이 낭비된다.

ex) file이 3.6KB일 경우 4개의 블록을 할당해주어야 하므로 0.4KB가 남게 된다.

 

 

2. 연결 할당 (Linked Allocation)

연속할당과 연속할당을 개선한 FAT

연속할당방식을 개선한 방식이다. 각 블록에 포인터를 두어 반드시 블록번호가 연속되지 않더라도 떨어져 있는 블록끼리 연결이 가능하도록 했다. → Linked List구조 → 5번, 2번, 6번, 10번, 9번, 8번...(파일 시작 위치 : 5)

 

장점 : 블록번호가 연속될 필요가 없으므로 외부단편화 문제가 발생하지 않는다.

단점 : 블록번호가 연속되지 않더라도 포인터에 연결된 순서대로 읽어야 하므로 direct access 불가능하다. sequential access만 가능하다. 또한 포인터를 지정해주어야 하므로 각 블록에 4바이트이상이 손실된다.

또한 특정번지가 읽혀야 다음 번지가 읽히는데, 특정번지가 읽히지 않으면 그 다음을 읽을 수 없어 신뢰성이 떨어진다.

그리고 포인터가 멀리 멀리 흩어져 있다면 헤더를 많이 움직여주어야 하므로 속도가 느려질 수 있다.

 

↓

 

FAT

블럭마다 끝에 있는 포인터들을 모아 별개의 테이블을 만들어 비어있는 디스크 블록에 저장

→ 신뢰성 문제 해결

→ FAT 망가짐을 대비해 FAT copy본을 하나 더 만들어 비어있는 디스크 블록에 저장해둠

 

 

3. 색인 할당 (Indexed Allocation)

각 블록에 포인터를 두어 반드시 블록번호가 연속되지 않더라도 떨어져 있는 블록끼리 연결이 가능하도록 했다.파일 한개 당 한개의 인덱스 블록을 생성한다.

인덱스 블록은 흩어져 있는 인덱스를 모아놓은 것이다. 

여러 개의 파일들을 하나의 디스크에 할당할 수 있다.

 

f1 : 4번, 2번, 3번, 0번(파일 시작 위치 : 4)

f2 : 8번, 5번 (파일 시작 위치 : 8)

 

장점 :  sequential access가능하다.(f1을 읽고 f2를 순서대로 읽으면 됨), direct access가능하다.(a,b,c,d가 아니라 바로 c를 읽을 수 있음), 파일을 연속적으로 두지 않으므로 외부단편화 현상이 일어나지 않는다.

단점 :  비어있는 블록 중 하나를 골라 인덱스블록으로 할당해주어야 하므로 저장공간이 손실된다. 

               1디렉토리 : 데이터블록 + 인덱스 블록 1개

한개의 인덱스 블록을 만들기 위해 한 블록 안에 들어갈 수 있는 엔트리 갯수가 제한적일 수 있다.

 

ex) 1 블록 = 512바이트 = 4바이트 * 128 → 엔트리수는 128개이고 파일 크기는 512 + 128 = 64KB

 

 

solution : 

• Link

인덱스 블록이 1개로 모자라다면 다른 비어있는 블록을 추가적으로 인덱스 블록으로 사용

 

• Multilevel

하나의 인덱스 블록에서 다른 인덱스 블록 여러개를 가리키도록 함

 

 

• Combined

 

하나의 인덱스 블록에서 여러 개의 파일을 가리키도록 함