[sw 정글] pintos 3주차 - part 1: Memory Management

1, 2 주차 pintos는 노션에만 대충 정리하여 블로그에 올릴 내용이 아닌듯하여 3주 차부터 올리려고 한다.

많은 정글 동료, 선배들이 좋은 내용을 많이 블로그에 작성해두었으니 부족한 내용은 좀 더 찾아보면 도움이 될 것이다.

---

기존 pintos 메모리 문제점

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

• 기존 핀토스 메모리 탑재 과정
  • 각 세그멘트(stack, Data, BSS, Code)가 물리페이지에 탑재
  • heap 제외(pintos에는 heap이 없음)

가상메모리 수행전

이 페이지 테이블에 맵핑된 물리주소는 다른 프로세스와 같은 곳을 가리킬 수 있고 이럴 때 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, page 구조체, frame 구조체는 모두 thread의 pml4와 물리메모리를 맵핑하기 위한 보조 구조체이다. 결국 물리메모리와 연결되는 것은 pml4로 이 점을 잘 유의하고 핀토스를 작성하기 바람

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 코드page fault 시 page_initializer에 저장된 init 함수 호출됨
     • 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); };
  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;
}

구현 중 문제점

1. SPT 이 기존의 plm4를 완전히 대체하는 page table인줄 알았다.
   • 그렇기에 물리 메모리와 맵핑되는 부분에 대해서 해결되지 않았다.
   • thread.h 에 있는 pml4가 userprog에서만 thread에 포함되어 있었기에 사용하지 않는 것인줄 알았다.
   • 기존에 있던 코드라도 구현할 때 의심이 든다면 생각해보고 수정해보자
   • SPT는 기존의 plm4를 보조하여 효율적인 가상메모리 paging을 구현할 수 있게 도와주는 자료구조이다.
   • 기존의 pml4를 수정하여 구현할 수 있지만 매우 어려운 작업이기에 추천하지 않음
   → pml4 page table을 같이 사용하여 문제 해결