6/28 PintOS Project4 File System(3)

Indexed and Extensible Files

오늘은 File System의 첫 부분 Indexed and Extensible Files에 대한 구현을 해봤습니다

기본 파일 시스템은 파일을 단일 익스텐트로 할당하기 때문에 외부 조각화 에 취약 하다 . 온디스크 inode 구조를 수정하여 이 문제를 제거하십시오.

실제로 이는 직접, 간접 및 이중 간접 블록이 있는 인덱스 구조를 사용하는 것을 의미할 수 있습니다. 이전 학기에 대부분의 학생들은 다단계 인덱싱이 있는 Berkeley UNIX FFS 로 배운 것과 같은 것을 채택했습니다 . 그러나 귀하의 삶을 더 쉽게 만들기 위해 FAT라는 더 쉬운 방법으로 구현합니다. 주어진 스켈레톤 코드로 FAT를 구현해야 합니다. 귀하의 코드에는 다단계 인덱싱(강의의 FFS)을 위한 코드가 포함되어서는 안 됩니다. 파일 성장 부분은 0점 처리됩니다.

참고: 파일 시스템 파티션이 8MB보다 크지 않을 것이라고 가정할 수 있습니다. 파티션만큼 큰 파일을 지원해야 합니다(메타데이터 제외). 각 inode는 하나의 디스크 섹터에 저장되어 포함될 수 있는 블록 포인터의 수를 제한합니다.

설명은 Git Book을 가져왔습니다

FAT(File Allocation Table)로 대용량 파일 인덱싱

경고: 이 문서는 당신이 강의를 통해 일반 파일 시스템과 FAT의 기본 원리를 이미 이해했다고 가정합니다. 그렇지 않다면 강의 노트로 돌아가서 파일 시스템과 FAT가 무엇인지 이해하십시오.

이전 프로젝트에 사용했던 기본 파일 시스템에서 파일은 여러 디스크 섹터에 연속적인 단일 청크로 저장되었습니다. 클러스터 (청크)는 하나 이상의 연속 디스크 섹터를 포함할 수 있으므로 연속 청크를 클러스터라고 부르겠습니다 . 이러한 관점에서 기본 파일 시스템의 클러스터 크기는 클러스터에 저장된 파일의 크기와 동일했습니다.

외부 조각화를 완화하기 위해 클러스터 크기를 줄일 수 있습니다(가상 메모리의 페이지 크기를 기억하십시오). 단순화를 위해 스켈레톤 코드에서 클러스터의 섹터 수를 1. 이와 같이 더 작은 클러스터를 사용하면 클러스터가 전체 파일을 저장하기에 충분하지 않을 수 있습니다. 이 경우 파일에 대해 여러 클러스터가 필요하므로 inode의 파일에 대한 클러스터를 인덱싱할 데이터 구조가 필요합니다. 가장 쉬운 방법 중 하나는 연결된 목록(일명 체인) 을 사용하는 것입니다.). inode는 파일의 첫 번째 블록의 섹터 번호를 포함할 수 있으며 첫 번째 블록은 두 번째 블록의 섹터 번호를 포함할 수 있습니다. 그러나 이 순진한 접근 방식은 파일의 모든 블록을 읽어야 하기 때문에 너무 느립니다. 실제로 필요한 것은 마지막 블록뿐이지만 파일의 모든 블록을 읽어야 합니다. 이를 극복하기 위해 FAT(파일 할당 테이블)는 블록 자체가 아닌 고정된 크기의 파일 할당 테이블에 블록의 연결성을 부여합니다. FAT는 실제 데이터가 아닌 연결 값만 담고 있기 때문에 DRAM에 캐싱할 수 있을 정도로 크기가 작습니다. 결과적으로 테이블에서 해당 항목을 읽을 수 있습니다.

에 제공된 스켈레톤 코드를 사용하여 inode 인덱싱을 구현합니다 filesys/fat.c. 이 섹션에서는 do에 이미 구현된 기능 fat.c과 구현해야 하는 기능에 대해 간략하게 설명합니다.

먼저 , , , , 의 6가지 기능은 fat.c부팅 fat_init()시 fat_open()디스크 fat_close()를 초기화 및 포맷하므로 수정할 필요가 없습니다 fat_create(). fat_boot_create()그러나 작성해야 하며 fat_fs_init()그들이 하는 일을 간략하게 이해하면 도움이 될 수 있습니다.

fat_fs_init

FAT 파일 시스템을 초기화합니다. fat_length의 data_start필드를 초기화해야 합니다 fat_fs. fat_length파일 시스템에 있는 클러스터 수를 저장하고 data_start파일 저장을 시작할 수 있는 섹터를 저장합니다. 에 저장된 일부 값을 이용할 수 있습니다 fat_fs->bs. 또한 이 함수에서 다른 유용한 데이터를 초기화할 수도 있습니다.

void
fat_fs_init (void) {
	/* TODO: Your code goes here. */
	fat_fs->fat_length = fat_fs->bs.fat_sectors / SECTORS_PER_CLUSTER;
	fat_fs->data_start = fat_fs->bs.fat_start + fat_fs->bs.fat_sectors;
}

위의 코드는 fat_fs_init 함수입니다.

1. 함수 시그니처:
   fat_fs_init 함수는 FAT 파일 시스템을 초기화하는 역할을 합니다.

2. 함수 동작:

   1. FAT 길이 설정: fat_fs 구조체의 fat_length 멤버를 초기화합니다. 이 값을 FAT 테이블의 섹터 수를 클러스터 단위로 나눈 값으로 설정합니다. FAT 테이블은 파일 시스템에서 파일과 디렉터리의 메타데이터와 클러스터 간의 매핑 정보를 저장하는 테이블입니다. 따라서 fat_length는 FAT 테이블의 길이를 클러스터 단위로 표현한 값입니다.

   2. 데이터 시작 위치 설정: fat_fs 구조체의 data_start 멤버를 초기화합니다. 이 값을 FAT 테이블의 마지막 섹터 위치에 1을 더한 값으로 설정합니다. FAT 테이블 다음 섹터부터 데이터 영역이 시작되기 때문에 data_start는 FAT 테이블의 마지막 섹터 다음 위치를 가리킵니다.

위의 코드는 FAT 파일 시스템 구조체(fat_fs)에 필요한 정보를 설정하는 단계로, 파일 시스템 초기화 과정 중 일부입니다. 이 정보는 파일 시스템의 구조와 클러스터 및 데이터 영역의 위치 등을 나타내며, 파일 시스템의 기능을 제공하기 위해 필요한 중요한 매개변수들입니다.

fat_create_chain

clst(클러스터 인덱싱 번호) 에 지정된 클러스터 뒤에 클러스터를 추가하여 체인을 확장합니다 . 0과 같으면 clst새 체인을 만듭니다. 새로 할당된 클러스터의 클러스터 번호를 반환합니다.

cluster_t
fat_create_chain (cluster_t clst) {
	/* TODO: Your code goes here. */
	// 빈 클러스터 찾기
	cluster_t i;
	for (i = 2; i <= fat_fs->fat_length; i++)
	{
		if (fat_get(i) == 0)
			break;
	}
	if (i == fat_fs->fat_length) // 빈 클러스터가 없으면 0 반환
		return 0;

	// 위에서 찾은 빈 클러스터를 새 클러스터로 추가
	fat_put(i, EOChain);

	// clst가 0인 경우, 새 클러스터 추가만 하고 종료
	if (clst == 0)
		return i;

	// clst가 0이 아닌 경우, 최종 클러스터 <-> i 연결
	cluster_t cur_clst = clst;
	// 현재 클러스터와 연결된 최종 클러스터 탐색 (가장 마지막 클러스터와 i를 연결)
	while (true)
	{
		if (fat_get(cur_clst) == EOChain)
		{
			fat_put(cur_clst, i);
			break;
		}
		cur_clst = fat_get(cur_clst);
	}

	return i;
}

위의 코드는 fat_create_chain 함수입니다.

1. 함수 시그니처:
   fat_create_chain 함수는 FAT 파일 시스템에서 연결 리스트 형태로 클러스터 체인을 생성하는 역할을 합니다.

2. 함수 동작:

   1. 빈 클러스터 찾기: 빈 클러스터를 찾기 위해 for 루프를 사용합니다. i를 2부터 시작하여 FAT 테이블의 길이(fat_length)까지 반복하면서 FAT 테이블의 엔트리를 확인합니다. FAT 테이블의 엔트리 값이 0인 경우, 해당 클러스터는 사용되지 않고 비어있음을 의미합니다. 따라서 빈 클러스터를 찾으면 루프를 종료하고 i의 값을 유지합니다.

   2. 빈 클러스터 추가: 찾은 빈 클러스터(i)를 FAT 테이블에 추가합니다. 이를 위해 fat_put(i, EOChain) 함수를 사용하여 i 위치에 연결 리스트의 끝을 나타내는 값(EOChain)을 설정합니다. 이로써 i는 새로운 클러스터가 되고, 해당 클러스터는 연결 리스트의 마지막에 추가되었음을 나타냅니다.

   3. clst가 0인 경우: 만약 clst 값이 0이라면, 새로운 클러스터(i)를 추가한 후 함수를 종료합니다. 이는 단순히 새 클러스터를 생성하고 종료하는 상황입니다.

   4. clst가 0이 아닌 경우: clst 값이 0이 아닌 경우, 기존 클러스터와 새 클러스터를 연결합니다. 현재 클러스터(clst)와 연결된 최종 클러스터를 탐색하여 가장 마지막 클러스터와 i를 연결합니다. 이를 위해 while 루프를 사용하며, 현재 클러스터를 FAT 테이블에서 읽어와서 확인합니다. 만약 현재 클러스터의 FAT 엔트리 값이 연결 리스트의 끝(EOChain)인 경우, 해당 엔트리를 i로 설정하여 cur_clst와 i를 연결합니다. 그 후 루프를 종료합니다.

   5. 결과 반환: 최종적으로 생성된 새 클러스터(i)의 값을 반환합니다.

위의 코드는 파일 시스템에서 파일을 저장하기 위해 새로운 클러스터 체인을 생성하는 함수입니다. 이 함수는 파일 시스템의 공간 할당을 담당하며, 새로운 데이터를 저장하기 위해 필요한 클러스터를 동적으로 할당하고 연결 리스트 형태로 관리합니다.