(2022.02.20) 프로젝트 3 Introduction 맛보기

20220220220...

 

하루 쉬고 왔다. 여전히 할 건 없다. 문서나 보자.

 

사실 pintos가 KAIST 식으로 개편(마개조)되면서 가장 많이 변한 부분이 프로젝트 3과 4가 아닐까하는 생각이 들 정도로 프로젝트 3은 역변했다. 기존 pintos의 프로젝트 3 디렉토리는 공허 그 자체였는데 지금은 뭔가 그득그득하다.

 

vm 디렉토리에 Makefile이랑 Make.vars 말고 다른게 있다니...

친절한 pintos라니. 정말 익숙하지 않다. 난이도가 너무 높아서 너프한거겠지?

 

물론 마냥 풀어주면 우리의 악명높은 CS330 수업이 아닐 것이기에 요구사항은 남아있다. 첫 번째로, 이건 예전에도 마찬가지였지만 프로젝트 2가 정상적으로 동작하는 위에 프로젝트 3를 얹어야 한다. FAQ에 나와있는 바:

Do we need a working Project 2 to implement Project 3?
Yes.

 

캬 엄근진 Yes.

 

두 번째로는 스켈레톤 코드를 둔 대신 제약 조건에서 벗어나면 가차없이 0점처리한다는 것이다. 이러면 코드가 정형화될텐데 치팅 방지 대책은 잘 세워 둔 거겠지? 애먼 사람 잡고 그러면 안 될텐데....

You MUST follow the given template. That is, if you submit the code, that is not based on the given template, you get 0pts. Also, you should never change the template where it is marked "DO NOT CHANGE". Here, we provide some details about each template file that you will be modifying.

 

그래서 이번에는 introduction도 생략하고 넘어가면 안 될 것 같아 맛보기로 읽어보려고 한다. 

 

vm에서 주요하게 다루어야 할 것은 page-frame 매핑이다. 대체 그놈의 page는 뭐고 frame은 뭔데 프로젝트 2 때부터 꾸준히 우리를 괴롭히는 것일까. 매뉴얼에 적힌 내용을 살펴보자.

 

---

 

page(virtual page라고도 한다)는 가상 메모리 공간에서 연속되는 4096 byte 크기의 영역이다. 한 page(후술 페이지)의 시작 주소는 반드시 4096으로 나누어 떨어져야 하며, 해당 상태를 page-aligned 되어있다고 표현한다. 이를 16진법으로 바꿔서 생각하면 더 직관적인데, 4096 = 0x1000이므로 반드시 페이지의 시작 주소의 하위 12 bit를 0x000으로 하도록 하라는 것이다. 이러한 점으로 인해 가상 주소의 하위 12 bit는 해당 주소가 속하는 페이지 내에서의 offset이라고도 볼 수 있기에 page offset이라고 한다. 주소의 상위 bit는 앞선 포스팅에서 살펴 보았듯이 일정 bit씩 쪼개 페이지 테이블에서의 index 값으로 사용된다. 다시 해당 그림을 보면:

sign extension 부분과 하위 offset을 제외한 영역을 4개의 영역으로 나눠 각 부분의 bit 열을 각 단계의 페이지 테이블에서의 offset(index)으로 활용하고 있다는 것을 볼 수 있다. 참고로 sign extension은 16bit, 각 index의 크기는 9bit이다.

 

가상 공간은 이전 포스팅에서 설명했듯이 일정 주소를 경계로 하여 커널 영역과 유저 영역으로 분류된다. pintos외에 다른 운영 체제는 정확히 어떻게 구현되어 있는지는 모르겠으나 pintos는 KERN_BASE (현재 pintos는 0x8004000000)를 기준으로 유저 영역은 각 프로세스마다 별개로 가지고 있는 공간이며, 커널 영역은 모든 프로세스에서 하나의 커널 공간을 공유한다. 커널에서는 유저 영역과 커널 영역 모두 접근 가능하지만, 유저 프로세스는 고유의 유저 영역에만 접근할 수 있다. 각 유저 프로세스는 각자 서로 다른 최상위 테이블을 만들어 CR3 레지스터로 가리키고 있으므로, 다른 유저 프로세스에서 같은 가상 주소로 메모리에 접근한다 할지라도 접근할 수 있는 물리 공간의 영역은 서로 달라지게 된다. 

 

페이지와 대응하는 물리 공간의 page-aligned된 연속된 4096 byte의 공간을 frame(=physical frame)이라고 한다. 페이지와 마찬가지로 frame(후술 프레임)도 하위 12 bit는 frame 내의 offset이 되며, 상위 bit들은 해당 프레임의 frame number를 나타낸다. x86-64는 물리 공간에의 직접 접근은 허가하지 않고 있기에 pintos는 이를 우회해서 접근하는 방식을 사용한다. 이전에도 설명했듯, pintos는 커널 영역 자체가 물리 영역인 것처럼 취급한다. 커널 영역의 첫 번째 페이지는 물리 영역의 첫 번째 프레임이며 두 번째 페이지는 두 번째 프레임... 이런 식으로 대응이 되는 것이다. 때문에 모든 유저 프로세스의 실질적인 내용은 커널 영역 중 일부에 담겨 있다고 보면 된다. 사실 이런 vm 관련된 내용을 알려주고 fork같은 걸 구현하라고 했어야 맞지 않을까 싶은데....

 

---

 

아무튼 이제 페이지와 프레임에 대한 개념이 어느정도 잡혔다. 이번 프로젝트의 목표인 페이지-프레임 매핑을 다시 상기해보자. 매핑을 생성만 하는 것이었다면 지금 구현된 것으로도 충분하다. 그러나 실제로는 지금까지 우리가 고려하지 않았던 여러 변수가 았다. stack 공간이 늘어나 추가적인 공간의 할당이 필요하다거나, 물리 메모리 공간이 부족해 일정 frame을 잠시 디스크(해당 임시 저장 공간을 swap slot이라고 한다)에 저장한다거나, 디스크에 저장된 frame에 접근하려고 할 때 다시 메모리 공간에 불러오는 것 등 여러 상황을 고려해야 한다. 이런 상황에도 정상적으로 프로세스가 실행되어 유저 입장에서는 가상 공간 전체를 사용할 수 있도록 제대로 "환상"을 주도록 하는 것이 이번 프로젝트의 목표이다.

 

여기서 매뉴얼은 각 page를 용도에 따라 분류할 수 있다고 한다. VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE로 나뉘어져 해당 용도에 맞게끔 설계를 해야 한다고 나온다. (VM_PAGE_CACHE 종류는 플젝 4에서 다룰 것이라고 하니 일단 무시하자.) vm 디렉토리 내의 각 파일들 uninit.c, anon.c, file.c는 각 종류의 page의 동작에 맞는 함수를 제공하도록 구현해야 한다. 해당 파일들이 이번 프로젝트에서 주요하게 수정해야 할 파일일 것이다.

 

그래서 구체적으로 해야 할 것이 무엇인지 이제부터 살펴보자. 매뉴얼은 다음의 3개의 데이터 구조를 설계하라고 한다.

 

• page fault 발생 시 해당 page fault에 대응할 수 있도록 필요한 정보를 제공하는 supplemental page table
• 물리 메모리 공간이 부족할 경우 디스크로 쫓아낼 (eviction) frame을 효율적으로 결정하도록 하는 frame table
• 디스크에 임시 저장된 frame들의 공간인 swap slot의 사용 현황을 추적할 수 있도록 하는 swap table

해당 구조들이 이번 프로젝트의 주가 될 것이다. 매뉴얼에 따르면 3개를 각각 따로 구현해도, 하나로 통합해서 관리하는 거대한 구조가 있어도 상관은 없다고 한다. 매뉴얼은 해당 table들의 구현에 사용될 자료구조로는 이미 pintos에 구현되어 있는 것들을 추천한다. 물론 더 복잡한 자료구조일 수록 효율성 증대에 기여를 할 수 있지만 그만큼 구현에 부담을 주기 때문에 추가적인 자료구조 구현은 지양하고 있다. 그러면 선택지가 객관식화되는데,

 

• arrays
• list (list.c)
• bitmap (bitmap.c)
• hash (hash.c)

해당 자료구조를 조합해서 되도록 최대의 효율을 뽑아내는 것이 목적이 될 것이다.

 

---

 

이러한 구조들을 사용해서 궁극적으로 해결해야 할 것은 page fault이다. 프로젝트 2까지는 page fault가 나면 어딘가 잘못된 것이었기에 프로세스를 종료해 주었다. 그러나 이제는 막무가내로 종료시키면 안 된다. 페이지에 대응되는 프레임이 현재는 없더라도, swap slot이나 파일에서 이를 가져올 수 있기 때문이다. 이 때문에 유저 프로세스에 page fault가 발생했을 경우, 대응 후 정상 실행 상태로 복귀시킬 것일지, 아니면 실행을 종료해야 하는지 판단할 수 있도록 수정해야 한다. 자세한 대응 방법은 위의 구조를 만들 때 살펴보도록 하자.

 

page fault의 수정과 더불어서 프로젝트 3에서는 프로젝트 2에 이어서 mmap, munmap system call을 구현하게 된다. 일단 기본적인 페이지 매핑부터 구현한 뒤 후반부에 구현해보도록 하자.

 

---

 

이제 얼추 Introduction에서 살펴볼 만한 주의사항이나 구현 목표는 다 짚어본 것 같다. 다음 포스팅부터는 대략적으로 말로 짚고 넘어간 부분을 코드 단위로 살펴보면서 구체적인 구현 방향을 잡아본다.