[Pintos-KAIST] Project 4 :: 디스크의 파일 데이터 할당 방법

Pintos Project4에서는 FAT 방식으로 파일 데이터를 할당한다.

FAT 방식은 파일이 할당된 블록의 위치 정보를 chain 형태로 관리하는 Linked Allocation 방식에 해당한다.

이외에도 파일 데이터를 할당하는 방식은 여러가지가 있다.

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

 

1. Contiguous Allocation

연속 할당 방식은 각 파일을 디스크의 연속적으로 이어지는 공간에 할당한다.

 

 

이 상황에서 중간에 있는 길이가 5인 주황색 파일이 삭제되어 공간이 비었을 때,
길이가 6인 노랑색 파일을 저장하려고 한다면,

 

실제 디스크의 공간이 6 이상 비어있음에도 불구하고,
연속된 공간이 아니기 때문에 할당할 수 없어 4 ~ 9 영역은 사용하지 못해 외부 단편화가 발생한다.

더불어 다음 파일이 연속적으로 할당되어 있기 때문에, 이미 할당된 파일의 크기가 늘어나는 상황을 대응할 수 없는 경우가 발생한다.

 

이러한 단점을 보완하는 것이 다음의 Linked Allocation 방식이다.

 

2. Linked Allocation

Linked Allocation 방식에서는 각 파일이 할당되어 있는 블록 정보를 각 블록에 저장해서 마치 linked-list처럼 블록의 연결 정보를 가지고 있다.

파일의 내용을 이어서 읽으려면 블록에 저장된 다음 블록의 위치 정보를 파악해서 해당 위치로 이동해 이어서 내용을 읽어나간다.

 

이렇게 하면, Contiguous Allocation 방식에서처럼 블록이 연속된 영역에 할당될 필요가 없기 때문에
외부 단편화를 방지할 수 있고,
이미 할당된 파일의 크기가 늘어나는 상황(File Growth)에도 대응이 가능해진다. 👉 아무데나 빈 공간에 할당하고 연결 정보만 추가하면 되기 때문!

 

 

하지만 이 방식도 단점이 있는데,
linked-list 형태로 구현되어 있는 중간 블록에는 파일의 정보가 없어서 파일의 중간 부분부터 접근할 수 없고, 항상 파일의 첫 블록부터 접근해나가야 한다.

또한, 연결된 블록들 중에서 중간에 있는 블록의 데이터가 유실되는 경우, 연결 정보를 확인할 방법이 없어 이후의 데이터를 확인할 수 없다.

 

이 형태를 보완해서 나온 것이 Pintos에서 구현한
File Allocation Table, 줄여서 FAT 방식이다.

File Allocation Table

기존 방식은 다음 블록의 위치 정보가 디스크에 저장되어 있었다. (👇 Linked Allocation 방식)

 

 

FAT 방식은 별도의 FAT 테이블을 만들고
체인 정보(다음 블록의 위치 정보)를 FAT 테이블에 저장한다.

기존 방식이 파일의 중간에 접근하려 했을 때는
디스크 헤더가 첫 블록부터 모두 접근해야 했지만,
FAT는 메모리에 위치한 FAT 테이블을 탐색한 후 디스크에 바로 해당 위치에 접근할 수 있어 더 나은 성능을 보여준다.

 

또한 디스크의 정보가 일부 유실되어도 FAT 테이블에 정보가 남아있기 때문에 안정적인 방식이다.

 

3. Indexed Allocation

Indexed Allocation 방식에서는 Index block이라는 특별한 데이터 블록을 활용한다.
Index block은 파일이 저장된 위치를 배열 형태로 저장한다.

 

이 방식은 특정 위치 접근 시 chain을 거칠 필요 없이 배열의 인덱스를 이용해 더 빠르게 접근이 가능하다.

 

하지만, 파일의 크기가 커서 파일이 할당된 위치를 한 Index block에 모두 저장할 수 없는 경우가 발생할 수 있고,
파일의 크기가 아주 작은데도 불구하고 Index block을 반드시 하나 사용해야 하기 때문에 낭비되는 공간이 발생할 수 있다.

 

파일의 크기가 커서 한 Index block에 모두 저장할 수 없는 상황에 대응하기 위한 Multi-level Index 방식이 있다.

 

Multi-level Index

이 방식은 inode 구조체를 활용한다.
inode 구조체에는 메타데이터 정보와 파일의 위치 정보가 포함되어 있다.

 

 

그리고, 파일의 위치 정보가 담긴 block은 Direct block과 Indirect block으로 나뉜다.

 

Direct block은 위 방식과 동일하게 파일이 저장된 data block의 위치를 가지고 있다.
만약 파일의 크기가 커져서 한 block에 모두 저장할 수 없다면 Indirect block을 사용한다.

Indirect block은 파일의 위치 정보 자체가 아닌, 그 정보를 담고 있는 data block을 가리키게 된다.
(간접적으로 가리키기 때문에 Indirect!!)

 

이렇게 하면 훨씬 많은 위치 정보를 저장할 수 있게 된다.

 

 

그렇다면, 이 방식과 FAT 방식 중 어떤 방식을 사용하는 것이 좋을까?

 

FAT vs Multi-level Index

FAT는 상대적으로 구현이 쉽다는 장점이 있지만,
파일의 크기가 커질수록 탐색 시간이 선형으로 증가한다.
따라서 Index로 빠르게 접근하는 Multi-level Index 방식에 비해 탐색 효율이 좋지 못하다.

 

따라서, 저장할 데이터의 특성에 따라서 적절한 방식을 선택해야 한다.
데이터의 크기가 큰 경우에는 빠르게 접근할 수 있는 Multi-level Index 방식이 유리할 것이고,
데이터의 크기가 작은 경우에는 구현이 간단한 FAT가 더 적합하다.