Pintos Project3 - Memory Management

과제 개요

Pintos는 pml4 라는 메모리를 효율적으로 사용하기 위해 가상 및 물리적 매핑을 관리하는 페이지 테이블이 있다.
그러나 이것으로 충분하지 않고 page fault 발생과 자원 관리를 위해서
각각 페이지에 대한 추가 정보를 들고 있는 SPT(Supplementary page table)가 필요하다.

Supplemental Page Table(SPT)

• Page fault시 커널이 SPT에서 오류가 발생한 가상 페이지를 조회해서 어떤 데이터가 있는지를 확인
• 프로세스가 종료시 커널이 SPT를 참조하여 어떤 리소스를 free 할 것인지를 결정한다.

Supplemental page table 구현 방법

Pintos에서 권장하는 테이블을 구성하는 방법 아래와 같이 총 4가지가 있고 장단점은 다음과 같다.
1. 배열(array) - 가장 구현이 간단하나 공간복잡도가 커서 메모리 용량을 낭비한다.
2. 연결리스트(linked list) - 연결리스트도 구현이 비교적 간단하지만 일일이 확인하면서 찾아야 하기 때문에 시간 복잡도 O(N)으로 낭비가 크다.
3. 해시 테이블(Hash table) - (Key, Value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있는 자료구조이다.
4. 비트맵(Bitmap) - 정보를 비트에 저장하는 구조이다. 구분해야 할 자료가 많지 않을 때는 효율적이지만 구분해야 할 자료가 많으면 많을수록 복잡해진다.
이 중에서 해시 테이블(Hash table)을 이용하여 구현할 것이다.

Hash Table

해시 테이블은 Key값에 해시함수를 적용해서 나온 output인 Hash(정수 값으로 나옴)를
해시 테이블의 전체 배열의 크기인 Capacity로 나눠서(모듈러연산) 나온 나머지로 배열의 고유한 index를 생성한다.
예를 들면 010-2222-2222이라는 key값을 해시함수에 넣어서 202라는 Hash값이 나온다고 하면
전체 배열의 크기를Capacity 8로 정했다면 모듈러 연산(%8)해서 나온 나머지는 2가 된다. 이것이 해시 테이블의 고유한 index값이 된다. 이러한 고유한 공간을 bucket 혹은 slot 이라고 한다.

그러나 이 방식에 문제가 하나가 있는데 다른 key값을 해쉬함수에 넣었을 때 동일한 값이 나오면 같은 공간에 어떻게 여러개의 데이터를 저장할 것인지에 대한 문제가 발생한다.
이러한 문제를 해결하기 위해서는 비어있는 다른 주소를 활용하는 개방주소법 과 동일한 bucket에 대해 추가적인 자료구조를 이용(Linked list, Self-Balancing Binary Search Tree 등등)해서 Chaining 방식으로 해결한 분리 연결법이 있다.

SPT 구현사항

lib/kernel/hash.c

struct hash_elem *
hash_find (struct hash *h, struct hash_elem *e) {
	// project3
	return find_elem (h, find_bucket (h, e), e); // 찾으면 해당 hash_elem을 반환하고 못찾으면 NULL 반환
}

1. 찾고자 하는 hash_elem 찾는 함수 수정

static struct list *
find_bucket (struct hash *h, struct hash_elem *e) {
	// project3
    // hash()로 찾은 해시 값(hash_bytes)과 bucket_cnt - 1개를 bit 연산하여 해당 요소가 들어있는 인덱스를 찾고
	size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1); 
	return &h->buckets[bucket_idx]; // SPT의 어떤 buckets인지를 반환
}

2. SPT내에 어떤 bucket인지 알려주는 find_bucket 함수 수정

---

include/vm/vm.h

struct supplemental_page_table {
    // project3
	struct hash spt_hash; // SPT 테이블로 hash로 관리하기 추가
};

1. hash table을 사용하기 때문에 hash 자료구조를 추가해준다.

struct page {
	...
	/* Your implementation */
    // project3
	struct hash_elem hash_elem; // hash_elem으로 page를 찾아서 va로 접근
	bool writable; // 해당 page가 writable 가능한지를 저장
    ...    
	};
};

2. page 구조체에 자신이 속한 해시 테이블에 연결해주는 해시 테이블 요소인 hash_elem 추가

struct frame {
	void *kva;
	struct page *page;
    // project3
	struct list_elem frame_elem; // 전역변수로 들어가는 frame table의 요소인 frame elem 추가
};

3. 전역 변수로 들어가는 frame table의 요소인 frame_elem 추가

...
//project 3 
unsigned page_hash(const struct hash_elem *p_, void *aux UNUSED);
bool page_less(const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED);
bool insert_page(struct hash *pages, struct page *p);
bool delete_page(struct hash *pages, struct page *p);

4. 추가적으로 구현에 필요한 함수의 원형 추가

---

vm/vm.c

// project3
struct list frame_table; // frametable을 리스트로 관리하기 위해 전역 변수 선언
struct list_elem* start; // 쫓아낼(evict) page를 찾기 위해 사용하는 전역변수

1. frametable을 리스트로 관리하기 위해 전역 변수를 선언해주고
2. frame이 꽉 찼을 때 마지막으로 쫓아낸 위치값을 저장하는 start 전역 변수 선언

/* Find VA from spt and return page. On error, return NULL. */
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));
	// 1. 임시 page를 만든다.
	struct hash_elem *e;
    
	/*
    	2. 인자로 전달받은 va가 가리키는 page 시작 주소를(BITMASK로 offset은 0으로 설정된) 
        반환하여 임시 page->va 담아준다.
    */ 
	page->va = pg_round_down(va); 
    
	// 3. SPT에서 hash_elem과 같은 요소가 있으면 hash_elem을 리턴 아니면 NULL 리턴
	e = hash_find(&spt->spt_hash, &page->hash_elem); 
	free(page);
    
	// 4. 인자로 받은 va로 찾은 hash_elem이 page내 존재하면 page 반환, 아니면 NULL 반환
    return e != NULL ? hash_entry(e,struct page,hash_elem) : NULL; 
}

SPT내에 인자로 받은 va가 있는지를 찾는 함수. SPT내에 있다면 그 page를 리턴한다.

/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	int succ = false;
	/* TODO: Fill this function. */
	// project 3
	return insert_page(&spt->spt_hash, page);
}

// SPT내에 인자로 주어진 page 내의 hash_elem이 없는지 확인하고 삽입한다.
bool insert_page(struct hash *pages, struct page *p){
	// SPT에 hash_elem을 넣을 수 있다는 것은 찾아서 넣으려는 요소가 내부에 없다(old == NULL)라는 말이다.
    if(!hash_insert(pages, &p->hash_elem)) 
        return true;
    else
        return false;
}

SPT내에 요청한 page의 hash_elem이 없다면 SPT내에 넣는 함수

/* Evict one page and return the corresponding frame.
 * Return NULL on error.*/
static struct frame *
vm_evict_frame (void) {
	struct frame *victim UNUSED = vm_get_victim ();
	/* TODO: swap out the victim and return the evicted frame. */
	// project 3
	swap_out(victim->page);
	return victim;
}

vm_evict_frame 함수는 frame 공간을 디스크로 내리는 swap out을 진행하는 함수이다.

/* Get the struct frame, that will be evicted. */
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;
    
	// 최근에 방출된 frame_table의 위치부터 탐색 해야되기 때문에 첫번째 for문 사용
	for(start = e; start != list_end(&frame_table); start = list_next(start)){ 
        victim = list_entry(start, struct frame, frame_elem);
        // page table entry가 최근에 액세스된 경우 (pml4_is_accessed에서 true반환 시)
        if (pml4_is_accessed(curr->pml4, victim->page->va)) 
        	// 함수에서 accessed bit을 1-> 0으로 설정
            pml4_set_accessed(curr->pml4, victim->page->va, 0); 
        
        else // accessed bit가 0이면 쫓겨날(victim)대상이 된다.
            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;
}

실제로 물리 frame에서 해당 정보를 지우는 건 vm_get_victim()에서 처리하고
victim을 찾는 방식은 clock 알고리즘으로 구현되어있다.
최근에 방출된 frame_table의 위치부터 탐색 해야되기 때문에
그 위치를 저장한 값을 전역변수 start로 저장했었고 그 위치부터 첫번째 for문으로 쫓아낼 대상을 찾는다.
그럼에도 불구하고 쫓아낼 수 없는 경우가 생길 수도 있기 때문에
전체적으로 한번 더 탐색해서 쫓아낼 대상을 찾는 두번째 for문을 실행하게 된다.

/* palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/
static struct frame *
vm_get_frame (void) {
	/* TODO: Fill this function. */
	// project 3
	struct frame *frame = (struct frame*)malloc(sizeof(struct frame));
    // user pool에서 커널 가상주소 공간으로 1page 할당하고 frame의 kva(kernel virtual address)에 넣는다
	frame->kva = palloc_get_page(PAL_USER); 

	if(frame->kva == NULL) // frame에서 가용할 수 있는 공간이 없다면
	{
		frame = vm_evict_frame(); // 쫓아낼 frame을 받음
		frame->page = NULL;
		return frame;
	}
	list_push_back(&frame_table,&frame->frame_elem); // frametable에 frame_elem을 넣음(맨끝에)
	frame->page = NULL;

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

vm_get_frame은 palloc_get_page 함수로 사용 가능한 frame을 가져온다.
사용가능한 page가 없다면 frame을 제거해서 memory를 확보하는 함수이다.

/* Claim the page that allocate on VA. */
bool
vm_claim_page (void *va UNUSED) {
	struct page *page = NULL;
	/* 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);
}

/* Claim the PAGE and set up the mmu. */
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. */
	// page에 선언한 writable 값의 유무에 따라서 swap_in 실행
	// install_page 실행시 pml4_get_page()가 NULL이고, 
    // pml4_set_page()에서 writable의 값을 넣어서 true일 경우 swap_in 가능
	if(install_page(page->va, frame->kva, page->writable)){
		return swap_in(page, frame->kva);
	}
    return false;
}

vm_claim_page 함수로 va를 가진 page가 SPT 내에 있다면
vm_do_claim_page 함수로 virtual memory 공간의 page를 physical memory에 할당한다.
frame을 가져와서 frame과 page의 서로 연결 해준다.
install_page 함수는 유저 가상 주소(UPAGE)에서 커널 가상 주소(KPAGE)로의 mapping을 page table에 추가함
인자로 받는 writable이 true면 user process가 page를 수정할 수 있고 그렇지 않으면 read-only
KPAGE는 user pool에서 가져온 page여야 한다.
UPAGE가 이미 mapping되었거나 메모리 할당이 실패하면 false를 반환한다.
성공하면 true를 반환하고 swap_in함수가 실행된다.

/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->spt_hash, page_hash, page_less, NULL);
}

SPT를 hash table로 구현하기 때문에 hash_init()을 통해 초기화한다.
hash_init시에 필요한 추가적인 함수들은 아래와 같이 추가한다.

// hash_elem가 있는 page의 va로 hash 값을 return해줌
unsigned page_hash(const struct hash_elem *p_ , void *aux UNUSED){
	const struct page *p = hash_entry(p_, struct page, hash_elem);
	// hash_elem만 알고 있으니 hash_entry()로 hash_elem이 있는 해당 페이지의 주소를 가져오고
	return hash_bytes(&p->va, sizeof p->va); // page의 va에 암호화된 해시 값 리턴
}

// 두 page 요소에 대해 page의 주소값을 비교하는 함수, 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;
}