지금까지의 구현한 PintOS는 여러 스레드를 동기화해서 핸들링할 수 있고, 여러 개의 유저 프로그램들을 한 번에 로드할 수 있다. 그러나 돌릴 수 있는 프로그램의 개수와 사이즈는 메인 메모리 크기에 맞춰 제한되어 있다.
이 물리 메모리의 한계를 극복하고 더 많은 프로그램을 실행시킬 수 있도록 가상 메모리 개념을 도입하는 것이 프로젝트3의 가장 큰 목표다.
📍 첫 번째 과제, Supplemental Page Table(보조 페이지 테이블)
기존의 PintOS에서의 Page Table은 pml4로, 가상 메모리와 물리 메모리 간 매핑을 관리한다. 하지만 이는 물리 주소를 향한 pointing에 불과하다.
우리는 page fault 처리와 자원 관리를 위해 각각의 페이지에 대한 추가적인 정보를 담은 테이블이 필요하다.
*supplemental page table: 각 페이지에 대한 추가 정보(데이터 위치/포인터/활성화 여부 등)을 추적하는 프로세스별 데이터 구조
🛠️ page table management
supplemental page table는 다양한 자료구조로 구현할 수 있다.
배열/연결 리스트/해시 테이블/비트 맵
여러 측면에서 해시 테이블로 구성하는 것이 좋아보였다.
사진에서 보이는 vm이 바로 우리가 구현 할 supplemental page table이다.
각 스레드마다 하나씩 가지고 있으며, 각 테이블에서 가르키는 물리 메모리는 여러 supplemental page table에서 가리킨다.
hash 구조체 안에는 buckets와 다양한 멤버 변수들이 담겨 있고, buckets 내부엔 PTE들이 연결 리스트로 구성되어 있다.
hash에 관한 함수들은 구성/구현할 필요 없이 pintos에는 이미 include/lib/kernel/hash.h에 관련 함수들과 구조체들이 선언되어 있다. 이를 적절히 활용해 supplemental page table을 구현해보자.
1. supplemental page table 구조체 구성
struct supplemental_page_table
{
/* 보충 페이지 테이블 = 페이지에 대한 추가 정보를 담아서 관리하도록(해시 테이블 자료구조 활용) */
struct hash spt_hash;
};2. page 구조체에 supplemental page table을 관리하기 위한 elem 추가
struct page
{
...
struct hash_elem bucket_elem; /* 해시 테이블 요소 */
...
}3. supplemental page table 초기화 함수 구현
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
/* spt 초기화 */
hash_init(&spt->spt_hash, hash_func, less_func, NULL);
}4. hash_func()
: 해싱하는 함수 (key값 계산)
uint64_t hash_func(const struct hash_elem *e, void *aux)
{
/* 해싱하는 함수 */
/* hash_elem으로 page 가져오기 */
const struct page *page_ = hash_entry(e, struct page, bucket_elem);
/* page의 va(가상주소)를 key값으로 해 해싱한 후 bucket_idx 값 반환 */
return hash_bytes(&page_->va, sizeof(page_->va));
}5. less_func()
: 주소(va) 비교하는 함수
bool less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux)
{
/* hash_elem으로 가져온 두 페이지의 가상주소를 기준으로 비교하는 함수 */
const struct page *a_page = hash_entry(a, struct page, bucket_elem);
const struct page *b_page = hash_entry(b, struct page, bucket_elem);
return a_page->va < b_page->va;
}6. spt_find_page()
: spt에서 인자로 받은 va값에 해당하는 page를 찾아 반환하는 함수
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
struct page *page = NULL;
/* TODO: Fill this function. */
page = malloc(sizeof(struct page));
struct hash_elem *e;
/* 할당한 page의 va 값 할당 후, 해당 va에 해당하는 elem 찾기 */
/* pg_round_down: 가장 가까운 페이지 경계로 반올림 */
/* 사용자가 원하는 임의의 가상 주소에 접근 시, 해당 주소가 포함된 page의 시작 주소를 찾기 위해 진행 */
page->va = pg_round_down(va);
e = hash_find(&spt->spt_hash, &page->bucket_elem);
free(page);
/* 해당하는 hash_elem이 있으면, 그 hash_entry로 해당 페이지 반환 */
return e != NULL ? hash_entry(e, struct page, bucket_elem) : NULL;
}7. spt_insert_page()
: spt에 page를 삽입하는 함수 (동일한 va가 존재하는지 유효성 검사 과정 필요)
bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
struct page *page UNUSED)
{
/* 유효성 검사?: 동일한 va값이 있으면 안 되기 때문에 spt에 삽입할 page의 va값이 있는지 검사 = hash_insert에서 해줌 */
/* hash_insert를 해서 동일 va값이 없었다면, 즉 반환값이 NULL이라면 삽입 성공 true 반환 */
/* 동일한 va값이 존재한다면, 반환값이 NULL이 아니기 떄문에 false 반환 */
return hash_insert(&spt->spt_hash, &page->bucket_elem) == NULL ? true : false;
}supplemental page table을 구성하고, 관련 함수들을 모두 작성했다면 page table management 파트는 끝난다. 다음으로는 페이지가 아닌 프레임 관리를 위한 구현에 들어가야 한다.
🛠️ Frame Management
1. vm_get_frame()
: user pool로부터 새로운 물리 페이지(=frame)을 할당 받는 함수
vm_get_frame(void)
{
struct frame *frame = NULL;
struct page *page = NULL;
/* TODO: Fill this function. */
/* 유저 풀에서 새로운 물리 메모리 할당 받음 */
/* palloc_get_page가 kva를 반환 */
/* physical adress = virtual adress + KERN_BASE(커널은 모두 공유) */
void *kva = palloc_get_page(PAL_USER);
if (kva == NULL)
{
/* kva가 NULL이라면 할당 실패, 물리 메모리 공간 꽉 찼다는 의미 */
/* 나중에 SWAP-OUT 처리 필요 */
PANIC("SWAP OUT");
}
/* 프레임 동적 할당 후 멤버 초기화 */
frame = malloc(sizeof(struct frame));
frame->kva = kva;
frame->page = NULL;
lock_acquire(&frame_table_lock);
list_push_back(&frame_table, &frame->frame_elem);
lock_release(&frame_table_lock);
ASSERT(frame != NULL);
ASSERT(frame->page == NULL);
return frame;
}2. vm_do_claim_page()
: 새 frame을 할당받아와 page와 매핑하는 함수
static bool
vm_do_claim_page(struct page *page)
{
/* 프레임 할당 받음 */
struct frame *frame = vm_get_frame();
/* Set links, 페이지와 프레임 매핑 */
frame->page = page;
page->frame = frame;
/* 가상주소와 물리주소를 매핑한 정보를 페이지 테이블에 추가 */
struct thread *curr = thread_current();
pml4_set_page(curr->pml4, page->va, frame->kva, page->writable);
return swap_in(page, frame->kva);
}3. vm_claim_page()
: spt에서 va에 해당하는 page를 가져와 vm_do_claim_page로 frame과의 매핑을 요청하는 함수
bool vm_claim_page(void *va UNUSED)
{
struct page *page = NULL;
struct thread *curr = thread_current();
/* spt에서 va에 해당하는 page를 가져와 vm_do_claim_page()로 매핑하기 */
page = spt_find_page(&curr->spt, va);
if (page == NULL)
{
return false;
}
return vm_do_claim_page(page);
}vm_get_frame() & vm_do_claim_page() & vm_claim_page()의 관계성 🤔
세 함수가 연관되어 있다는 것은 분명히 알겠는데, 각자 따로 보니 헷갈려서 그림을 그려서 이해해봤다.
결국 vm_get_frame()과 vm_do_claim()을 활용해 page와 frame을 매핑하는 것이 가장 큰 목적인 것 같다.
project(3)의 첫 번째 과제인 memory management는 이게 끝이다.
아직 file 관련된 구현들이 되어있지 않기 때문에 테스트에 대한 변화는 없을 것이다.
⚙️Modify List
1. vm/vm.c
- hash_func() 추가 구현
- less_func() 추가 구현
- supplemental_page_table_init() 구현
- vm_get_frame() 구현
- vm_do_claim_page() 구현
- vm_claim_page() 구현
- spt_find_page() 구현
- spt_insert_page() 구현
2. include/vm/vm.h
- supplemental_page_table 구조체 수정
- page 구조체 수정