Project3. Virtual Memory (PintOS)

Project3. Virtual Memory

1. Memory Management

늘 그래왔듯, 가장 기초 즉 이 project3가 흘러가는 코드의 시작을 공부한다.
Project2까지는 load를 어떻게 해왔는지 생각해보자.
우리는 process_exec -> load -> load_segment -> setup_stack 등의 방식으로 메모리를 적재했다. (load_segment, setup_stack은 주의깊게 보지 못했을 수 있다.)
그러나 프로그램 전체를 메모리에 load 하는 것은 매우 비효율적이다. 그래서 우리는 lazy_load를 사용한다.

지금 당장 사용해야할 부분만 load하고, 사용하지 않는 부분은 표시만 해둔다고 생각하면 될 것 같다.
이렇게 하면 당장 큰 프로그램을 모두 load하지 않아도 되고, 그때그때 필요한 부분만 올리면 되므로 훨씬 효율적이다.

이 방식을 사용하기 위해, page 구조체를 살펴보자.

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 hash_elem;
	bool writable;

	/* Per-type data are binded into the union.
	 * Each function automatically detects the current union */
	union {
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

page 구조체는 함수형 포인터인 operations를 가지고, 가상 주소 va / 맵핑되는 물리 주소의 page 개념 frame 등등을 가진다.  이 page가 무엇인지 생각해보자. 우리가 100 크기짜리 메모리를 가지고 있다고 생각하자.
아래부터 차곡차곡 10짜리가 10개가 쌓일 수 있겠지만, 중간에 10짜리가 빠지고 7이 채워지고, 또 10이 빠지고 3이 채워지고... 이런일이 생기다보면 빈 공간이 많이 생길 것이다.
이를 방지하고자, 미리 10 정도의 크기로 메모리를 나눠놓거나 가장 딱 맞는 빈 공간에 메모리를 채워넣는 방식으로 메모리 효율성을 높이고자 했다.

그러나 이런 방식으로도 메모리는 많이 낭비됐고, 이를 위해 생긴 개념이 페이지이다. 실제 물리 메모리가 100이라면 frame을 10개를 만들고, 각각 프로세스가 가지는 메모리도 크기 10짜리 page로 나누어둔다. 이렇게하면 우리는
프로세스 A의 page 3개, 프로세스 B의 페이지 5개, 프로세스 C의 페이지 2개를 메모리에 올릴 수 있다.
이런 식의 효율적인 메모리 사용을 위한 개념이 page이다. (그림을 추가하자 ㅠㅠㅠ)

이런 구조가 있기 때문에 앞서 말한 lazy_load도, 필요한 page만 메모리에 올리고 필요할 때마다 disk에서 page를 올린다고 생각하면 된다!!

1번 과제에서 구현해야 할 것은 6개의 함수이다. (물론 process.c의 lazy_load_segment 등 3개 함수와 여기저기 손 댈 곳은 있다..!)

void supplemental_page_table_init (struct supplemental_page_table *spt);
struct page *spt_find_page (struct supplemental_page_table *spt, void *va);
bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

이 3개의 함수는, page를 불러오고 supplemental_page_table에 저장, 탐색하는 함수이다. spt는 실제로 메모리에 적재는 하지 않고, lazy_load를 할 때! 필요한 정보를 저장하는 table이라고 생각하면 될 듯하다..!

 

static struct frame *vm_get_frame (void);
bool vm_do_claim_page (struct page *page);
bool vm_claim_page (void *va);

get_frame을 통해 할당 가능한 frame을 받아온다. (메모리에 남는 frame이 있다면 받고, 없다면 추후에 swap을 통해 받아온다.)
claim은 page와 frame을 연결해주는 함수이다.

6개 함수 + segment 3가지 함수를 구현해도 test는 여전히 all fail이다.

2. Anonymous Page

2장에선 코드 흐름을 더 이해할 수 있다.

bool vm_alloc_page_with_initializer (enum vm_type type, void *va,
        bool writable, vm_initializer *init, void *aux);

load_segment에 있는 이 함수를 시작으로, 우리는 page를 만들고 load한다.
type: page의 타입 (VM_UNINIT, VM_ANON, VM_FILE 중 하나이다 (지금은))
va: page의 가상 주소
writable: write이 가능한지 여부
init: page를 진짜로 올릴 때 실행하는 함수 (일단 넘어가자..!)
aux: 그 init 함수를 실행 할 때 넘겨주는 argument (필요한 것들을 여기 담아주면 된다!)

if (VM_TYPE(type) == VM_ANON)
	uninit_new (p, upage, init, type, aux, anon_initializer);
else if (VM_TYPE(type) == VM_FILE)
	uninit_new (p, upage, init, type, aux, file_backed_initializer);

vm_alloc_page_with_initializer -> spt_find_page (첫 load 때 spt에 page를 적재한다)
uninit_new는 page를 uninit으로 만들어서 spt에 올려두는 과정이다. (그러나 실제 type을 담아둔다)

p라는 page 구조체는 upage: 주소, init: lazy_load, type: 타입, initializer: 타입에 따른 함수 를 가진다.
그 이후 spt_insert_page를 통해 spt에 page를 저장한다. (이때, uninit 타입이지만 실제 type과 initializer를 가지고 있다)

 

여기까지하면 우리는 spt에 page를 저장했고, 실제로 frame(물리 메모리)와 연결(mapping)되진 않았다. 그저 이런 page가 있다~ 정도로 해뒀고, 정말 그 page가 필요할 때! 빠르게 page에 접근할 수 있게 된 것이다.

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

추가로, stack 영역은 바로 page를 할당하고 claim한다. 

 

그럼 언제 lazy_load_segment를 하는걸까??
우리는 page를 올려두진 않았기 때문에, 실제로 page가 필요할 때 page fault가 발생한다.

bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED)

이 함수에서 spt table에서 page를 탐색하고 해당 page의 swap_in operator를 호출한다.
uninit_new를 통해 uninit_page로 등록해둔 spt의 page는 

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, kva) &&
		(init ? init (page, aux) : true);
}

를 swap_in operator로 가진다. (코드를 따라가보면 알 수 있다. uninit_new를 확인해보자!)
그럼 마지막 줄에서 page_initializer (type에 따라 anon_initializer 혹은 file_initializer 일 것이다.)를 실행하고

init도 실행한다 (이건 lazy_load_segment이다.)

이런 흐름으로 코드가 진행되어 lazy_load_segment가 진행되고
gitbook에 명시된 함수들을 모두 작성하고 이 흐름에 존재하는 함수들!을 수정해주면

비로소 Project2. Userprog test-case들이 모두 pass가 된다...!!

3. Stack Growth

Load_segment가 아닌, Argument_passing에서 수행했던, file 명 / arguments를 parsing, passing했던 과정을 생각해보자. 이 값들은 setup_stack에 의해 바로 claim되고 스택에 쌓인다.
그런데 문제는, 우리는 한개의 page만큼만 할당을 했다는 것이다.

그럼 PGSIZE를 넘어서는 주소값이 들어온다면 어떻게 될까??

이 경우 stack을 확장하고 새로운 page를 할당해줘야한다. 3번 과제는 이것을 구현하면 된다.

bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED)

static void
vm_stack_growth (void *addr UNUSED)

여기에 추가로 구현하면 된다. 

4. Memory Mapped Files

각 process마다 가상메모리를 가지고, 이를 page로 나누어 메모리에 올릴 수 있게 됐다.
이제, 디스크에 있는 파일을 메모리의 물리 주소에 올리도록 요청하는 시스템 콜을 구현하자.

void *mmap (void *addr, size_t length, int writable, int fd, off_t offset);

fd로 열린 파일의 length 바이트만큼 프로세스 가상주소인 addr에 매핑한다. 연속된 가상 페이지로 매핑되고, 마찬가지로 필요한 정보만 올려둔 뒤, lazy_load로 구현한다.

syscall.c에 mmap을 구현하고 file.c의 do_mmap을 구현한다 (여기가 메인..)

마찬가지로 mummap도 구현한다!!

추가로 file.c의 init, initiallizer, destroy까지도 구현한다!!
file, offset, read_byte를 담은 구조체를 생성하여 vm_alloc_page_with_initializer에 aux값으로 넘겨주어 구현했다.

 

5. Swap In/Out

앞선 개념에서, frame에 page를 할당하여 채운다. 여러가지 process의 page를 쌓고 필요하면 올리고 하다보니 frame이 가득차게 됐다. 그럼 새로운 page를 메모리에 적재하기 위해선, 기존의 page를 내려야한다.
이 과정이 swap이다.

어떤 page를 내리는게 효율적일까??
흔히 아는 LRU는 가장 오래동안 사용하지 않은, 즉 최근에 사용한적이 없는 page부터 swap-out한다.

LFU는 가장 적게 사용한 page를 뺀다.
이런식의 여러가지 page replacement algorithm이 있는데 (LRU, LFU는 실제로 구현할 순 없다?!)
그 중에서 clock algorithm을 사용했다.

clock은 LRU에 근사한 효과를 내는 방식인데, OS가 page fault가 아닌 hit는 참고할 수 없으니, bit를 하나 추가하여 최근에 사용됐는지 안됐는지만 판별한다.
https://www.youtube.com/watch?v=b-dRK8B8dQk

이 영상을 통해 공부하면 도움이 많이 된다.

아무튼! anon.c / file.c에서 모두 swap in / out을 구현해주고 일부 필요한 부분을 수정하면된다!!

 

6. Copy-on-Write (Extra)