PintOS Project 3 VM swap in/out

핀토스 프로젝트 3 의 마지막 구현 과제인 (cow 제외) swap in/out 구현에 대한 이야기를 작성 해보려고 한다.
기초적인 swap in out 에 대한 이야기와 내가 구현한 방법과 어이없는 실수로 인한 디버깅을 이야기 해보겠다.

 

Swap in / out 이 뭔데요???

운영체제의 메모리 관리 기법중 하나이다. 당장 사용할 (페이지폴트나서 요청받은) 새로운 물리 메모리가 필요한데 이미 (사용자 영역의) 물리 메모리가 꽉차서 더이상 새로운 물리 메모리 프레임도 할당 받지 못 할 때 안쓰는 다른 프레임을 하드 디스크의 스왑 영역에 보내버리고 그 공간을 지금 쓰고싶은 페이지에게 주는 것이다.

 

Swap in / out Flow

1. 메모리가 꽉 차서 frame 할당 받는 것에 실패한다.
2. 현재 물리 메모리에 올라가있는 frame 들 중에서 운영체제만의 정책(policy)로 swap disk 로 보낼 frame을 고른다.
3. 골랐다면 swap disk 에 저장 가능한 공간을 찾는다.
4. 공간을 찾았다면 해당 위치에 frame을 저장하고 공간을 사용했다고 표시한다.
5. 나중에 swap disk에서 진짜 frame 을 찾기위해 frame 구조체에 해당 공간 위치(인덱스)를 저장한다.
6. 내쫒은 frame을 새로 할당 받고싶어하는 페이지에게 제공한다.
7. frame을 달라고 요청한 page 는 swap in을 실행한다.

 

ANON_Page Swap out - in Flow

page fault 발생

 

victim 고르고 swap out 시키기

 

frame 요청한 page에게 victim의 frame 위치 return 해주기

page내의 정보로 내가(frame을 요청한 page가) swap out 시켰었던 frame 찾기

이제 해당 페이지와 해당 페이지가 사용하던 진짜 프레임이 연결되어서 프로세스는 마저 하던일을 하면 된다!

 

뭐가 필요할까?

flow를 보면 사용중인 frame에서 내쫒을 frame도 찾아야하고 swap disk 에서 swap out 시켯었던 frame 도 찾아야한다.

그러니

현재 사용중인 frame들을 담는 list 가 필요하고 swap 영역에 있는 frame 들을 담는 bitmap(list 던 뭐든...) 이 필요하다.

또 프레임을 요청한 anon_page로 swap out 되었던 frame 도 찾아야하니, anon_page 구조체에 bitmap의 몇번째 인덱스에 저장했는지도 표시해야한다. 

또, 디스크의 스왑 영역도 받아야한다.

 

anon.h

vm.c

anon.c

anon.c

 

왜 anon 타입으로 콕 찝어서 설명하셨나요?
저희 핀토스에서는 anon만 스왑 영역을 사용해서 그랬습니다.
file 타입 페이지는 그 실체가 file에 있으니까 스왑영역에 해당 프레임을 백업해둘 필요는 없고 그저 원래 파일에 사용했던 내용을 작성(백업?) 하고 -swap out
swap in 할때는 그 파일을 읽도록 구현했습니다.

 

Evict policy

퇴출 정책 

스왑 아웃을 수행할 때, 어떤 페이지를 선택하여 스왑 아웃할지 결정하는 알고리즘을 퇴출 정책(evict policy)이라고 합니다. 다음과 같은 퇴출 정책이 있습니다.

LRU (Least Recently Used):

가장 최근에 사용되지 않은 페이지를 선택하여 스왑 아웃합니다.
이를 위해 각 페이지의 사용 시간을 기록하고, 가장 오랫동안 사용되지 않은 페이지를 선택합니다.

 

Clock Algorithm:

원형 버퍼를 사용하여 페이지를 순회하면서, 최근에 사용되지 않은 페이지를 찾습니다.
각 페이지에 '사용 비트'를 두어, 페이지가 참조될 때마다 이 비트를 설정합니다.
스왑 아웃할 페이지를 찾을 때는 이 비트를 확인하여, 설정되지 않은 페이지를 선택합니다.

 

우선 우리조는 가장 단순한 방법인 FIFO 로 구현했다.
list_pop_front() 했다는 뜻.

 

메모리가 꽉찬(부족한) 순간은 언제인지 어떻게 알아요???

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

	// 프레임 구조체 멤버들 초기화
	frame->kva = palloc_get_page(PAL_USER | PAL_ZERO); 
	if (frame->kva == NULL) {	<< 여기서 알아요 !!!!!
		free(frame);
		frame = vm_evict_frame();
	}

	// list_push_back(&frame_table, &frame->elem);

	frame->page = NULL;

	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
	return frame;
}

vm.c 의 vm_get_frame() 함수 (프레임을 요청하는 곳)에서 palloc_get_page 가 실패한다면 더이상 메모리에 공간이 없다는 것이니 저 if 문이 해당 순간을 포착하는 곳이다.

 

우리의 구현

git_repo

vm.c

anon.c

file.c

 

디버깅

프로세스를 잘 실행하고 종료하고 다음 테스트를 진행하는 사이 단계에 패닉을 내뿜는 버그 발생.

잘 실행하고 종료할 때 패닉을 내니 exit() 단계를 추적함.

버그가 생기는 곳은 process_clean 에서 spt_table_kill 이었음.

 

따라서, 내가 이미 이전에 삭제한 페이지이지만 spt table에서도 제대로 삭제를 하지 않아서 발생하는 문제라고 판단함.

하지만 아무리 찾아봐도 spt_remove를 더 추가할 곳이 보이지 않았음...

 

그래서 다음은 무엇을 하나 보았더니 pml4 테이블을 청소함. 그래서 pml4 destroy 함수에 중단점을 찍고 디버깅을 해봄. 여기서 터지는 거였음.

 

그래서, 더 이상 페이지가 사용되지 않는 순간에 pml4에서도 제거 되도록 코드를 수정함. (1번 이유를 해결한것임) 하지만!! 그래도 버그가 계속됨... (2번 이유가 있음)

그래서 로그를 더 자세히 보고 실제로 값을 받아 오는 순간에 버그가 생긴다고 생각했다. 그래서 실제로 값을 저장할 공간을 할당 받는 palloc_get_page 들을 찾아 보았다.

 

원인

우리는 사용중인 페이지들을 pml4테이블에 담아서 찾아가고있었다. 그래서 anon_page_destroy 를 할 때 pml4_clear_page로 더이상 사용하지 않는 anon_page를 제거 하도록 코드를 짰다. 

그런데 pml4 에서 페이지를 제거만하고 실제로 해당 페이지가 사용하던 frame을 free를 안해주었었다. 그래서 새로 kva(물리메모리 영역) 에서 프레임을 할당받을때, pml4상으로 찾아갔을 땐 비어있어야 할 곳이 비어있지 않아서 새로 frame을 할당 받을 때 문제가 생겼던 것이다!!!

 

해결방법

static void
anon_destroy (struct page *page) {
	struct anon_page *anon_page = &page->anon;
	
	// 스왑 테이블에서 스왑 인덱스 해제
	if (anon_page->swap_idx != BITMAP_ERROR) {
		lock_acquire(&bitmap_lock);
		bitmap_reset(swap_table, anon_page->swap_idx);
		lock_release(&bitmap_lock);
	}

	// 프레임이 존재하면 프레임을 리스트에서 제거하고 해제
	if (page->frame) {
		list_remove(&page->frame->elem);
		page->frame->page = NULL;
		palloc_free_page(page->frame->kva); // <<<<< 여기 추가함!!!!
		free(page->frame);
		page->frame = NULL;
	}

	pml4_clear_page(thread_current()->pml4, page->va);
}

후... 이제 정말 cow와 swap-fork를 제외한 모든 테스트를 통과한다.

swap-frok 는 왜 안통과하면서 자랑해요??? ec2 에서는 swap 용량이 부족해서 안된단다. (주의 이거 정확한 정보가아님 이유는 뭔가 있었는데 내가 제대로 공부를 안함!!!) ec2 용량을 늘리거나 wsl 로 돌리면 통과한다.

 

마치며,

이제 정말 핀토스가 끝났다. filesys는 보지도 못했고 cow는 개념만 안채로 남아서 아쉬웠지만 vm을 구현할 때, 답을 보지않고 직접 이론과 요구사항을 보고 흐름을 그려보고 어떤 것이 필요할지 정리해서 설계를 하면서 만들어서 성공했던 그 쾌감을 잊지 못할 것이다. 무엇을 만들어야 할 땐 흐름을 정리하고 무엇이 필요한지 잘 정리해보고 설계를 잘해보자!!!

 

lazy load