PintOS Virtual Memory
이번 과제는 OS 상에서 가상 메모리를 구축하고 활용할 수 있도록 하는 것을 목표로 한다.
이를 위해서 page, frame을 정의하고 가상 메모리와 물리 메모리를 mapping 하는 등의 작업이 필요하다.
| page | frame |
|---|---|
| virtual memory | physical memory |
원활한 과제 수행을 위해 gitbook을 먼저 살펴보자.
Page
우리는 먼저 page 구조체를 이해하고 넘어가야 한다.
page 구조체는 수정 전에 아래와 같은 항목을 갖는다.
struct page {
const struct page_operations *operations;
void *va; /* Address in terms of user space */
struct frame *frame; /* Back reference for frame */
union {
struct uninit_page uninit;
struct anon_page anon;
struct file_page file;
#ifdef EFILESYS
struct page_cache page_cache;
#endif
};
};union에 의해 page는 uninit_page, anon_page, file_page, page_cache 중 하나로 정의된다.
그리고 이렇게 정의된 type에 따라 page_operations는 다른 함수로 설정된다.
page_operations는 swap_in, swap_out, destroy 등의 함수 등을 포함하고 있는 구조체이며, page의 type에 따라 각각 다른 page_operations가 사용된다.
// function pointer (함수 포인터)
struct page_operations {
bool (*swap_in) (struct page *, void *);
bool (*swap_out) (struct page *);
void (*destroy) (struct page *);
enum vm_type type;
};// page type = anon_ops 일때, page_operations
static const struct page_operations anon_ops = {
.swap_in = anon_swap_in,
.swap_out = anon_swap_out,
.destroy = anon_destroy,
.type = VM_ANON,
};이때, page의 type이 결정되고 이에 따라 operation이 어떤 종류의 함수를 가리킬 것인지는 주로 page 초기화, page 할당, 페이지 type 전환 단계에서 이뤄진다.
// anon 초기화
/** Project 3: Anonymous Page - Initialize the file mapping */
bool anon_initializer(struct page *page, enum vm_type type, void *kva) {
/* Set up the handler */
/* 데이터를 모두 0으로 초기화 */
struct uninit_page *uninit = &page->uninit;
memset(uninit, 0, sizeof(struct uninit_page));
**// page의 operations가 anon_ops로 설정된다.
page->operations = &anon_ops;**
struct anon_page *anon_page = &page->anon;
/** Project 3: Swap In/Out - ERROR로 초기화 */
anon_page->slot = BITMAP_ERROR;
return true;
}// page type이 무엇인지 확인하는 함수
enum vm_type page_get_type(struct page *page) {
**int ty = VM_TYPE(page->operations->type);**
switch (ty) {
case VM_UNINIT:
return VM_TYPE(page->uninit.type);
default:
return ty;
}
}이렇듯, page 구조체는
- type에 따라 사용될 함수를 가리키는 함수 포인터 page_operations
- 가상 메모리 주소 va
- 연결된 물리 메모리를 가리키는 frame
- type을 결정한 union
등으로 이루어져 있다.
우리는 이러한 struct page를 활용해 PintOS에 가상 메모리 개념을 구축하고 물리 메모리와의 연결성 확보, page fault 처리, 자원 동기화 등을 문제를 하나씩 해결해나가야 한다.
이제부턴 PintOS에 기존 존재하는 pml4 page table 외에, supplemental page table(spt)를 추가로 구축하여 page fault, resource management 등을 처리할 것이다.
이때 page 구조체와 spt와의 관계성을 확보해주기 위해 struct page에 spt_elem을 추가해주어야 한다.
struct page {
const struct page_operations *operations;
void *va; /* Address in terms of user space */
struct frame *frame; /* Back reference for frame */
/** Project 3: Memory Management - Your implementation */
struct hash_elem hash_elem;
bool accessible; /** Project 3: Copy On Write (Extra) */
bool writable;
/* Per-type data are binded into the union.
* Each function automatically detects the current union */
union {
struct uninit_page uninit;
struct anon_page anon;
struct file_page file;
#ifdef EFILESYS
struct page_cache page_cache;
#endif
};
};Supplemental Page Table (SPT)
이제부터 spt에 대해 보다 자세히 알아보자.
기존에 PintOS는 pml4라고 하는 page table을 이미 가지고 있다.
하지만 pml4에는 page fault, resource management 등의 처리 기능이 없다.
따라서 SPT를 새로 정의하여 이러한 기능을 구현하여야 가상 메모리 기능을 제대로 구현해 낼 수 있다.
본격적인 SPT 구현에 앞서, SPT를 구축할 때 어떤 자료구조를 사용할 것인지에 대한 결정이 필요하다.
SPT는 array, linked list, hash table, bitmap 등을 이용해 구현할 수 있다.
- 자료구조 보충 설명 구현할 수 있는 테이블 유형에는
-
배열(array)
-
연결리스트(linked list)
-
해시 테이블(Hash table)
-
비트맵(Bitmap)
정도가 있다.
각 자료구조의 장단점을 살펴보면
- array
- 가장 구현이 간단하나 공간복잡도가 크다는 문제(메모리 용량을 낭비) / 시간복잡도는 O(1)
- linked list
- 탐색 시 시간 복잡도 - O(n) 낭비가 크다. 리스트 역시 심플하긴 하지만, 일일이 확인하면서 찾아야 하기 때문에 시간이 낭비
- Hash table
- 탐색시 시간복잡도 O(1)이라는 장점이 있으며 array와 달리 연속적인 공간을 쓰는 개념이 아니기에 공간복잡도 측면에서도 효율적.
- Bitmap
-
말 그대로 해당 정보를 비트에 매핑시키는 자료구조. 비트로 정보를 저장하기에 공간 복잡도 측면에서 매우 효율적임. 구분해야 할 자료가 많지 않을 때는 이만큼 효율적인 것도 없으나 구분해야 할 서로 다른 자료가 많으면 많을수록 복잡해지는 측면이 있음.
-
우리는 탐색과 수정시 Big O를 고려하여 hash table을 활용해 SPT를 구현한다.
이를 위해, spt 구조체를 아래와 같이 설정한다.
spt는 spt_hash라는 이름의 hash 구조체를 포함한다.
// vm.h
struct supplemental_page_table {
struct hash spt_hash; /** Project 3: Memory Management - 해시 테이블 사용 */
};/* 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'. */
};이러한 spt 구조체는 초기화가 필요하며, 이때 hash_init 함수를 사용해 spt의 초기화를 진행해준다.
// vm.c
/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED) {
hash_init(&spt->spt_hash, hash_func, less_func, NULL);
}hash_init의 사용을 위해 hash_func *hash와 less_func *less를 정의해주어야 한다.
/* 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_func
- hash_bytes 이용하여 page에 대한 hash index 반환
/** Project 3: Memory Management - 해시 인덱스 리턴 */
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));
}// Fowler-Noll-Vo 해시 함수를 활용해 hash 값 계산
uint64_t hash_bytes(const void *buf_, size_t size) {
/* Fowler-Noll-Vo 32-bit hash, for bytes. */
const unsigned char *buf = buf_;
uint64_t hash;
ASSERT(buf != NULL);
hash = FNV_64_BASIS;
while (size-- > 0)
hash = (hash * FNV_64_PRIME) ^ *buf++;
return hash;
}less_func
- page 주소의 대소 비교 후 true or false 반환
/** Project 3: Memory Management - 오름차순 정렬, 가상 주소의 대소 비교 */
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; // true or false 반환
}이어서 spt와 매칭되는 page를 찾고, 특정 page를 spt에 삽입해주는 함수를 구현해주어야 한다.
spt_fine_page
/** Project 3: Memory Management - spt에서 va를 찾아 페이지를 리턴합니다. 오류가 발생하면 NULL을 반환합니다. */
struct page *spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
/* TODO: Fill this function. */
struct page *page = (struct page *)malloc(sizeof(struct page)); // 가상 주소에 대응하는 해시 값 도출을 위해 새로운 페이지 할당, 이 페이지는 해시 검색을 위한 임시 객체로 사용됨
page->va = pg_round_down(va); // 페이지 크기 단위로 내림하여 가상 주소의 시작 주소를 페이지의 va에 복제
struct hash_elem *e = hash_find(&spt->spt_hash, &page->hash_elem); // spt hash 테이블에서 hash_elem과 같은 hash를 갖는 페이지를 찾아서 return
free(page); // 복제한 임시 페이지 객체 해제하여 메모리 누수 방지
return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL; // 검색 결과 존재하면 해당 페이지 반환, 아니면 NULL 반환
}// spt 안의 h 값과 일치하는 page 구조체의 hash_elem 값을 찾는 함수
/* Finds and returns an element equal to E in hash table H, or a
null pointer if no equal element exists in the table. */
struct hash_elem *hash_find(struct hash *h, struct hash_elem *e) {
return find_elem(h, find_bucket(h, e), e);
}// page 구조체 안의 hash_elem의 주소로부터 page 구조체의 주소를 찾고 반환하는 함수
#define hash_entry(HASH_ELEM, STRUCT, MEMBER) ((STRUCT *)((uint8_t *)&(HASH_ELEM)->list_elem - offsetof(STRUCT, MEMBER.list_elem)))spt_insert_page
/** Project 3: Memory Management - 검증을 통해 spt에 PAGE를 삽입합니다. */
bool spt_insert_page(struct supplemental_page_table *spt UNUSED, struct page *page UNUSED) {
/* TODO: Fill this function. */
return hash_insert(&spt->spt_hash, &page->hash_elem) ? false : true; // 존재하지 않으면 삽입
}/* NEW를 해시 테이블 H에 삽입하고, 테이블에 동일한 요소가 없으면 null 포인터를 반환합니다.
테이블에 동일한 요소가 이미 있는 경우, NEW를 삽입하지 않고 해당 요소를 반환합니다. */
struct hash_elem *hash_insert(struct hash *h, struct hash_elem *new) {
struct list *bucket = find_bucket(h, new);
struct hash_elem *old = find_elem(h, bucket, new);
if (old == NULL)
insert_elem(h, bucket, new);
rehash(h);
return old;
}