wil 11-12주차
서론
내가 여기에 왜 왔을까....
일단 PintOS를 하고 싶어서 오지는 않았다.
하면서도 팀한테 미안하다는 생각이 들정도로 의욕이 있지는 않았던 것 같다.
그래도 진행했던 것들을 정리해보자면....
개발하면서 진행했던 부분들
이번 가상메모리 파트에서는 큰 주제를 나누고, 그 안에서 다시 세부 기능을 나눠서 개발하는 방식으로 진행했다.
각 주제마다 팀원들이 세부 작업을 나눴고, 그중에서 내가 하겠다고 고른 작업들을 구현했다.
그래서 내가 선택해서 진행했던 부분 위주로 정리했다.
lazy loading을 위한 page 예약
처음 가상 메모리 구현을 시작할 때도 세부 작업은 여러 갈래로 나뉘어 있었다.
page fault를 어디서 처리할지, SPT에서 page를 어떻게 찾을지, frame을 어떻게 claim할지, lazy loading을 위해 page를 어떻게 등록할지 같은 작업들이 따로 있었다.
내가 고른 쪽은 그중에서도 page를 바로 메모리에 올리지 않고, 일단 SPT에 예약 해두는 기능이었다.
처음에는 page를 만든다고 하면 당연히 frame까지 같이 잡고 파일 내용도 바로 읽는다고 생각했다.
그런데 가상 메모리에서는 실제로 접근하지 않은 page까지 전부 메모리에 올리면 낭비가 크다.
그래서 지금 당장 필요한 데이터가 아니라면 나중에 이 주소에 접근하면 이런 방식으로 초기화하면 된다는 정보만 저장해둔다.
vm_alloc_page_with_initializer()가 그런 함수였다.
bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
vm_initializer *init, void *aux) {
ASSERT (VM_TYPE(type) != VM_UNINIT);
struct supplemental_page_table *spt = &thread_current ()->spt;
void *va = pg_round_down(upage);
if (spt_find_page (spt, va) == NULL) {
struct page *page;
bool (*initializer)(struct page *, enum vm_type, void *);
page = malloc(sizeof *page);
if(page == NULL)
return false;
if (VM_TYPE(type) == VM_ANON)
initializer = anon_initializer;
else if (VM_TYPE(type) == VM_FILE)
initializer = file_backed_initializer;
else{
free(page);
return false;
}
uninit_new(page, va, init, type, aux, initializer);
page->writable = writable;
if(spt_insert_page(spt, page))
return true;
else{
free(page);
return false;
}
}
return false;
}함수명과 달리 이 함수는 page를 완성시키는 함수가 아니라 spt에 페이지를 할당하는게 전부인 함수이다.
VM_ANON이나 VM_FILE 타입을 보고 어떤 initializer를 써야 하는지만 정한 뒤, 실제 page는 uninit_new()로 만든다.
즉, 처음에는 전부 VM_UNINIT 상태로 SPT에 들어간다.
나중에 page fault가 발생하면 그제서야 이 page가 anonymous page인지 file-backed page인지에 따라 바뀐다.
처음에는 왜 굳이 VM_UNINIT이라는 중간 상태를 두는지 잘 와닿지 않았다.
그냥 처음부터 VM_ANON, VM_FILE로 만들면 되는거 아닌가 싶었다.
그런데 생각해보면 이 page는 아직 frame도 없고, 파일 내용도 안 읽었고, 실제 메모리에 올라간 상태도 아니다.
실제 초기화는 첫 접근 때 이쪽으로 넘어간다.
static bool
uninit_initialize (struct page *page, void *kva) {
struct uninit_page *uninit = &page->uninit;
vm_initializer *init = uninit->init;
void *aux = uninit->aux;
enum vm_type type = uninit->type;
bool (*page_initializer) (struct page *, enum vm_type, void *) =
uninit->page_initializer;
if (!page_initializer (page, type, kva))
return false;
if (init == NULL)
return true;
return init (page, aux);
}uninit_initialize()에서는 먼저 page type에 맞는 initializer를 호출한다.
anonymous page라면 anon_initializer(), file-backed page라면 file_backed_initializer()로 넘어간다.
bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
page->operations = &anon_ops;
struct anon_page *anon_page = &page->anon;
return true;
}bool
file_backed_initializer (struct page *page, enum vm_type type, void *kva) {
void *aux = page->uninit.aux;
page->operations = &file_ops;
if (aux == NULL)
return false;
struct file_page *a = aux;
struct file_page *f = &page->file;
f->file = a->file;
f->ofs = a->ofs;
f->read_bytes = a->read_bytes;
f->zero_bytes = a->zero_bytes;
f->page_cnt = a->page_cnt;
f->is_mmap_start = a->is_mmap_start;
return true;
}여기서 page->operations가 바뀐다.
처음에는 uninit page였기 때문에 uninit용 함수 테이블을 가지고 있다가, 실제 초기화가 끝나면 anonymous page나 file-backed page용 함수 테이블로 바뀐다.
이 구조를 보고 나서야 왜 page struct 안에 operations가 있고, 왜 swap_in, swap_out, destroy를 함수 포인터로 관리하는지 이해가 됐다.
같은 struct page여도 실제 타입에 따라 해야 하는 일이 다르기 때문이다.
SPT 정리
그 다음 주제에서는 stack growth, page destroy, SPT cleanup처럼 프로세스의 메모리 공간을 정리하는 작업들이 나뉘어 있었다.
여기서 고른 부분은 프로세스가 종료될 때 SPT를 정리하는 기능이었다.
처음에는 정리라고 하면 그냥 hash table을 free하면 끝나는 줄 알았다.
그런데 SPT 안에는 단순한 숫자나 문자열이 들어있는게 아니라 struct page들이 들어있다.
그리고 그 page들은 타입에 따라 추가로 정리해야 하는 자원이 다르다.
file-backed page는 파일과 연결되어 있을 수 있고, anonymous page는 나중에 swap slot을 가지고 있을 수도 있다.
그래서 SPT를 지울 때도 그냥 hash만 없애면 안 되고, 안에 들어있는 page마다 제거를 해줘야 했다.
구현은 생각보다 짧았다.
static void
spt_page_destructor (struct hash_elem *e, void *aux UNUSED) {
struct page *p = hash_entry(e, struct page, elem);
vm_dealloc_page(p);
}
void
supplemental_page_table_kill (struct supplemental_page_table *spt) {
hash_destroy (&(spt->hash), spt_page_destructor);
}짧은데 처음에는 이게 오히려 더 헷갈렸다.
내가 직접 타입별로 따로 불러야 하는 줄 알았다.
그런데 실제로는 vm_dealloc_page()가 공통함수로 작동한다.
void
vm_dealloc_page (struct page *page) {
destroy (page);
free (page);
}그리고 destroy(page)는 page가 현재 가지고 있는 operation table을 보고 타입별 destroy 함수로 넘어간다.
#define destroy(page) \
if ((page)->operations->destroy) (page)->operations->destroy (page)여기서 배운건, 정리 함수가 모든 타입의 세부사항을 다 알 필요는 없다는 것이다.
SPT 정리 쪽에서는 "SPT 안의 page를 하나씩 꺼내서 page 정리 함수로 넘긴다"까지만 책임진다.
실제로 어떤 자원을 어떻게 정리할지는 각 page type의 operation이 처리한다.
처음에는 이게 괜히 돌아가는 구조처럼 보였는데, 나중에 보니 이게 맞았다.
만약 SPT 정리 코드가 모든 page type을 직접 구분하기 시작하면, page type이 늘어날수록 cleanup 코드가 계속 복잡해진다.
반대로 operation table을 쓰면, 공통 흐름은 그대로 두고 타입별 동작만 갈아끼울 수 있다.
이 부분은 구현량 자체보다 책임 분리가 더 중요했던 것 같다.
free 하나 하는 것도 그냥 free가 아니라, 누가 어떤 자원까지 책임지는지 정해야 한다는걸 배웠다.
mmap page 등록
그 다음 주제는 mmap이었다.
이 주제도 하나의 함수만 구현하면 끝나는게 아니라, 인자 검증, page 등록, file-backed page load, munmap과 write-back 같은 세부 작업으로 나뉘어 있었다.
내가 고른 부분은 그중에서 파일을 page 단위로 나누어 SPT에 등록하는 쪽이었다.
처음에는 mmap이라고 하면 파일 내용을 바로 메모리에 읽어오는 기능이라고 생각했다.
그런데 여기서도 lazy loading이 적용된다.
mmap이 호출되었다고 파일 내용을 전부 읽는 것이 아니라, 해당 주소 범위에 file-backed page들을 SPT에 등록해두고 실제 접근이 발생했을 때 파일에서 읽어온다.
그래서 do_mmap()에서 중요한건 파일을 읽는 것이 아니라, 주소 범위를 page 단위로 쪼개고 각 page가 나중에 읽을 파일 정보들을 aux에 담아두는 것이었다.
먼저 mmap할 주소 범위가 유저 영역 안에 있는지, 그리고 이미 SPT에 등록된 page와 겹치지 않는지 확인했다.
uint8_t *start = addr;
uint8_t *end = start + length - 1;
if (end < start || !is_user_vaddr (end)) {
return NULL;
}
struct supplemental_page_table *spt = &thread_current ()->spt;
size_t check = 0;
while (check < length) {
void *upage = (uint8_t *) addr + check;
if (spt_find_page (spt, upage) != NULL) {
return NULL;
}
check += PGSIZE;
}여기서 end < start를 확인하는 이유는 주소 계산 오버 플로우 때문이다.
처음에는 끝 주소가 유저 주소인지 정도만 보면 된다고 생각했는데, 주소 계산이 넘쳐버리면 이상한 범위가 정상처럼 보일 수도 있다.
이런 검증은 구현할 때는 귀찮지만, 안 해두면 테스트에서 바로 터질만한 부분이었다.
그 다음에는 mmap 전용 파일 객체를 따로 열었다.
struct file *mmap_file = file_reopen (file);
if (mmap_file == NULL) {
return NULL;
}이 부분도 처음에는 원래 받은 파일 포인터를 그대로 쓰면 되는거 아닌가 싶었다.
그런데 파일 객체는 내부 위치값을 가질 수 있고, 같은 파일을 여러 곳에서 공유하면 예상치 못하게 위치가 꼬일 수 있다.
그래서 mapping마다 독립적인 파일 참조를 가지도록 file_reopen()을 사용했다.
그 다음부터는 페이지 단위로 돌면서 각 페이지의 메타 데이터를 만든다.
size_t page_cnt = DIV_ROUND_UP (length, PGSIZE);
size_t i = 0;
while (i < length) {
struct file_page *file_page = palloc_get_page (0);
if (file_page == NULL) {
for (size_t j = 0; j < i; j += PGSIZE) {
struct page *page = spt_find_page (spt, (uint8_t *) addr + j);
if (page != NULL)
spt_remove_page (spt, page);
}
file_close (mmap_file);
return NULL;
}
size_t page_left;
if (length - i < PGSIZE) {
page_left = length - i;
} else {
page_left = PGSIZE;
}
size_t file_left = 0;
if (ofs + i < file_size) {
file_left = file_size - (ofs + i);
}
size_t read_bytes;
if (file_left < page_left) {
read_bytes = file_left;
} else {
read_bytes = page_left;
}
size_t zero_bytes = PGSIZE - read_bytes;이 계산이 생각보다 중요했다.
모든 페이지가 파일에서 4096바이트씩 읽는게 아니기 때문이다.
마지막 페이지는 요청 길이가 page 크기보다 작을 수도 있고, 파일이 요청 길이보다 짧으면 남은 부분은 0으로 채워야 한다.
그래서 각 페이지마다 read_bytes와 zero_bytes를 따로 계산했다.
이 정보를 잘못 넣으면 나중에 page fault가 났을 때 잘못된 오프셋에서 읽거나, 0으로 채워야 하는 부분까지 파일에서 읽으려고 할 수 있다.
계산한 값은 file_page에 저장한 뒤 SPT에 등록한다.
file_page->file = mmap_file;
file_page->ofs = ofs + i;
file_page->read_bytes = read_bytes;
file_page->zero_bytes = zero_bytes;
if (i == 0) {
file_page->is_mmap_start = true;
file_page->page_cnt = page_cnt;
} else {
file_page->is_mmap_start = false;
file_page->page_cnt = 0;
}
if (!vm_alloc_page_with_initializer (VM_FILE, (uint8_t *) addr + i, writable,
mmap_lazy_load, file_page)) {
palloc_free_page (file_page);
for (size_t j = 0; j < i; j += PGSIZE) {
struct page *page = spt_find_page (spt, (uint8_t *) addr + j);
if (page != NULL)
spt_remove_page (spt, page);
}
file_close (mmap_file);
return NULL;
}
i += PGSIZE;여기서도 실제 파일을 읽는게 아니라 VM_FILE page를 등록만 한다.
실제 읽기는 나중에 page fault가 발생하고 mmap_lazy_load가 호출될 때 일어난다.
처음에는 mmap을 구현한다고 해서 파일 입출력 쪽이 중요할거라 생각했는데, 실제로는 metadata를 정확히 나누는게 더 중요했다.
주소, offset, read_bytes, zero_bytes가 page마다 정확히 맞아야 fault 시점에 맞는 데이터를 가져올 수 있다.
그리고 중간에 실패했을 때 이미 등록한 페이지들을 다시 제거하는 rollback도 필요했다.
처음부터 전부 성공하면 좋겠지만, 중간에 aux 할당이나 페이지 등록이 실패할 수도 있다.
그때 앞에서 등록한 페이지를 그대로 두면, 실패한 mmap인데 SPT에는 찌꺼기 페이지가 남아버린다.
이런 부분이 생각보다 구현할 때 신경이 많이 쓰였다.
frame을 내보낼 대상 고르기
마지막으로 본 주제는 메모리가 부족할 때 기존 페이지를 내보내는 흐름이었다.
이쪽도 세부 작업이 나뉘어 있었다.
누군가는 실제 eviction 흐름을 연결해야 하고, anonymous page는 swap disk 쪽으로 보내야 하고, file-backed page는 파일과 연결해서 처리해야 했다.
내가 개발한 부분 중 하나는 그 앞단에서 어떤 프레임을 내보낼지 고르는 부분이었다.
처음에는 프레임이 부족하면 그냥 프레임 테이블 앞에서 하나 꺼내면 되는거 아닌가 싶었다.
그런데 그러면 방금 사용한 페이지도 바로 쫓겨날 수 있다.
운영체제 입장에서는 최근에 사용한 페이지는 다시 사용할 가능성이 높으니, 가능하면 덜 사용된 페이지를 내보내는게 낫다.
그래서 accessed bit를 보고 second-chance 방식으로 victim을 고르게 했다.
static struct frame *
vm_get_victim (void) {
struct frame *victim = NULL;
void *va = NULL;
uint64_t *pml4 = NULL;
lock_acquire(&frame_table_lock);
for(int i = 0; i < (int)list_size(&frame_table); i++){
victim = frame_table_next();
if (victim == NULL){
lock_release(&frame_table_lock);
return NULL;
}
if (victim->page == NULL || victim->owner == NULL)
continue;
va = victim->page->va;
pml4 = victim->owner->pml4;
if (va == NULL || pml4 == NULL)
continue;
if(pml4_is_accessed(pml4, va)){
pml4_set_accessed(pml4, va, false);
continue;
}
lock_release(&frame_table_lock);
return victim;
}accessed bit가 켜져 있으면 최근에 접근된 페이지라는 뜻이다.
그래서 바로 victim으로 고르지 않고 accessed bit를 false로 내린 뒤 한 번 더 기회를 준다.
이게 second-chance 방식이다.
그리고 한 바퀴를 돌았는데도 victim을 못 찾으면 두 번째 순회에서는 바로 반환하도록 했다.
for(int i = 0; i < (int)list_size(&frame_table); i++){
victim = frame_table_next();
if (victim == NULL){
lock_release(&frame_table_lock);
return NULL;
}
if (victim->page == NULL || victim->owner == NULL)
continue;
va = victim->page->va;
pml4 = victim->owner->pml4;
if (va == NULL || pml4 == NULL)
continue;
lock_release(&frame_table_lock);
return victim;
}
lock_release(&frame_table_lock);
return NULL;
}여기서 중요한건 이 함수가 실제로 페이지를 내보내지는 않는다는 점이다.
이 함수는 어디까지나 "내보낼 후보 frame을 고르는 것"까지만 한다.
실제로 swap_out을 호출하거나, pml4 mapping을 지우거나, page->frame 연결을 끊는 것은 다음 흐름에서 처리해야 한다.
처음에는 victim을 고르는 김에 다 처리해도 되지 않나 싶었는데, 그렇게 하면 함수 책임이 너무 커진다.
victim selection은 정책이고, eviction flow는 실행이다.
둘을 섞으면 나중에 정책을 바꾸기도 어려워지고, anonymous page와 file-backed page를 내보내는 방식도 같이 꼬일 수 있다.
이 부분을 하면서 프레임과 페이지의 관계도 다시 정리하게 됐다.
프레임은 실제 물리 메모리 한 칸이고, 페이지는 유저 가상 주소의 정보다.
그래서 프레임 테이블에서는 프레임을 돌지만, accessed bit를 확인하려면 그 f프레임이 어떤 페이지와 연결되어 있는지 알아야 한다.
그래서 frame->page, page->va, frame->owner->pml4가 필요했다.
file-backed page write-back
같은 메모리 부족 흐름 안에서 내가 고른 또 다른 부분은 file-backed page를 프레임에서 내보낼 때 파일에 다시 써야 하는 부분이었다.
여기서도 처음에는 내보낼 때마다 파일에 쓰면 되는거 아닌가 싶었다.
그런데 file-backed page라고 해서 항상 파일에 다시 써야 하는 것은 아니었다.
파일에서 읽기만 하고 수정하지 않은 페이지라면 굳이 write-back할 필요가 없다.
원본 파일과 내용이 같기 때문이다.
그래서 dirty bit를 확인해서, 수정된 페이지만 backing file에 다시 쓴다.
static bool
file_backed_swap_out (struct page *page) {
struct file_page *file_page = &page->file;
struct frame *frame = page->frame;
if (frame == NULL || frame->kva == NULL)
return false;
uint64_t *pml4 = frame->owner != NULL ? frame->owner->pml4 : thread_current ()-> pml4;
if (pml4_is_dirty (pml4, page->va)){
off_t written = file_write_at(file_page->file, frame->kva,
(off_t) file_page->read_bytes, file_page->ofs);
if(written != (off_t) file_page->read_bytes)
return false;
pml4_set_dirty (pml4, page->va, false);
}
return true;
}이 함수에서 중요한 포인트는 세 가지다.
첫 번째는 프레임이 실제로 있는지 확인하는 것이다.
file-backed page라도 아직 lazy 상태라 frame이 없을 수 있고, 그런 page는 지금 frame에서 내보낼 내용이 없다.
두 번째는 dirty bit를 확인하는 것이다.
pml4_is_dirty()가 true일 때만 파일에 다시 쓴다.
이걸 안 하면 수정하지 않은 페이지까지 매번 write-back하게 된다.
성능도 별로고, 무엇보다 "수정된 내용만 반영한다"는 mmap의 동작과도 맞지 않는다.
세 번째는 read_bytes만큼만 쓰는 것이다.
페이지 하나는 4096바이트지만, file-backed page가 실제 파일에서 읽어온 부분은 그보다 작을 수 있다.
나머지는 zero padding일 수 있으므로 파일에 다시 쓸 때도 read_bytes만큼만 써야 한다.
여기서 anonymous page와 file-backed page의 차이도 좀 정리됐다.
anonymous page는 원래 backing file이 없으니 내보낼 때 swap disk 같은 임시 공간이 필요하다.
반대로 file-backed page는 원래 파일을 backing store로 사용한다.
그래서 dirty한 경우에는 그 파일에 다시 쓰면 된다.
다만 이 함수도 전체 eviction을 혼자 다 처리하는 함수는 아니다.
이 함수는 file-backed page가 프레임에서 내려갈 때 파일에 필요한 내용을 반영하는 일만 한다.
어떤 프레임을 고르는지, page table mapping을 언제 지우는지, 프레임과 페이지 연결을 언제 끊는지는 다른 흐름과 연결되어야 한다.
이렇게 나눠놓고 보니, 가상 메모리 구현은 함수 하나하나보다 경계가 더 중요한 것 같았다.
어떤 함수는 페이지를 SPT에 등록만 하고, 어떤 함수는 실제 claim만 하고, 어떤 함수는 victim만 고르고, 어떤 함수는 dirty page만 write-back한다.
처음에는 이게 여기저기 흩어져 있어서 복잡해 보였는데, 나중에는 오히려 이렇게 나눠야 덜 꼬인다는 생각이 들었다.
전체적으로 배운 것
이번에 개발한 부분들을 연결해보면 결국 하나의 흐름으로 이어진다.
처음에는 페이지를 바로 메모리에 올리지 않고 SPT에 예약해둔다.
사용자 프로그램이 그 주소에 접근하면 page fault가 나고, 그때 SPT를 찾아 frame을 붙이고 실제 데이터를 읽어온다.
프로세스가 끝나면 SPT를 순회하면서 page type에 맞게 정리한다.
mmap은 파일의 특정 구간을 페이지 단위로 쪼개서 file-backed lazy page로 등록한다.
메모리가 부족해지면 frame table을 돌면서 내보낼 프레임을 고르고, file-backed page가 수정되었다면 원래 파일에 다시 써준다.
처음에는 page fault가 그냥 에러라고 생각했는데, 이번 구현에서는 page fault가 오히려 정상적인 실행 흐름의 일부였다.
아직 준비되지 않은 페이지를 실제로 준비하는 타이밍이 page fault였기 때문이다.
그리고 struct page 하나 안에 모든 정보를 다 때려넣는 것이 아니라, operations와 union을 이용해서 타입별 동작을 나눈 것도 인상적이었다.
C에는 클래스가 없지만, 함수 포인터 테이블을 이용해서 비슷한 구조를 만들 수 있었다.
이번 구현에서 제일 많이 느낀건, VM은 한 함수만 보고 이해하기 어렵다는 점이었다.
vm_alloc_page_with_initializer()만 보면 page를 만들 뿐이고, uninit_initialize()만 보면 초기화만 하고, do_mmap()만 보면 등록만 하고, file_backed_swap_out()만 보면 파일에 쓰기만 한다.
그런데 이 함수들이 page fault, SPT, 프레임, 파일, pml4와 연결되면 그제서야 가상 메모리의 흐름이 된다.
(수정중)
