pintos - project3(Memory Management) 수도 코드
해당 포스팅은 핀토스 프로젝트를 구현하는것에 도움을 주기위한 포스팅입니다.이 글을 읽으시는 분들은 VM 과제의 흐름이 어떻게 흘러가는지도 알아야 아래의 구현이 조금 더 쉬워진다고 생각합니다.전 개인적으로 구현을 하고 나서 흐름을 파악하는 방법으로 해당 과제를 진행하였습니다.
Memory Management
주어진 gitbook을 읽어보면 저희가 가장 먼저 구현해야할 과제는 Supplemental Page Table입니다.기존에 핀토스에서는 pml4라는 페이지 테이블을 제공을 하고 있지만 가상메모리를 구현하기에는 그 역할이 부족합니다.pml4의 경우 주어진 va에 대한 실제 kva(즉,물리메모리)로의 단순한 변환만을 해주고 있습니다.즉,저희가 사용할 페이지라는 구조체의 정보에 대한 어떠한 정보도 가지지 않고 있습니다.그래서 SPT는 각각의 페이지에 대한 정보를 추가적으로 보충해주는 역할을 수행합니다.
깃북에 따르면 SPT의 목적은 최소한 두가지로 나누어집니다.첫번째,페이지 폴트가 발생했을 경우 해당 페이지 폴트가 발생한 페이지를 찾을 수 있고,저희가 찾은 페이지가 가지고 있는 여러가지 데이터들에 접근하기 위한 목적입니다.두번째로 커널이 프로세스(쓰레드)를 종료시킬 때,해당 SPT를 참고하여 어떠한 데이터들이 할당 해제되어야 할지 결정합니다. 구현을 다하고 나서 위 목적들을 읽어보니 다음과 같이 이해할 수 있었습니다.페이지 폴트가 일어난 가상 주소(va)를 포함하는 페이지 구조체가 있는데 이 구조체에 접근해 다양한 데이터들을 사용하기 위해 사용하는구나라고 이해할수 있었습니다.
본격적으로 SPT를 구현하기 전에 SPT를 어떤 자료구조로 구현할지를 정해야합니다.이번 글에서는 정글 알고리즘 주간에서는 다루지 않은 자료구조인 해시 테이블을 통해 구현합니다.
Implement Supplemental Page Table
- 해당 챕터는 모두 vm.c의 파일을 수정합니다.
void supplemental_page_table_init (struct supplemental_page_table *spt);
- 첫번째로 저희가 구현해야할 함수입니다.이 함수는 사실상 해시 테이블을 init해줘야 하는 역할을 수행하기에 깃북-appendix의 해시 테이블 부분을 자세히 읽어보시길 바랍니다.핀토스에서 자체적으로 해시테이블 자료구조를 제공해주기에 미리 구현되어 있는 함수들을 잘 활용해서 구현하면 됩니다.
struct page *spt_find_page (struct supplemental_page_table *spt, void *va);
- 본격적으로 프로젝트3에서 자주 활용되는 함수들을 구현합니다.
- 위 함수는 기본적으로 SPT에 존재하는 페이지를 찾아줍니다.
- 인자를 바라보면 spt와 저희가 찾을 페이지의 va가 주어집니다.
- SPT의 value에는 페이지가 아닌 페이지 구조체의 멤버인
hash_elem이 들어갑니다.즉,간접적으로 page를 찾아올 수 있습니다.(이전 과제까지의list_entry를 생각하시면 됩니다) - 저희는 하나의 더미 페이지를 할당시킨후,해당 페이지의 va를 주어진 인자로 설정한 다음 더미 페이지의
hash_elem을 통해 저희가 찾으려는 페이지를 검색하였습니다.대부분 구현되어있는 해시 함수들을 통해 해결가능합니다.
bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);
- SPT에 인자로 들어온 페이지를 삽입시키는 기능을 합니다.
- 리턴 값이 bool형임을 유의하고 구현하시면 됩니다.
이렇게 3가지 함수를 구현하면 깃북이 준 첫번째 미션을 해결한것입니다.아쉽게도 구현이 제대로 되었는지 확인할 수 있는 방법(구글링 제외)이 없습니다.스스로를 믿고 다음 챕터로 넘어갑시다.
Frame Management
지금부터 본격적으로 머리가 아픕니다.구현을 하기 앞서 프레임과 페이지에 대한 이론적 개념을 학습해야합니다.당연히 이론적으로 공부하시겠지만 헷갈리는 개념을 몇개를 적어두고 구현을 넘어가겠습니다.아래 항목들은 핀토스 운영체제를 가정으로 성립합니다.
- Frame 구조체의 kva는 물리메모리와 1대1로 매핑된다.
- 가상 메모리는 크게 유저 영역과 커널 영역으로 나뉘고, 커널 영역은 User pool과 Kernel pool로 나뉜다.또한 커널영역은 물리 메모리와 1대1로 매핑된다.
palloc_get_page(PAL_USER)는 커널영역의 User-Pool 영역에서 물리 메모리를 할당하여 kva값을 반환해줍니다.- Page 구조체의 va + KERNBASE는 kva라는 공식이 성립됩니다.
우선 해당 챕터는 Frame을 관리하는 코드들을 작성해야합니다.함수를 구현하기 전에 먼저 아래와 같이 프레임 구조체를 관리하는 하나의 Frame-Table을 생성합니다.이는 앞서 자주 사용한 리스트를 통해 구현합니다.
//vm.c
struct list frame_table;
위 리스트는 전역적으로 선언하였으며,어떠한 함수에서는 이를 초기화시켜줘야할것입니다.
또한 해당 리스트에 frame 구조체를 담기위해 list_elem을 Frame 구조체 안에 선언해줍니다.
//vm.h
struct frame {
void *kva; //kernel virtual address
struct page *page;
struct list_elem frame_elem;
};
본격적으로 주어진 함수를 구현해봅시다.
static struct frame *vm_get_frame (void);
- 해당 함수는
palloc_get_page(USER_PAL)를 호출하여 실제 물리메모리의 User Pool로부터 물리 프레임의 주소를 하나 반환받습니다. - 즉,반환받은 주소를 Frame 구조체에 할당해줘야합니다.
- 만약 User Pool로부터 정상적으로 물리 프레임 주소를 할당받지 못할 경우에 대한 예외처리 또한 해줘야합니다.깃북에서는 이러한 경우
PANIC("todo")로 처리하고 넘어가지만 저희는vm_evict_frame()를 호출해 통해 기존의 물리메모리에 존재하는 프레임과 연결된 페이지 한개를 swap-out 시키고 해당 프레임을 반환시켜 줍니다. - 이후 할당 받은 프레임을 프레임 테이블에 넣어주고 추후 관리될수 있도록 합니다.
bool vm_claim_page (void *va);
- 해당 함수는 아래에 구현할
do_claim...함수의 wrapper함수라고 생각하셔도 됩니다. - 이 함수에서는 물리 프레임과 연결을 할 페이지를 SPT를 통해서 찾아준뒤,
do_claim...함수를 호출하면 됩니다. - 주어진 va,즉 페이지의 가상메모리 주소를 통해 페이지를 얻어옵니다.
bool vm_do_claim_page (struct page *page);
- 실질적으로 Frame과 인자로 받은 Page를 연결해주는 역할을 수행합니다.
- 그러면 우선적으로 해당 페이지가 이미 어떠한 물리 주소(kva)와 미리 연결이 되어 있는지 확인해줘야합니다.
- 이후 미리 연결된 kva가 없을 경우,해당 va를 kva에 set해줍니다.
- 최종적으로 페이지와 프레임간의 연결이 완료되었을 경우,
swap_in()을 통해 해당 페이지를 물리 메모리에 올려줍니다. - 페이지가 물리주소와 연결이 되어있는지 확인할때는 핀토스에서 주어진 Page Table인 pml4를 사용합니다.
- 페이지와 관련된 함수를 모두 찾는다는 생각으로 코드를 뒤지다보면 어떠한 함수가 보이실겁니다.
이까지 진행하시면 깃북에서 하라는 Memory Management의 모든 단계를 전부 진행하신것입니다.하지만 저희도 과제를 구현할때 막힐때마다 구글링을 통해 참조를 하였는데 대부분 이 단계에서 앞서 말씀드린 희생페이지를 선택하는 알고리즘을 구현을 하였기에 저희도 해당 방식을 따라가겠습니다.
static struct frame *vm_evict_frame (void);
- 해당 함수는
vm_get_victim를 호출해서 하나의 프레임을 받아오고 이후 해당 프레임을 swap-out을 해주는 역할을 수행합니다. - 기본적으로 구현된 코드에서 swap-out을 수행하는 코드만 구현해주시면 됩니다.
- 앞서도 언급했지만 swap-out의 대상은 프레임이 아닌 프레임과 연결된 페이지입니다.
static struct frame *vm_get_victim (void);
- 실질적으로 희생될 한개의 프레임을 선택하는 함수입니다.
- 전역적으로 선언한
list_elem을 사용하여 Clock 알고리즘을 사용했습니다. - 우선적으로 구현을 하고싶은 분들은 FIFO를 사용해서 간단히 사용하셔도 됩니다.
- FIFO의 경우 아래 코드를 사용해서 Frame을 선택할 수 있습니다.
list_pop_front(&frame_table);
- 만약 Clock 알고리즘을 사용하실 분들이면
pml4_is_accessed()함수와pml4_set_accessed()를 사용하셔셔 해당 페이지의 access 비트가 어떻게 설정되어 있는지 확인하고 구현하시면 됩니다.
여기까지 구현하시면 첫번째 단계인 Memory Management를 끝마치게 됩니다.마찬가지로 아직까지 내 코드를 어떻게 확인할 수 있는 방법이 존재하지 않습니다.