[PintOS] Project 3: Anonymous Page

설현아·2025년 6월 5일
pintos
post-thumbnail

지난 이틀 정도는 컨디션 이슈로 오래 앉아있지를 못했다.
개념 정리까지만 포스팅을 하고, 구현 단계에서는 정리하면서 개발하진 못했다.

컨디션이 좋아졌으니,
고민의 기억이 소멸되기 전에 정리해보자!

PintOS 마지막 팀의 협업 규칙

이번 팀에서는 코드 병합을 어떻게 할지 더 깊이 고민하였다.
다른 반이 협업하는 방식을 엿보았을 때, 기능 단위로 티켓을 나누어 각자의 티켓에 좀 더 집중하여 구현하는 협업 방식이 좋게 느껴졌다.

지난 팀에서는 각자 개발하는 성질이 강했다보니,
함께 고민한다기보다는 막히는 부분이 있을 때 진도가 더 빠른 팀원에게 조언을 구하며 '나의 것'을 구현해나가는 성질이 강했다.

그렇다보니, 마지막 협업에서 '우리의 것'을 구현해보고 싶다는 욕구가 있었다.
팀원들과의 간단한 상의를 통해, 공통되는 부분은 함께 고민하고 짧은 단위로 코드 병합을 하기로 하였다.
anonymous page까지는 다같이 구현하고, 그 이후는 티켓 단위로 나누어 구현하는 것이 최초의 계획이었다.
지금은 생각보다 시간 여유가 있을 것 같아서 우선은 계속 같이 구현해보기로 한 상태이다. 아무래도 모든 파트의 빈 종이부터 고민해보는 시간이 유의미하다고 생각했기 때문이다.

여튼 우리 팀은
촘촘하게 파고들어 탄탄한 기본기를 가진 매우 섬세하고 초사랑스러운 한 명의 팀원과,
무뚝뚝해보이는 이미지와는 달리 굉장히 뜨뜻한 고지능의 팀원이 있다.

마지막 핀토스 주차에 열심히 하는 팀원들을 만나게 되어 운이 좋다고 생각한다.

  • ☑️ 6/4 Memory Management
  • ☑️ 6/5 Anonymous Page
  • ☑️ 6/7 Stack Growth
  • ☑️ 6/10 Memory Mapped Filed
  • ☑️ 6/10 ~ Swap In/Out

이렇게 구현 일정을 계획하였다.
역시 계획이 있으면 늘 발등에 불 떨어진 기분을 느낄 수 있어 효율이 증가한다. ㅎ

포스팅하는 지금은 Anonymous Page까지 구현하고 코드를 병합한 상태이다.

Memory Management

Implement Supplemental Page Table

Lazy Loading을 구현하기 위한 보조 도구로 SPT를 설계하는 것이 목표이다.

현재 구현되어있는 pml4만 가지고는 Lazy Loading을 구현할 수 없다.
실제로 메모리에 접근하는 시점에 이 페이지가 어떤 역할을 하는 페이지인지, 어떤 것을 요구했었는지를 저장해둘 보조 도구가 필요하다.

struct supplemental_page_table

git book에서는 이 자료구조를 구현하기 위해 다양한 자료구조 중 선택하여 사용해도 된다고 하지만, hash table로 구현하기를 권장한다.
따라서 기존에 구현되어 있는 hash 자료구조를 활용한다.

구현되어있는 hash 자료구조를 bucket은 list로 구현되어있다.
따라서 list_elem을 page 구조체에 추가로 선언해준다.

struct supplemental_page_table {
 	struct hash spt_hash;
 };
struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */
	struct hash_elem elem;
   .
   .

실은 이번 과제는
구현되어있는 hash 함수를 얼마나 잘 이해했는가가 중요하다.
그거면 된다.

SPT와 관련하여 구현을 요하는 함수는

  • supplemental_page_table_init
  • spt_find_page
  • spt_insert_page

이렇게 세 가지이다.

이는 hash 자료구조로 구현하기로 하였으니, 이 자료구조를 초기화하고, 삽입하고, 원소를 찾는 연산을 잘 구현해주면 될 것으로 보인다.

그렇다면 hash 관련 함수를 먼저 분석하자.
https://casys-kaist.github.io/pintos-kaist/appendix/hash_table.html

hash 자료구조는 아래와 같이 구현되어있다.

chaining을 적용한 표준 hash table 방식이다.

element의 데이터(key)를 hash function을 활용하여 해시값을 산출한다. 이 해시값을 doubly linked list 배열의 인덱스로 사용한다.
즉, 각 bucket[i]는 해시값이 i인 모든 요소에 대하여 doubly linked list로 저장한다.

더 자세한 건 다음에 다룰 수 있으면 다루도록 한다.
.
.

hash table을 사용하기 위해서는 두 개의 helper 함수가 필요하다.

  • hash function은 addr를 key로 구현할 수 있다.
  • comparison function은 같은 key를 가진 원소가 이미 존재하는지 확인하기 위해 대소 비교를 하는 함수이다.


아주 친절하게 예시까지 주어준다. 이 가이드가 있어서 그대로 구현한다.

supplemental_page_table_init()

void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->spt_hash, hashing_page, comp_less_addr, NULL);
}
  • hashing_page
unsigned hashing_page(const struct hash_elem *e, void *aux UNUSED){
	const struct page *p = hash_entry(e, struct page, elem);
	return hash_bytes(&(p->va), sizeof(p->va));
}
  • comp_less_addr
static bool comp_less_addr(const struct hash_elem *a, const struct hash_elem *b, void *aux){
	const struct page *p1 = hash_entry(a, struct page, elem);
	const struct page *p2 = hash_entry(b, struct page, elem);

	return p1->va < p2->va;
}

spt_find_page()

struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	struct page *page = NULL;
	/* TODO: Fill this function. */
	page = (struct page*)malloc(sizeof(struct page));
	page->va = pg_round_down(va);

	struct hash_elem* find_e = hash_find(&spt->spt_hash, &(page->elem));
	free(page);

	if(find_e == NULL) return NULL;

	return hash_entry(find_e, struct page, elem);
}

spt_insert_page()

bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	int succ = false;
	/* TODO: Fill this function. */
	succ = insert_page(&(spt->spt_hash), page);
	return succ;
}
  • insert_page
bool insert_page(struct hash *ha, struct page *pa){
	struct hash_elem* check = hash_insert(ha, &(pa->elem));
	if(check == NULL){
		return true;
	}
	return false;
}

Frame Management

물리 메모리는 페이지 단위로 가상 메모리와 매핑되는데, 이 때 물리 메모리를 frame 구조체로 os 단에서 관리한다.

이유는 이전 포스팅에서 다뤘듯, 물리 메모리의 frame 또한 table로 관리하여, 비어있는 frame을 선택하거나 희생자 페이지를 결정하는 데 사용한다.

이제 frame table을 설계해보자.

구현을 요구하는 함수는 세 가지이다.

  • vm_get_frame
  • vm_do_claim_page
  • vm_claim_page

frame을 선택하고, page table에 매핑하는 역할을 할 것 같다.

struct frame

frame table은 list로 관리하기로 한다.
그러면 frame 구조체에는 list_elem이 추가되어야 하며,
frame table은 vm.c 내에서 전역적으로 사용되어야 한다.

// vm.h
struct frame {
	void *kva;
	struct page *page;

	struct list_elem elem;
};
// vm.c
static struct list frame_list;
static struct lock frame_lock;

여기에서 lock을 같이 선언해주었는데,
frame table은 공유자원이기 때문에 race condition이 발생할 수 있다. 따라서 lock으로 관리해줄 필요가 있다. vm_init에서 list, lock을 초기화해주는 것까지 잊지말자.
(lock은 내가 미처 생각하지 못했는데 우리 팀원의 코드를 보고 아차 싶었다. 참 좋다!)

vm_get_frame()


palloc_get_page를 호출하여 user pool에서 physical page를 가져오면 된다.


static struct frame *
vm_get_frame (void) {
	struct frame *frame = NULL;
	/* TODO: Fill this function. */

	frame = (struct frame*)malloc(sizeof(struct frame));
	if(frame == NULL) PANIC("vm_get_frame: allocate failed");

	frame->page = NULL;

	frame->kva = palloc_get_page(PAL_USER);

	if(frame->kva == NULL){
		frame = vm_evict_frame();
		frame->page = NULL;
		return frame;
	}

	lock_acquire(&frame_lock);
	list_push_back(&frame_list, &(frame->elem));
	lock_release(&frame_lock);

	frame->page = NULL;

	return frame;
}

frame 구조체를 malloc으로 할당해준 후에 palloc_get_page 함수를 PAL_USER flag를 가지고 호출한다.
만약, 할당에 실패했다면 eviction을 수행한다.(희생자 페이지를 선택하여 swap out)
그리고 frame list에 추가해준다.
frame list는 FIFO를 기반으로 하기 때문에 list_push_back으로 삽입해준다.

vm_do_claim_page()


여기에서는 vm_get_frame으로 선택된 frame을 pml4(page table)에 매핑해준다.

이 때 중요한 것은
물리 메모리에 매핑된 이후, 그 페이지를 다시 swap in 하는 절차가 필요하다는 점이다.


static bool
vm_do_claim_page (struct page *page) {
	struct frame *frame = vm_get_frame ();

	/* Set links */
	frame->page = page;
	page->frame = frame;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	
	if (!pml4_set_page (thread_current ()->pml4,
        page->va,
        frame->kva,
        page->rw_w)) {
        
        frame->page = NULL;
        page->frame = NULL;
        palloc_free_page (frame->kva);
        free (frame);
        return false;
    }

    if (!swap_in (page, frame->kva)) {
        pml4_clear_page (thread_current ()->pml4, page->va);
        frame->page = NULL;
        page->frame = NULL;
        palloc_free_page (frame->kva);
        free (frame);
        return false;
    }

    return true;
}

vm_claim_page()


이 함수는 위에서 정의한 vm_do_claim_page() 의 wrapper 함수다.
다른 파일에서 사용하려 할 때는 VA를 가지고 SPT에서 해당 page를 찾는 절차가 하나 더 필요하다.

bool
vm_claim_page (void *va UNUSED) {
	struct page *page = NULL;
	/* TODO: Fill this function */

	page = spt_find_page(&thread_current()->spt, va);
	if(page == NULL) return 0;

	return vm_do_claim_page (page);
}

.
.

요구사항과 별개로 구현이 필요한 TODO 함수들이 꽤나 많다.
그 중, 나는 미뤄뒀던 함수를 똑똑이 팀원분이 페이지 교체 알고리즘 중, clock 알고리즘으로 vm_get_victim을 구현하셨다.

vm_get_victim()

clock 알고리즘?
지금 사용하지 않는다고 해서 바로 희생자 페이지로 선택하는 것이 아니라, 한 번의 기회를 더 주는 것이다.
accessed bit가 1일 때, 0으로 내려주며 기회를 한 번 더 준다.
이후에 accessed bit가 0이라면 해당 frame을 희생자로 선택한다.
조금 더 자비로운 FIFO 방식이라고 보면 된다.

전역적으로 clock_hand를 정의한다.

static struct list_elem *clock_hand = NULL;

지난 loop에서 어느 frame까지 기회를 줬는지 기억해야하기 때문.

static struct frame *
vm_get_victim (void) {
	struct frame *victim = NULL;
	 /* TODO: The policy for eviction is up to you. */
	if (list_empty(&frame_list))
        return NULL;

    /* clock_hand가 아직 초기화되지 않았으면, 리스트의 첫 번째 요소로 설정 */
    if (clock_hand == NULL || clock_hand == list_end(&frame_list))
        clock_hand = list_begin(&frame_list);

    /* 무한 루프 돌며 accessed 비트를 체크 */
    while (true) {
        struct frame *f = list_entry(clock_hand, struct frame, elem);

        /* 현재 쓰레드(page_table 기준)에서 accessed 비트 확인 */
        if (pml4_is_accessed(thread_current()->pml4, f->page->va)) {
            /* accessed 비트가 1이면, 우선권(Second Chance)을 주고 비트를 지운 후 다음으로 */
            pml4_set_accessed(thread_current()->pml4, f->page->va, 0);

    ![](https://velog.velcdn.com/images/sha0209/post/43f061f6-0b84-42cd-9e5b-3439c7e99bc1/image.png)
    ![](https://velog.velcdn.com/images/sha0209/post/11e13b5f-0175-4a73-858f-d628d273033c/image.png)
    /* 다음으로 이동. 리스트 끝에 도달하면 다시 처음으로 순환 */
            clock_hand = list_next(clock_hand);
            if (clock_hand == list_end(&frame_list))
                clock_hand = list_begin(&frame_list);
        }
        else {
            /* accessed 비트가 0이면 이 프레임을 희생자로 선택 */
            victim = f;

            /* 다음 호출에서도 순환을 이어가기 위해 핸드를 다음 요소로 이동 */
            clock_hand = list_next(clock_hand);
            if (clock_hand == list_end(&frame_list))
                clock_hand = list_begin(&frame_list);

            return victim;
        }
    }
}

여기까지가 Memory Management 과제이다.
make check 해보면 124 fail이 뜬다.

Anonymous Page

본격적으로 Lazy Loading을 구현한다.
Lazy Loading을 구현하기 위해서는 이 흐름을 잘 이해해야 한다.

코드에 휩쓸려가지말고, 이론 먼저 탄탄히 다지는 게 중요하다.

Lazy Loading을 하기 위해서는 어떤 것들이 추가적으로 필요할지 생각해보자.
최초에 프로세스가 load될 때는 물리 메모리에 즉시에 매핑되지 않는다.
가상 주소를 부여받고, page 구조체를 구성하지만 물리 메모리와는 관련 없다.
따라서, 최초에 접근하는 시점에 page fault가 발생한다.

page fault가 발생했을 때, 이 페이지가 lazy loading을 위한 페이지인지, 혹은 잘못된 접근인지 어떻게 판단할까?

여태까지 구현한 SPT가 그 도구가 된다.

page fault가 생기면 SPT에서 그 페이지가 있는지 확인한다.
만약, SPT에서 찾았다면 위에서 구현해둔 메서드로 frame과 매핑해준다.
근데 이미 다른 프로세스로 제어권이 넘어가고, 또다시 제어권을 획득하고 메모리에 접근해야만 매핑되고 그 이후에 파일을 로드하는 등의 작업을 수행하게 되는데,
최초에 어떤 작업을 요구받은 페이지였는지 의 정보를 어떻게 보존할 수 있을까?

다시 제어권을 획득했을 떄, 여전히 그 페이지의 정보를 알고있어야 파일을 로드하여 physical memory에 올릴 수 있다.
따라서 SPT에서는 이런 페이지의 정보들을 저장해두어야 한다.
페이지의 정보에는 다음과 같은 것들이 포함될 수 있겠다.

  • 페이지의 type(anonymous? file backed?)
  • 페이지 별로 정의된 함수들(initializer, swap-in, swap-out 등)
  • virtual address
    등

여기까지 보면 gitbook에서 나오는 uninit의 존재 이유를 더 잘 이해할 수 있다.
page의 type별로 정의된 함수가 있고, lazy loading이 됨에 따라 최초부터 원본 type으로 정의해두면 이 페이지가 어떤 상태인지 알기 어렵다.

따라서,
초기화되지 않은, 즉 lazy loading을 기다리는 페이지의 타입을 uninti으로 설정하여 초기화한다.

uninit 페이지는 초기화 과정에서 가장 중요하게는 두 가지 일을 해야한다.

  1. 나중에 frame에 매핑될 때, 원본 type에 따른 초기화를 미리 준비해두어야 한다.(file backed page라면 file을 읽어야 하며, anonymous page라면 0으로 초기화해야한다.)
  2. page의 기본적인 정보를 초기화한다.

이를 이해하고 시작해보자.

vm_alloc_page_with_initializer()

이 함수가 이번 과제의 거의 전부라고 해도 과언이 아닐만큼 이해하는 것도 어렵고, 복잡하지만 중요하다.

page type에 따른 initializer를 포함하여 새로운 페이지를 할당해주는 함수이다.

VM_ANON이라면, anon_initializer를 page_initailizer로 설정하고
VM_FILE이라면, file_backed_initializer를 page_initailizer로 설정한다.

또한, init이 의미하는 바를 이해하는 것도 중요하다.
이는 page type 별 초기화 함수가 아닌, 초기화 과정에서 호출되어야 할 함수를 정의한 것을 인자로 넘겨받은 것이다. 이 함수에 대한 인자로는 aux를 받는다.(이 함수는 lazy_load_segment 가 된다는 것을 조금 후에 알 수 있다.)

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;

	// to do
	/* Check wheter the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {
		/* TODO: Create the page, fetch the initialier according to the VM type,
		 * TODO: and then create "uninit" page struct by calling uninit_new. You
		 * TODO: should modify the field after calling the uninit_new. */

		// need to modify(control with switch case)
		struct page* new_page = (struct page*)malloc(sizeof(struct page));

		if(type == VM_ANON) uninit_new(new_page, upage, init, type, aux, anon_initializer);
		else uninit_new(new_page, upage, init, type, aux, file_backed_initializer);

		new_page->rw_w = writable;
		/* TODO: Insert the page into the spt. */
		return spt_insert_page(spt, new_page);
	}
err:
	return false;
}

uninit_initialize()

uninit page의 swap in 함수로 매핑된 루틴이다.

static bool
uninit_initialize (struct page *page, void *kva) {
	struct uninit_page *uninit = &page->uninit;

	/* Fetch first, page_initialize may overwrite the values */
	vm_initializer *init = uninit->init;
	void *aux = uninit->aux;

	/* TODO: You may need to fix this function. */
	return uninit->page_initializer (page, uninit->type, aux) &&
		(init ? init (page, aux) : true);
}

수정은 하지 않았다.
위에서 매핑해준 두 개의 initailizer를 실행시켜준다.

다시 상기하자면다시 상기하자면,
1. type 별 initializer → anon_initializer or file_backed_iinitializer
2. vm_alloc_page_with_initializer 호출시 인자로 넘겨받은 init 함수 → lazy_load_segment

vm_anon_init()

이 함수는 도무지 내 힘으로 하지 못했다.
(지금 봐도 disk의 컴퓨터적 지식과 disk.c 파일의 코드 지식이 없다면 어렵지 않을까 싶다.)
똑똑이 팀원분께서 도와주셨고, 흐름을 요약하자면 아래와 같다.

  • bitmap 자료구조로 swap table을 관리한다.
  • 먼저 disk 내 swap 목적의 위치인 1, 1에서 get해온다.
  • 그 size를 page 단위로 얻는다.
  • swap table에 얻어온 page 단위의 slot 개수 만큼 생성해준다.
  • swap table을 0으로 초기화한다.

swap slot이 -1 즉, 음수이면 swap_disk에 존재하지 않는 것이고,
양수이면 해당 slot의 index를 가진다.


static struct bitmap* swap_table;


void
vm_anon_init (void) {
	/* TODO: Set up the swap_disk. */
	swap_disk = disk_get(1, 1);
	if(swap_disk == NULL) PANIC("vm_anon_init: swap_disk failed");

	size_t total_sectors = disk_size(swap_disk);
	if(!total_sectors) PANIC("vm_anon_init: zero_sectors");

	
	size_t sector_count = (1<<12) / DISK_SECTOR_SIZE;
	ASSERT(sector_count > 0);

	size_t total_slots = total_sectors / sector_count;
	if(!total_slots) PANIC("vm_anon_init: disk too small");

	swap_table = bitmap_create(total_slots);
	if(swap_table == NULL) PANIC("vm_anon_init: bitmap failed");

	bitmap_set_all(swap_table, false);

	lock_init(&swap_lock);
}

anon_initializer()

bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
	/* Set up the handler */
	ASSERT(type == VM_ANON);

	page->operations = &anon_ops;

	struct anon_page *anon_page = &page->anon;
	anon_page->swap_slot = -1;
}

실은 위의 두 함수는 팀원 분의 코드여서 100% 내 것으로 만들지 못했다ㅜㅜ
내게는 아직 swap table이 어렵게 느껴진다.
좀 더 공부해야겠다!

졸리니까 내일 다시...

load_segment()


static bool
load_segment(struct file* file, off_t ofs, uint8_t* upage,
	uint32_t read_bytes, uint32_t zero_bytes, bool writable) {
	ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT(pg_ofs(upage) == 0);
	ASSERT(ofs % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0) {
		/* Do calculate how to fill this page.
		 * We will read PAGE_READ_BYTES bytes from FILE
		 * and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* TODO: Set up aux to pass information to the lazy_load_segment. */

		struct vm_aux* load_arg = malloc(sizeof(struct vm_aux));
		if(load_arg == NULL) return false;
		load_arg->file = file;
		load_arg->ofs = ofs;
		load_arg->read_bytes = page_read_bytes;
		load_arg->zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer(VM_FILE, upage,
			writable, lazy_load_segment, load_arg)){
				free(load_arg);
				return false;
		}

		/* Advance. */
		ofs += page_read_bytes;
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
	}
	return true;
}

lazy_load_segment()


static bool
lazy_load_segment(struct page* page, void* aux) {
	/* TODO: Load the segment from the file */
	/* TODO: This called when the first page fault occurs on address VA. */
	/* TODO: VA is available when calling this function. */
	struct vm_aux* load_arg = (struct vm_aux*) aux;
	bool succ = true;
	void *kva = page->frame->kva;
	ASSERT(kva!=NULL);

	if(load_arg->read_bytes > 0){
		int bytes_read = file_read_at(
            load_arg->file,
            kva,
            load_arg->read_bytes,
            load_arg->ofs
        );
        if (bytes_read != (int) load_arg->read_bytes) {
            succ = false;
            goto done;
        }
	}

    if (load_arg->zero_bytes > 0) {
        memset(kva + load_arg->read_bytes, 0, load_arg->zero_bytes);
    }
done:
    free(load_arg);
    return succ;
}

setup_stack()


static bool
setup_stack(struct intr_frame* if_) {
	bool success = false;
	void* stack_bottom = (void*)(((uint8_t*)USER_STACK) - PGSIZE);

	/* TODO: Map the stack on stack_bottom and claim the page immediately.
	 * TODO: If success, set the rsp accordingly.
	 * TODO: You should mark the page is stack. */
	 /* TODO: Your code goes here */
	
    if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1)) {
        success = vm_claim_page(stack_bottom);

        if (success) {
            if_->rsp = USER_STACK;
            thread_current()->stack_bottom = stack_bottom;
        }
    }
    return success;

}
profile
설현아
어서오세요! ☺️ 후회 없는 내일을 위해 오늘을 열심히 살아가는 개발자입니다.
이전 포스트

Pintos VM에 대한 오해와 외면 극뽁 😁

다음 포스트

[PintOS] Project 3: Stack Growth

0개의 댓글