do_mummap을 마무리하고 바로 swap in/out 구현으로 넘어갔다.
구현하기에 앞서 개념과 뭘 해야할지에 대해 정리하고 가자.
현재 vm_alloc_page_with_initializer 함수를 통해 type별 initializer를 건네주면서 anon_page를 만들고 있다.
여기까지의 상태는 page를 만들고 현재 진행중인 프로세스/스레드의 spt에 넣었을 뿐이다. 즉, 물리 메모리에는 아직 올리지 않았다.
'물리 메모리에 올렸다' 라는 것은 다음과 같다.
page와 frame은 실제로 우리가 쓸 4KB의 공간이 아니다. 4KB의 공간을 지칭해주는 추상자료형으로 생각하자.
실제로 4KB의 공간은 va와, kva이다. 그동안 우리가 공간할당을 어떻게 해줬는지 보면 이해가 쉽다.
struct page *page = malloc(sizeof(struct page));
struct frame *frame = malloc(sizeof(struct frame));
void *kva = palloc_get_page(PAL_USER);메모리 할당은 커널영역에 대한 공간을 반환하다. 여기서 커널영역도 kernel pool과 user pool로 나뉜다.
palloc_get_page(PAL_USER)를 하게 되면 user pool의 공간을 반환한다. 그 외에는 전부 kernel pool이다. malloc, calloc도 kernel pool에 대한 공간이다.
va는 사용자영역이기에 따로 메모리 할당은 해주지 않지만 page별로 4KB씩 공간을 사용할 수 있도록 컨트롤 해주고 있다.
vm_alloc_page_with_initializer의 upage 인자에는 4KB-align 되어있는 사용자영역의 주소가 전달될것이다. 이어서 spt에 등록이 되면 해당 upage는 (upage) ~ (upage + 4KB - 1)의 공간을 담당하게 된다.
vm_alloc_page_with_initializer의 역할은 spt에 page를 넣어주는 것이 전부다.
이제 이 상태에서 특정 주소를 참조하려고 한다면 page fault가 나고 vm_try_handle_fault가 실행될 것이다. 사용자영역 주소가 아니면 false가 나고 해당 프로세스/스레드는 비정상 종료가 된다.
또 사용자영역 주소라고 해도 spt에서 page fault가 난 주소를 커버하는 page가 없어도 비정상 종료가 된다.
이제부터가 swap in/out에 대한 내용이다.
vm_try_handle_fault에서 주소 검사를 통과하고 page가 존재한다면 이 page를 물리 메모리에 올리는 작업이 시작된다.
물리 메모리에 올리기 위해서 vm_get_frame을 호출하는데 이 때 물리 메모리에 이미 많은 page들이 올라가있어서 공간이 없다면 kva에 대한 palloc_get_page가 실패한다. 이 때 필요한게 swap in/out 이다.
swap in/out을 위해 먼저 swap_disk가 무슨 변수일까 살펴보자.
swap_disk
#define DISK_SECTOR_SIZE 512
typedef uint32_t disk_sector_t;
struct disk {
char name[8]; /* Name, e.g. "hd0:1". */
struct channel *channel; /* Channel disk is on. */
int dev_no; /* Device 0 or 1 for master or slave. */
bool is_ata; /* 1=This device is an ATA disk. */
disk_sector_t capacity; /* Capacity in sectors (if is_ata). */
long long read_cnt; /* Number of sectors read. */
long long write_cnt; /* Number of sectors written. */
};
static struct disk *swap_disk;간단하게 말하면 특정 frame을 swap out 시킬 때 정보를 디스크에 저장하게 되는데 sector별로 쪼개서 저장이 된다. 한 개의 sector별로 512B 만큼 기록이 가능하다.
즉, frame의 정보를 disk에 백업해두기 위해서는 총 8개의 sector를 사용하게 된다.
그렇다면 생각해봐야 할것이다. 어느 sector가 사용/미사용 중인지 어떻게 알 수 있냐는 것이다.
필자는 bool 배열을 전역변수로 선언에 관리하였다.
vm_anon_init
bool *swap_arr;
void vm_anon_init (void) {
/* TODO: Set up the swap_disk. */
swap_disk = disk_get(1, 1);
/* disk에 들어갈 수 있는 page 개수 */
int swap_arr_len = disk_size(swap_disk) / 8;
swap_arr = malloc(swap_arr_len);
for (int i = 0; i < swap_arr_len; i++) {
swap_arr[i] = false;
}
}disk_size는 disk의 용량을 sector 갯수로 반환 해준다. 한 개의 page당 8개의 sector를 사용해야하니 8로 나누면 disk에 저장할 수 있는 총 page 수가 나오고 그만큼 배열을 만들어주고 false 미사용중으로 초기화 하였다.
anon_swap_out
anon_swap_out 함수를 살펴보자.
static bool anon_swap_out (struct page *page) {
struct anon_page *anon_page = &page->anon;
int arr_len = disk_size(swap_disk) / 8;
int start_sec_no = 0;
/* page가 들어갈 수 있는 sector 위치 찾기 */
for(int i = 0; i < arr_len; i++) {
if (swap_arr[i] == false) {
swap_arr[i] = true;
start_sec_no = i * 8;
break;
}
}
/* 해당 sector 위치에 page를 8개로 쪼개 넣기 */
int j = 0;
page->anon.occupy_sector_num = start_sec_no; // anon_page에 start_sec_no 저장
for (int i = start_sec_no; i < start_sec_no + 8; i++) {
disk_write(swap_disk, i, page->frame->kva + j * DISK_SECTOR_SIZE);
j++;
}
pml4_clear_page(thread_current()->pml4, page->va);
return true;
}first fit 방식으로 미사용중인 disk sector를 찾는다. index를 이용하여 실제 사용할 sector_num에 물리 메모리에 있던 내용을 512B씩 쪼개 8번 기록한다. 이어서 해당 frame은 이제 다른 page에게 주어야 하니 기존의 page와의 연결을 끊어준다.
해당 page 정보를 page table에서 지우면 된다.
anon_swap_in
static bool anon_swap_in (struct page *page, void *kva) {
struct anon_page *anon_page = &page->anon;
int start_sector_no = anon_page->occupy_sector_num;
anon_page->occupy_sector_num = -1;
int j = 0;
swap_arr[start_sector_no / 8] = false;
for (int i = start_sector_no; i < start_sector_no + 8; i++) {
disk_read(swap_disk, i, kva + j * DISK_SECTOR_SIZE);
j++;
}
return true;
}디스크에서 꺼내어 백업되어있던 정보를 다시 물리 메모리에 올려주는 작업이다.
swap_out 할 때 anon_page 구조체의 멤버변수 occupy_sector_num을 저장해 주었기 때문에 해당 위치에서부터 8개의 sector에서 정보를 읽어오자.
swap_arr의 미사용중으로 초기화 해주는 작업도 잊지말자.
file_backed_swap_out
anon_page와 달리 file_page는 디스크에 저장을 하지 않는다.
file을 읽어와서 물리 메모리에 올리고 변경을 했으면 swap out 할 때 다시 file에 덮어 씌워주면 된다. 즉, anon_page의 백업 공간은 디스크 / file_page의 백업 공간은 file이다.
static bool file_backed_swap_out (struct page *page) {
struct file_page *file_page = &page->file;
if (pml4_is_dirty(thread_current()->pml4, page->va)) {
file_write_at(file_page->file_segment->file, page->frame->kva, file_page->file_segment->page_read_bytes, file_page->file_segment->ofs);
pml4_set_dirty(thread_current()->pml4, page->va, 0);
}
pml4_clear_page(thread_current()->pml4, page->va);
return true;
}정말 간단하다. 수정 되었으면 file에 덮어씌우고 frame과의 연결을 끊어주면 된다.
file_backed_swap_in
static bool file_backed_swap_in (struct page *page, void *kva) {
struct file_page *file_page = &page->file;
file_read_at(file_page->file_segment->file, kva, file_page->file_segment->page_read_bytes, file_page->file_segment->ofs);
memset(kva + file_page->file_segment->page_read_bytes, 0, file_page->file_segment->page_zero_bytes);
return true;
}file을 다시 물리 메모리에 올리면 된다. 하지만 다른 page가 쓰던 물리 공간을 받아왔으니 page_zero_bytes에 대해서는 0으로 초기화를 해주었다.
아마 memset을 쓰고 싶지 않다면 file_read_at의 세 번째 인자에 PGSIZE를 넣어주면 될거라고 생각한다.
실제 해보지는 않았기 때문에 안될수도 있다.
여기까지 swap in/out 함수에 대해서 알아보았다. 그렇다면 swap out 당하는 frame은 어떻게 골라지는 것일까?
vm_get_victim 쪽을 살펴보자.
vm_get_victim에 대한 내용을 필자가 작성한 함수가 아니다. 필자가 작성한 코드도 돌아가기는 하지만 좀 기괴하기에 동료의 코드를 가져다 쓰겠다.
vm_get_victim
struct list lru_list;
static struct frame *vm_get_victim (void) {
struct frame *victim = NULL;
struct list_elem *now_elem = list_head(&lru_list);
/* TODO: The policy for eviction is up to you. */
while((now_elem = list_next(now_elem)) != list_tail(&lru_list)){
victim = list_entry(now_elem, struct frame, frame_elem);
return victim;
}
return victim;
}frame만을 관리해주기 위한 lru_list를 선언해주었다. 자연스레 frame의 구조체에도 list_elem을 선언해주면 된다.
lru_list의 앞에서 부터 frame을 가져온다.
vm_evict_frame
static struct frame *vm_evict_frame (void) {
struct frame *victim = vm_get_victim ();
/* TODO: swap out the victim and return the evicted frame. */
list_remove(&victim->frame_elem);
swap_out(victim->page))
victim->page->frame = NULL;
victim->page = NULL;
return victim;
}lru_list에서 제거 해주고 해당 frame에 대해 swap out을 해준다.
vm_get_frame
static struct frame *vm_get_frame(void) {
struct frame *frame = NULL;
/* Project 3 */
frame = malloc(sizeof(struct frame)); // kernel pool 할당
void *kva = palloc_get_page(PAL_USER); // user pool 할당
if (!kva) {
free(frame);
frame = vm_evict_frame();
}
else {
frame->kva = kva;
frame->page = NULL;
}
list_push_back(&lru_list, &frame->frame_elem);
return frame;
}
static bool vm_do_claim_page(struct page *page) {
struct frame *frame = vm_get_frame();
/* Set links */
frame->page = page;
page->frame = frame;
/* Project 3. */
/* TODO: Insert page table entry to map page's VA to frame's PA. */
uint64_t* pml4 = thread_current()->pml4;
// 가상 주소와 물리 주소를 맵핑한 정보를 페이지 테이블에 추가한다.
pml4_set_page(pml4, page->va, frame->kva, page->writable);
// #define swap_in(page, v) (page)->operations->swap_in ((page), v)
return swap_in(page, frame->kva);
}swap out을 통해 해당 frame과 연결된 page는 날려버렸으니 page_fault가 났던 va를 커버하는 page와의 맵핑을 해준다.
여기까지 마쳤다면 5개의 fail이 난다.
pass tests/userprog/args-none
pass tests/userprog/args-single
pass tests/userprog/args-multiple
pass tests/userprog/args-many
pass tests/userprog/args-dbl-space
pass tests/userprog/halt
pass tests/userprog/exit
pass tests/userprog/create-normal
pass tests/userprog/create-empty
pass tests/userprog/create-null
pass tests/userprog/create-bad-ptr
pass tests/userprog/create-long
pass tests/userprog/create-exists
pass tests/userprog/create-bound
pass tests/userprog/open-normal
pass tests/userprog/open-missing
pass tests/userprog/open-boundary
pass tests/userprog/open-empty
pass tests/userprog/open-null
pass tests/userprog/open-bad-ptr
pass tests/userprog/open-twice
pass tests/userprog/close-normal
pass tests/userprog/close-twice
pass tests/userprog/close-bad-fd
pass tests/userprog/read-normal
pass tests/userprog/read-bad-ptr
pass tests/userprog/read-boundary
pass tests/userprog/read-zero
pass tests/userprog/read-stdout
pass tests/userprog/read-bad-fd
pass tests/userprog/write-normal
pass tests/userprog/write-bad-ptr
pass tests/userprog/write-boundary
pass tests/userprog/write-zero
pass tests/userprog/write-stdin
pass tests/userprog/write-bad-fd
pass tests/userprog/fork-once
pass tests/userprog/fork-multiple
pass tests/userprog/fork-recursive
pass tests/userprog/fork-read
pass tests/userprog/fork-close
pass tests/userprog/fork-boundary
pass tests/userprog/exec-once
pass tests/userprog/exec-arg
pass tests/userprog/exec-boundary
pass tests/userprog/exec-missing
pass tests/userprog/exec-bad-ptr
pass tests/userprog/exec-read
pass tests/userprog/wait-simple
pass tests/userprog/wait-twice
pass tests/userprog/wait-killed
pass tests/userprog/wait-bad-pid
pass tests/userprog/multi-recurse
pass tests/userprog/multi-child-fd
pass tests/userprog/rox-simple
pass tests/userprog/rox-child
pass tests/userprog/rox-multichild
pass tests/userprog/bad-read
pass tests/userprog/bad-write
pass tests/userprog/bad-read2
pass tests/userprog/bad-write2
pass tests/userprog/bad-jump
pass tests/userprog/bad-jump2
pass tests/vm/pt-grow-stack
pass tests/vm/pt-grow-bad
pass tests/vm/pt-big-stk-obj
pass tests/vm/pt-bad-addr
pass tests/vm/pt-bad-read
pass tests/vm/pt-write-code
pass tests/vm/pt-write-code2
pass tests/vm/pt-grow-stk-sc
pass tests/vm/page-linear
pass tests/vm/page-parallel
FAIL tests/vm/page-merge-seq
FAIL tests/vm/page-merge-par
FAIL tests/vm/page-merge-stk
FAIL tests/vm/page-merge-mm
pass tests/vm/page-shuffle
pass tests/vm/mmap-read
pass tests/vm/mmap-close
pass tests/vm/mmap-unmap
pass tests/vm/mmap-overlap
pass tests/vm/mmap-twice
pass tests/vm/mmap-write
pass tests/vm/mmap-ro
pass tests/vm/mmap-exit
pass tests/vm/mmap-shuffle
pass tests/vm/mmap-bad-fd
pass tests/vm/mmap-clean
pass tests/vm/mmap-inherit
pass tests/vm/mmap-misalign
pass tests/vm/mmap-null
pass tests/vm/mmap-over-code
pass tests/vm/mmap-over-data
pass tests/vm/mmap-over-stk
pass tests/vm/mmap-remove
pass tests/vm/mmap-zero
pass tests/vm/mmap-bad-fd2
pass tests/vm/mmap-bad-fd3
pass tests/vm/mmap-zero-len
pass tests/vm/mmap-off
pass tests/vm/mmap-bad-off
pass tests/vm/mmap-kernel
pass tests/vm/lazy-file
pass tests/vm/lazy-anon
pass tests/vm/swap-file
pass tests/vm/swap-anon
pass tests/vm/swap-iter
pass tests/vm/swap-fork
pass tests/filesys/base/lg-create
pass tests/filesys/base/lg-full
pass tests/filesys/base/lg-random
pass tests/filesys/base/lg-seq-block
pass tests/filesys/base/lg-seq-random
pass tests/filesys/base/sm-create
pass tests/filesys/base/sm-full
pass tests/filesys/base/sm-random
pass tests/filesys/base/sm-seq-block
pass tests/filesys/base/sm-seq-random
pass tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
pass tests/filesys/base/syn-write
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
FAIL tests/vm/cow/cow-simple
5 of 141 tests failed.