[Pintos-KAIST] Project 3 : Swap In / Out

👩🏻‍💻 GITHUB 레포지토리
👩🏻‍💻 GITHUB Swap In / Out 이슈

과제 설명

Memory swapping은 physical memory 사용을 극대화하기 위한 memory 회수 기법이다. main memory의 frame이 할당되면 system은 user program의 메모리 할당 요청을 더 이상 처리할 수 없다. 한 가지 해결책은 최근에 사용되지 않는 memory frame을 disk로 교체하는 것이다. 이렇게 하면 일부 memory resource가 확보되어 다른 응용프로그램에서 사용 가능해진다.

가상 주소 안의 VPN에 Present Bit을 두어 해당 페이지가 디스크로 스왑되었는지를 나타낸다.

swapping은 OS 에 의해 실행된다. system에서 memory가 부족한데 메모리 할당 요청을 받으면 교환할(evict) page를 고른다. 그 다음 메모리 frame의 정확한 상태가 disk에 복사된다. 프로세스가 swap out된 page에 액세스하려고 하면 OS는 정확한 내용을 memory에 다시 가져와서 page를 복구한다.

---

구현

1. 사전 설정 ~~

✔️ 자료구조, lock, 헤더파일 선언하기!

• vm/anon.c
• 디스크에서 사용 가능한 swap slot과 사용 불가능한 swap slot을 관리하는 자료구조인 Swap Table(=swap_bitmap)을 선언해준다.
• 이 때 스왑 테이블은 비트맵 객체로 선언된다.
• 스왑 테이블은 가상 메모리에 있는 객체이다.

/** Project 3-Swap In/Out */
#include <bitmap.h>
#include "threads/vaddr.h"
#define SECTOR_PER_PAGE (PGSIZE / DISK_SECTOR_SIZE)
static struct bitmap *swap_bitmap;
static struct lock swap_lock;

💡 SECTORS_PER_PAGE
한 페이지에 들어갈 수 있는 디스크 섹터의 개수를 의미한다. PGSIZE == 1<<12 == 4kb이고 DISK_SECTOR_SIZE == 512byte이다.

2. vm_anon_init() 구현

• vm/anon.c
• anon 페이지를 위한 디스크 내 스왑 영역을 생성해주는 함수이다.
• 디스크 내에 스왑 영역을 만들어주고 이를 관리하는 스왑 테이블도 만들어준다.
• swap_size는 스왑 디스크 안에서 만들 수 있는 스왑 슬롯의 개수를 의미한다.

void
vm_anon_init (void) {
	/** Project 3-Swap In/Out */
	swap_disk = disk_get(1, 1);
	swap_bitmap = bitmap_create(disk_size(swap_disk) / SECTOR_PER_PAGE);
	lock_init(&swap_lock);
}

3. anon_page 자료구조 수정

• include/vm/anon.h

struct anon_page {
    /** Project 3-Swap In/Out */
    size_t page_no;
};

4. anon_initializer() 구현

• vm/anon.c
• page struct 안의 Union 영역은 현재 uninit page이다.
• anon page를 초기화해주기 위해 해당 데이터를 모두 0으로 초기화해준다.
• 이제 해당 페이지는 anon이므로 operations도 anon으로 지정한다.

bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
	/** Project 3-Swap In/Out */
	struct uninit_page *uninit = &page->uninit;
	memset(uninit, 0, sizeof(struct uninit_page));
	page->operations = &anon_ops;
	
	struct anon_page *anon_page = &page->anon;
	anon_page->page_no = BITMAP_ERROR;
	return true;
}

5. anon_swap_out() 구현

• vm/anon.c
• 가상 메모리의 스왑 테이블에서 비트가 false인 스왑 슬롯을 찾는다. 비트가 false라는 말은 해당 스왑 슬롯에 swap out된 페이지를 할당할 수 있다는 의미이다.
• 해당 스왑 슬롯에 해당하는 디스크의 영역에 가상 주소 공간의 데이터를 페이지의 시작 주소부터 디스크 섹터 크기로 잘라서 저장한다.
• 해당 스왑 슬롯에 대응되는 스왑 테이블의 비트를 TRUE로 바꿔주고, anon 페이지의 page_no에 스왑 슬롯 번호를 저장해서 이 페이지가 디스크의 스왑 영역 중 어디에 swap 되었는지를 확인할 수 있도록 한다.

static bool
anon_swap_out (struct page *page) {
	struct anon_page *anon_page = &page->anon;
	/** Project 3-Swap In/Out */
	lock_acquire(&swap_lock);
	size_t page_no = bitmap_scan_and_flip(swap_bitmap, 0, 1, false);

	if (page_no == BITMAP_ERROR){
		lock_release(&swap_lock);
		return false;
	}

	for (size_t i = 0; i < SECTOR_PER_PAGE; i++)
		disk_write(swap_disk, (page_no * SECTOR_PER_PAGE) + i, page->va + (i * DISK_SECTOR_SIZE));
	anon_page->page_no = page_no;
	page->frame->page = NULL;
	page->frame = NULL;
	pml4_clear_page(thread_current()->pml4, page->va);
	lock_release(&swap_lock);
}

6. anon_swap_in() 구현

• vm/anon.c
• SWAP OUT된 페이지에 저장된 swap_index 값으로 스왑 슬롯을 찾아 해당 슬롯에 저장된 데이터를 다시 페이지로 원복시킨다.

static bool
anon_swap_in (struct page *page, void *kva) {
	struct anon_page *anon_page = &page->anon;
	/** Project 3-Swap In/Out */
	lock_acquire(&swap_lock);
	if (anon_page->page_no == BITMAP_ERROR){
		lock_release(&swap_lock);	
		return false;
	}


	if (!bitmap_test(swap_bitmap, anon_page->page_no)){
		lock_release(&swap_lock);	
		return false;
	}

	for (size_t i = 0; i < SECTOR_PER_PAGE; i++)
		disk_read(swap_disk, (anon_page->page_no * SECTOR_PER_PAGE) + i, kva + (i * DISK_SECTOR_SIZE));

	bitmap_set(swap_bitmap, anon_page->page_no, false);

	lock_release(&swap_lock);
	anon_page->page_no = BITMAP_ERROR;

	return true;
}

7. anon_destroy() 구현

• vm/anon.c

static void
anon_destroy (struct page *page) {
	struct anon_page *anon_page = &page->anon;
	/** Project 3-Swap In/Out */
    if (anon_page->page_no != BITMAP_ERROR)
        bitmap_reset(swap_bitmap, anon_page->page_no);

    if (page->frame) {
		lock_acquire(&swap_lock);
        list_remove(&page->frame->frame_elem);
		lock_release(&swap_lock);
        page->frame->page = NULL;
        free(page->frame);
        page->frame = NULL;
    }
}

8. file_backed_swap_out() 구현

• vm/file.c
• swap out 시키려는 페이지가 비어있으면 안되므로 검사해준다.
• aux에 컨테이너 구조체를 입력하고 dirty bit를 통해 수정이 되었는지 확인한다.
• 만약 수정되었다면 파일에 수정된 내용을 기입하고 dirty bit를 0으로 갱신시켜준다.
• 그 후 pml4의 present bit를 수정하여 page fault가 발생하도록 한다.

static bool
file_backed_swap_out (struct page *page) {
	struct file_page *file_page UNUSED = &page->file;
	/** Project 3-Swap In/Out */
	struct frame *frame = page->frame;

	if (pml4_is_dirty(thread_current()->pml4, page->va))
	{
		file_write_at(file_page->file, page->frame->kva, file_page->page_read_bytes, file_page->offset);
		pml4_set_dirty(thread_current()->pml4, page->va, false);
	}
	page->frame->page = NULL;
	page->frame = NULL;
	pml4_clear_page(thread_current()->pml4, page->va);
	return true;
}

9. file_backed_swap_in() 구현

• vm/file.c
• 파일로 부터 데이터를 읽어 메모리로 올린다.
• lazy_load_segment()와 유사하다.

static bool
file_backed_swap_in (struct page *page, void *kva) {
	struct file_page *file_page UNUSED = &page->file;
	/** Project 3-Swap In/Out */
	int read = file_read_at(file_page->file, page->frame->kva, file_page->page_read_bytes, file_page->offset);
	memset(page->frame->kva + read, 0, PGSIZE - read);
	return true;
}

10. vm_get_victim() 구현

10-1. vm.c lock 추가 및 초기화

• vm/vm.c

/** Project 3-Swap In/Out */
struct lock frame_lock;

void
vm_init (void) {
	vm_anon_init ();
	vm_file_init ();
#ifdef EFILESYS  /* For project 4 */
	pagecache_init ();
#endif
	register_inspect_intr ();
	/* DO NOT MODIFY UPPER LINES. */

	/** Project 3-Memory Management */
	list_init(&frame_table);
	
	/** Project 3-Swap In/Out */
	lock_init(&frame_lock);
}

10-2. next list_elem 선언

• vm/vm.c

/** Project 3-Swap In/Out */
struct lock frame_lock;
struct list_elem *next = NULL;

10-3. vm_get_victim() 구현

• vm/vm.c

static struct frame *
vm_get_victim (void) {
	struct frame *victim = NULL;
	/** Project 3-Swap In/Out */
	lock_acquire(&frame_lock);
	for (next = list_begin(&frame_table); next != list_end(&frame_table); next = list_next(next))
	{
		victim = list_entry(next, struct frame, frame_elem);
		if (pml4_is_accessed(thread_current()->pml4, victim->page->va))
			pml4_set_accessed(thread_current()->pml4, victim->page->va, false);
		else{
			lock_release(&frame_lock);
			return victim;
		}
	}
	lock_release(&frame_lock);
	return victim;
}

11. vm_evict_frame() 구현

• vm/vm.c

static struct frame *
vm_evict_frame (void) {
	/** Project 3-Swap In/Out */
	struct frame *victim = vm_get_victim ();
	if (victim->page)
		swap_out(victim->page);
	return victim;
}

테스트 결과

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
pass tests/vm/page-merge-seq
pass tests/vm/page-merge-par
pass tests/vm/page-merge-stk
pass 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
1 of 141 tests failed.

ec2 환경에서 swap-fork가 FAIL하였지만, WSL 환경에서 pass하는 것을 확인함.