Project_3 : Virtual Memory - Memory Management(2)

Implement Supplemental Page Table

Pintos에서 제공하는 supplemental page table은 프로세스 별로 생성되는 별도의 구조체이다.

이는 페이지 테이블(pml4)이 담지 못하는 정보들을 추가로 저장하기 위해 사용된다. 

기존 페이지 테이블은 물리 메모리 매핑 정보를 제공한다. 그런데 하나의 물리 메모리에 여러 가상 주소가 매핑되는 경우가 있을 수 있다. 

해당 경우, 물리 메모리의 값이 변화하였을 때 특정 가상 주소에 심각한 문제가 발생할 수 있다. 

spt에는 물리 메모리가 가지고 있어야 할 데이터가 무엇인지에 대한 정보가 담겨있어 이러한 문제를 해소한다.

또한, spt는 자원을 해제해야하는 경우, 무엇을 해제할지 결정하는 데에도 사용된다. 

 

supplemental page table을 사용하기 위해서는 몇 가지 기본 기능을 구현해야 한다.

그런데 이에 앞서 supplemental page table의 자료구조를 선택해야 한다. 여기서는 해시 테이블(hash table)을 사용하고자 한다.

해시 테이블은 key-value 형식의 자료구조로, 해시 함수를 사용하여 key를 해시 값으로 변환하고 이를 인덱스로 하여 value를 저장한다.

데이터의 삽입, 삭제, 검색 과정이 평균적으로 O(1)의 시간 복잡도를 갖는다.

 

page 구조체의 va는해시 테이블의 key로써인덱스 값(특정 버켓)을 결정하는데 사용된다.

h_elem 변수는 해시 테이블의 value, 즉 특정 버켓에 담겨질 요소를 나타내는 변수로 아래와 같이 page 구조체에 추가해야 한다.

/* include/vm/vm.h */

/*--------------- PROJECT3: Virtual Memory ----------------*/
#include <hash.h>

struct supplemental_page_table {
	struct hash page_table; // spt 자료 구조 : 해시 테이블 
};
/*---------------------------------------------------------*/


struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	struct hash_elem h_elem;
	/*---------------------------------------------------------*/

	// 중략
};

다음으로 supplemental page table(spt)을 초기화하는 함수, supplemental_page_table_init( )를 만들어보자.

아래와 같이 해당 함수 안에 hash_init( ) 함수를 추가해주었다. hash_init( ) 함수는 해시 테이블을 초기화하는 함수로, 

해쉬 값을 계산하는 page_hash( ) 함수와 해시 테이블 버켓의 요소들을 비교하는 page_less( ) 함수를 인자로 받는다.

/* vm/vm.c */

/*--------------- PROJECT3: Virtual Memory ----------------*/
/* Returns a hash of element's data, as a value anywhere in the range of unsigned int */ 
uint64_t page_hash (const struct hash_elem *e, void *aux UNUSED) {
	struct page *p = hash_entry(e, struct page, h_elem);
	return hash_bytes(&p->va, sizeof p->va);
}

/*  Compares the keys stored in elements a and b. 
	Returns true if a is less than b, false if a is greater than or equal to b. 
	If two elements compare equal, then they must hash to equal values. */
bool page_less (const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED) {
	struct page *pa = hash_entry(a, struct page, h_elem);
	struct page *pb = hash_entry(b, struct page, h_elem);
	return pa->va < pb->va; 
}
/*---------------------------------------------------------*/


void supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	hash_init(&spt->page_table, page_hash, page_less, NULL);
	/*---------------------------------------------------------*/
}

다음으로 spt_find_page( ) 함수를 수정해보자. 해당 함수는 인자로 받은 va가 속한 페이지가 spt에 있는지 확인하는 함수이다.

함수 내부를 보면 pg_round_down( ) 함수를 사용하여 va의 오프셋을 0으로 변환하여 page.va에 저장한다.

이는 va가 들어있는 가상 페이지의 시작 주소를 가져오는 것과 같다.

이후, hash_find( ) 함수를 사용하는데, 이를 통해 spt 해시 테이블에 가상 주소에 해당하는 페이지가 존재하는지 확인한다.

없으면 NULL을 반환하고, 있으면 hash_entry( ) 함수를 리턴한다.

/* vm/vm.c */

struct page *spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	/* TODO: Fill this function. */
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	struct page page; 
	page.va = pg_round_down(va); // page boundary에 일치하도록 조정
	struct hash_elem *e;
	e = hash_find(&spt->page_table, &page.h_elem);
	// va가 일치하는 page를 찾지 못한 경우
	if (e == NULL)
		return NULL;
	// va가 일치하는 page를 찾은 경우
	return hash_entry(e, struct page, h_elem);
	/*---------------------------------------------------------*/
}

spt에 새로운 page를 집어넣는 spt_insert_page( ) 함수를 구현해보자.

우선, spt 해시 테이블에 집어 넣으려는 page가 존재하는지 확인해야 한다. 이는 hash_insert( ) 함수를 이용하여 확인할 수 있다.

hash_insert( ) 함수는 해시 테이블 내의 버켓에서 page의 해시 값과 일치하는 인덱스의 버켓에 page를 삽입하고 NULL을 리턴한다.

만약, 해당 해시 값을 가진 요소가 이미 버켓에 있으면 삽입하지 않고 해당 원소를 리턴한다.

/* vm/vm.c */

/* Insert PAGE into spt with validation. */
bool spt_insert_page (struct supplemental_page_table *spt UNUSED, struct page *page UNUSED) {
	/* TODO: Fill this function. */
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	struct hash_elem *e;
	e = hash_insert(&spt->page_table, &page->h_elem);
	// 새로운 page 추가에 실패한 경우 (기존에 동일한 주소값을 가진 page가 존재한 경우)
	if (e != NULL) {
		return false;
	}
	// 새로운 page 추가에 성공한 경우
	return true;
	/*---------------------------------------------------------*/
}

Frame Management

물리 메모리내 프레임 관리를 위해 각 프레임의 정보를 갖고 있는 frame table을 구현해야 한다.

frame table은 일종의 리스트이며, 각 frame은 해당 리스트의 entry가 된다.

이를 구현하기 위해 list형의 frame_table을 선언해주고, 기존 frame 구조체에 list_elem 형의 frame_elem을 추가한다. 

/* vm/vm.c */

/*--------------- PROJECT3: Virtual Memory ----------------*/
static struct list frame_table;
/*---------------------------------------------------------*/

/* include/vm/vm.h */

struct frame {
	void *kva;
	struct page *page;
    /*--------------- PROJECT3: Virtual Memory ----------------*/
	struct list_elem frame_elem;
    /*---------------------------------------------------------*/
};

 

Implement vm_get_frame, vm_claim_page and vm_do_claim_page in vm/vm.c.

 

프로젝트의 요구사항 순서에 맞추어 vm_get_frame( ) 함수를 먼저 구현하고자 한다.

vm_get_frame( ) 함수를 보면 frame을 선언해주고 malloc을 통해 메모리를 할당받는다.

이후, 물리 메모리의 유저 풀에서 페이지를 할당 받고, 리턴 값을(해당 페이지의 커널 가상 주소) frame의 가상 주소에 저장한다. 

만약, 유저 풀에서 페이지를 할당 받지 못하였다면, 페이지가 할당되어 있는 프레임 중에서 방출할 프레임을 찾는다.

해당 과정은 vm_evict_frame( ) 함수를 통해 이루어진다. 방출할 프레임을 찾았다면 해당 프레임의 page를 NULL로 지정한다.

이와 달리 유저 풀에서 페이지를 할당 받았다면, frame_table 리스트에 frame을 삽입하고, page를 NULL로 지정한다.

vm_evict_frame( ) 함수는 내부에서 vm_get_victim( ) 함수를 호출하여 리턴 받은 값을 swap_out 시키는 함수이다.

vm_get_victim( ) 함수는 frame_table 리스트에서 방출할 프레임을 찾는 함수로, 방출 정책에 따라 다양하게 구현할 수 있다.

/* vm/vm.c */

static struct frame * vm_get_frame(void){
	struct frame *frame = NULL;
	/* TODO: Fill this function. */
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	struct frame *frame = (struct frame *)malloc(sizeof(struct frame));

	frame->kva = palloc_get_page(PAL_USER);
	if (frame->kva == NULL){
		frame = vm_evict_frame();
		frame->page = NULL;

		return frame;
	}
	list_push_back(&frame_table, &frame->frame_elem);

	frame->page = NULL;

	ASSERT(frame != NULL);
	ASSERT(frame->page == NULL);
	return frame;
	/*---------------------------------------------------------*/
}


static struct frame * vm_evict_frame(void){
	struct frame *victim UNUSED = vm_get_victim();
	/* TODO: swap out the victim and return the evicted frame. */
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	swap_out(victim->page);
	/*---------------------------------------------------------*/
	return NULL;
}


static struct frame *vm_get_victim(void){
	struct frame *victim = NULL;
	/* TODO: The policy for eviction is up to you. */
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	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;
	/*---------------------------------------------------------*/
}

다음으로 vm_claim_page( ), vm_do_claim_page( ) 함수를 구현해보도록 하겠다.

vm_claim_page( ) 함수는 현재 실행되고 있는 프로세스의 spt에서 인자로 받은 가상 주소 va가 포함된 페이지를 찾는 함수이다.

이는 내부에서 spt_find_page( ) 함수 호출을 통해 이루어지며, 페이지를 찾으면 vm_do_claim_page( ) 함수를 호출하고

아니라면 false를 리턴한다.

vm_do_claim_page( ) 함수는 인자로 받은 page와 새로운 frame을 연결하는 함수이다.

자세히 살펴보면 함수 내부에서 vm_get_frame( ) 함수를 호출하여 새로운 frame을 만든다.

이후, 해당 frame의 page 변수를 인자로 받은 page로 설정하고,

인자로 받은 page의 frame 변수를 vm_get_frame( ) 함수 호출을 통해 만든 frame으로 설정한다.

이후 install_page( ) 함수를 호출, 유저 가상 메모리 페이지와 커널 가상 메모리 페이지의 매핑을 페이지 테이블(pml4)에 더한다.

만약 매핑이 성공이라면 swap_in( ) 함수를 호출하고 아니라면 false를 리턴한다.

/* vm/vm.c */

/* Claim the page that allocate on VA. */
bool vm_claim_page(void *va UNUSED){
	struct page *page = NULL;
	/* TODO: Fill this function */
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	page = spt_find_page(&thread_current()->spt, va);

	if (page == NULL) {
		return false;
	}
	return vm_do_claim_page(page);
	/*---------------------------------------------------------*/
}


/* Claim the PAGE and set up the mmu. */
static bool vm_do_claim_page(struct page *page){
	struct frame *frame = vm_get_frame();

	/* Set links */
	frame->page = page;
	page->frame = frame;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	/*--------------- PROJECT3: Virtual Memory ----------------*/
	if (install_page(page->va, frame->kva, page->writable)) {	// 유저페이지가 이미 매핑되었거나 메모리 할당 실패 시 false
        return swap_in(page, frame->kva);
    	}
    	return false;
	/*---------------------------------------------------------*/
}