PintOS Project 3 : Virtual Memory (1) - supplemetal page table 보조 페이지 테이블

PintOS  세 번째 과제에서는 가상 메모리를 다루는 것이다. 

그 중 가장 처음에 해야할 것은 보조 페이지 테이블(supplemetal page table)을 만드는 것이었다.

 

보조 페이지 테이블을 spt라고 하겠다. 

spt는 demand page할 때 pml4에 매핑을 하기 위해 또는 물리 메모리에 load 하기 위해 필요한 임시 거처라고 할 수 있다.

spt는 다양한 자료구조로 구성할 수 있는데 이전에 스레드를 관리했던 연결리스트, 배열, 해시, 비트맵 등이 있겠지만 이번에는 해시테이블 자료구조를 사용하고 체이닝 기법으로 해시값이 같은 페이지를 관리하도록 spt 를 구성했다. 

해시 테이블 장점 
시간 복잡도가 O(1) 이므로 빠른 검색, 삽입, 삭제가 가능하다. 또한 배열의 인덱스가 아닌 것으로 탐색을 할 수 있다.  프로젝트의 경우 hash_elem으로 page 를 탐색할 수 있다.

 

// spt 자료구조
struct supplemental_page_table {
	struct hash hash_table;
};


struct page{
		...
struct hash_elem hash_elem;
		...
}

// 해시 함수 : 페이지의 내용을 bytes로 리턴함

uint64_t hash_func(const struct hash_elem *e, void *aux) {
    const struct page *p = hash_entry(e, struct page, hash_elem);

    return hash_bytes(&p->va, sizeof(p->va));
}


// 해시 함수로 계산한 bytes를 spt에 오름차순으로 정렬함

bool less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux) {
    const struct page *pa = hash_entry(a, struct page, hash_elem);
    const struct page *pb = hash_entry(b, struct page, hash_elem);

    return pa->va < pb->va;
}

 

// spt 초기화
void supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->hash_table, hash_func, less_func, NULL);
}

 

 

spt를 초기화 한 후, spt_insert_page 함수를 통해 page의 hash_elem을 spt->hash_table에 추가한다.