translation.md



Project2: User Programs

Introduction
Project1에서 Pintos를 다뤄보고 PintOS 시스템 구조와 스레드 패키지에 익숙해졌으니, 이제는 사용자 프로그램을 실행할 수 있도록 PintOS 시스템 일부를 구현해야합니다. 현재의 PintOS 시스템(코드)는 유저 프로그램을 로드하고 실행할 수 있는 기본적인 코드 구현이 되어있습니다. 하지만, 현재의 PintOS 시스템은 실행중인 유저 프로그램이 다른 유저 프로그램 혹은 커널 및 다양한 하드웨어 장치와 상호작용하는 기능을 지원하고 있지 않습니다. 결국 Project2 에서는 유저 프로그램이 시스템콜 (시스템호출) 을 통해 다른 유저 프로그램, 운영체제와 상호작용하는 기능을 구현하는것이 주 목표입니다. Project 2 에서는 userprog 디렉토리에서 작업할 것이지만, 거의 모든 다른 부분의 Pintos와도 상호작용할 것입니다. 관련 부분은 아래에 설명하겠습니다.
(% 결국 Project 2 에서는 유저 프로그램이 시스템콜을 호출해서 커널 모드로 전환하고, 커널 모드에서 요청받은 작업을 수행하는 코드 구현을 해야 합니다~)
Project 2는 Project 1을 기반으로 빌드가 됩니다. Project 1의 코드가 Project 2의 코드에 직접적으로 영향을 주는건 아니지만, Project 2를 진행하기 전에 Project 1의 테스트 케이스를 모두 통과해야 합니다. 이는 PintOS가 점진적으로 기능을 추가하는 프로젝트이기 때문입니다. 또한, Project 2 에는 추가적인 도전 과제가 있습니다(이는 선택적인 구현입니다). 추가 도전 과제를 위해 제공되는 것은 테스트 케이스뿐이며, 테스트 케이스 코드는 없습니다. 모든 설계는 전적으로 여러분에게 맡겨집니다. 추가 요구 사항을 제출하고 테스트하려면 userprog/Make.vars를 수정해야 합니다. 마지막으로, TODO가 없는 코드(함수)들은 반드시 수정할 필요는 없습니다. Project 2의 소스 코드는 테스트 코드를 제외한 모든 코드에서 자유롭게 수정할 수 있습니다.

Background
Project 1 에서 실행한 모든 코드는 운영체제 커널의 일부였습니다. 즉, 예를 들어 Project 1 에서 실행한 모든 테스트 코드는 커널의 일부로 실행되었으며 시스템의 특권이 있는 부분에 완전하게 접근할 수 있었습니다. (% 즉, Project 1에서 돌린 테스트케이스들은 유저 프로그램이 아닌, 커널로 실행되어서 시스템 호출을 하지 않고 다양한 하드웨어 장치와 상호작용을 하여 문제 없이 실행되었습니다~). 하지만 이제 유저 프로그램을 이 PintOS 위에서 실행하게 되면, 더 이상 정상적으로 실행되지 않을겁니다. PintOS 에서는 동시에 하나 이상의 프로세스가 실행될 수 있습니다. (% 유저 프로그램이 메모리에 로드되면 프로세스로 불립니다~). 각 프로세스는 하나의 스레드를 포함하고 있습니다. 유저 프로그램은 마치 전체 컴퓨터를 독점적으로 사용하는 것처럼 작성됩니다. 즉, 여러 유저 프로그램을 동시에 로드하고 실행할 때, 이 환상을 유지하기 위해 메모리 관리, 스케줄링 및 다른 상태들을 올바르게 관리해야 합니다.이전 프로젝트에서는 테스트 코드를 직접 커널에 컴파일했기 때문에, 커널 내에서 특정 함수 인터페이스를 요구해야 했습니다. 이제부터는 PintOS 를 사용자 프로그램을 실행하여 테스트합니다. 이것은 더 큰 자유를 제공합니다. 사용자 프로그램 인터페이스가 여기에서 설명된 사양을 충족하는지 확인해야 하지만, 그 제한 내에서 커널 코드를 어떻게 재구성하거나 다시 작성할지는 여러분의 자유입니다. 모든 코드가 #ifdef VM으로 둘러싸인 블록에 위치하지 않도록 해야 합니다. 이 블록은 프로젝트 3에서 구현할 가상 메모리 서브시스템을 활성화한 후에 포함될 것입니다. 또한, 코드가 #ifndef VM으로 둘러싸인 경우, 해당 코드는 프로젝트 3에서 제외될 것입니다.
Project 2를 시작하기 앞서 synchronization(동기화)와 virtual address(가상 주소)파트를 읽어보는 것을 매우 강력하게 추천합니다.

Source Files
프로그램을 개요를 파악하는 가장 쉬운 방법은 작업할 각 부분을 간단히 살펴보는 것입니다. userprog 디렉토리에는 몇 개의 파일만 있지만, 여기서 대부분의 구현 작업이 이루어질 것입니다.


process.c, process.h 

ELF 바이너리를 로드하고 프로세스를 시작합니다 (% ELF 바이너리는 해당 유저 프로그램의 파일 헤더 등을 포함하고 있습니다 ~)


syscall.c, syscall.h

유저 프로그램이 커널 모드로 전환해서 커널 및 다른 하드웨어 장치와 상호작용을 하려면 시스템 콜을 호출해야 합니다. 시스템 콜 핸들러에 대한 스켈레톤 코드가 구현되어있습니다. 현재는 메시지를 출력하고 프로세스가 종료되도록 구현되어있습니다. Project 2에서는 시스템 콜이 제대로 작동할 수 있도록 코드 구현을 완성시켜야 합니다.


syscall-entry.S

시스템 콜 핸들러를 bootstrap 하는 어셈블리 코드입니다. (% bootstrap은 초기 설정이라고 생각하시면 됩니다~). 이 부분을 굳이 이해할 필요는 없습니다.


exception.c, exception.h

프로세스가 특권을 요구하는 작업이나 금지된 작업을 수행하면, 예외나 결함으로 커널로 트랩됩니다. 이 함수가 이 예외를 처리해줍니다. 현재 모든 예외는 단순히 메시지를 출력하고 프로세스를 종료시킵니다. Project 2의 일부 예외는 이 파일의 page_fault() 함수를 수정해야 할 수 있습니다.


gdt.c, gdt.h

x86-64는 세그먼트화된 아키텍처입니다. 전역 기술자 테이블(GDT)은 사용 중인 세그먼트를 설명하는 테이블입니다. 이 파일들은 GDT를 설정합니다. 프로젝트 진행 중에는 이 파일들을 수정할 필요는 없습니다. GDT가 어떻게 작동하는지에 관심이 있다면 코드를 읽어볼 수 있습니다. (% 이 파트도 굳이 이해할 필요가 없습니다~)


tss.c, tss.h

태스크 상태 세그먼트(TSS)는 x86 아키텍처에서 태스크 스위칭에 사용되었습니다. 그러나 x86-64에서는 태스크 스위칭이 더 이상 사용되지 않습니다. 그럼에도 불구하고, TSS는 링 스위칭 중에 스택 포인터를 찾기 위해 여전히 존재합니다. 즉, 사용자 프로세스가 인터럽트 핸들러에 진입할 때, 하드웨어는 TSS를 참조하여 커널의 스택 포인터를 조회합니다. 프로젝트를 진행하면서 이 파일들을 수정할 필요는 없습니다. TSS가 어떻게 작동하는지에 관심이 있다면 코드를 읽어볼 수 있습니다. (% 이 파트도 굳이 이해할 필요가 없습니다~)


Using File System
Project 2에서는 파일 시스템 코드를 이용해야 합니다. 왜냐하면 유저 프로그램이 파일 시스템에서 로드되며, 구현해야 할 많은 시스템 콜이 파일 시스템과 관련되어있기 떄문입니다. 하지만 Project 2의 주 목표는 파일 시스템 이해가 아니기 떄문에, filesys 디렉터리에 간단하지만 완전한 파일 시스템 코드를 구현해두었습니다. 파일 시스템을 사용하는 방법과 그 제약 사항을 이해하려면, filesys.h와 file.h 인터페이스를 살펴보는 것이 좋습니다. 

Project 2를 통과하기 위해서 파일 시스템 코드를 수정할 필요가 없고, 그러지 않길 추천드립니다. 파일 시스템에서 작업하는것은 이 프로젝트의 주요 목표에서 주의를 분산시킬 가능성이 있습니다.

파일 시스템 루틴을 적절히 사용하면, Project 4에서 파일 시스템 구현을 개선할 때 작업이 훨씬 수월해질 것입니다. 하지만 그때까지는 다음과 같은 제약 사항을 감수해야 합니다:

내부 동기화 없음: 동시 접근이 서로 간섭을 일으킬 수 있습니다. 파일 시스템 코드가 한 번에 하나의 프로세스만 실행되도록 동기화를 사용해야 합니다. (% 만약 동기화가 없다면 하나의 파일이 여러개의 프로세스에서 동시에 수정되서 오류가 발생합니다~)


파일 크기 고정: 파일은 생성 시 크기가 고정됩니다. 루트 디렉토리도 파일로 표현되므로, 생성 가능한 파일의 수가 제한됩니다. 


단일 연속(extent) 할당: 파일 데이터는 디스크의 연속된 섹터 범위를 차지해야 합니다. 따라서 시간이 지남에 따라 파일 시스템을 사용할 때 외부 단편화 문제가 심각해질 수 있습니다. (% Project 4에서 이 파트를 수정해야 합니다~) 


서브디렉토리 없음: 하위 디렉토리를 생성할 수 없습니다. (% 이것도 Project 4에서 수정합니다~)


파일 이름 길이 제한: 파일 이름은 최대 14자로 제한됩니다. 


시스템 충돌: 작업 중간에 시스템이 충돌하면 디스크가 자동으로 복구할 수 없는 방식으로 손상될 수 있습니다. 파일 시스템 복구 도구도 제공되지 않습니다. 


한 가지 포함된 중요한 기능:


filesys_remove()의 Unix 스타일 동작이 구현되어 있습니다. 즉, 파일이 삭제될 때 해당 파일이 열려 있으면, 마지막으로 닫힐 때까지 그 파일의 블록은 해제되지 않고, 열려 있는 스레드에서 계속 접근할 수 있습니다. 자세한 내용은 "Removing an Open File"을 참조하십시오. 


Project 1과는 달리, 여기서는 테스트 프로그램이 커널 이미지에 포함되어 있지 않습니다. 대신 유저 스페이스에서 실행되는 테스트 프로그램을 Pintos 가상 머신에 넣어야 합니다. 다행히, 테스트 스크립트(예: make check)가 이를 자동으로 처리해주기 때문에 대부분의 경우 이 과정을 이해할 필요는 없습니다. 하지만 이 과정을 이해하면 개별 테스트 케이스를 실행할 때 큰 도움이 됩니다. (% 즉, Project 2에서는 각 테스트 케이스는 파일로 되어있고, 이를 PintOS의 디스크에 올려야합니다~ ) 

Pintos 가상 머신에 파일을 넣는 방법: 


파일 시스템 파티션을 포함하는 디스크 생성:


먼저, 파일 시스템 파티션이 포함된 디스크를 생성해야 합니다. 이를 위해 pintos-mkdisk 프로그램을 사용합니다.


userprog/build 디렉토리에서 다음 명령어를 실행하세요:

pintos-mkdisk filesys.dsk 2 

이 명령어는 2MB 크기의 Pintos 파일 시스템 파티션을 포함하는 디스크 filesys.dsk를 생성합니다. 


디스크 지정: 


디스크를 지정하려면, --fs-disk filesys.dsk를 pintos 뒤에, 그리고 -- 앞에 추가합니다: 


pintos --fs-disk filesys.dsk -- KERNEL_COMMANDS... 


여기서 -- 는 --fs-disk가 Pintos 스크립트에 대한 옵션임을 나타내며, 시뮬레이션된 커널에 전달되는 것이 아님을 명확히 합니다. 


파일 시스템 포맷: 


파일 시스템 파티션을 포맷하려면 커널 명령어로 -f -q를 전달해야합니다:

pintos SCRIPT_COMMANDS -- -f -q 


-f: 파일 시스템을 포맷 (% Project 4 전까지는 Continuous Allocation 방식의 파일 시스템을 사용합니다~ )


-q: 포맷이 완료되면 Pintos를 종료 


파일 복사: 


파일 시스템 안팎으로 파일을 복사하려면 pintos -p(파일 복사)와 pintos -g(파일 가져오기) 옵션을 사용합니다. 


예: 파일 file을 Pintos 파일 시스템에 복사하려면: pintos -p file -- -q 


파일을 newname으로 복사하려면: pintos -p file:newname -- -q 


파일을 가상 머신에서 가져오려면 -g를 대신 사용합니다. 


내부 구현: 

-이 명령들은 특별한 명령어 extract 와 append 를 커널 명령어로 전달하고, 가상의 "scratch" 파티션을 사용하여 파일을 복사합니다. 


자세한 내용은 pintos 스크립트와 filesys/fsutil.c 파일을 참조하면 확인할 수 있습니다.

요약 정리
(% 결국, 파일인 테스트 케이스를 PintOS에서 실행하려면, 디스크 생성 -> 파일 복사(새로 만든 파일 디스크로)->실행. 이 3 단계를 거쳐야 합니다~) 

아래는 파일 시스템 파티션이 포함된 디스크를 생성하고, 파일 시스템을 포맷하고, args-single 프로그램(이 프로젝트의 두 번째 테스트 케이스)을 새 디스크에 복사하고, 이를 실행하는 명령어입니다. args-single 프로그램에 'onearg'라는 인수를 전달합니다(인수 전달 기능은 구현 후에 동작합니다). 
 현재 디렉토리가 userprog/build라고 가정합니다:


디스크 생성 및 포맷: 

pintos-mkdisk filesys.dsk 10 


파일 복사 및 실행: 

pintos --fs-disk filesys.dsk -p tests/userprog/args-single:args-single -- -q -f run 'args-single onearg' 


이를 단일 명령어로 실행할 수 있습니다.
파일 시스템 디스크를 일시적으로만 사용하고 싶다면, 모든 단계를 단일 명령어로 결합할 수 있습니다. --filesys-size=n 옵션을 사용하면 임시 파일 시스템 파티션을 생성하여 Pintos 실행 동안만 유지됩니다.

pintos --fs-disk=10 -p tests/userprog/args-single:args-single -- -q -f run 'args-single onearg' 

(% 보시다시피 개별 테스트 케이스 명령어를 만드는건 생각보다 복잡합니다. make test 명령어를 치면 각 테스트 케이스에 대한 실행 명령어를 프린트 해주니까 그렇게 하면 굉장히 편합니다~ ) 


How User Progams Work
Pintos는 메모리에 적합하고 구현된 시스템 콜만 사용하는 경우 일반적인 C 프로그램을 실행할 수 있습니다. 하지만, 이 프로젝트에서 메모리 할당을 허용하는 시스템 콜이 제공되지 않으므로 malloc()은 구현할 수 없습니다. (% 이후 프로젝트에서는 malloc()을 사용할 수 있습니다~). 또한, Pintos는 스레드 전환 시 프로세서의 부동소수점 유닛(Floating-Point Unit)을 저장하고 복원하지 않기 때문에 부동소수점 연산을 사용하는 프로그램도 실행할 수 없습니다. 

Pintos는 userprog/process.c에 제공된 로더를 사용하여 ELF 실행 파일을 로드할 수 있습니다. **ELF(Executable and Linkable Format)**는 Linux, Solaris, 그리고 많은 다른 운영 체제에서 객체 파일, 공유 라이브러리 및 실행 파일에 사용되는 파일 형식입니다. 

Pintos에서 실행할 프로그램을 생성하기 위해 x86-64 ELF 실행 파일을 출력하는 컴파일러와 링커를 사용할 수 있습니다. (Pintos와 함께 제공된 컴파일러와 링커는 이 목적에 적합합니다.) 그러나 테스트 프로그램을 시뮬레이션된 파일 시스템에 복사하지 않으면 Pintos가 유용한 작업을 수행할 수 없음을 알아두어야 합니다. 다양한 프로그램을 파일 시스템에 복사하지 않으면 흥미로운 작업을 수행할 수 없습니다. 

디버깅 중에 파일 시스템 디스크(filesys.dsk)가 유용하지 않을 정도로 손상될 수 있으므로, 깨끗한 참조 파일 시스템 디스크를 만들어 필요할 때 이를 복사해 사용하는 것이 좋습니다.

Virtual Memory Layout
Pintos의 가상 메모리는 유저 가상 메모리와 커널 가상 메모리 두 영역으로 나뉩니다. (% 실제 물리 메모리도 유저, 커널 공간으로 나뉘어진다~) 


유저 가상 메모리(User Virtual Memory): 


유저 가상 메모리는 0부터 KERN_BASE 까지의 주소를 가집니다. KERN_BASE는 include/threads/vaddr.h에 정의되어 있으며 기본값은 0x8004000000입니다.
유저 가상 메모리는 프로세스별로 관리됩니다. 커널이 한 프로세스에서 다른 프로세스로 전환할 때, 프로세서의 페이지 디렉터리 베이스 레지스터를 변경함으로써 유저 가상 주소 공간도 함께 전환됩니다(자세한 내용은 thread/mmu.c의 pml4_activate() 참조). (% 모든 프로세스는 자신만의 ) 


struct thread는 해당 프로세스의 페이지 테이블에 대한 포인터를 포함합니다. 


커널 가상 메모리(Kernel Virtual Memory): 


커널 가상 메모리는 글로벌로 관리됩니다. 실행 중인 유저 프로세스나 커널 스레드에 관계없이 항상 같은 방식으로 매핑됩니다.


Pintos에서 커널 가상 메모리는 물리 메모리와 1:1 매핑됩니다. 매핑은 KERN_BASE부터 시작합니다. ex) 가상 주소 KERN_BASE는 물리 주소 0에 접근하고, 가상 주소 KERN_BASE + 0x1234는 물리 주소 0x1234에 접근합니다. 이는 머신의 물리 메모리 크기까지 동일합니다. 


사용자 프로그램은 자신의 유저 가상 메모리만 액세스할 수 있습니다. 커널 가상 메모리에 접근하려고 시도하면 페이지 폴트가 발생하며, 이는 userprog/exception.c의 page_fault() 함수에서 처리되고 해당 프로세스는 종료됩니다. 반면 커널 스레드는 커널 가상 메모리와 실행 중인 프로세스의 유저 가상 메모리 모두에 접근할 수 있습니다. 그러나 커널에서도 매핑되지 않은 사용자 가상 주소의 메모리에 접근하려고 하면 페이지 폴트가 발생합니다. (% 이는 가상 메모리의 레이지 로딩 같은 상황 때문에 발생합니다 ~) 


Typical Memory Layout
개념적으로, 각 프로세스는 자신의 유저 가상 메모리를 원하는 대로 구성할 수 있습니다. 하지만 실제로는 유저 가상 메모리가 다음과 같은 방식으로 구성됩니다:
(% 이 부분은 사진이라 원본 사진 보면 됩니다 ~)  

PintOS 프로젝트에서 유저 스택의 크기는 고정되어 있지만, Project 3에서는 스택 크기를 확장할 수 있도록 허용됩니다. (% Stack Growth). 원래는 초기화되지 않은 데이터 세그먼트(uninitialized data segment)의 크기는 시스템 호출을 통해 조정할 수 있지만, 이번 프로젝트에서는 이를 구현할 필요가 없습니다.  Pintos에서 코드 세그먼트는 사용자 가상 주소 0x400000에서 시작하며, 이는 주소 공간의 하단에서 약 128MB 떨어진 위치입니다. 이 값은 Ubuntu에서 일반적으로 사용되는 값이었으며, 특별한 뜻을 가지지는 않습니다. 링커는 "링커 스크립트(linker script)"의 지시에 따라 유저 프로그램의 메모리 레이아웃을 설정합니다. 링커 스크립트는 다양한 프로그램 세그먼트의 이름과 위치를 지정합니다. 링커 스크립트에 대한 자세한 내용은 링커 매뉴얼의 "Scripts" 챕터를 읽어보면 알 수 있습니다. 매뉴얼은 info ld 명령을 통해 접근할 수 있습니다. 특정 실행 파일의 레이아웃을 확인하려면, objdump 명령에 -p 옵션을 사용하여 실행하면 됩니다.

Accessing User Memory
시스템 호출의 일부로, 커널은 유저 프로그램이 제공한 포인터를 통해 메모리에 접근해야 하는 경우가 종종 있습니다. 이 과정에서 커널은 매우 신중해야 합니다. 사용자가 널 포인터(null pointer), 매핑되지 않은 가상 메모리 주소, 또는 커널 가상 주소 공간(주소가 KERN_BASE 이상인)을 가리키는 포인터를 전달할 수 있기 때문입니다. 이러한 모든 잘못된 포인터는 커널이나 다른 실행 중인 프로세스에 피해를 주지 않고 거부되어야 하며, 이를 위해 문제를 일으킨 프로세스를 종료하고 해당 프로세스의 자원을 해제해야 합니다. (% 메모리, pte, ,,) 이를 올바르게 처리할 수 있는 합리적인 방법이 최소 두 가지 있습니다.

유저 제공 포인터의 유효성을 확인한 다음 이를 역참조(dereference)하는 것입니다. 이 방법을 선택하면, thread/mmu.c와 include/threads/vaddr.h에 있는 함수들을 참고하면 됩니다. 이는 유저 메모리 접근을 처리하는 가장 간단한 방법입니다. 


유저 포인터가 KERN_BASE 아래를 가리키는지만 확인한 다음 이를 역참조하는 것입니다. 잘못된 사용자 포인터는 "페이지 폴트(page fault)"를 발생시키며, 이를 userprog/exception.c의 page_fault() 코드를 수정하여 처리할 수 있습니다. 이 기법은 프로세서의 MMU(Memory Management Unit)를 활용하기 때문에 일반적으로 더 빠르며, 실제 커널(예: Linux)에서도 주로 사용됩니다. 


어느 방법을 선택하든 자원을 "누수(leak)"하지 않도록 주의해야 합니다. 예를 들어, 시스템 호출이 잠금을 획득하거나 malloc()을 사용해 메모리를 할당한 경우를 생각해봅시다. 이후에 잘못된 유저 포인터를 만나더라도, 반드시 잠금을 해제하거나 할당된 메모리를 해제해야 합니다. 유저 포인터를 역참조하기 전에 유효성을 확인하는 방법을 선택하면 비교적 간단하게 이를 처리할 수 있습니다. 하지만 잘못된 포인터가 페이지 폴트를 유발하는 경우에는 메모리 접근에서 에러 코드를 반환할 방법이 없기 때문에 처리하기가 더 어렵습니다. (% 유저 프로세스에서 포인터로 이동하기 전에, 해당 포인터의 유효성을 먼저 판단하고 진행한다는 뜻입니다~)
따라서 후자의 방법을 시도하고자 하는 사람들을 위해 도움말 코드를 제공할 것입니다:
(% 이부분도 사진이라 원본에서 보시면 됩니다) 


Argument Passing
x86-64 호출 규약 (Calling Convention)
이 섹션에서는 Unix의 64비트 x86-64 구현에서 정상적인 함수 호출에 사용되는 규약의 중요한 점들을 요약합니다. 일부 세부사항은 간결성을 위해 생략되었습니다. 더 자세한 정보는 System V AMD64 ABI를 참고하세요.

호출 규약은 다음과 같이 작동합니다.

유저 레벨 애플리케이션이 정수 레지스터를 %rdi, %rsi, %rdx, %rcx, %r8, %r9 순서로 인수 전달에 사용합니다. 


호출자는 자신의 다음 명령어 주소(반환 주소)를 스택에 푸시하고 피호출자의 첫 번째 명령어로 점프합니다. x86-64 명령 CALL이 이를 수행합니다. 


피호출자가 실행합니다 


피호출자가 리턴값이 있다면, RAX 레지스터에 리턴값이 저장됩니다. 


피호출자는 반환 주소를 스택에서 팝(pop)하여 해당 위치로 점프함으로써 반환합니다. 이를 위해 x86-64 RET 명령어를 사용합니다. 


예를 들어, 전달 인수가 3개인 함수 f(1, 2, 3)이 있다고 가정해봅시다. 이 아래 그림이 f()가 실행될때 스택 포인터, 레지스터 값들을 보여줍니다. (% 그림은 원본에 있습니다) 

Pintos의 사용자 프로그램용 C 라이브러리는 lib/user/entry.c에 있는 _start()를 사용자 프로그램의 시작점으로 지정합니다. 이 함수는 main()을 감싸고 있으며, main()이 반환되면 exit()를 호출합니다.
커널은 유저 프로그램이 실행을 시작하기 전에 초기 함수의 인수를 레지스터에 올려야 합니다. 인수 전달은 일반적인 호출 규약과 동일한 방식으로 이루어집니다. 다음 예제 명령어 /bin/ls -l foo bar에 대한 인수를 처리하는 방법을 고려해 봅시다: 

명령어를 단어로 나눕니다: /bin/ls, -l, foo, bar.
단어들을 스택의 상단에 배치합니다. 참조는 포인터를 통해 이루어지므로 순서는 중요하지 않습니다.
각 문자열의 주소와 null 포인터 센티넬(null pointer sentinel)을 오른쪽에서 왼쪽 순서로 스택에 푸시합니다. 이는 argv의 요소들이 됩니다. null 포인터 센티넬은 C 표준에 따라 argv[argc]가 null 포인터임을 보장합니다. 이 순서는 argv[0]이 가장 낮은 가상 주소에 위치하도록 합니다. 워드(word) 정렬된 접근은 비정렬 접근보다 빠르므로, 첫 번째 푸시 전에 스택 포인터를 8의 배수로 내리는 것이 성능에 유리합니다.(% 핀토스에서 모든 명령어는 단어 단위로 잘리는데, 이는 8의 주소차이로 저장됩니다.)
%rsi를 argv (즉, argv[0]의 주소)로 설정하고 %rdi를 argc로 설정합니다.
마지막으로, 가짜 "반환 주소"를 푸시합니다. 비록 진입 함수가 반환되지 않을 것이지만, 스택 프레임은 다른 함수와 동일한 구조를 가져야 합니다. (% 가짜 반환 주소라는게 헷갈릴수도 있는데, 사진을 보면 명령어들이 어떻게 저장되는지 알 수 있습니다.)
아래 표는 사용자 프로그램 시작 직전 스택과 관련 레지스터 상태를 보여줍니다. 참고로 스택은 아래 방향으로 성장합니다.
(% 사진은 원본에 있습니다. ) 


User Memory Access
시스템 호출을 구현하려면 사용자 가상 주소 공간에서 데이터를 읽고 쓰는 방법을 제공해야 합니다. 하지만 시스템 호출의 인수를 가져올 때는 이러한 기능이 필요하지 않습니다. 그러나 시스템 호출의 인수로 제공된 포인터에서 데이터를 읽을 때는 반드시 이러한 기능을 통해 간접적으로 접근해야 합니다. 이 작업은 약간 까다로울 수 있습니다. 예를 들어, 사용자가 잘못된 포인터를 제공하거나, 커널 메모리로의 포인터를 제공하거나, 이러한 영역 중 일부에 걸친 블록을 제공하면 어떻게 될까요? 이러한 경우를 모두 처리하여 사용자 프로세스를 종료해야 합니다.

System Calls
userprog/syscall.c 안에 시스템 콜 핸들러를 구현하세요. 우리가 제공한 최소한의 기능은 프로세스를 종료 시키므로써 시스템 콜을 다룹니다. 여러분이 구현하는 시스템 콜 핸들러는 시스템 콜 번호를 받아오고, 인자들을 받아오고, 그에 알맞은 액션을 취해야 합니다.

System Call Details
첫 프로젝트에서 이미 운영 체제가 유저 프로그램에게서 제어권을 되찾아 갈 수 있는 방법을 다뤘습니다. 예를 들어, 타이머와  I/O 디바이스들로 부터의 인터럽트들. 이런 인터럽트들은 외부 인터럽트들 입니다. 운영 체제는 sw exception도 다룹니다. Page fault나 division by zero 같은 에러들이 이런 것들 입니다. 또한 sw exception은 유저 프로그램이 시스템 콜 이라는 서비스를 운영체제에게 요청하는 수단입니다. 전통적인 x86 아키텍쳐에서 시스템 콜은 다른 sw exception과 동일하게 다뤄집니다. 하지만 x86-64에서는 제조사가 syscall 이라는 시스템 콜을 위한 특별한 명령어를 제공합니다. 이 명령어는 시스템 콜 핸들러를 호출하는 빠른 방법을 제공합니다. 요즘엔 syscall 명령어가 x86-64에서 시스템 콜을 불러올 때 가장 흔하게 사용되는 수단입니다. Pintos에서 유저 프로그램은 시스템 콜을 만들기 위해서 syscall을 호출합니다. Syscall 명령어를 불러오기전에 시스템 콜 번호와 추가적인 인자는 레지스터에 일반적인 방법으로 설정됩니다. 이때 일반적이지 않은 점 두 가지는 다음과 같습니다. 


%rax 는 시스템 콜 번호 입니다. 


4번째 인자는 %r10 입니다. %rcx 가 아닙니다. 

그러므로 시스템 콜 핸들러 syscall_handler() 가 제어권을 얻으면 시스템 콜 번호는 rax 에 있고, 인자는 %rdi, %rsi, %rdx, %r10, %r8, %r9 순서로 전달됩니다. 시스템 콜 핸들러를 호출한 콜러의 레지스터는 전달받은 struct intr_frame 에 접근할 수 있습니다. (struct intr_frame은 커널 스택에 있습니다). 함수 리턴 값을 위한 x86-64의 관례는 그 값을 RAX 레지스터에 넣는 것 입니다. 값을 리턴하는 시스템 콜도 struct intr_frame의  rax 멤버를 수정하는 식으로 이 관례를 따를 수 있습니다.


Implement the following system calls
include/lib/user/syscall.h 을 포함하는 유저 프로그램이 보게되는 시스템 콜들의 프로토타입 목록 입니다. (이 헤더파일과 include/lib/user 에 있는 모든 건 유저 프로그램만 사용합니다.) 각 시스템 콜의 시스템 콜 번호는 include/lib/syscall-nr.h 에 정의 되어 있습니다: 


void halt (void); 

power_off()를 호출해서 Pintos를 종료합니다. 이 함수는 웬만하면 사용되지 않아야 합니다. deadlock 상황에서 문제가 생길 수 있습니다 


void exit (int status); 

현재 동작중인 유저 프로그램을 종료합니다. 커널에 상태를 리턴하면서 종료합니다. 만약 부모 프로세스가 현재 유저 프로그램의 종료를 기다리던 중이라면, 그 말은 종료되면서 리턴될 그 상태를 기다린다는 것 입니다. 관례적으로, 상태가 0이면 성공을 뜻하고 0 이 아닌 값들은 에러를 뜻 합니다. 


pid_t fork (const char *thread_name); 

THREAD_NAME이라는 이름을 가진 현재 프로세스의 복제본인 새 프로세스를 만듭니다. 피호출자의 저장 레지스터인 %RBX, %RSP, %RBP와 %R12 - %R15를 제외한 레지스터 값을 복제할 필요가 없습니다. 자식 프로세스의 pid를 반환해야 합니다. 그렇지 않으면 유효한 pid가 아닐 수 있습니다. 자식 프로세스에서 반환 값은 0이어야 합니다. 자식 프로세스에는 파일 식별자 및 가상 메모리 공간을 포함한 복제된 리소스가 있어야 합니다. 부모 프로세스는 자식 프로세스가 성공적으로 복제되었는지 여부를 알 때까지 fork에서 반환해서는 안 됩니다. 즉, 자식 프로세스가 리소스를 복제하지 못하면 부모의 fork() 호출이 TID_ERROR를 반환할 것입니다.
(% 복제해야하는 요소들에는 fd table, memory, pte table 등이 있기 때문에 프로젝트를 진행하면서 이 부분을 계속 수정해줘야 합니다~)
(% 모든 프로세스는 결국 fork로 태어납니다. 최초의 프로세스 하나만 존재하고, 나머지는 다 fork, exec으로 탄생합니다~)


int exec (const char *cmd_line);

현재의 프로세스가 cmd_line에서 이름이 주어지는 실행가능한 프로세스로 변경됩니다. 이때 주어진 인자들을 전달합니다. 성공적으로 진행된다면 어떤 것도 반환하지 않습니다. 만약 프로그램이 이 프로세스를 로드하지 못하거나 다른 이유로 돌리지 못하게 되면 exit state -1을 반환하며 프로세스가 종료됩니다. 이 함수는 exec 함수를 호출한 스레드의 이름은 바꾸지 않습니다. file descriptor는 exec 함수 호출 시에 열린 상태로 있다는 것을 알아두세요. (% 해당 함수 이름으로 된 프로세스를 먼저 찾아야 합니다~) 


int wait (pid_t pid);

자식 프로세스가 pid와 exit state를 반환할때까지 기다립니다. 만약 자식 프로세스 pid가 살아있다면, 종료될때까지 기다리세요. 만약 자식 프로세스가 exit()을 호출하지 않았고 커널에 의해 종료된 상태라면 -1을 반환하세요. 부모 프로세스가 wait 함수를 호출한 시점에서 이미 종료되어버린 자식 프로세스를 기다리도록 하는 것은 가능하지만, 커널은 부모 프로세스에게 자식의 종료 상태를 알려주든지, 커널에 의해 종료되었다는 사실을 알려줘야합니다. wait 함수는 아래 중 하나라도 해당된다면 즉시 -1을 반환해야합니다. 


5-1. pid 는 호출하는 프로세스의 직속 자식을 바로 참조하지 않습니다. 오직 프로세스가 fork() 호출 후 성공적으로 pid를 반환받은 경우에만, pid 는 호출하는 프로세스의 직속 자식입니다. 자식들은 상속되지 않는다는 점을 알아두세요. 예를 들어 만약 A 가 자식 B를 낳고 B가 자식 프로세스 C를  낳는다면, A는 C를 기다릴 수 없습니다. 심지어 B가 죽은 경우에도요. 프로세스 A가  wait(C) 호출하는 것은 실패해야 합니다. 마찬가지로, 부모 프로세스가 먼저 종료되버리는 고아 프로세스들도 새로운 부모에게 할당되지 않습니다.
(% 원래는 부모를 새로 연결해주는데, 여기서는 새로 연결해주지 않는다고 가정하고 하는겁니다~) 

5-2. wait 를 호출한 프로세스가 이미 pid에 대해 기다리는 wait 를 호출할 수 없습니다. 즉, 한 프로세스는 어떤 주어진 자식에 대해서 최대 한번만 wait 할 수 있습니다. 

프로세스들은 자식을 얼마든지 낳을 수 있고 그 자식들을 어떤 순서로도 기다릴 수 있습니다. 자식들의 신호는 기다리지 않고도 종료될 수 있습니다. (% 이러면 고아 프로세스가 생깁니다~ ). 여러분의 설계는 발생할 수 있는 기다리는 모든 경우를 고려해야합니다. 한 프로세스의 자원들은 부모, 자식 관계에 상관없이 exit 하기전에 꼭 자원 할당을 해제되어야 합니다. 최초의 process가 종료되기 전에 Pintos가 종료되지 않도록 하십시오. 제공된 Pintos 코드는 main() (in threads/init.c)에서 process_wait() (in userprog/process.c ) 를 호출하여 Pintos가 최초의 process 보다 먼저 종료되는 것을 막으려고 시도합니다. 여러분은 함수 설명의 제일 위의 코멘트를 따라서 process_wait() 를 구현하고 process_wait() 의 방식으로 wait system call을 구현해야합니다. 


bool create (const char *file, unsigned initial_size);

위의 함수는 file을 이름으로 하고 크기가 initial_size인 새로운 파일을 생성합니다. 성공적으로 파일이 생성되었다면 true를 반환하고, 실패했다면 false를 반환합니다. 새로운 파일을 생성하는 것이 그 파일을 여는 것을 의미하지는 않습니다: 파일을 여는 것은 open 시스템콜의 역할로, open과 개별적인 연산입니다.


bool remove (const char *file); 

위의 함수는 file이라는 이름을 가진 파일을 삭제합니다. 성공적으로 삭제했다면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 파일은 열려있는지 닫혀있는지 여부와 관계없이 삭제될 수 있고, 파일을 삭제하는 것이 그 파일을 닫았다는 것을 의미하지는 않습니다. 자세한 내용을 알고 싶다면 FAQ에 있는 Removing an Open File를 참고하세요. 


int open (const char *file); 

위의 함수는 file(첫 번째 인자)이라는 이름을 가진 파일을 엽니다. 해당 파일이 성공적으로 열렸다면, 파일 식별자로 불리는 비음수 정수(0또는 양수)를 반환하고, 실패했다면 -1를 반환합니다. 0번 파일식별자와 1번 파일식별자는 이미 역할이 지정되어 있습니다. 0번은 표준 입력(STDIN_FILENO)을 의미하고 1번은 표준 출력(STDOUT_FILENO)을 의미합니다. open 시스템 콜은 아래에서 명시적으로 설명하는 것처럼 시스템 콜 인자로서만 유효한 파일 식별자들을 반환하지 않습니다.  각각의 프로세스는 독립적인 파일 식별자들을 갖습니다. 파일 식별자는 자식 프로세스들에게 상속(전달)됩니다. 하나의 프로세스에 의해서든 다른 여러개의 프로세스에 의해서든, 하나의 파일이 두 번 이상 열리면 그때마다 open 시스템콜은 새로운 식별자를 반환합니다. 하나의 파일을 위한 서로 다른 파일 식별자들은 개별적인 close 호출에 의해서 독립적으로 닫히고 그 한 파일의 위치를 공유하지 않습니다. 당신이 추가적인 작업을 하기 위해서는 open 시스템 콜이 반환하는 정수(fd)가 0보다 크거나 같아야 한다는 리눅스 체계를 따라야 합니다. 


int filesize (int fd); 

위의 함수는 fd(첫 번째 인자)로서 열려 있는 파일의 크기가 몇 바이트인지 반환합니다. 


int read (int fd, void *buffer, unsigned size); 

buffer 안에 fd 로 열려있는 파일로부터 size 바이트를 읽습니다. 실제로 읽어낸 바이트의 수 를 반환합니다 (파일 끝에서 시도하면 0). 파일이 읽어질 수 없었다면 -1을 반환합니다.(파일 끝이라서가 아닌 다른 조건에 때문에 못 읽은 경우) 


int write (int fd, const void *buffer, unsigned size); 

buffer로부터 open file fd로 size 바이트를 적어줍니다. 실제로 적힌 바이트의 수를 반환해주고, 일부 바이트가 적히지 못했다면 size보다 더 작은 바이트 수가 반환될 수 있습니다. 파일의 끝을 넘어서 작성하는 것은 보통 파일을 확장하는 것이지만, 파일 확장은 basic file system에 의해서는 불가능합니다. 이로 인해 파일의 끝까지 최대한 많은 바이트를 적어주고 실제 적힌 수를 반환하거나, 더 이상 바이트를 적을 수 없다면 0을 반환합니다. fd 1은 콘솔에 적어줍니다. 콘솔에 작성한 코드가 적어도 몇 백 바이트를 넘지 않는 사이즈라면, 한 번의 호출에 있는 모든 버퍼를  putbuf()에 적어주는 것입니다. 


void seek (int fd, unsigned position); 

open file fd에서 읽거나 쓸 다음 바이트를 position으로 변경합니다. position은 파일 시작부터 바이트 단위로 표시됩니다.
(따라서 position 0은 파일의 시작을 의미합니다). 이후에 read를 실행하면 파일의 끝을 가리키는 0바이트를 얻습니다. 이후에 write를 실행하면 파일이 확장되어 기록되지 않은 공백이 0으로 채워집니다. (하지만 Pintos에서 파일은 프로젝트 4가 끝나기 전까지 길이가 고정되어 있기 때문에 파일의 끝을 넘어서 작성하려고 하면 오류를 반환할 것입니다.) 이러한 의미론은 filesystem 안에서 구현되며 system call을 구현할 때에는 특별히 노력할 필요는 없습니다. 


unsigned tell (int fd); 

열려진 파일 fd에서 write, read 할 다음 바이트의 위치를 반환합니다. 파일의 시작지점부터 몇 바이트인지로 표현됩니다. 


void close (int fd); 

파일 식별자 fd를 닫습니다. 프로세스를 나가거나 종료하는 것은 묵시적으로 그 프로세스의 열려있는 파일 식별자들을 닫습니다. 마치 각 파일 식별자에 대해 이 함수가 호출된 것과 같습니다. 


Process Termination Message
프로세스가 exit 함수를 호출 했거나 다른 이유들로 유저 프로세스가 종료될 때 마다 프로세스의 이름과exit 코드를 출력합니다. 아래 예시 처럼 출력해야합니다. 

printf ("%s: exit(%d)\n", ...);

출력되는 이름은 fork()로 전달된 풀네임이어야 합니다. 유저 프로세스가 아닌 커널 스레드가 종료될때나 halt할때 이 메시지를 출력하지마세요. (% 이 이유 때문에 Project 1의 테스트케이스와 Project 2 테스트 케이스의 종료 메시지가 다른 형태를 띄어야 합니다). 이것을 제외하고도, PintOS에서 제공한 출력 문장을 제외하고 다른 메시지를 출력하지마세요. 디버깅을 할때 유용할수도 있겠지만, 테스트케이스를 채점할때 여러분의 성적을 낮출겁니다. (% 테스트케이스 검사는 출력 문자열로 판단하기 떄문에, 디버깅용 출력 문장을 지우지 않으면 다 틀릴겁니다~)

Deny Write on Executables
실행중인 파일에 쓰기를 거부하는 코드를 작성하세요. 어떤 코드가 디스크에서 수정되고 있는 도중에 프로세스가 그 코드를 실행하려고 시도하면 예상치 못한 결과를 낳을 수 있기 때문에, 많은 OS들이 이를 방지합니다. 이는 프로젝트 3에서 가상 메모리가 구현된 이후에 특히 중요해지는 부분이지만, 그렇다고 해서 지금 코드가 손상되어도 괜찮다는 말은 아니죠. 열려있는 파일에 쓰기를 방지하려면 file_deny_write()  함수를 사용하면 됩니다. 그리고 file_allow_write()를 파일 안에서 호출하면 다시 쓰기가 가능해지도록 만들 수 있습니다. 그리고 파일을 닫아도 다시 쓰기가 가능해지게 됩니다. 그러므로, 프로세스의 실행 파일에 쓰기를 계속 거부하려면, 프로세스가 돌아가는 동안에는 실행 파일이 쭉 열려 있게끔 해야 합니다.

Project 4

Introduction
이전 두 번의 프로젝트에서 여러분은 파일 시스템이 실제 어떻게 구현되어있는지 잘 모르는 상태에서, 파일 시스템을 엄청나게 이용하였습니다. 이번 마지막 과제에서는 파일 시스템의 구현을 향상시킬겁니다. 여러분은 filesys 디렉터리에서 주로 작업 할 것입니다. Project 4의 코드를 project 2,3위에 올려도 상관없습니다. Project2까지 구현한 코드만으로도 이번 과제의 구현을 성공시킬 수 있습니다. Project 3위에 올리기 위해서는 filesys/Make.vars를 고쳐야 VM(%가상메모리)이 제대로 작동합니다. VM을 활성화시키지 않고 Project 4를 구현하면 10% 감점이 있을 예정입니다.

Background
여기있는 파일들은 여러분들이 아마 처음 보는 파일들입니다. 


filesys/fsutil.c: 커널 커맨드 라인에서 접근할 수 있는 파일시스템을 위한 간단한 유틸리티들이 있습니다. 


include/filesys/filesys.h, filesys/filesys.c: 파일 시스템에 대한 최상위 인터페이스가 있습니다. 들어가기 전, 파일 시스템 사용 방법을 보실 수 있습니다. 


include/filesys/directory.h, filesys/directory.c: 파일 이름을 inode로 변환해줍니다. 디렉토리 자료구조는 파일로서 저장되어 있습니다. 


include/filesys/inode.h, filesys/inode.c: 디스크에 있는 파일의 레이아웃을 보여주는 자료구조를 관리합니다.


include/filesys/fat.h, filesys/fat.c: FAT 파일시스템을 관리합니다 


include/filesys/file.h, filesys/file.c: 파일 read와 write를 디스크 섹터 read와 write로 변환 합니다. 

(% page cache 부분은 구현을 하지 않았기에 넘기도록 하겠습니다~) 


우리의 파일시스템은 Unix와 비슷한 인터페이스입니다. 따라서 create, open, close, read, write, lseek, unlink 함수들에 대한 Unix man 페이지를 읽어 보길 권합니다. 우리의 파일 시스템은 이것들과 동일하지는 않지만 비슷한 함수들을 갖고 있습니다. 파일 시스템은 이런 함수들로 디스크를 동작시킵니다. 모든 기본적인 기능이 위의 코드에 있습니다. 그래서 여러분이 앞의 두 프로젝트를 하며 보신 것 처럼 시작부터 파일시스템이 사용가능 했습니다. 하지만 심각한 제한사항들이 있고 여러분이 이제 그 제한들을 없애게 될 것 입니다. filesys 에서 대부분의 작업을 할테지만, 이전의 모든 파트들과도 상호작용하도록 해야합니다.

Testing File System Persistence
지금까진 각 테스트가 Pintos 를 한번만 실행 시켰습니다. 하지만 파일 시스템의 중요한 목적은 재부팅시에도 같은 데이터에 계속 접근 가능하도록 보장하는 것 입니다. 따라서 파일 시스템 프로젝트의 테스트는 Pintos를 두번 실행 시킵니다. 두번째 실행에서 파일 시스템의 모든 파일과 디렉토리를 하나의 파일로 결합하고, 해당 파일을 핀토스 파일 시스템에서 호스트(Unix)의 파일 시스템으로 복사합니다. 테스트 케이스들은 이 두번쨰 실행의 결과로 채점합니다. 즉, tar 명령어를 수행할 수 있도록 파일 시스템의 대부분을 구현하지 않으면,테스트 케이스 대부분이 실패할거라는 뜻입니다. Tar 명령어를 수행하려면 extensible file, subdirectory support를 구현해야 합니다. 그때까지는 make check 에서 extracted 관련 실패 에러들은 무시해도 됩니다. (% 개인적인 의견으로는 정말 상당 부분 구현해야 프로젝트4의 테스트 케이스들이 성공합니다. 다른 프로젝트들과 달리 구현을 먼저 최대한 끝까지 해보고 테스트케이스를 돌리는것을 추천합니다~)

Indexed and Extensible Files
기본 파일 시스템은 파일들을 단일 면적에 할당하기 때문에 외부 단편화에 취약합니다. 즉, n개 블록이 비어 있는데도 불구하고 (외부 단편화가 되어 서로 떨어져 있다면) n개 길이의 블록이 할당될 수 없다는 말입니다. (% 예를 들어, 하나의 프로그램에 해당하는 모든 메모리 공간을 연속적으로 배치하면 문제가 생긴다는 말입니다~ ) 이 말은 실제 구현에서 직접, 간접, 이중 간접 블록들을 사용하는 인덱스 구조를 사용해야 할지도 모른다는 것을 의미합니다. 이전 학기에서는, '멀티레벨 인덱싱을 사용하는 Berkeley 유닉스 FFS’라고 배웠던 방식 비슷한 것을 대부분의 학생들이 채택했습니다. 그러나 당신의 삶을 보다 쉽게 만들어주기 위해서, 저희는 더 쉬운 방법으로 구현하게끔 했습니다. 바로 FAT이죠. 당신은 반드시 주어진 스켈레톤 코드로 FAT을 구현해야 합니다. 당신의 코드는 멀티레벨 인덱싱 (강의에서 FFS로 배웠던)을 포함해서는 안됩니다. 그러면 file growth 파트에서 0점을 받을 겁니다. 알아두세요. 당신은 파일 시스템 파티션이 8MB보다 크지 않을 것이라고 가정해도 좋습니다. 당신의 구현은 메타데이터를 제외한 파티션 크기만큼의 큰 파일들을 지원해야 합니다. (FILESIZE) ≤ (PARTITION SIZE) - (METADATA). 각 inode는 하나의 디스크 섹터에 저장됩니다. 그 섹터가 담을 수 있는 만큼으로 블록 포인터의 수가 제한됩니다.

Indexing large files with FAT (File Allocation Table)
기존의 프로젝트에서 사용했던 파일 시스템은 파일을 연속된 디스크 섹터에 저장했습니다. 이렇게 연속적으로 할당 받은 섹터를 클러스터라고 합시다. 그렇기 때문에 기존 파일 시스템에서는 클러스터의 크기와 파일의 크기가 같았습니다. 외부 단편화를 완화하기 위해 클러스터의 크기를 줄일 수 있습니다. 스켈레톤 코드를 보면 우리는 섹터당 클러스터의 개수를 1로 고정했습니다. 이런 식으로 하면, 하나의 클러스터로 파일의 전부를 담을 수 없을수도 있습니다. 이럴땐 여러개의 클러스터가 필요합니다. 이 클러스터를 관리하기 위해 해당 파일에 해당하는 클러스터의 섹터 인덱스를 저장하는 자료구조가 필요합니다. 가장 쉬운 방법은 링크드 리스트를 사용하는겁니다. 아이노드가 첫번째 섹터에 해당하는 인덱스 번호를 가지고 있고, 첫번째는 두번째의 인덱스 번호를, 연쇄적으로 이어집니다. 하지만 이 접근은 모든 블럭을 읽어야하기 때문에 굉장히 비효율적입니다. 이것을 극복하기 위해 FAT을 사용하는데, 이렇게 하면 각 블록들이 자신의 구조 안에 연결정보를 담는 대신에 고정 크기의 FAT에 블록들의 연결정보를 저장하게 됩니다. FAT이 실제 데이터가 아닌 연결정보 값만 담고 있기 때문에, DRAM에 캐시될 수 있을 만큼 충분히 작은 크기를 가지게 됩니다. 이렇게 해서, 우리는 테이블에서 상응하는 엔트리만 읽으면 되게 되었습니다. 당신은 inode 인덱싱을 filesys/fat.c에 제공되는 스켈레톤 코드와 함께 구현하게 될 것입니다. 이번 섹션에서는 fat.c에 이미 구현된 함수들과 당신이 앞으로 구현해야 하는 내용들에 대해 간략하게 설명해 보겠습니다. 우선, fat.c에 있는 6개의 함수들 (i.e. fat_init(), fat_open(), fat_close(), fat_create(), and fat_boot_create())은 부팅 시에 디스크를 초기화하고 포맷하기 때문에, 이들을 수정할 필요는 없습니다. 하지만 당신은 fat_fs_init() 함수를 작성하고, 이들이 하는 일이 어떤 도움이 될지를 간략하게 이해해야 할 겁니다. 


cluster_t fat_fs_init (void): FAT 파일 시스템을 초기화합니다. 당신은 fat_fs의 fat_length와 data_start 필드를 초기화해야 합니다. fat_length는 파일시스템에 몇 개의 클러스터가 있는지에 대한 정보를 저장하고, data_start는 어떤 섹터에서 파일 저장을 시작할 수 있는지에 대한 정보를 저장합니다. 당신은 어쩌면 fat_fs->bs 에 저장된 값을 이용하고 싶어질 수도 있습니다. 또한, 이 함수에서 다른 유용한 데이터를 초기화하고 싶어질수도 있습니다. 


void fat_remove_chain (cluster_t clst, cluster_t pclst): clst 인자(클러스터 인덱싱 넘버)로 특정된 클러스터 뒤에 다른 클러스터를 추가함으로써 체인을 연장합니다. 만약 clst가 0이라면, 새로운 체인을 만듭니다.새롭게 할당된 클러스터의 넘버를 리턴합니다. 


void fat_put (cluster_t clst, cluster_t val): 클러스터 넘버 clst 가 가리키는 FAT 엔트리를 val로 업데이트합니다. FAT에 있는 각 엔트리는 체인에서의 다음 클러스터를 가리키고 있기 때문에 (만약 존재한다면 그렇다는 거고, 다음 클러스터가 존재하지 않으면 EOChain (End Of Chain)입니다), 이 함수는 연결관계를 업데이트하기 위해 사용될 수 있습니다. 


cluster_t fat_get (cluster_t clst): clst가 가리키는 클러스터 넘버를 리턴합니다. 


disk_sector_t cluster_to_sector (cluster_t clst): 클러스터 넘버 clst를 상응하는 섹터 넘버로 변환하고, 그 섹터 넘버를 리턴합니다. 


File Growth
크기를 증가시킬 수 있는 파일을 구현하세요. 기본 파일 시스템에서는 파일의 생성 시에 파일 크기가 특정되었습니다. 하지만 대부분의 현대 파일 시스템에서는 파일은 크기 0으로 생성되고, 파일의 끝에서 쓰기가 이루어질 때마다 확장됩니다. 여러분의 파일 시스템은 이를 충족해야합니다. 파일의 크기는 미리 정해두면 안됩니다(파일이 파일 시스템 크기보다 크면 안됩니다). 또한 루트 디렉터리 파일 또한 16 개 이상의 파일을 만들 수 없습니다. (% 이것은 핀토스의 제한). 유저 프로그램은 현재 파일의 끝(EOF)을 넘어서 seek 해도 됩니다. Seek을 하는것만으로 파일의 크기를 늘리지 않습니다. 만약 EOF를 넘어선 포지션에서 write를 하면 파일을 확장시키고, 기존 EOF 부터 새로운 확장 크기의 섹터 사이까지는 다 0으로 채워야합니다. EOF를 한참 넘어서서 write 하는 것은 수많은 블록들을 완전히 0으로 만들어 버릴 겁니다. 어떤 파일 시스템들은 이런 묵시적인 0으로 이루어진 블록들을 실제로 할당하고 write 합니다. 하지만 다른 어떤 파일 시스템들은 명시적으로 write되기 전까지는 그 블록들을 할당하지 않습니다. 후자의 파일 시스템들은 “sparse files (밀도가 희박한 파일)”을 지원한다고 불립니다. 당신은 이러한 파일 시스템의 할당 전략 두가지 중 어떤 쪽이든 채택해도 됩니다.

Subdirectories
기존의 파일 시스템에서 모든 파일은 하나의 디렉터리에 있었습니다. 이 부분을 변경하여 디렉터리 entry가 다른 파일이나 디렉터리를 가리킬 수 있게 해야합니다. 디렉터리 또한 파일처럼 확장을 할 수 있습니다. (% 여러 섹터에 걸쳐서 존재할 수 있습니다. 왜냐면 하나의 디렉터리에는 최대 16개의 파일밖에 못만들기 때문입니다~) 기본 파일 시스템은 파일의 이름을 최대 14글자로 설정할 수 있습니다. 이 제한을 빼서 파일 이름을 확장할 수 있습니다. 여러분의 선택에 달려있습니다. 각 프로세스는 현재 디렉터리를 별도로 유지합니다. 프로세스가 시작할때, 프로세스의 현재 디렉터리 초기값은 root 디렉터리로 설정하세요. 한 프로세스가 fork 시스템 콜로 다른 프로세스를 시작하게 하면, 그렇게 만들어진 자식 프로세스는 부모 프로세스의 현재 디렉터리를 상속 받습니다. fork 이후에, 두 프로세스의 현재 디렉터리들은 서로 독립적이므로, 각 프로세스가 자신의 현재 디렉터리를 변경하는것은 다른 프로세스에게 영향을 미치지 않습니다. (% 부모나 자식이 chdir 해도 영향을 주지 않습니다~) 기존의 시스템 콜을 수정해서, 호출자가 전달한 file name이 절대 또는 상대 경로인 이름을 사용할 수 있도록 하세요. 디렉터리를 구분하는 문자는 슬래시(’/’) 입니다. 또한 여러분은 Unix에서와 동일한 의미의 특별한 파일 이름들인 ‘.’ 과 ‘..’ 도 지원해야 합니다. "open" 시스템 콜을 수정해서 디렉터리도 열수있게 수정하세요. "remove" 시스템콜을 업데이트해서 루트 디렉터리 일반 파일 외에 비어있는 디렉터리(root 제외)도 삭제할 수 있게 수정하세요.  

bool chdir (const char *dir): 프로세스의 현재 작업 디렉터리를 dir로 변경합니다. dir은 상대 경로 또는 절대 경로일 수 있습니다. 성공하면 true를 반환하고, 실패하면 false를 반환합니다. 

bool mkdir (const char *dir): 절대 또는 상대 경로인 디렉터리 dir를 만듭니다. 성공했다면 true를, 그렇지 않으면 false를 반환합니다. 만약 dir 이 이미 존재하거나, 마지막 디렉터리 이외의 디렉터리 이름이 존재하지 않는 경우 실패합니다. 이 말은, mkdir(”a/b/c”) 는 /a/b 가 이미 존재하면서 /a/b/c 가 존재하지 않는 경우에만 성공한다는 뜻 입니다. 

bool readdir (int fd, char *name): 디렉터리를 나타내는 파일 식별자 fd 에서 directory entry를 읽습니다. 성공한다면, null로 끝나는 파일 이름을, READDIR_MAX_LEN + 1 bytes의 공간이 있는 name 에 저장하고 true를 반환합니다. 만일 디렉터리에 남은 항목이 없다면 false를 반환합니다. readdir 에서 . 과 .. 을 반환하면 안됩니다. 만일 디렉터리가 열려있는 동안 변경된다면, 일부 entry들을 전혀 읽지 않거나 여러번 읽는 것이 허용됩니다. 그렇지 않다면(열려 있는 동안 변경되지 않았다면), 각 directory entry는 순서에 관계없이 한번만 읽어야 합니다. READDIR_MAX_LEN 는 lib/user/syscall.h 에 정의되어 있습니다. 만약 파일 시스템이 기본 파일 이름보다 더 긴 파일 이름을 지원한다면, 여러분은 READDIR_MAX_LEN 의 값을 기본값인 14에서 더 늘려야 합니다. 

bool isdir (int fd): fd 가 디렉터리를 나타내면 true를, 일반 파일을 나타내면 false를 반환합니다. 

int inumber (int fd): 일반 파일 또는 디렉터리에 대한 fd 와 연관된 inode의 inode number를 반환합니다.
inode number는 파일 또는 디렉터리를 영구적으로 식별하며, 이는 파일이 존재하는 동안 고유합니다. Pintos에서, inode의 섹터 번호가 inode number로 사용되기에 적합합니다.


Soft Link
Soft Link를 PintOS에 구현하세요. 소프트 링크는 다른 파일이나 디렉터리를 가리키는 유사 파일 객체. 이 파일은 지정된 파일의 절대 또는 상대 경로의 방식의 경로 정보를 포함합니다. 다음과 같은 상황을 가정해보겠습니다: 

/
├── a 

│   ├── link1 -> /file 

│   │ 

│   └── link2 -> ../file 

└── file 

/a 에 위치하는 link1 이라는 이름의 soft-link는 /file 을 (절대 경로로)가리키고 있고, /a 에 위치하는 link2 는 ../file 을 (상대 경로로)가리키고 있습니다. link1 이나 link2를 읽는다는 것은 /file 을 읽는것과 같습니다. 

int symlink (const char *target, const char *linkpath): 문자열 target을 포함하는 linkpath 라는 이름의 symbolic link를 만드세요. 성공 한다면 0이 반환되고, 실패 한다면 -1이 반환됩니다. 


Synchronization
제공된 파일 시스템은 외부 동기화가 필요합니다. 즉, 호출자는 파일 시스템 코드에서 동시에 실행되는 스레드가 하나만 있도록 보장해야 합니다. 하지만 제출물에서는 외부 동기화 없이 작동할 수 있는 더 세분화된 동기화 전략을 채택해야 합니다. 가능한 한, 독립적인 개체에 대한 작업은 서로 독립적으로 이루어져야 하며, 작업 간 대기할 필요가 없도록 해야 합니다. 

세부 요구 사항 


캐시 블록 간 독립성 

서로 다른 캐시 블록에서 작업할 때, 특정 블록에서 I/O가 필요하더라도 I/O와 무관한 작업은 기다리지 않고 계속 진행되어야 합니다. 


파일 접근의 동시성 

여러 프로세스가 단일 파일에 동시에 접근할 수 있어야 합니다. 또한 단일 파일에 대한 다중 읽기 작업은 서로 대기하지 않고 완료될 수 있어야 합니다. 파일 크기를 확장하지 않는 쓰기 작업의 경우, 여러 프로세스가 동시에 동일한 파일에 쓸 수 있어야 합니다. 한 프로세스가 파일을 쓰는 동안 다른 프로세스가 해당 파일을 읽을 경우, 읽기 결과는 쓰기가 전부, 일부, 또는 전혀 완료되지 않은 상태를 보여줄 수 있습니다. 하지만 쓰기 작업이 호출자에게 반환된 이후에는 모든 후속 읽기 작업이 변경된 내용을 확인할 수 있어야 합니다.
두 프로세스가 동일한 파일의 같은 부분에 동시에 쓰는 경우, 데이터가 교차(interleaved)될 수 있습니다. 


파일 확장 및 쓰기 원자성 

파일 크기를 확장하고 새 섹션에 데이터를 쓰는 작업은 원자적으로 이루어져야 합니다. 예를 들어, A와 B 두 프로세스가 파일을 열어 각각 파일의 끝부분에서 작업을 진행한다고 가정합니다. 이때: A가 읽고 B가 파일에 쓰는 경우, A는 B가 쓴 데이터를 전부, 일부, 또는 전혀 읽지 못할 수 있습니다. 그러나 A는 B가 쓴 데이터 외의 다른 데이터를 읽을 수는 없습니다. (예: B가 모든 데이터를 0이 아닌 값으로 작성했을 경우, A는 0을 볼 수 없어야 함.)


디렉터리 작업 동시성 

서로 다른 디렉터리에 대한 작업은 동시에 수행되어야 합니다. 같은 디렉터리에 대한 작업은 서로 대기할 수 있습니다. 


동기화 범위 최소화 

여러 스레드가 공유하는 데이터만 동기화가 필요합니다. 기본 파일 시스템에서는 struct file과 struct dir가 단일 스레드에서만 접근되므로 동기화가 필요하지 않습니다. 위의 조건들을 만족하도록 동기화를 설계하세요.