Pintos project3_Memory management

가상 메모리 시스템을 지원하려면 가상페이지와 물리적 프레임을 효과적으로 관리해야 한다.

즉 어떤 메모리 영역이 어떠한 목적으로 누구에 의해 사용되고 있는지 등을 추적해야 한다.

핀토스에서 supplemental page table(spt)을 처리한 후 physical frame을 처리할 것이다.

페이지 구조체

/*include/vm/vm.h*/
struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */

	/* 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
	};
};

struct page_operations {
	bool (*swap_in) (struct page *, void *);
	bool (*swap_out) (struct page *);
	void (*destroy) (struct page *);
	enum vm_type type;
};

 

 

 

페이지에 대해 알아야 하는 모든 필요 데이터를 저장한 구조체이다.

page_oprations, 가상 주소, 물리적 프레임, union 필드가 보인다. 유니온은 메모리 영역에 다른 유형의 데이터를 저장할 수있는 데이터 유형으로 여러 구성원이 있지만 한 번에 하나의 구성원 값만 포함 할 수있다.

즉 시스템 페이지는 unit_page/anon_page/file_page/page_cache가 될 수 있음을 말한다.

 

만약 page 가 anon_page인 경우 해당 페이지 구조체는 struct anon_page anon를 멤버중 하나로 가진다. anon_page에는 이를 유지하는데 필요한 모든 정보를 포함해야 한다.

 

페이지는 앞서 말한바와 같이 unit, anon, file중 하나가 될 수있다 page는 스왑인, 스왑아웃, 페이지 삭제 와 같은 몇몇 기능을 가지는데 각 페이지 타입별로 이 기능들이 요구되는 단계가 다르다.(예를 들어 anon타입 페이지와 file타입 페이지는  서로 다른 destroy 함수를 호출해야 한다.)

 

이들을 처리하는 한가지 방법으로 switch-case문을 사용해 각각의 케이스를 처리하는 것이 있다고한다.

 

추가 페이지 테이블 구현

수정전 핀토스는 가상주소 공간을 초기화할때 프로그램의 모든 세그멘트에 대해 물리메모리로 그대로 읽어 들이며 load_segment()로 data와 code segment를 Setup_stack()으로 Stack에 물리페이지를 할당한다.

수정을 하게 되면 위와같이 디스크 이미지의 세그멘트를 전부 물리메모리에 올리는 것이 아닌 가상페이지마다 vm_enrty를 통해 적재할 정보들만 관리하게 된다.

 

즉 현재 pintos는 가상메모리와 물리적 메모리를 매핑하기위한 페이지 테이블(pml4) 를 가지고 있지만 현재는 충분하지 않다고한다.

따라서 우리는 각 페이지들이 page fault 나 자원관리를 위한 추가적인 정보를 가지게 하기 위한 supplementaal page table이 필요하다. 위 강의 자료에서 보듯 이는 hash Table로 구성하게 될 것같다.

 

구현은 vm/vm.c에서 한다.

 

보충 페이지 테이블을 구현하고나면 해당 보충 페이지 테이블에 대해  아래 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);

 

우선 hash 테이블을 supplemental page table에 사용하기위해 hash구조체를 선언해주자

/*include/vm/vm.h*/

//hash 테이블을 사용하니 헤더도 추가해준다.
#include <hash.h>

struct supplemental_page_table {
	struct hash pages;//pjt3
};

 

spt를 초기화 하는 함수에 해시테이블도 초기화 해준다. 해시테이블 초기화 함수인 hash_init은 핀토스내에 기본 함수로 정의되어있다. 이 함수는 파라미터로 받는 함

supplemental_page_table_init

/*vm/vm.c*/
unsigned page_hash(const struct hash_elem *p_, void *aux UNUSED)
{
	const struct page *p = hash_entry(p_, struct page, hash_elem);
	return hash_bytes(&p->va, sizeof p->va);
}

bool page_less(const struct hash_elem *a_, const struct hash_elem *b_, void *aux UNUSED)
{
	const struct page *a = hash_entry(a_, struct page, hash_elem);
	const struct page *b = hash_entry(b_, struct page, hash_elem);

	return a->va < b->va;
}

/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->pages, page_hash, page_less, NULL);
}

spt_find_page

이제 spt_find_page에 대해 구현해 보자.

가상 주소에 해당하는 헤이지 번호를 spt에서 검색하여 페이지 번호를 추출 pg_round_down으로 가상 주소의 페이지 번호를 얻고, hash_find()를 이용하여 hash_elem 구조체를 얻는다.

/*vm/vm.c*/
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	//struct page *page = NULL;
	/* TODO: Fill this function. */
	struct page *page = (struct page *)malloc(sizeof(struct page));
	struct hash_elem *e;

	page->va = pg_round_down(va); // va가 가리키는 가상 페이지의 시작 포인트(오프셋이 0으로 설정된 va) 반환
	e = hash_find(&spt->pages, &page->hash_elem);

	free(page);

	return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}

spt_insert_page

마지막으로 spt_insert_page를 완성하자.

spt_inser_page함수는 주어진 spt에 page를 삽입하는 함수로 먼저 가상주소가 spt에 존재하는지 여부를 체크하여 없으면 삽입후 True를 반환한다.

/*vm.c*/
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	//int succ = false;
	/* TODO: Fill this function. */
	return insert_page(&spt->pages, page);
}

bool insert_page(struct hash *pages, struct page *p)
{
	if (!hash_insert(pages, &p->hash_elem))
		return true;
	else
		return false;
}

 

Frame management

위에서 가상메모리의 page table과 관련된 코드를 구현했으니 이제 물리 주소인 Frame관련 함수를 수정해 보자.

include/vm/vm.h에 struct frame 이 있다. 이건 물리메모리를 대표하는 구조체 이다.

초기에는 여기 kva(kernal virtual address)와 pagerk 존재한다. 

프레임들을 리스트화 하기 위한 list_elem필드를 추가한다.

/* The representation of "frame" */
struct frame {
	void *kva;
	struct page *page;
	struct list_elem elem; //PJT3 
};

이와 함꼐 아래 함수들도 구현한다.

static struct frame *vm_get_frame (void);

bool vm_do_claim_page (struct page *page);

bool vm_claim_page (void *va);

vm_get_frame

vm_get_frame은 user pool에서 새로운 물리 페이지를 palloc_get_page를 통해 가져온다.

성공적으로 가져오면 프레임을 할당하고 그 안의 멤버를 초기화 한 후 리턴해 준다.

vm_get_frame를 구현후 이 함수를 통해 모든 사용자 공간 페이지((PALLOC_USER)를 할당해야 한다. 

 메모리가 가득 차서 가용한 페이지가 없다면, 이 함수는 가용한 메모리 공간을 얻기 위해 (할당되어 있는) 프레임을 제거한다. 

struct list frame_table;

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

	frame->kva = palloc_get_page(PAL_USER);
	if (frame->kva == NULL)
	{
		frame = vm_evict_frame();//페이지 초기화 후 프레임반환
		frame->page = NULL;

		return frame;
	}
	list_push_back(&frame_table, &frame->frame_elem);

	frame->page = NULL;

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

static struct frame *
vm_evict_frame (void) {
	struct frame *victim = vm_get_victim ();
	/* TODO: swap out the victim and return the evicted frame. */
	swap_out(victim->page);//pjt3
	return victim;
}

palloc_get_page(PAL_USER)를 하게되면 사용자 풀에서 메모리를 할당한다. 사용자 풀에서 메모리를 할당하는 이유는 커널 풀의 페이지 부족시 많은 커널 함수들이 메모리확보에 문제가 생길 수 있고 그로인해 많은 오류가 발생하기 때문이다. 사용자 풀의 페이지 부족은 사용자 프로그램의 페이지 부족으로 프레임을 초기화 해 주어도 문제가 없다.

 

vm_get_victim()함수는 프레임을 실제로 제거하는 함수다.

static struct frame *
vm_get_victim (void) {
	struct frame *victim = NULL;
	 /* TODO: The policy for eviction is up to you. */
	//pjt3
	struct thread *curr = thread_current();
	struct list_elem *e = start;

	for (start = e; start != list_end(&frame_table); start = list_next(start))
	{
		victim = list_entry(start, struct frame, frame_elem);
		if (pml4_is_accessed(curr->pml4, victim->page->va))
			pml4_set_accessed(curr->pml4, victim->page->va, 0);
		else
			return victim;
	}

	for (start = list_begin(&frame_table); start != e; start = list_next(start))
	{
		victim = list_entry(start, struct frame, frame_elem);
		if (pml4_is_accessed(curr->pml4, victim->page->va))
			pml4_set_accessed(curr->pml4, victim->page->va, 0);
		else
			return victim;
	}

	return victim;
}

 

vm_claim_page & vm_do_claim_page 

여기서 클레임의 의미는 물리적 프레임을 에 페이지를 할당을 요구하여 할당해 주는 것이다.

먼저 vm_claim_page로 va를 할당할 page를 가져오고 vm_do_claim_page를 호출한다.

 

vm_do_claim_page 에서는

vm_get_frame으로 frame(물리공간)을 가져오고 MMU를 set up 해서 가상주소를 물리주소 테이블로 매핑한다.

return 값으로 성공했다면  True 아니면 False를 반환한다.

/*vm.c*/

/* Claim the page that allocate on VA. */
bool
vm_claim_page (void *va UNUSED) {
	struct page *page;
	/* TODO: Fill this function */
	page = spt_find_page(&thread_current()->spt, va);

	if (page == NULL)
	{
		return false;
	}

	return vm_do_claim_page(page);
}

/* Claim the PAGE and set up the mmu. */
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 (install_page(page->va, frame->kva, page->writable))
	{//install_page()  Verify that there's not already a page at that virtual address, then map our page there. 
		return swap_in(page, frame->kva);
	}
	return false; //할당 실패
}