지금까지의 핀토스 파일 시스템은 파일을 한꺼번에 하나의 chunk로 할당하기 때문에 외부 단편화에 취약하다. On-disk inode 구조를 수정하여 이 문제를 해결해 본다.
직접, 간접, 이중 간접 포인터를 사용하는 멀티 레벨 인덱스를 구현한다. 이 때 파일 시스템은 FFS보다는 쉬운 FAT을 구현한다. 스켈레톤 코드는 만들어져 있으니, 코드의 빈 자리를 채워나가본다.
각각의 아이노드들은 각각 하나의 디스크 섹터에 저장된다. 크기가 한정되어 있으므로, 아이노드 안에 있는 데이터 블록 포인터들의 개수 역시 한정된다.
지금까지의 핀토스 파일 시스템은 파일을 한꺼번에 하나의 chunk로 할당한다. 디스크에서 할당되는 데이터의 크기 단위를 클러스터라고 하는데, 현재까지는 하나의 클러스터 크기가 파일 크기와 같다. 파일의 크기가 디스크 섹터 하나보다 큰 경우(512byte 이상), 당연히 파일 클러스터는 여러 디스크 섹터에 나뉘어 저장된다.
외부 단편화를 줄이기 위해 클러스터의 크기를 줄일 것이다. 일단 스켈레톤 코드에서는 클러스터의 크기가 디스크 섹터 하나의 크기와 같다고 해 놓았다. 파일의 크기가 큰 경우 당연히 한 파일을 저장하기 위해서는 여러 클러스터가 필요할 것이기 때문에, 파일의 아이노드에 각각의 클러스터의 정보를 담을 수 있는 자료구조가 필요하다.
간단하게는 링크드 리스트로 이를 구현할 수 있겠다. 아이노드는 링크드 리스트의 첫 블록(섹터)의 번호만 저장해 놓는다. 그리고 각각의 데이터 블록(클러스터)에 다음 블록의 번호를 저장해 놓는다. 이런 방법은 파일의 모든 블록을 읽어야 한다. 따라서 Random Access가 쉽지 않다는 것. 따라서 데이터 블록의 상태 및 next 블록의 번호를 저장해 놓는 테이블을 만든다. 이를 **FAT(File Allocation Table)**이라고 한다. FAT에는 실제 데이터가 아닌 연결 값만 포함되기 때문에 크기가 작아 DRAM에 캐시할 수 있다.
filesys/fat.c의 아이노드 인덱싱을 구현한다.