기본 파일 시스템은 파일을 단일한 범위(연속 할당한다는 의미인듯)로 파일을 할당하는데, 이는 외부 단편화에 취약하다. 즉, 이는 n개의 블록이 가용 상태임에도 n개 블록을 점유해야 하는 파일이 할당되지 못한다는 것을 의미한다.(외부 단편화!) on-disk inode 구조를 수정해 이 문제를 제거해라.

실제로, 이것은 아마 직접/간접/이중 간접 인덱스 구조를 사용하라는 의미다. 지난 학기에, 대부분 학생은 멀티 레벨 인덱싱을 사용하는 Berkeley UNIX FFS로 배운 것과 같은 것을 적용했다. 하지만, 우리의 삶을 더 쉽게 하기 위해, 더 쉬운 방식으로 구현하도록 만든다. 그것이 FAT이다. 우리는 주어진 스켈레톤 코드로 반드시 FAT을 구현해야 한다. 우리의 코드는 절대 multi-level indexing에 관한 어떤 코드도 포함해서는 안된다 (ex-FFS).

주의: 우리는 파일 시스템 파티션이 8MB보다 커져서는 안될 것임을 유추할 것이다. 우리는 파티션만큼 큰 파일을 지원해야 한다(단, 메타데이터는 제외). 각 inode는 하나의 디스크 섹터에 저장되어 포함할 수 있는 블록 포인터의 수를 제한한다.

Indexing large files with FAT(FIle Allocation Table)

이전 프로젝트까지 우리가 사용했던 기본 파일 시스템에서, 파일은 연속적인 단일 청크 형태로 여러 디스크 섹터에 걸쳐 저장되었다. 연속적인 청크를 cluster라고 하자. 왜냐면 하나의 클러스터는 하나 혹은 그 이상의 연속적인 디스크 섹터를 포함할 수 있기 때문이다. 이 관점에서, 기본 파일 시스템에서 클러스터의 사이즈는 클러스터에 저장된 파일의 크기와 동일하다.

외부 단편화를 완화하기 위해, 우리는 클러스터 사이즈를 축소할 수 있다. (가상 메모리에서 페이지 사이즈를 생각해봐라.) 간단히, 우리의 스켈레톤 코드에서, 우리는 클러스터 내에 섹터 수를 1로 고정했다. 우리가 더 작은 클러스터를 사용할 때, 클러스터는 전체 파일을 저장하기 충분치 않을 지도 모른다. 이 경우, 우리는 하나의 파일을 위해 여러 클러스터가 필요한데, 그래서 우리는 inode에 있는 파일을 위해 클러스터를 인덱싱할 수 있는 자료구조가 필요하다. 한 가지 쉬운 방법은 linked-list를 사용하는 것이다. inode는 파일의 첫번째 블록의 섹터 번호를 담는다. 그리고 첫번째 블록은 두 번째 블록의 섹터 번호를 담을 수 있다. 하지만 이 나이브한 접근방식은 너무 느린데, 왜냐면 비록 우리가 진짜로 필요로 하는 블록이 마지막 블록일지라도 우리는 파일의 모든 블록을 읽어야만 하기 때문이다. 이를 극복하기 위해, FAT(File Allocation Table) 방식에서는 각 블록에 다음 블록 번호를 넣는 방식이 아니라 각 블록의 연결을 고정된 사이즈의 파일 할당 테이블에 넣는다. FAT는 실제 데이터보다 연결 값만 담고 있기 때문에, DRAM 내에 캐싱되기 충분히 작은 사이즈다. 결과적으로, 우리는 단지 이 테이블에서 관련 엔트리를 읽기만 하면 된다.

우리는 filesys/fat.c에 주어진 스켈레톤 코드로 inode indexing을 구현할 것이다. 이 섹션에서는 fat.c 에서 이미 구현되어 제공되는 함수를 간단히 기술한다. 그리고 우리가 구현해야 하는 함수 역시.

첫째로, fat.c에 있는 6개 함수 (i.e. fat_init(), fat_open(), fat_close(), fat_create(), and fat_boot_create())는 부팅 시에 디스크를 초기화하고 포맷한다. 따라서 우리는 이들을 수정할 필요가 없다. 하지만, 우리는 fat_fs_init()을 작성할 필요가 있을 것이다. 그리고 이들이 왜 무엇을 하는지를 이해하면 도움이 될 것이다.

cluster_t fat_fs_init (void);

FAT 파일 시스템4을 초기화한다. 우리는 fat_length와 fat_fs의 data_start 필드를 초기화할 필요가 있다. fat_length는 파일 시스템에 얼마나 클러스터가 많은지를 저장하고 data_start는 우리가 파일 저장을 시작할 수 있는 섹터가 어디인지를 저장한다. 우리는 fat_fs→bs에 저장된 몇가지 값을 사용하기를 원할 것이다. 또한, 우리는 이 함수에서 몇가지 다른 유용한 데이터를 초기화하기를 원할 것이다.

cluster_t fat_create_chain (cluster_t clst);