[Pintos] - File System - (Indexed and Extensible Files)

Junyeong Fred Kim·2022년 2월 2일
0

운영체제

목록 보기
25/27

기본 파일 시스템은 외부 단편화에 취약한 single extent로 파일을 할당한다. 즉 n-block 파일은 n개의 블록이 할당 가능 상태일지라도 할당되지 않는다(외부 단편화). on-disk inode 구조체를 수정하여 이 문제를 제거해야한다.

on-disk inode 구조체는 filesys/inode.c에 있다.

/* On-disk inode.
 * Must be exactly DISK_SECTOR_SIZE bytes long. */
struct inode_disk {
	disk_sector_t start;                /* First data sector. */
	off_t length;                       /* File size in bytes. */
	unsigned magic;                     /* Magic number. */
	uint32_t unused[125];               /* Not used. */
};

여기서 start 멤버는 시작 블록번호를 뜻하고,
length는 할당된 블록길이(byte)로 파일 생성 시, 디스크 상에 연속된 블록을 할당 받는다.

You must implement FAT with given skeleton code.

Indexing large files with FAT (File Allocation Table)

Warning:

  • 이 문서는 강의에서 일반 파일 시스템 및 FAT의 기본 원리를 이미 이해했다고 가정한다.
  • 그렇지 않다면 lecture note로 돌아가서 파일 시스템과 FAT가 무엇인지 이해하고 와라.

이전 프로젝트에 사용한 기본 파일 시스템에서는 파일이 여러 디스크 섹터에 걸쳐 연속적인 single chuck로 저장되었다. cluster(chunk)에 하나 이상의 contiguous disk sectors가 포함될 수 있으므로 contiguous chuck as cluster라고 부른다. 이 관점에서 기본 파일 시스템의 cluster size는 cluster에 저장된 file size와 같다.

  • external fragmentation을 migrate하기 위해 cluster 크기를 축소할 수 있다.
  • 단순화를 위해 skeleton code에서 cluster의 sectors 수를 1로 고정한다.
    • 하지만 이렇게 작은 cluster를 사용하게되면, cluster가 전체 파일을 저장하기 충분하지 않을 수 있다.
    • 이 경우 파일 하나에 여러 개의 클러스터가 필요하기 때문에 inode에 있는 파일의 cluster를 인덱싱하기 위한 자료구조가 필요하다.
  • 가장 쉬운 방법 중 하나는 linked-list를 사용하는 것
    • inode는 파일의 첫 번째 블록의 섹터 번호를 포함할 수 있으며 첫 번째 블록은 두 번째 블록의 섹터 번호를 포함할 수 있다.

하지만, 이런 방법은 파일의 모든 블록을 읽게 되어 속도가 느리고, 직접 접근에도 비효율 적이다. 또한 포인터 저장을 위한 공간도 필요하기 때문에 공간 활용에 비효율적이다.

이를 해결하기 위해 FAT(File Allocation Table)를 사용한다. FAT에는 실제 데이터가 아닌 연결 값만 포함되기 때문에 크기가 작아 DRAM에 캐싱할 수 있다.

filesys/fat.c에 있는 skeleton code에 inode indexing을 구현해라.

filesys/fat.cfat_init(), fat_open(), fat_close(), fat_create(), fat_boot_create()들은 수정할 필요 없고, fat_fs_init()만 수정해라.


fat_fs_init() 함수는 FAT 파일 시스템을 초기화하는 함수이다. fat_fsfat_lengthdata_start필드를 초기화해야한다.

void fat_fs_init (void) {
	/* TODO: Your code goes here. */
}
struct fat_fs {
	struct fat_boot bs;
    unsigned int *fat;
    unsigned int fat_length;
    disk_sector_t data_start;
    cluster_t last_clst;
    struct lock write_lock;
}

FAT의 구조

  • 예약지역: 부트 블록, 파일시스템 정보 블록
    • 부트 블록: 부팅관련 정보
    • 파일 시스템 정보 블록: 운영체제에 알려줄 파일 시스템 정보들
  • FAT 지역: Meta Area - 파일이 얼마나 클러스터에 할당되어있는지
  • DATA 지역: 데이터가 저장되어있는 공간

fat_fs_init() 구현

void fat_fs_init (void) {
	/* TODO: Your code goes here. */
	// FAT byte 크기
    // FAT의 섹터 수 X 512bytes / cluster 당 sector 수
    fat_fs->fat_length = fat_fs->bs.fat_sectors * DISK_SECTOR_SIZE / (sizeof(cluster_t) * SECTORS_PER_CLUSTER);

	//! DATA sector가 시작하는 지점
    fat_fs->data_start = fat_fs->bs.fat_start + fat_fs->bs.fat_sectors;
}

fat_create_chain() 구현

이 함수는 clst(클러스터 인덱싱 번호)에 지정된 클러스터 뒤에 클로스터를 추가하여 체인을 확장한다. 만약 clst가 0이라면, 새로운 체인을 생성한다. 새로 할당된 클러스터의 클러스터 번호를 리턴하면 된다.

/* Add a cluster to the chain.
 * If CLST is 0, start a new chain.
 * Returns 0 if fails to allocate a new cluster. */
cluster_t
fat_create_chain (cluster_t clst) {
	/* TODO: Your code goes here. */
	cluster_t new = get_free_cluster();
	if (new == -1) {
		return 0;
	}
 
	if(clst != 0) {
		fat_put(clst, new);
	}
 
	return new;
}

fat_remove_chain() 구현

  • clst에서부터 이어지는 clst들을 모두 비운다.
  • pclst의 값을 EOChain으로 설정
    • 이 때, pclst가 0인 경우, chain이 모두 사라진 것이므로 처리해줄 필요 없음
/* Remove the chain of clusters starting from CLST.
 * If PCLST is 0, assume CLST as the start of the chain. */
void
fat_remove_chain (cluster_t clst, cluster_t pclst) {
	/* TODO: Your code goes here. */
	if (pclst != 0)
	{
		fat_put(pclst, EOChain);
	}
 
	cluster_t start = fat_fs->data_start;
	cluster_t start_next = fat_get(start);
 
	cluster_t cur = clst;
	cluster_t next = fat_get(cur);
 
	fat_put(cur,start_next);
	fat_put(start, cur);
	fat_fs->free_blocks += 1;
 
	while (next != EOChain)
	{
		cur = fat_get(next);
		start_next = fat_get(start);
		fat_put(next, start_next);
		fat_put(start, next);
		fat_fs->free_blocks += 1;
	}
}
profile
기억보다 기록

0개의 댓글