PintOS Proj_3 Virtual Memory
User Program을 실행시키기 위한 프로젝트들중의 두번째로 Virtual Memory(이하 VM)을 구현한다. 프로젝트2까지의 핀토스는 반쪽짜리 VM을 사용하고 있다. 가상 주소 공간을 사용하고 있고 Page map level 4 (이하 pml4)를 사용하고 있기는 하나, process를 실행시키는데 필요한 자원들이 처음부터 모두 다 물리메모리에 올려지고 있으며 process가 종료되지 않는 한 물리메모리를 점유하고 있어 메모리를 효율적으로 관리하지 못하고 있다. 따라서 가상메모리 기술의 핵심인 page fault또한 활용하지 못하고 있다. 이번 프로젝트에서는 이 반쪽짜리 VM이 VM답게 작동할 수 있도록 디자인한다.
Virtual Memory
도입배경
초창기의 메모리는 커널과 유저 프로세스들이 물리메모리를 직접 접근하여 사용하며 모든 프로세스들이 물리메모리를 공유하고 있는 형태였다. 이러한 형태에서의 문제점은 각각의 프로세스가 다른 프로세스의 메모리(심지어 커널에도)에 접근하여 수정할 수 있다는 점이었다. 따라서 프로그램들이 오작동하기 쉬웠으며 보안에도 취약했다. 그리하여 커널을 유저 프로세스로부터 보호(Protection)하고 유저 프로세스들 간에 분리(또는 고립. Isolation)하기 위한 가상메모리(VM)가 등장하게 되었다.
VM의 발전
가상 주소 공간의 이점
VM의 기본 컨셉은 프로세스들에게 각각의 독립된 가상 주소공간을 제공하고 해당 주소들을 물리메모리에 매핑하여 프로세스가 가상 주소로 접근할 때 해당되는 물리메모리로만 접근할 수 있게 하는 것이다. 이로써 유저 프로세스가 주어진 어떤 주소로 접근하더라도 독립된 주소공간을 사용하고 있기 때문에 접근이 허용되어있는 매핑된 메모리에만 접근할 수 있어 유저 프로세스들간의 isolation이 가능해진다. 또한 같은 맥락에서 유저 프로세스가 메모리 공간을 독차지하고있다는 환상을 갖게 되어 다른 프로세스를 전혀 신경쓰지 않고 자유롭게 프로그램을 작성할 수 있게된다.
VM을 구현하는 방식은 시간이 흐름에 따라 발전되어왔다.
베이스 바운드
Base and bound 방식은 VM이 매핑되는 물리메모리의 첫번째 주소를 base로 하여 주소를 번역하고 VM의 크기를 bound에 저장하여 bound를 넘는 주소로 접근시 부적절한 접근으로 판단하여 처리하는 방식이다. 예를 들어 물리메모리가 총 16KB이고 가상메모리가 4KB라고 가정하며 물리메모리 주소의 8K 지점에서 VM이 매핑된다고 하면, 8K 지점을 base로 하여 가상 주소를 더하는 방식(8K + 가상주소)으로 주소가 번역되어 메모리에 접근할 수 있게 되는 것이다. 또한 가상주소가 4KB를 초과하게 되면 bound에 걸려 접근할 수 없게 된다. 이 방식이 적용되던 때 base와 bound는 base register와 bound register에 저장되어 관리되었다고 한다. 이 방식은 단순하였지만 가상주소 공간을 통째로 물리메모리에 매핑하였기 때문에 실제 사용하지 않는 영역까지 메모리를 점유하게 되어 내부 단편화가 심한 방식이었다.
세그멘테이션
Segmentation 방식은 일반화된 Base and bound 방식으로, 가상주소공간을 용도에 따라 segment로 나누고 해당 segment들을 base and bound 방식으로 물리메모리에 매핑시키는 방식이다. 사용하지 않는 영역은 매핑시키지 않기 때문에 내부 단편화는 개선되나 하나의 세그먼트를 덩어리로 매핑시키다보니 여전히 외부단편화는 피할 수 없는 방식이다.
페이지
페이지 방식은 물리메모리와 가상메모리를 4KB 단위로 나누어 매핑하는 방식이다. 가상주소 공간을 4KB로 나눈 하나의 덩어리를 page라고 하며 물리메모리를 4KB로 나눈 덩어리는 물리페이지 또는 물리프레임이라고 한다. Kaist PinsOS에서는 이를 혼동이 없도록 하기 위해 프레임이라고 하기에, 필자도 이하에서는 프레임이라고 하겠다.
Page방식은 4KB 덩어리로 관리하는 만큼 할당되었으나 사용되지 않는 영역이 포함되어 내부단편화가 발생하긴 하나 크지 않으며, 메모리를 잘게 나누었기 때문에 여러page를 묶어서 할당하지 않는 한 외부단편화는 발생하지 않는다.
32비트 운영체제에서는 2의 32제곱 만큼의 가상주소공간을 사용할 수 있다. 이는 32비트 운영체제가 메모리를 4GB까지밖에 사용할 수 없는 이유이기도 하다. 반면에 64비트 운영체제에서는 2의 64제곱 만큼의 가상주소공간을 사용할 수 있지만, 실제로는 48제곱까지만 사용한다. 이는 가상주소공간이 커질수록 늘어나는 페이지에 대응하는 페이지테이블이 필요하고 이를 위한 굉장히 큰 공간이 추가로 필요해지기 때문이며, 48제곱 만으로도 256TB라는 충분한 크기의 공간을 제공할 수 있기 때문이라고 한다.
48개의 비트로 표현되는 가상주소 체계에서는 256TB의 공간을 사용할 수 있으며 이를 페이지로 표현하면 64G개에 해당된다. VM에서 가상페이지와 물리프레임의 매핑은 페이지테이블로 관리되는데, 이 하나하나의 페이지테이블 또한 4KB의 페이지들로 관리된다. 하나의 페이지테이블이 4KB이고 각각의 페이지의 매핑정보를 담는 페이지테이블 엔트리(PTE: Page Table Entry)는 주소를 저장하므로 8바이트에 해당하기에 하나의 페이지테이블에는 512개의 PTE를 담을 수 있다. 48비트 가상주소의 페이지매핑을 전부 저장하기 위해서는 128M개의 페이지테이블이 필요하며 이의 크기는 512GB에 달한다. 현실적으로 불가능한 크기라고 할 수 있다. 메모리의 크기는 커질수록 속도가 느려지며 최근 컴퓨터들도 보통 8GB에서 32GB 사이의 물리메모리를 사용할 뿐이다.
VM은 실제로 가상주소공간에 대응되는 페이지테이블들을 한번에 다 만들지 않는다. 오히려 필요한 페이지들만 미리 만들어놓고 user process에 의해 추가적으로 필요한 경우에 추가로 테이블을 생성한다. 이를 구현하기 위한 체계가 Page Map Level 4(pml4)이다. 48비트 가상주소에서 하위 12개 비트는 page offset을 의미한다(1page는 4KB이며 이는 12개 비트로 표현되기 때문). 그 외 상위 36개 비트는 page의 number를 의미하는데, 이를 9비트씩 4개 구간으로 나누면 해당 구간마다 512(2의 9제곱)개의 하위 테이블의 number를 의미하도록 구분할 수 있다. 예를 들어 page offset 상위 첫번째 구간은 page table에서의 Entry number를 의미하며, 이보다 한단계 상위구간은 page table을 '가리키는' table의 page table index를 의미한다고 볼 수 있다. 여기서 구간을 9비트로 나누는 이유는 각각의 테이블 또한 4KB의 페이지로 관리되며 각 엔트리는 8바이트이므로 512개를 담을 수 있기 때문이다.
User process가 가상주소로 접근할 경우 매핑되어있는 물리주소로의 주소번역이 필요하다. 매핑되는 정보는 페이지테이블에 있기에 커널에 의해 소프트웨어 수준에서 주소를 번역하여 데이터에 접근하고 user에게 돌려줄 수도 있으나 이는 매우 느린 과정이다. 이렇게 소프트웨어 수준에서 속도가 나지 않는 경우 하드웨어의 도움을 받아 해결하곤 한다. 그래서 탄생하게 된 것이 MMU(Memory Management Unit)라는 주소번역 하드웨어이며, 페이지테이블을 메모리에서 가져오는 과정의 느린 속도를 개선하기 위해 자주 사용되는 페이지테이블 엔트리를 캐싱하는 하드웨어가 바로 TLB(Translation Loockaside Buffer)이다.
Memory Management
Project2까지 진행한 PintOS는 반쪽짜리 VM이 적용되어있다. Kernel의 protection과 user process간의 isolation은 구현되어 있지만 메모리가 효율적으로 관리되고 있지는 않다. 당장 필요하지 않은 자원들까지도 한번에 물리메모리에 올리고 있기 때문이다. 그렇다면 적시 적절한 자원을 메모리에 적재할 수 있도록 관리하려면 어떠한 방법을 써야하는걸까?
우선 자원들은 바로 물리메모리에 load 및 매핑하지 않고 이후에 load할 수 있도록 필요한 정보만 따로 저장해두어야 한다. 이후 아래와 같은 두가지 방법을 통해 자원들을 관리한다.
첫번째는 page fault이다. Page fault는 user process가 어떤 가상주소에 접근했을 때 NULL 접근이거나 kernel 주소와 같이 권한이 없는 주소에 대한 접근일 때 발생하거나 매핑된 정보가 없을 때 발생한다. 전자와 같이 부적절한 접근일 경우에는 프로세스를 종료해야한다. 하지만 후자의 경우에는 해당 주소에 해당되는 페이지가 유효한지(이전에 저장해둔 정보가 있는 페이지인지) 확인하고 유효하다면 load 및 매핑을 통해 user process가 원하는 data에 접근할 수 있도록 해주어야 한다. 이 방법을 사용하면 user process가 필요로 할 때에만 data를 물리메모리에 적재하여 program 실행시 load하는 시간을 단축시킬 수 있으며 물리메모리 공간을 절약할 수 있다.
두번째는 swap이다. Page fault 발생시 물리메모리(프레임)을 할당하고 해당 공간에 필요한 data를 적재하고 매핑하는 것이 swap in이다. 문제는 물리메모리가 가득 찬 경우 발생한다. 이때에는 적재되어있는 data(page) 중 우선순위가 낮은 data를 victim으로 선택하고 eviction하여 물리프레임을 확보하는데 이를 swap out이라고 한다. 우선순위를 판단하는 기준은 LRU 등 다양하지만 단순한 알고리즘으로는 Clock 알고리즘이 있다. PTE에는 accessed라는 bit가 있는데 이는 process가 해당 page를 읽거나 쓰면 1로 변경되는 bit이다. 따라서 eviction을 수행하는 시점에 accessed가 0인 PTE가 있다면 이를 우선순위가 낮은 page로 판단할 수 있다. Accessed bit가 모두 1일때는 어떻게 해야할까? 이때 사용되는 알고리즘이 Clock 알고리즘이다. 하나하나의 accessed bit를 확인할때 1이면 0으로 바꿔준 뒤 다음 프레임을 확인한다. 그러다가 모든 페이지의 bit가 1이어서 한바퀴 돌게되면 처음으로 확인하고 0으로 바꿔주었던 페이지를 만나게 되는데 이때 이를 우선순위가 낮다고 판단하고 eviction하는 것이다. 이러한 Swap을 사용하여 당장 사용하지 않는 페이지를 물리프레임에서 제거하고 필요한 page만 물리메모리에 있도록 하여 메모리를 효율적으로 사용할 수 있다.
이러한 방법들을 적용하여 메모리를 관리하기 위해서는 관련된 자료들을 저장하고 관리할 data structure가 필요하다.
Supplemental Page Table
PintOS에서는 Supplemental Page Table(이하 spt)을 통해 페이지들을 관리한다. Spt에 저장되는 data는 page라는 구조체이다. 각각의 page는 해당하는 가상주소와 해당 주소에 매핑되어야할 정보들을 저장할 수 있는 field들로 구성되어있다. Page fault 발생시 이 table에서 fault가 발생한 주소에 해당하는 페이지가 있는지 검색하고, 있다면 유효한 페이지라고 판단하여 load(또는 swap in)을 진행하게 된다. 이 외에도 어떠한 주소가 유효한 페이지인지 확인이 필요한 경우에도 활용될 수 있다.
Page fault를 빠르게 수행하기 위해서는 spt에서의 검색 속도가 빨라야 한다. 이를 위해 다양한 디자인을 할 수 있겠지만, 필자는 hash 자료구조를 사용하여 구현하였다. PintOS에서 제공하는 hash table은 최적의 경우 O(1~2)에서 최대 O(4)의 시간복잡도로 구현되어 매우 빠르게 검색을 수행할 수 있다.
Frame Table
물리메모리의 User pool에 대한 프레임 관리를 위해 table이 필요하다. 특히 swap out시 eviction을 위해 victim을 찾을 때 대상들을 관리하기 위해 필요하다. 이 또한 다양한 디자인이 가능하지만, clock 알고리즘을 적용하기 위해서는 선형탐색만 가능하면 되기 때문에 필자는 linked list를 이용하여 frame table을 구현하였다.
Anonymous Page
Page의 종류 중 anonymous page(익명 페이지)는 매칭되는(또는 기반이되는?) 특정한 file source가 없는 페이지이다. PintOS에서 anonymous page는 stack과 segment에 해당한다. Stack은 그렇다쳐도 segment는 왜 anonymous 인지 의아할 수 있다. 실행 file(executables)로부터 data를 읽어오기 때문에 file source가 있다고 생각이 들기 때문이다. 실행 file의 data는 해당되는 page가 initialize 되는 때에 딱 한 번만 file로부터 data를 읽어온다. 그 이후에는 해당 file에서 data를 읽어오거나 쓸 일이 없다. 왜냐하면 실행하는데 필요한 data를 초기에 읽어오고 이후에 .bss나 .data에 해당하는 세그먼트의 경우 실행되는 도중에 data가 바뀌는데 이를 실행file에 저장해서는 안되기 때문이다. 실행file의 data들은 실행을 위한 초기값들을 저장하고 있기 때문에 내용이 바뀌어서는 안된다. 따라서 실행file에서 읽어오는 segment는 돌아갈 수 있는 파일(backing file)이 없는 anonymous page로 관리된다.
PintOS에서 모든 page는 uninit page로 시작된다. Uninit page의 swap in operation은 initializer로 되어있으며, page fault가 발생되어 swap in이 실행될 때 이 initializer가 실행되어 미리 설정해놓은 type에 따른 initializer와 그 외 추가적으로 지정해둔 initializer가 실행된다. Anonymous page의 경우 type은 VM_ANON type으로 uninit page를 생성한다. 이에 따라 추후에 anon initializer가 실행될 수 있게 된다. 또한 segment의 경우에는 segment로 분류하기 위해 VM_SEGMENT를 or연산하여 함께 넣어준다. 마찬가지로 stack의 경우에는 VM_STACK으로 함께 넣어준다.
Proj2 까지의 PintOS는 user program이 실행될 때 모든 segment data를 물리메모리에 적재시켰으나 이번 프로젝트에서는 해당 시점에는 추후에 initialize 될 수 있도록 uninit page만 생성하며, initialize시에 data가 올라갈 수 있도록 lazy load 기능을 구현하고 uninit page 생성시 인자로 전달해준다. Stack의 경우에는 user program 실행시 arguments를 passing하기위해 setup되어있어야 하므로 반드시 lazy load없이 initialize해야 한다.
Stack Growth
User stack의 꼭대기에 위치한 첫번째 스택 영역의 경우 process의 load단계에서 바로 setup 해주었으나 현재 상태에서는 이후에 process가 진행되다가 해당 영역을 벗어나는 경우 유효하지 않은 주소를 참조한 것으로 판단되어 process는 kernel에 의해 종료된다. 따라서 stack이 성장하는 경우 이를 판단하여 추가적인 메모리를 할당해 줄 필요가 있다.
X86-64의 PUSH Intruction은 rsp를 아래로 내리고 데이터를 저장하기 전에 먼저 8바이트 아래의 주소가 유효한지 확인한다. 이때 해당 주소가 유효하지 않다면 rsp는 변동되지 않은 채로 page fault가 발생하게 된다. 따라서 kernel은 user process에서의 rsp와 fault address를 비교하여 8바이트 차이가 나면 stack growth가 필요한 상황으로 판단하고 추가 메모리를 할당해줄 수 있다.
위와 같은 경우 외에도 stack growth라고 판단할 수 있는 경우가 한가지 더 있다. 함수 내에서 초기화되지 않는 지역변수가 선언되는 경우이다. 이러한 지역변수가 선언되는 경우 PUSH instruction이 실행되지 않는다. 초기화하지 않았기 때문에 해당 변수의 값에는 접근이 일어나지 않으며 단지 해당 변수에 stack의 일부 영역과 그 주소가 주어질 뿐이다. 또한 rsp는 PUSH 없이 해당 변수의 아래로 이동하게 된다. 따라서 그 시점에 해당되는 stack 메모리가 할당되지 않으며 지역변수에 접근이 일어났을 때 page fault가 발생된다. 이 경우에는 위처럼 8바이트의 차이로는 stack growth라고 판단할 수 없다. 따라서 다른 방법을 생각해야 한다.
System call이나 interrupt가 user process에서 발생되어 kernel로 mode switching이 발생한 경우 interrupt frame에 user process의 rsp값이 저장되지만 kernel에서 진행하다가 page fault가 발생하는 경우 interrupt frame에는 원하지 않는 값이 저장되어있다. 따라서 system call이나 interrupt 발생 시 user에서 바로 넘어온 경우 tcb 등 가능한 다른 공간에 rsp값을 저장하여 page fault 발생 시 rsp를 읽어올 수 있도록 해주어야 한다.
Memory Mapped Files
Page의 종류 중 File mapped page(Memory Mapped File)는 file을 기반으로 한 page이다. Initialize할 때에는 Anon page와 비슷한 방식으로 물리메모리에 load되지만 destroy(unmap)시에는 load되었던 물리메모리의 변경사항 유무에 따라 원본 file에 수정이 일어나는 점이 anon page와의 차이점이다.
File mapped page는 user process의 mmap system call에 의해 만들어지며 munmap에 의해 제거된다. User process의 mmap 요청에 대해 kernel은 인자로 전달된 가상주소에 file을 mapping할 수 있도록 필요한 data들을 담아 page를 생성한다. 추후에 process가 해당되는 주소로 접근했을 때 page fault가 발생되면 segment와 마찬가지로 lazy load 방법으로 물리메모리에 file을 읽어와 매핑시키게 된다. Mmap 구현시 user process로 넘어온 fd(file descriptor)에 해당하는 file을 찾되 그대로 사용하는 것이 아니라 file_reopen 함수를 통해 file 구조체를 새로 만들어 사용해야한다. 그 이유는 먼저 user가 넘겨준 fd를 가지고 user는 다시 read, write, close 등을 수행할 수 있어야한다. 따라서 file 구조체의 offset이 file mapped page에 의해 변동되어서는 안되며 file이 먼저 close되어서도 안된다. 또한 user가 fd를 사용하여 file을 close하더라도 munmap하지 않았다면 mmap에 의해 이루어진 매핑이 유지되어야 한다. 이와 같은 이유로 mmap이 수행될 때에는 mmap만을 위해 file을 reopen하여 사용해야한다.
User process가 munmap system call을 요청하면 kernel은 인자로 전달된 가상주소가 이전에 mmap에 의해 file이 매핑되어있는 주소가 맞는지, 그리고 이전에 munmap된 주소는 아닌지 확인하고 유효하다면(unmap이 진행될 수 있다면) 해당 주소에 매핑되어있는 page의 destroy를 진행한다. File mapped page의 destroy을 진행할 때에는 매핑되어있는 물리메모리의 수정이 일어났는지 확인하고 수정이 되어있다면 file에 수정을 반영하고 수정이 되어있지 않다면 별도 반영 없이 매핑을 해제한다. 물리메모리의 수정이 일어나면 해당 물리메모리에 접근하기 위해 사용된 user 가상 주소에 해당하는 PTE의 dirty bit가 0에서 1로 변경된다. 따라서 destroy의 대상이되는 page의 PTE의 dirty bit를 확인함으로써 file에 저장을 해야할지 유무를 판단할 수 있다.
Mmap시 요청된 length가 page의 크기 4KB보다 크다면 전달된 가상주소로부터 연속된 페이지로 file을 매핑할 수 있도록 page를 생성한다. User가 인자로 넘겨준 addr로부터 읽고싶은 위치만큼 offset을 주고 계산하여 접근하였을 때 원하는 data를 읽을 수 있게 하기 위함이다. 반대로 munmap시 user는 매핑되어있는 주소 중 맨 첫번째 주소만 인자로 넘겨주는데 kernel은 그 주소로 요청받아 매핑하였던 page들을 모두 unmap해주어야 한다. 여러 page로 매핑되어있는 경우 user의 가상주소에 연속된 페이지로 매핑되도록 page를 생성하였기 때문에 총 page수를 저장해두었다면 어렵지 않게 해당되는 page들을 찾아 destroy를 진행할 수 있다.
User process가 mmap으로 file을 매핑한 후에 munmap을 호출하지 않고 종료하더라도 매핑되어있는 page들은 정리되어야 한다. 이는 process exit시에 clean up 하는 과정에서 이루어지는데, 문제는 의도적인 unmap 과정과 다르게 page들에 random하게 접근하여 destroy를 진행하게 되면서 발생된다. File mapped page가 destroy될 때에는 mmap시 reopen했던 file을 close해주어야 하는데, 이는 여러 page가 생성되었더라도 모든 페이지가 정리되고 마지막 페이지가 destroy될 때 close되어야 한다. Munmap시에는 의도적으로 destroy되는 순서를 정할 수 있지만 process exit시에는 모든 spt의 page들에 대해서 random하게(정확히는 hash table에 저장되어있는 순서대로) destroy가 진행되기 때문에 어떤 순서로 destroy되더라도 마지막 page가 정리될 때 file을 close할 수 있도록 구현해야 한다. 다양한 방법이 있겠으나 필자의 팀은 해당 시점마다 정리되어있지 않은 페이지수를 저장하고 page들이 해당 변수를 공유할 수 있도록 pointer와 malloc을 활용하였다. 예를 들면 총 3페이지로 구성된다면 malloc으로 할당받은 count변수에 3을 저장하여 각각의 페이지에 포인터변수로 저장해두고 각각의 페이지가 destroy될 때마다 해당 값을 1씩 감소시켜 값이 0이 되었을 때에 마지막 page로 간주하고 file을 close하는 방식이다.
Fork가 일어날 때에는 동일한 context로 진행되도록 하기 위해 부모의 모든 spt의 page들을 copy해주어야 한다. Page 종류에 따라 이런저런 신경써주어야할 것이 많기에 굉장히 까다로운 부분이다. 그 중에서도 mmap page는 더욱 그렇다. Page안에 page type 별로 필요한 contents를 담을 수 있도록 struct들을 union으로 묶어놓은 field가 있는데, file page의 경우 load와 destroy(또는 swap in/out)을 위해 필요한 data들을 저장해야하기 때문이다. 특히 file은 여러 page로 매핑되었더라도 하나의 file 구조체를 가리켜야 하고 위에서 언급한 count는 여러 page가 같은 변수를 참조하고(가리키고) 있어야 의도한대로 작동될 수 있기 때문이다. 따라서 부모의 page들을 copy할 때에 이러한 점들을 충분히 고려하여 design할 필요가 있다. 필자의 팀은 file mapped page의 경우 initialize될 때 copy상황인지 판단하고, copy상황이라면 동일한 file로 매핑되어야하는 page들 중 이미 initialize된 page가 있는지 확인하여 있다면 해당 page의 file과 count변수를 가져와 저장하고, 없다면 file reopen과 malloc으로 새로 생성하여 저장하는 방식으로 구현하였다.
Swap In/Out
위에서 언급한 것처럼 page fault 발생시 해결할 수 있는 fault(유효한 page가 있는 경우)라면 해당되는 data를 load(또는 swap in)하여 user가 해당 addr에 접근할 수 있도록 해야한다. 그러나 그 과정 중에 물리메모리가 모두 할당되어 추가 할당할 수 있는 공간이 없다면 다양한 방법(한가지 방법 Clock 알고리즘은 위에서 간단히 언급하였다)을 통해 eviction 대상이 될 page를 찾고 해당 page를 swap out하여 이후에 다시 해당 page에 접근 시 swap in이 될 수 있도록 하고 물리frame을 확보하여야 한다.
File mapped page의 경우 swap in/out이 비교적 단순하다. Backing store가 되는 file이 있기 때문에 swap out의 경우 destroy와 마찬가지로 수정여부를 확인 후 file에 반영하면 되고 swap in은 lazy load처럼 file로부터 data를 읽어와 물리메모리와 매핑하기만 하면 된다.
Anon page의 경우는 file mapped page와 달리 추가적인 구현이 필요하다. Backing store가 되는 file이 없기 때문에 임시로 저장해둘 공간이 따로 필요하기 때문이다. 이를 위해 disk의 일부 partition을 swap partition으로 사용하는데 PintOS에서는 이를 swap disk로 제공하며 disk를 initialize하고 read/write하기 위한 interface를 제공한다.
Swap disk는 swap out시 data를 임시 저장하기 위한 공간으로 다시 swap in operation이 일어나기 전까지 해당 data는 안전하게 유지되어야 한다. 따라서 swap disk의 할당여부를 관리하기 위한 swap table이 필요하다. Swap disk는 page를 저장하기 위해 4KB씩 나누어 관리하며 이 단위를 swap slot이라고 한다. Swap table은 이 swap slot의 할당여부를 관리해야하는데 이는 간단하게 1(할당됨)과 0(할당가능)으로 관리할 수 있기에 PintOS에서 제공하는 bitmap을 사용하면 간단하게 구현할 수 있다.
PintOS의 bitmap은 사용할 수 있는 bit의 개수를 저장하는 bit cnt와 실제 bit를 저장하는 bits로 구성되며, bits는 32bit unsigned long의 배열로 되어있다. bitmap create시 bit cnt를 인자로 넘겨주면 해당 bit를 표현하기 위해 필요한 unsigned long의 개수를 계산하여 bits배열을 생성한다. 예를 들어 100개의 bit를 관리해야한다면 100개의 bit를 표현하기 위해서는 32bit unsigned long이 4개 필요하므로 길이 4의 배열을 생성한다. 이후 swap slot의 할당을 위해 bitmap scan and flip을 호출하면 bits 배열의 처음부터 scan하여 할당되지 않은(bit가 0인) 인덱스를 찾아 반환한다. 또한 swap slot을 반납하기 위해 bitmap set을 실행하면 해당 index가 배열의 몇번째 인덱스에 속하며 몇번째 offset에 위치하는지 계산하고 그 위치에 접근하여 값을 set하게 된다.
Disk는 sector라는 최소단위로 data를 관리하며 sector의 크기는 시스템마다 다를 수 있으나 PintOS에서는 512bytes를 사용한다. 따라서 한개의 page를 저장하기 위해 한개의 swap slot은 8개의 sector를 사용해야한다. 또한 disk를 read/write할 때에 disk에서의 위치는 sector no.로 표현하기 때문에 swap slot과 swap slot당 sector수인 8의 곱으로 실제 disk에 write/read해야할 위치를 계산할 수 있다.
Copy-on-write (Extra)
동일한 file에 대해서 여러 process가 mmap요청을 하는 경우 이미 물리메모리에 mapping되어있는데도 추가로 메모리를 할당하여 매핑하는 것은 비효율적이다. 특히 write가 발생하지 않는 경우라면 완전히 동일한 data를 여러 메모리에 load하고 매핑하게되어 정말 비효율적이다. 하여 이미 매핑된 물리메모리가 있는 경우 우선 같은 물리메모리를 참조하도록 하여 user process가 해당 data에 접근하여 read할 수 있도록 하고 write동작이 발생할 때에야 물리메모리의 copy를 진행하여 각각 data를 따로 수정할 수 있도록 한다. 이러한 방법을 copy-on-write 방식이라고 한다.
Copy-on-write 방식을 구현하려면 user process의 write 동작을 kernel이 알아챌 수 있어야 한다. 이는 단순히 PTE의 writable bit를 0으로 세팅하여 read only page인것처럼 만들어놓고 write동작이 일어나면 page fault가 발생되는것을 이용하여 write 동작을 알아채도록 할 수 있다.
PintOS에서는 이 챕터는 extra에 해당하는 부분으로 fork시에 file mapped page를 copy하는 경우에만 copy-on-write가 적용되도록 구현하라고 하고 있다.
회고
Project2까지는 한양대 ppt 자료를 참고하여 구현해왔지만 이번 VM 프로젝트에서는 기타 자료의 참고 없이 kaist git book과 PintOS의 base code만을 참고하고 설계하여 프로젝트를 진행했다. 그래서 세세하게 신경써서 설계하고 구현한 코드가 정상적으로 동작할때 정말 즐거웠고 자신감이 많이 올랐던 것 같다. 특히 여러모로 신경을 많이 써야했고 우리만의 로직을 적용해서 구현해야했던 supplemental page table copy부분은 정말 흥미진진했다. 이전에도 reference code를 참고하지 않고 도움이되는 ppt자료만 보고 구현했기에 물론 의미가 있었지만 이번 프로젝트를 진행하면서 충분히 직접 설계할 수도 있었을텐데 그렇게 하지 않았던 것에 대해 아쉬움을 많이 느꼈다.
거의 모든 test case가 통과되었지만 page-merge-par, page-merge-stk, page-merge-mm 이 세가지 case는 random하게 pass/fail이 발생했다. 다른 모든 각각 기능에 대한 case는 통과되고 있고 이 case들에서도 종종 pass가 되어서, 그리고 워낙 case가 복잡하고 print가 잘 되지 않아서 어떤 부분에서 fail이 발생하는지 찾지 못한채 이번 프로젝트가 종료되었다. 조금 더 집착을 가지고 깊게 tracking해보면 해결할 수 있을텐데 시간의 한계로 해결하지 못한 부분이 아쉬움으로 남았다. 또한 copy on write는 시간관계상 구현하지 못했는데 내용을 읽어보니 흥미로워서 조금 더 목표를 높게 잡고 이 부분까지 구현했더라면 또 재미있었겠다 하는 생각이 든다.
지난주에 비해 내용이 너무 방대하여 여러가지 빼먹은 부분도 많고 글도 좀 횡성수설 하는 부분이 있는 것 같다. 혹시나 이 글의 독자가 있다면 거를건 거르고 도움이 되는 부분만 잘 골라 얻어가길 바란다. 잘못된 내용에 대한 태클은 언제나 환영입니다.
