우리 핀토스의 기본 파일 시스템은 파일을 한 덩어리로 할당해서 외부 단편화에 취약하므로, n개의 블록이 가용함에도 n개의 블록 파일이 할당되지 못할 수 있다. 고로 디스크의 inode 구조를 수정해서 이 문제를 해결하자.
현재 inode 구조는 이러하다.
/* In-memory inode. */
struct inode {
struct list_elem elem; /* inode list 요소 */
disk_sector_t sector; /* 디스크 위치의 섹터 번호 */
int open_cnt; /* opener 수 */
bool removed; /* 삭제하면 true, 아니면 false */
int deny_write_cnt; /* 0: writes ok, >0: deny writes. */
struct inode_disk data; /* Inode content */
};실제로 직접/간접 혹은 이중 간접 블록을 사용하는 인덱스 구조를 사용해야한다. multi-level indexing을 가진 FFS도 있으나 우리는 FAT을 사용해서 구현하면 된다. 주어진 핀토스 스켈레톤 코드를 이용하여서 FAT를 구현해보자. 코드에 multi-level indexing (FFS)가 있으면 file growth에서 0점 주의!
파일 시스템 파티션은 8MB를 넘지 않으니 파티션 크기만큼의 파일을 지원해야 한다. 각 inode는 하나의 디스크 섹터에 저장되어 포함할 수 있는 블럭 포인터의 수를 제한한다.
💡디스크 섹터
섹터는 하드디스크의 물리적 최소 단위여서 파일은 모두 이 섹터 공간에서 읽고 쓰고 삭제한다. 정도로 알면 될 거 같다.
💡파티션
FAT를 사용한 대용량 파일 인덱싱(파일 할당 테이블)
이전 프로젝트에서의 기본 파일 시스템에서는, 파일이 여러 디스크 섹터에 걸친 연속적 하나의 청크로 저장된다.
클러스터는 하나 이상의 연속적 디스크 섹터를 포함하므로, 연속적 청크를 클러스터라 부르자. 기본 파일 시스템의 클러스터 크기는 클러스터에 저장된 파일의 크기와 동일하다.
💡클러스터란
포스팅 맨 위 그림에서의 섹터가 물리적 최소 단위라면, 클러스터는 논리적 최소 단위이다. 블록(청크) = 클러스터. 간단하게, 섹터가 그릇이라면 클러스터는 그릇들을 모아 옮기는 쟁반이라 생각하니 한결 쉬웠다.
외부 단편화를 완화하려면 클러스터의 크기를 줄일 수 있다. 우리 핀토스는 단순하게 클러스터의 섹터 수를 1개로 고정했다. 이 경우 한 파일에 대해 여러 클러스터가 필요하므로, inode 안에 파일들의 클러스터 인덱스를 위한 자료구조가 필요하다.
linked-list 가장 쉬운 방법이지만, 마지막 블럭을 찾기에 매우 느린 방법이기에 FAT는 고정 크기의 FAT에 블럭의 연결을 넣는다. FAT는 데이터가 아닌 연결 값만 포함하기에, DRAM에 캐시할 수 있을 정도로 크기가 작다. 결과적으로, 우리는 테이블에서 해당 항목을 읽을 수 있으므로 FAT로 고고.
fat.c 안 5개 함수는 간단히 이해하는 것이 구현에 도움이 되었다.
우리조의 경험상으로는 구현순서를 아래와 같이 하는 것이 좋았다. 깃북 순서대로 진행하였다가 fat_put, fat_get, cluster_to_sector 구현 후 다시 위로 돌아와 fat_create_chain과 fat_remove_chain을 바꾸는 불상사가 생겼다.🤪
fat_put
void
fat_put (cluster_t clst, cluster_t val) {
/* 클러스터 번호 clst가 가리키는 FAT 엔트리를 val로 업데이트한다.
FAT의 각 엔트리가 체인의 다음 클러스터를 가리키므로, (존재하는 경우; 그렇지 않다면 EOChain)
이는 연결을 업데이트하는데 사용할 수 있다. */
unsigned int *fat= fat_fs->fat;
fat[clst-1] = val;
}fat_get
cluster_t
fat_get (cluster_t clst) {
unsigned int *fat= fat_fs->fat;
return fat[clst-1];
}주어지는 클러스터 clst 가 가리키는 클러스터 번호를 반환한다.
cluster_to_sector
disk_sector_t
cluster_to_sector (cluster_t clst) {
/* 클러스터 번호 clst를 해당하는 섹터 번호로 변환하고, 반환한다.*/
return fat_fs->bs.fat_sectors + clst;
}alarm_clock test_case를 뽑아보았을 때 fat_sectors는 157이 나왔고 + clst를 한다면 해당 찐 섹터 번호가 나올 것이다.
sector_to_cluster
cluster_t
sector_to_cluster(disk_sector_t sector){
/* 클러스터 번호 clst를 해당하는 섹터 번호로 변환하고, 반환합니다.*/
// 159 - 157 = 2
return sector - fat_fs->bs.fat_sectors;
}추가적으로 cluster_to_sector 함수와 반대로 sector를 cluster로 변환하는 함수를 구현해주었다.
fat_fs_init
void
fat_fs_init (void){
fat_fs->fat_length = fat_fs->fat_length = fat_fs->bs.total_sectors;
fat_fs->data_start = fat_fs->bs.fat_start + fat_fs->bs.fat_sectors;
}FAT 파일 시스템을 초기화하는 함수다.
fat_fs의 fat_length와 data_start 필드를 초기화해야 한다.
fat_length는 파일 시스템의 클러스터 수를 저장하고, data_start는 파일 저장을 시작할 수 있는 섹터를 저장한다. fat_fs→bs에 저장된 일부 값을 이용할 수 있고 이 함수에서 다른 유용한 데이터들을 초기화할 수도 있다.
fat_create_chain
cluster_t
fat_create_chain (cluster_t clst) {
/* clst(클러스터 인덱싱 번호)로 특정된 클러스터의 뒤에 클러스터를 추가하여 체인을 확장한다.
clst가 0이면 새 체인을 만든다.
새로 할당된 클러스터의 번호를 반환한다. */
for(cluster_t i=1; i <= (fat_fs->bs.fat_sectors*128); i++){
cluster_t c = fat_get(i);
if(c== 0){
fat_put(i, EOChain);
if (c !=0)
fat_put(clst, i);
return i;
}
}
return 0;
}clst(클러스터 인덱싱 번호)로 특정된 클러스터의 뒤에 클러스터를 추가하여 체인을 확장한다.
clst가 0이면 새 체인을 만들고 새로 할당된 클러스터의 번호를 반환한다.
fat_remove_chain
void
fat_remove_chain (cluster_t clst, cluster_t pclst) {
/* clst에서 시작하여, 체인에서 클러스터를 제거(0으로 바꾼다)한다.
pclst는 체인에서 clst의 바로 뒤에 있는 클러스터여야 하고,
만약 clst가 체인의 첫 요소라면, pclst는 0이 되어야 합니다. */
cluster_t i =clst;
cluster_t prev_i;
while(fat_get(i) != EOChain){
prev_i = i;
i = fat_get(i);
fat_put(prev_i, 0);
}
fat_put(i, 0);
if(pclst != 0)
fat_put(pclst, EOChain); // pclst의 값을 -1로 만듦
}makefile
# -*- makefile -*-
os.dsk: DEFINES = -DUSERPROG -DFILESYS -DEFILESYS
KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys
KERNEL_SUBDIRS += tests/threads tests/threads/mlfqs
TEST_SUBDIRS = tests/threads tests/userprog tests/filesys/base tests/filesys/extended
GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.no-vm
# Uncomment the lines below to enable VM.
os.dsk: DEFINES += -DVM
KERNEL_SUBDIRS += vm
TEST_SUBDIRS += tests/vm tests/filesys/buffer-cache
GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm아래 4줄 주석해제 후 돌리면 test case를 돌릴 수 있다. extra 구현을 하지 않는다면 아래서 2번째줄은 다시 주석! 패기로 주석을 전부 해제했더니 위 구현 후 175 of 193 tests failed!
free_map
fat함수 구현 후 발견한 free_map 관련해서 팀원들과 써야하나 하는 고민을 많이 했다. 이전까지 우리가 그려놓은 fat 세계관을 다시 뭉개고 free_map으로 free sector를 관리하는 건가에 대한 생각이었다. 하지만 free_map_init등 free_map을 사용하는 함수가 현재 makefile 통해 켜진 #ifdef EFILESYS 에서는 사용하지 않기에 결국 사용하지 않기로 결정 땅땅땅.
참고. [OS] Lec 11-2. File System Overview / 운영체제 강의
오늘의 나는
오전 체단실이 안열리는 건 처음 알아서ㅠㅠ 운동장 달렸는데 첫눈 밟는게 존잼 ><
근데 눈이 점점 관리가 안되는게 맞나.. 다행히 손목은 괜찮지만 목도 안괜찮다 ^^
동기들이랑 같이 달려도 재밌었겠다!
💡깨알 aws 팁
aws 리로딩 시간이 길고 time out이 계속 떠서 홈페이지가서 ec2 재부팅을 했는데 ec2가 사라졌다 잘못해서 종료를 눌렀나보다. 처음부터 다시 깔고 진행하는데도 time out으로 우분투 접속이 안되서 이런저런 방법을 시도했는데 알고보니 nw문제였다. 헛헛하다. 핫스팟으로 바꾸니 해결되는 문제여서 이런 문제를 겪는 사람은 나에서 끝나길 바라며 공유한다.
