1. Introduction

    프로젝트 2,3에서는 미리 만들어 두었던 파일 시스템을 별 걱정없이 사용하였다. 이번 프로젝트에서는 파일 시스템을 개선시킬 것이다. 주로 filesys 디렉토리에 있는 파일들을 수정할 것이다.

    프로젝트 2나 3 위에 빌드를 할 것이다. 프로젝트 2나 3가 모두 정상 작동해야한다. 그리고 vm이 정상작동하도록 filesys/Make.vars를 수정해야 한다.

    아래는 filesys 디렉토리에 있는 새로운 파일들에 대한 설명이다.

    핀토스는 Unix 와 같은 파일 시스템을 사용한다. 그래서 creat, open, close, read, write, lsee unlink 에 대하여 알아야한다. 비슷한 콜들이 있지만 동일하지는 않다. 파일 시스템음 이러한 시스템 콜들을 디스크 동작으로 변환한다.

    모든 기본 함수들은 위의 코드들에 있다. 그래서 현재도 파일 시스템을 이용할 수 있다. 하지만 우리가 극복해야 할 한계점이 있다. 대부분의 작업은 filesys에서 이루어지며 이전에 했던 작업과 연관이 있다.

    Testing File System Persistence

    지금까지는 각 테스트가 Pintos를 한번만 호출 했다. 하지만 파일 시스템의 중요한 목적은 다시 부팅 했을 때도 데이터의 신뢰성이 확보 되어야 한다는 것이다. 그래서 파일 시스템 관련 테스트들은 핀토스를 두번 호출 한다. 두번째 실행에서 모든 파일들과 디렉토리들을 한 개의 파일로 합친다. 그리고 합친 파일을 유닉스 파일 시스템에 복사한다.

    두 번째 실행에서 복사된 파일의 일치여부로 점수를 매긴다. 즉 tar을 제대로 사용할 수 없다면 파일시스템 관련 테스트를 통과 할 수 없다. tar 프로그램은 확장 가능한 파일과 하위 디렉토리를 지원해야한다. 그러고 나면 make check 시 tar 관련 에러를 무시할 수 있다.

    예상 할 수 있듯이, 파일 시스템 내용을 복사하는 파일 포맷은 유늑시 표준 tar 포맷이다. 테스트를 위해 tar 프로그램을 사용 할 수 있다. 테스트를 위한 tar 파일 이름은 t.tar 이다.

  2. Indexed and Extensible Files

    기본적인 파일시스템은 파일을 단일 범위로 할당한다. 그래서 외부 단편화에 취약하다. 이 말은 n개의 블락들이 할당되어 있지 않아도 n개 블락이 필요한 파일을 할당 할 수 없는 경우가 발생한다. 아이노드 구조를 변경하여 이러한 문제를 해결해야한다.

    이를 통해 실제로는 직접 참조나 간접 참조 또는 이중 참조 구조의 인덱스 구조를 사용할 것이라고 생각 해볼 수 있다. 전 학기들에서 대부분의 학생들은 다단계 인덱싱 구조를 사용했다. 하지만 편안한 핀토스 구현을 위해 FAT 사용을 추천한다. 우리는 반드시 FAT를 주어진 스켈레톤 코드를 통해 구현해야한다. 다단계 코드는 절대 사용하지 말아라.(왜?)

    NOTE: 파일시스템 파티션이 8MB가 넘지 않을 것이라 추측 할 수 있다. 파일 시스템은 파일 파티션 만큼 큰 파일도 지원해야한다. 각 아이노드는 하나의 디스크 섹터에 저장되어 지정 할 수 있는 블락 포인터의 수는 제한적이다.

    Indexing large files with FAT (File Allocation Table)

    이전 프로젝트들에서 사용했던 파일 시스템에서 파일은 여러 디스크 섹터위에 한 덩어리로 저장되었다. 한 덩어리를 cluster라고 부르겠다. 그 이유는 하나의 클러스터는 여러개의 디스크 섹터를 포함하기 때문이다. 이러한 관점에서 기본적인 파일 시스템에서 클러스터의 사이즈는 클러스터에 저장되는 파일의 크기와 동일하다.

    외부 단편화를 개선하기 위해 클러스터의 사이즈를 줄여야 한다. 간단하게 클러스터 1개당 섹터 수를 1로 수정하면 된다. 하지만 이런 경우에는 클러스터의 수가 부족 할 수 있다. 그래서 여러개의 클러스터를 이용하려면 아이노드에서 클러스터들을 연결할 자료구조가 필요하다. 가장 쉬운 방법은 링크드 리스트를 이용하는 것이다. 아이노드에 파일의 첫번째 블럭의 섹터 번호를 저장할 수 있다. 그리고 첫번째 블럭에는 두번째 블럭의 섹터 번호를 저장한다. 그러나 이 방법은 매우 느리다. 한 블럭을 찾기 위해서는 모든 블럭을 순회해야하기 때문이다. 이를 개선하기위해 블럭 안에 주소를 입력하지 않고 외부에 별도의 테이블을 만든다.(FAT) FAT는 실제 데이터가 아니라 블럭의 주소값을 입력하기 때문에 DRAM에 캐시 할 수 있을 정도로 용량이 적다.

    아이노드 인덱싱을 filesys/fat.c에서 구현한다. 이 섹션에서는 fat.c 가 어떻게 구현되어 있는지, 그리고 어떻게 개선해야 하는지에 대해 다룬다.

    우선 fat.c 에 있는 6가지 함수들은 부팅 시 디스크를 포맷하고 초기화시킨다. 그래서 변경할 필요가 없다. 그러나 fat_fs_init() 은 수정해야 할 것이다.

    cluster_t fat_fs_init (void);

    FAT 파일 시스템을 초기화 한다. fat_fs 영역의 fat_length와 data_start 영역을 초기화 해야한다. fat_length는 파일 시스템에 있는 클러스터들의 수를 저장한다. data_start는 파일을 저장할 수 있는 섹터의 시작점을 저장한다. fat_fs→bs의 값을 수정해야 할 수도 있다. 또한 이 함수에 있는 다른 유용한 데이터를 초기화 해야 할 수도 있다.

    cluster_t fat_create_chain (cluster_t clst);

    클러스터를 추가하여 클러스터 체인을 연장한다. 만약 clst(클러스터 인덱싱 번호)가 0 이면 새로운 체인을 만든다. 새로 할당된 클러스터 번호를 반환한다.

    void fat_remove_chain (cluster_t clst, cluster_t pclst);

    clst 부터 체인에 연결된 클러스터들을 제거한다. pclst는 체인에서 바로 전 클러스터이어야 한다. 즉, 함수 실행 후에 pclst는 갱신된 체인의 마지막 클러스터야 한다. 만약 clst가 첫번째 클러스터라면 pclst는 0이어야 한다.

    void fat_put (cluster_t clst, cluster_t val);

    FAT 엔트리 값을 val로 변경한다. FAT에 있는 각 엔트리는 체인에 있는 다음 클러스터를 가르키기 때문에 이것은 연결을 업데이트 할 수 있다.

    cluster_t fat_get (cluster_t clst);

    clst가 가르키는 클러스터 번호를 반환한다.

    disk_sector_t cluster_to_sector (cluster_t clst);

    clst를 섹터 번호로 변환한다. 그리고 해당 섹터 번호를 반환한다.

    File Growth

    확장 가능한 파일들을 구현한다. 기존 파일 시스템에서는 파일 크기는 파일 생성 후 변경 할 수 없었다. 그러나 현대 파일 시스템에서는 처음 파일 크기는 0 이며 파일에 내용이 작성될때 마다 파일 크기가 증가한다. 우리의 파일시스템도 이러한 특성을 가져야 한다.

    파일 크기가 파일시스템의 크기보다 크지 않는 한 파일 크기의 제한을 미리 설정할 필요는 없다. 이는 루트 디렉토리 파일에도 적용된다. 기존 파일 시스템에서 루트 디렉토리는 16개가 최대였다.

    유저 프로그램들은 EOF(end of file)를 탐색 할 수 있다. 탐색 그 자체로는 파일을 확장 시키지 않는다. 과거 EOF 위치에 내용을 쓰는 것은 파일을 확장시킨다. 그리고 전의 EOF와 작성 시작점 사이는 0으로 채워져야 한다. 전의 EOF에서부터 읽는 것은 바이트를 반환하지 않는다.

    EOF로 부터 멀리 떨어져서 작성하는 것은 많은 블럭을 0으로 만든다. 어떤 파일 시스템들은 묵시적으로 0이 작성된 블럭을 할당시키고 데이터를 입력힌다. 다른 파일 시스템들은 해당 블럭들이 명시적으로 작성될때 까지 할당시키지 않는다. 후자의 파일 시스템의 경우에서 sparse files를 지원한다고 한다. 핀토스의 파일시스템에는 두가지 정책을 모두 적용해야 할 것이다.

  3. Subdirectories and Soft Links

    계층적 경로 공간을 구현한다. 기존 파일시스템에서는 모든 파일들은 하나의 디렉토리에 존재했다. 이를 수정하여 디렉토리 엔트리가 다른 디렉토리나 파일을 가르키게 해야한다.

    디렉토리 또한 파일처럼 크기가 증가할 수 있다는 것을 명심해야한다.

    기본 파일시스템은 파일 이름이 14자 이하여야 했다. 원한다면 이를 수정할 수 있다. 총 파일 경로가 14자가 넘어도 되게끔 수정해야한다.

    각 프로세스에 대해 현재 디렉토리를 분리해야한다. 시작 시 루트를 초기 프로세스의 현재 디렉토리로 설정한다. 한 프로세스가 포크를 통해 다른 프로세스를 시작할 때, 자식 프로세스는 부모의 현재 디렉토리를 상속 받는다. 그 후 두 프로셋의 현재 디렉토리들은 독립적이다. 그래서 자식 프로세스가 부모의 현재 디렉토리를 모두 상속 받으면 서로에게 영향을 주지 않는다.(유닉스 시스템에서 cd 명령어가 외부 프로그램이 아닌 shell built-in인 이유이다.?)

    현재 시스템콜을 수정하여 절대 또는 상대 경로가 사용되어야 한다. 디렉토리 구분자는 ‘/’ 이다. 유닉스에서와 동일하게 “ . “ 과 “ .. ” 를 지원해야 한다.

    open 시스템 콜을 수정하여 디렉토리들을 open하게 해야한다. 현재 시스템 콜들 중에서 close만이 fd를 필요로 한다.

    remove 시스템 콜이 파일들 뿐만 아니라 빈 디렉토리도 삭제 할 수 있어야 한다. 디렉토리안에 하위 디렉토리나 파일이 없으면 삭제되야한다. 물론 루트 디렉토리와 . 과 .. 은 예외이다. 우리는 프로세스에 의해 열려있거나 프로세스가 사용중인 디렉토리의 삭제를 허용할지 말지 결정해야한다. 만약 허용된다면, 파일을 열려는 시도나 삭제된 디렉토리에 파일을 생성하려는 것은 허용될 수 없다. 아래 새로운 시스템콜들을 구현해야한다.

    bool chdir (const char *dir);

    프로세스의 현재 디렉토리를 dir로 변경한다. 성공하면 true, 실패하면 false를 반환한다.

    bool mkdir (const char *dir);

    dir 이름의 새로운 디렉토리를 생성한다. 성공하면 true, 실패하면 false를 반환한다. dir이 이미 존재 하거나 dir 이름을 가진 디렉토리가 존재하면 실패한다. 즉 mkdir(”a/b/c”) 는 /a/b가 이미 존재하고 /a/b/c는 없을 때 성공한다.

    bool readdir (int fd, char *name);

    fd로 부터 디렉토리 엔트리를 읽는다. 성공한다면 name에 null 로 끝나는 파일 이름을 저장한다. name은 READDIR_MAX_LEN + 1의 공간이 있어야 한다. 만약 디렉토리에 엔트리가 없다면 false를 반환한다.

    . 과 ..은 readdir 에 의해 반환되면 안된다. 디렉토리가 열려 있는 도중에 디렉토리가 변경되면 어떤 엔트리 들은 읽어지지 않거나 여러번 읽어야 하는것은 받아 들일수 있다. 그렇지 않으면 각 디렉토리 엔트리는 한번만 읽혀야 한다.

    READDIR_MAX_LEN 는 lib/user/syscall.h 에 정의되어 있다. 파일 이름 제한을 늘리고 싶다면 이전에 정의 되어있는 값을 수정해야한다.

    bool isdir (int fd);

    fd 가 디렉토리를 나타낸다면 true, 일반 파일이라면 false를 반환한다.

    int inumber (int fd);

    fd와 연관된 아이노드 번호를 반환한다. 아이노드 번호는 파일이나 디렉토리와 영구적으로 동일한 것으로 간주한다. 파일이 존재하는 동안은 유일하다. 핀토스에서 아이노드의 섹터번호는 아이노드 번호로 사용하는데 적합하다.

    Soft Link

  4. Buffer Cache

  5. Synchronization