Project_4 : File System - Indexed and Extensible Files

기본 파일 시스템은 파일을 single extent로 할당하여 외부 단편화에 취약하다.

즉, n개의 블록이 사용 가능하더라도 n개의 블록을 할당할 수 없는 상황이 발생한다.

on-disk inode 구조를 수정하여 이 문제를 제거해야 한다.

 

해당 문제를 해결하기 위해서 파일 시스템은 직접, 간접, 이중 간접 블록을 가진 인덱스 구조를 사용해야 한다.

Berkeley의 UNIX FFS의 멀티 레벨 인덱싱과 같은 방법을 사용할 수 있겠으나,

이번 프로젝트에서는 주어진 스켈레톤 코드로 FAT을 구현하는 것이 훨씬 편할 것이다.

 

참고로 파일 시스템 파티션은 8MB보다 크지 않다고 가정할 수 있으며,

파티션에서 메타데이터를 제외한 만큼 큰 파일을 지원할 수 있어야 한다.

각 inode는 하나의 디스크 섹터에 저장되며, 포함할 수 있는 블록 포인터의 수를 제한한다.

Indexing large files with FAT(File Allocation Table)

이전 프로젝트에서 사용한 기본 파일 시스템에서는 파일이 여러 디스크 섹터에 걸쳐 연속적인 단일 청크로 저장되었다.

연속적인 청크를 클러스터라고 하면, 클러스터는 하나 이상의 연속적인 디스크 섹터를 저장할 수 있다.

이러한 관점에서 기본 파일 시스템의 클러스터 크기는 클러스터에 저장된 파일의 크기와 같다.

 

외부 단편화를 줄이기 위해 클러스터의 사이즈를 축소할 수 있다. 단순화를 위해 기본 코드에서 클러스터의 섹터 수를 1로 고정하였다. 

이와 같은 소규모 클러스터를 사용하면 클러스터가 전체 파일을 저장하기에 부족할 수 있다.

이 경우 파일 하나에 여러 개의 클러스터가 필요하므로, inode 내 파일에 대한 클러스터들을 인덱싱 하기 위한 자료구조가 필요하다.

가장 쉬운 방법 중 하는 링크드 리스트를 이용하는 것이다.

inode는 파일의 첫 번째 블록의 섹터 번호를 포함할 수 있으며, 첫 번째 블록은 두 번째 블록의 섹터 번호를 포함할 수 있다.

그러나 이런 방식의 접근은 파일의 모든 블록을 읽어야 하기 때문에 속도가 매우 느리다.  

이를 극복하기 위해 FAT은 고정 크기 파일 할당 테이블에 블록 자체보다는 블록의 연결을 배치한다.

FAT은 실제 데이터가 아닌 연결 값만 포함하기 때문에, DRAM에 캐시 할 수 있을 만큼 그 크기가 충분히 작다.

결과적으로 테이블에서 상응하는 엔트리 값을 읽을 수 있다.

 

filesys/fat.c에 제공된 스켈레톤 코드를 사용하여 inode 인덱싱을 구현해야 한다.

아래는 fat.c에 이미 구현되어 있는 함수들과 구현해야 하는 작업들에 대한 설명이다.

 

우선, fat.c의 6개의 함수(fat_init( ), fat_open( ), fat_close( ), fat_create( ), fat_boot_create( ) 등)는

디스크를 초기화하거나 포맷하는 함수이므로 수정할 필요가 없다.

하지만 fat_fs_init( ) 함수를 구현할 필요가 있고, 함수들이 무엇을 하는지 간략히 이해하는 것이 도움이 될 것이다.

 

cluster_t fat_fs_init (void);

FAT 파일 시스템을 초기화한다. fat_fs의 fat_length와 data_start 필드를 초기화해야 한다.

fat_length는 파일 시스템에 담을 수 있는 클러스터 수를, data_start는 어떤 섹터에서 파일 저장을 시작할 수 있는지를 저장한다.

fat_fs->bs에 저장된 일부 값을 사용할 수 있다. 또한 이 함수의 유용한 데이터를 초기화할 수도 있다.

cluster_t fat_create_chain (cluster_t clst);

clst(클러스터 인덱싱 넘버)에 지정된 클러스터 뒤에 클러스터를 추가하여 체인을 확장한다. clst가 0이면, 새로운 체인을 만든다. 

새롭게 할당된 클러스터의 넘버를 반환한다.

void fat_remove_chain (cluster_t clst, cluster_t pclst);

clst부터 시작하여 체인에 있는 클러스터를 제거한다. pclst는 체인 상에서 바로 직전 클러스터여야 한다. 

즉, 이 함수를 실행한 후에 pclst가 업데이트된 체인의 마지막 요소가 되어야 한다.

만약, clst가 체인의 첫 번째 원소인 경우, pclst는 0이어야 한다.

cluster_t fat_get (cluster_t clst);

인자로 주어진 clst가 가리키는 클러스터의 넘버를 반환한다.

disk_sector_t cluster_to_sector (cluster_t clst);

클러스터 넘버 clst를 해당 섹터 번호로 변환하고 섹터 번호를 반환한다.

 

filesys.c와 inode.c에서 이러한 함수들을 이용하여 기본 파일 시스템을 확장할 수 있다.

File Growth

확장 가능한 파일을 구현한다. 기본 파일 시스템에서 파일 사이즈는 파일이 만들어질 때 특정된다.

그러나 대부분의 현대 파일 시스템에서 파일은 처음에 크기가 0인 상태로 생성되었다가 파일 끝에 쓰기를 할 때마다 확장된다.

 

파일이 파일 시스템의 크기를 초과할 수 없다는 점을 제외하고는 파일 크기와 관련해서 미리 결정된 제한이 없어야 한다.

이는 루트 디렉터리 파일에도 적용되며, 초기 제한인 16개 파일 이상으로 확장할 수 있다.

 

사용자 프로그램은 현재 EOF(End Of File)을 넘어 탐색할 수 있다. 탐색 그자체는 파일의 크기를 확장하지 않는다.

EOF를 넘어가는 위치에서 쓰면 파일이 기록 중인 위치로 확장되며, 이전 EOF와 쓰기 시작 사이는 0으로 채워져야 한다.

EOF를 넘아가는 위치에서의 읽기는 바이트를 반환하지 않는다.

 

EOF를 훨씬 넘어서 쓰면 많은 블록들이 0이 될 수 있다.

일부 파일 시스템은 암시적으로 제로화된 블록에 실제 데이터 블록을 할당하고 쓴다.

다른 파일 시스템은 블록이 명시적으로 작성될 때까지 이러한 블록을 할당하지 않는다.

후자의 파일 시스템은 "sparse files"을 지원한다. 이러한 할당 전략 중의 하나를 채택할 수 있다.