Project 3 : Memory Management 구현
우리가 무엇을 하는가?
PintOS는 메모리의 가상 및 물리적 매핑을 관리하기 위한 page table(pml4)이 있다. 하지만 이것만으로는 충분하지 않다. page fault 및 resource management를 처리하기 위해 각 page에 대한 추가 정보를 저장할 수 있는 supplementary page table이 필요하다.
supplemental_page_table 구현
supplemental_page_table을 hash table을 사용해서 구현해보자.
hash 구조체는 다음과 같다.
// include/lib/kernel/hash.h
/* Hash table. */
struct hash {
size_t elem_cnt; /* Number of elements in table. */
size_t bucket_cnt; /* Number of buckets, a power of 2. */
struct list *buckets; /* Array of `bucket_cnt' lists. */
hash_hash_func *hash; /* Hash function. */
hash_less_func *less; /* Comparison function. */
void *aux; /* Auxiliary data for `hash' and `less'. */
};hash table은 key와 value로 데이터를 저장하는 자료구조이다. O(1)의 시간복잡도로 데이터를 search 할 수 있는데 hash table에서는 각각의 key값에 hash함수를 적용해 배열의 고유한 index를 생성하고 이 index값을 활용하여 값을 search하기 때문이다. 여기서 실제 값이 저장되는 장소를 bucket이라고 한다.
구현을 시작하자.
// include/vm/vm.h
#include <hash.h>
struct supplemental_page_table {
struct hash spt_hash; // project 3
};struct hash를 사용하니까 hash를 어떻게 초기화하는지부터 살펴보자.
hash_init() 은 다음과 같다.
/* Initializes hash table H to compute hash values using HASH and
compare hash elements using LESS, given auxiliary data AUX. */
bool
hash_init (struct hash *h,
hash_hash_func *hash, hash_less_func *less, void *aux) {
h->elem_cnt = 0;
h->bucket_cnt = 4;
h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
h->hash = hash;
h->less = less;
h->aux = aux;
if (h->buckets != NULL) {
hash_clear (h, NULL);
return true;
} else
return false;
}hash_init 함수에 인자로 hash_hash_func *hash와 hash_less_func *less가 존재하는데, 처음에 봤을 때는 굉장히 생소했다. 보통은 함수에는 인자들이 들어오고, 따라서 int나 void 형으로 설정된 인자들이 들어오게 되는데, 이 친구들은 prototype으로 선언된 함수의 모양이 들어와야 하는 함수 포인터들이다.
초기화할 때 사용되는 함수들이므로 구현해주자.
// vm/vm.c
// project 3
// page p에 대한 hash value를 return해줌 (hash 값을 구해주는 함수의 pointer)
unsigned page_hash(const struct hash_elem *p_ , void *aux UNUSED){
const struct page *p = hash_entry(p_, struct page, hash_elem);
return hash_bytes(&p->va, sizeof p->va);
}
// page a가 page b를 앞서면 return true
bool page_less(const struct hash_elem *a_, const struct hash_elem *b_, void *aux UNUSED){
const struct page *a = hash_entry(a_, struct page, hash_elem);
const struct page *b = hash_entry(b_, struct page, hash_elem);
return a->va < b->va;
}여기서 hash_entry() 함수는 hash element인 hash_elem에 대한 pointer를 hash_elem이 포함된 구조에 대한 pointer로 변환하는 함수다.
supplemental page table을 hash table로 구현하기로 했기 때문에 hash_init()을 통해 초기화를 진행한다.
/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
hash_init(&spt->pages, page_hash, page_less, NULL);
}다음으로 spt에서 사용하는 기능들을 구현하자.
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
/* TODO: Fill this function. */
// project 3
struct page* page = (struct page*)malloc(sizeof(struct page)); // dummy page 생성
struct hash_elem *e;
// va가 가리키는 가상 page의 시작 포인트(offset이 0으로 설정된 va) 반환
page->va = pg_round_down(va); // Round down to nearest page boundary.
// hash에서 hash_elem과 같은 요소를 검색해서 발견하면 발견한 element 반환, 아니면 NULL반환
e = hash_find(&spt->pages, &page->hash_elem);
free(page);
// 성공시 page 반환, 실패시 NULL 반환
return e != NULL ? hash_entry(e,struct page,hash_elem) : NULL;
}주어진 supplemental page table에서 va에 해당하는 struct page를 찾는다. 실패시 NULL반환
현재 logic은 dummy page를 malloc()으로 받아와서, 그 page의 vm이라는 member로 va 의 offset을 지운값을 넣어준다. 그 후에 hash_find()함수로 hash_elem과 같은 요소가 있는지 hash로 검색하고 발견한 element를 반환해준다. 이 때 dummy page는 free() 해준다. 그 다음 hash_entry() 함수로 hash_elem이 포함된 page를 찾아서 반환한다. (실패시 NULL 반환)
굳이 dummy page를 생성하는 이유는 dummy page를 생성하면 거기에 hash_elem이 있고, 이걸 통해서 우리가 받아온 va(offset을 지운)로 접근하기 위해서이다.
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
struct page *page UNUSED) {
return insert_page(&spt->pages, page); // project 3
}struct page를 지정된 spt에 삽입. 이 함수에서 spt에 va가 있는지 없는지 check해야함. check는 insert_page 안에 hash_insert에서 확인해주는 것 같다.
// vm/vm.c
bool insert_page(struct hash *pages, struct page *p){
if(!hash_insert(pages, &p->hash_elem))
return true;
else
return false;
}
bool delete_page(struct hash *pages, struct page *p){
if(!hash_delete(pages, &p->hash_elem))
return true;
else
return false;
}page에 대한 insert, delete도 구현해준다.
frame management
// include/vm/vm.h
struct frame {
void *kva; // kernel virtual address
struct page *page;
// project 3
struct list_elem frame_elem;
};frame list로 관리하기 위해서 frame_elem을 frame 구조체에 넣어주었다.
GITBOOK에서는 그 다음 순서로 vm_get_frame() 함수를 구현하라고 한다.
함수에서 사용되는 전역변수를 vm.c에 정의하고 시작한다.
// vm/vm.c
struct list frame_table;// vm/vm.c
static struct frame *
vm_get_frame (void) {
// project 3
struct frame *frame = (struct frame*)malloc(sizeof(struct frame));
//user pool에서 frame 가져오고 kernel virtual address(kva) return해서 frame에 넣어줌
frame->kva = palloc_get_page(PAL_USER);
if(frame->kva == NULL) // frame 에서 가용한 page가 없다면
{
frame = vm_evict_frame(); // 쫓아냄
frame->page = NULL;
return frame;
}
list_push_back(&frame_table,&frame->frame_elem); // frame table에 frame_elem을 넣음(맨끝에)
frame->page = NULL;
ASSERT (frame != NULL);
ASSERT (frame->page == NULL);
return frame;
}이 함수는 palloc()으로 frame을 가져오는데, 사용가능한 page가 없다면 frame을 제거해서 memory를 확보하는 역할이다.
palloc_get_page(PAL_USER)를 하게되면 user pool에서 frame을 가져오게 되는데, 이 때 가용한 frame이 없다면 NULL을 반환하게 된다. 그러면 frame을 쫓아내고 그 frame을 return한다. 가용한 frame이 있다면 전역변수로 선언한 frame table에 frame_elem을 list_push_back() 함수로 넣어준다. 그 후에 frame을 return한다.
frame->page = NULL은 정확히 무슨의미일까? → 새 frame을 가져왔으니 page의 멤버를 초기화하는 의미.
함수 중간에 vm_evict_frame()으로 page를 evict(쫓아냄)하고 해당되는 frame을 return시키는 함수가 있다. 그 함수를 작성하자.
static struct frame *
vm_evict_frame (void) {
// project 3
struct frame *victim = vm_get_victim ();
/* TODO: swap out the victim and return the evicted frame. */
swap_out(victim->page);
return victim;
}쫓아낼(evict) page를 victim이라고 부르는데, 그 victim을 어떻게 찾을까?
vm_get_victim()이라는 함수로 찾는데 그걸 구현해보자.
이것을 위해 전역변수로 start를 선언한다.
struct list_elem* start;// vm/vm.c
static struct frame *
vm_get_victim (void) {
struct frame *victim = NULL;
/* TODO: The policy for eviction is up to you. */
// project 3
struct thread *curr = thread_current();
struct list_elem *e = start;
for(start = e; start != list_end(&frame_table); start = list_next(start)){
victim = list_entry(start, struct frame, frame_elem);
if (pml4_is_accessed(curr->pml4, victim->page->va))
pml4_set_accessed(curr->pml4, victim->page->va,0);
else
return victim;
}
for(start = list_begin(&frame_table); start != e; start = list_next(start)){
victim = list_entry(start, struct frame, frame_elem);
if(pml4_is_accessed(curr->pml4, victim->page->va))
pml4_set_accessed(curr->pml4, victim->page->va, 0);
else
return victim;
}
return victim;
}위 코드를 살펴보면 page table entry가 최근에 액세스된 경우(즉, pml4_is_accessed에서 true가 반환되면) pml4_set_accessed 함수에서 accessed bit을 0으로 설정한다. 그리고 만약에 pml4에 page table entry가 없는 경우 (pml4_is_accessed에서 false 반환) 바로 그 frame이 victim(쫓겨날 대상)이 된다. 그리고 그 대상이 start에 기록된다.
그리고 list의 맨 처음(list_begin)부터 한번 더 for문을 돌리면서 victim을 찾아낸다.
이 victim을 찾는 과정을 여러가지로 구현할 수 있지만 여기서는 clock algorithm으로 구현했다.
vm_claim_page를 구현해보자.
// vm/vm.c
/* Claim the page that allocate on VA. */
bool
vm_claim_page (void *va UNUSED) {
struct page *page;
/* TODO: Fill this function */
// project 3
page = spt_find_page(&thread_current()->spt,va);
if(page == NULL){
return false;
}
return vm_do_claim_page (page);
}이 함수는 page에 va를 할당하도록 claim을 하는 것이다.
claim이란 유저 virtual memory 공간의 page를 physical memory에 할당하는 것이다.
함수의 로직을 살펴보면 va를 가진 page를 spt에서 찾아서 그 page에 대해서 vm_do_claim_page(page)를 진행한다.
vm_do_claim_page() 함수를 구현해보자.
// vm/vm.c
static bool
vm_do_claim_page (struct page *page) {
struct frame *frame = vm_get_frame (); // frame을 가져온다.
/* Set links */
frame->page = page;
page->frame = frame;
/* TODO: Insert page table entry to map page's VA to frame's PA. */\
// project 3
if(install_page(page->va, frame->kva, page->writable)){
return swap_in(page, frame->kva);
}
return false;
}대략적인 동작은 다음과 같다. frame을 가져와서 frame과 page의 link를 설정한다. 그리고 pml4_set_page()로 프로세스의 pml4에 페이지 가상 주소와 프레임 물리 주소를 서로 매핑한 결과를 저장한다.
install_page() 함수는 user virtual address(UPAGE)에서 kernel virtual address(KPAGE)로의 mapping을 page table에 추가해주는 함수다(pml4 mapping 진행).
인자로 받는 writable이 true면 user process가 page를 수정할 수 있고, 그렇지 않으면 read-only이다. KPAGE는 user pool에서 가져온 page여야 한다. UPAGE가 이미 mapping되었거나, 메모리 할당이 실패하면 false를 반환한다. 성공하면 true를 반환한다. 성공시에 swap_in()함수가 실행된다.