[PintOS] Project3: Memory Management

Memory Management

기존 pintos 메모리 문제점

• PML4를 가진 기존의 핀토스는 가상메모리와 물리메모리가 바로 맵핑되어 있다.

• 기존 핀토스 메모리 탑재 과정

  • 각 세그멘트(stack, Data, BSS, Code)가 물리페이지에 탑재
    

이 페이지 테이블에 맵핑된 물리주소는 다른 프로세스와 같은 곳을 가리킬 수 있고 이럴 때 page fault가 된다. 그리고 한번 맵핑되면 물리메모리에서 항상 공간을 차지하기에 효율적인 메모리 관리가 되지 않는다.

목표
Supplemental Page Table 을 추가하고 페이지에 추가적인 정보를 저장하여 효율적인 메모리 관리를 할 수 있게 하는 것이 목표이다.

1. 기존의 페이지 테이블을 보완하고 page fault 발생시 가상페이지를 찾고 물리페이지(frame)을 할 당할 수 있게 처리한다.
2. 프로세스가 종료될 때 Supplemental Page Table 를 참조하여 해제할 리소스를 결정한다.

💡 supplemental page table은 process별로 생성되는 별도의 구조체로써, 동일하게 virtual address와 physical address간 mapping을 지원하지만 struct page와 struct frame 구조체들을 이용하여 기존 page table(pml4 table)이 담지 못하는 정보들을 추가적으로 저장하기 위해 사용됩니다. (ex. evicted page. mmaped page, etc...)

Supplemental Page Table(SPT 구현)

 자료구조 선택

테이블을 구현하기 위해 자료구조를 먼저 선택한다.

추천하는 자료구조 4가지 중에 Hash table 선택

Hash table관련 자료 https://mangkyu.tistory.com/102

• 이유
  1. 핀토스에서 hash table을 관련 함수를 모두 지원해줌
  2. hash table은 key값으로 O(1)의 시간복잡도로 자료를 빠르게 찾을 수 있다.
     • SPT에서 va(가상주소)에 맞는 page를 찾아야할 때 빠르게 접근할 수 있음
     • key 값을 va(가상주소)로 함
     • 해시충돌(collision)해결 방법
       • 분리 연결법(**Separate Chaining)**으로 해결
       • hash table에 저장되는 buckets을 이중연결리스트로 구현하여 해시 충돌 시 해당 hash index에 연결하여 줌

spt 테이블

struct supplemental_page_table{
	struct hash hash;
};

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; /* Hash table element. */
	struct file_information *file_inf;

	bool writable;
	union
	{
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

• va 키가 되는 가상주소
• frame 물리 주소랑 맵핑되는 frame 저장
• union 부분
  • page는 3가지 타입을 가진다.
  1. uninit_page: 제일 처음 만들어진 페이지의 타입
     1. page fault가 발생했을 때의 page의 타임이 변화하는데 변화하기 위해 필요한 정보를 가지고 있다.
     • uninit_page 코드

       struct uninit_page {
       	/* Initiate the contets of the page */
       	vm_initializer *init;
       	enum vm_type type;
       	void *aux;
       	/* Initiate the struct page and maps the pa to the va */
       	bool (*page_initializer) (struct page *, enum vm_type, void *kva);
       };

       page fault 시 page_initializer에 저장된 init 함수 호출됨
       
  2. anon_page: 비 디스크 기반 page
     1. 맵핑되는 파일이나 장치가 없어 디스크에 기록되지 않는다.
     2. file_backed_page와 다르게 달리 맵핑된 파일이 없어 익명이라한다.
  3. file_backed_page: 파일에 기반한 페이지
     1. 파일에 기반한 페이지
     2. 디스크에서 읽어온다.

구현 코드

• spt_find_page : va를 기준으로 hash_table에서 elem을 찾는다.

struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
	struct page *page = page_lookup(va);
}
///////
struct page *
page_lookup(const void *address)
{
	struct page p;
	struct hash_elem *e;

	p.va = pg_round_down(address);
	e = hash_find(&thread_current()->spt.hash, &p.hash_elem);
	return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}

• supplemental_page_table_init: SPT init 함수

void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
	hash_init(&spt->hash, page_hash, page_less, NULL);
}

• spt_insert_page

bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
										 struct page *page UNUSED)
{
	int succ = false;
	if (!hash_insert(&spt->hash, &page->hash_elem))
	{
		succ = true;
	}
	return succ;
}

PintOS Project3 GIthub 주소 PintOS