pintOS | Project 3 | Memory Management

 

프로젝트 3-1 Memory management에서는 효율적으로 페이지와 프레임을 관리하는 것에 대해 구현할 것이다.

사용되고 있는 가상/물리 메모리 영역에 대해 추적해야 한다는 것.

 

먼저 supplemental page table(spt), 그리고 physical frame을 다룰 것이다.

 

먼저 page 구조체가 어떻게 생겨먹었는지 확인해보자. page는 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 */

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

 

음.. 코드를 보면 union 타입 안에 uninit page, anonymous page, file page 등을 담고 있다. 어떤 한 페이지가 anonymous page면 여기에 필드로 들어간다는 것이겠지?

 

그래서 anonymous page가 뭔데? 참조 따라 들어가보자.

// ../include/vm/anon.h

...
struct anon_page {
};
...

? 아니 너 왜 없어? 저거 다 구현하라는거지? 주석이라도 달아주지 개불친ㅈ

 

Memory Management 다음 파트가 Anonymous Page라 아무것도 없나 보다 ㅎㅎㅎㅎ 열받넹 암튼 나중에 알아야 할 개념이니 일단 스킵. 저거 구현할 때 다시 보는 걸로 하구, 페이지는 uninit page나 anon page, file page가 될 수 있다는 것을 의미하는 듯.

 

페이지는 swaping in, swaping out이나 destroy 같은 액션들을 취할 수 있고, 각각의 타입의 페이지들은 어떤 것을 요구 받는지에 따라 다른 작업을 수행한다고 한다.

(단, anon page와 file page 에 대해서는 다른 destroy 함수를 호출해야 함)

 

하나의 방법으로 각 함수의 switch-case문을 사용하여 각각의 케이스들을 처리하는 것이 있다고 한다.

 

위의 페이지들이 작업하는 것과 관련된 구조체는 include/vm/vm.h에 있는 page_operations 함수에 정의되어 있다. 각각의 구조체들은 함수 포인터를 담고 있는 함수 테이블이다.

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

 

 

pintos는 가상 주소와 물리 주소의 매핑을 관리하는 페이지 테이블인 pml4가 있다. 하지만 이것으로는 page fault와 자원 관리를 처리하는데 충분하지 않다. 그래서! 우리는 프로젝트 3의 첫 번째 과제로 supplemental page table을 구현하는 것이 목표다.

 

오케이 일단 뭘 먼저 하라는지 아라쓰. supplemental page table(spt) 너 어딨냐. 검색해 보니 include/vm/vm.h에 있다.

/* Representation of current process's memory space.
 * We don't want to force you to obey any specific design for this struct.
 * All designs up to you for this. */
struct supplemental_page_table {
};

 

응~ 아무것도 없어~ 내가 다 해야돼...!

 

먼저 spt가 뭔지는 깃북의 introduction을 보면서 정리했었다. 간단하게 한 번 더 정리하자면 페이지들에 대해 추가적인 데이터로 페이지 테이블을 보완하는 것이다. 사용 용도는 페이지 폴트 상황에서 커널은 spt에서 fault된 가상 페이지는 찾는다. 다른 용도는 페이지가 다 사용 후 종료될 때 메모리 할당을 해제하기 위해 필요하다.

 

 정글 조교님께서는 spt에 대해 이렇게 설명해주셨다.

cpu의 cr3 레지스터에 저장되며 mmu에 의해 traverse(순회)되는 pml4 table은 supplemental page table과는 무관하게 virtual address to physical address mapping을 지원합니다.

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

 

 

흠. 그래서 뭐 어떻게 구현하라는거지? 막막하다. pintos 강의 자료를 찾아보자. 

 

과제 수행 전 pintos memory layout

위의 그림처럼 기존 pintos의 가상 주소 공간 초기화 과정은 디스크로부터 ELF이미지의 세그먼트를 물리메로리로 읽어들인다(load_segment()로 data, code 세그먼트를 읽고, setup_stack()로 스택에 물리페이지를 할당한다.).

 

이는 물리 메모리의 낭비를 초래하기 때문에 물리 메모리 할당 대신 가상 페이지마다 spt를 통해 적재할 정보들만 관리하도록 구현해야 한다.

 

그럼 어떻게 바꿔야 할까?? 아래의 그림을 보자.

구현 후 pintos 가상 메모리 형태는 이렇게 될 것!

 

ㅇㅅㅇ... 저기... 해시가 먼데? 해시태그는 관종이라 자주 쓰는ㄷ 

일단 핀토스에서 제공하는 hash 구조체를 보자.

// ../include/lib/kernel/hash.h

/* Hash table. */
struct hash {
	size_t elem_cnt;            /* Number of elements in table. */
	size_t bucket_cnt;          /* Number of buckets, a power of 2. */
	struct list *buckets;       /* Array of `bucket_cnt' lists. */
	hash_hash_func *hash;       /* Hash function. */
	hash_less_func *less;       /* Comparison function. */
	void *aux;                  /* Auxiliary data for `hash' and `less'. */
};

 

해시 테이블은 (key, value)로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있다고 한다(O(1)의 평균 시간복잡도). 이게 가능한 이유는 내부적으로 배열(버킷, 혹은 슬롯)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 인덱스를 활용하여 값을 저장하거나 검색한다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 위 그림처럼 해시 테이블의 인덱스 값들이 실제 주소를 가지고 있는 버킷을 찾는다. 

 

갑자기 해시가 왜 튀어나왔냐면, 프로세스가 요청한 페이지들에 대해서만 물리 페이지를 할당하기 위해서 해시 테이블 자료구조가 사용되기 때문이다. 

 

그럼 이 해시테이블이 어디서 쓰이냐? 위에서 얘기했던 spt에서 사용한다.

// ../include/vm/vm.h

struct supplemental_page_table {
	struct hash pages;
};

 

spt 내 해시 테이블을 통해 요청되는 주소들을 넣어야 한다는 것이고, spt를 초기화하는 함수에서 해시 테이블도 초기화를 해야겠네. hash_init은 어떤 놈일까?

/* Initializes hash table H to compute hash values using HASH and
   compare hash elements using LESS, given auxiliary data AUX. */
bool
hash_init (struct hash *h, hash_hash_func *hash, hash_less_func *less, void *aux) {
	h->elem_cnt = 0;
	h->bucket_cnt = 4;
	h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
	h->hash = hash;
	h->less = less;
	h->aux = aux;

	if (h->buckets != NULL) {
		hash_clear (h, NULL);
		return true;
	} else
		return false;
}

 

hash_init()은 파라미터로 받는 함수들로 해시 테이블의 해시들을 초기화한다. 이 함수는 malloc()을 호출해서 메모리를 할당받고, 만약 실패했다면 메모리에 할당되지 않는다.

 

hash_init이 받는 파라미터 중 hash_hash_func 과 hash_les_func가 있는데, 전자는 주어진 aux 데이터에서 해시 요소에 대한 해시 값을 계산하고 반환하는 것이고, 후자는 해시 요소들을 비교하는 것이다. 즉 저것들을 또 구현해야 한다는 것... 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);
}

// 해시 테이블 초기화할 때 해시 요소들 비교하는 함수의 포인터
// a가 b보다 작으면 true, 반대면 false
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;
}

 

자 그럼 supplemental_page_table_init() 함수도 구현 ㄱ!

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

 

깃북을 보면 다음으로 truct page *spt_find_page (struct supplemental_page_table *spt, void *va); 와 bool spt_insert_page (struct supplemental_page_table *spt, struct page *page); 를 구현하라고 한다.

 

spt_find_page는 인자로 받은 va(가상 주소)에 해당하는 페이지 번호를 spt에서 검색하여 페이지 번호를 추출하는 함수이고, 이 때 pg_round_down() 함수로 vaddr의 페이지 번호를 얻고, hash_find() 함수를 사용해서 hash_elem 구조체를 얻는다.

/* Find VA from spt and return page. On error, return NULL. */
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;
}

/* Insert PAGE into spt with validation. */
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;
}

 

추가로 해시 delete하는 함수도 구현한다.

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

 

 

자 page table과 관련된 코드들을 구현했다면 이제는 물리 주소와 매핑할 때 필요한 frame을 수정해야 한다. vm.h에 frame 구조체가 있다. 기존에는 커널의 가상 주소를 나타내는 kva와 매핑될 page 구조체 이 두 개만 필드로 있다. 프레임들을 리스트화 시키기 위해 list_elem 필드를 추가해주자.

/* The representation of "frame" */
struct frame {
	void *kva;				// 커널의 가상 주소
	struct page *page;		// 페이지 구조체
	struct list_elem frame_elem;
};

 

그 다음은 뭘 해야 할까. 깃북을 보니 vm.c에 있는 vm_get_frame, vm_claim_page, vm_do_claim_page 이 세 개의 함수를 구현하라고 한다. vm_get_frame() 부터 살펴보자.

 

vm_get_frame() 함수는 palloc_get_page() 함수 호출로 유저풀로부터 새로운 물리 페이지를 받는다. 유저풀로부터 페이지를 받고 프레임을 할당 받았을 때, 멤버들을 초기화하고 유효한 주소를 리턴한다. 즉 이 함수를 구현한 후에는 이 함수를 통해 모든 유저 공간 페이지들을 할당받게 된다. 만약 유저풀 메모리가 가득 차서 가용한 페이지가 없다면, 이 함수는 가용한 메모리 공간을 얻기 위해 (할당되어 있는) 프레임을 제거한다. 

 

함수를 구현하기 전에 먼저 vm.c파일 상단에 frame_table 변수를 선언하자.

struct list frame_table;

 

이제 vm_get_frame() 구현

static struct frame * vm_get_frame (void) {
	/* TODO: Fill this function. */
	struct frame *frame = (struct frame*)malloc(sizeof(struct frame));
	
	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
	
	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;

	return frame;
}

 

여기서 palloc_get_page()에 PAL_USER를 넣어서 전달하도록 되어 있다. PAL_USER를 사용하는 이유는 위에서 언급했던 것처럼 커널 풀 대신 사용자 풀에서 메모리를 할당하게 하기 위해서다. 사용자 풀의 페이지가 부족하면 사용자 프로그램의 페이지가 부족해지지만 커널 풀의 페이지가 부족해지면 많은 커널 함수들이 메모리를 확보하는 데 문제가 생길 수 있고, 많은 오류가 발생한다. 

 

if문 안에 frame에 vm_evict_frame()함수를 넣는다. 이 함수는 초기화를 위해 페이지를 지우고 해당 프레임을 반환한다.

/* Evict one page and return the corresponding frame.
 * Return NULL on error.*/
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);

    return victim;
}

 

함수 안에 또 처음 보는 함수가 등장한다. vm_get_victim()은 또 뭐냐! 위의 함수에서 넘겨 받은 프레임을 가져와서 실제로 제거하는 함수다.

/* Get the struct frame, that will be evicted. */
static struct frame * vm_get_victim (void) {
	struct frame *victim = NULL;
    /* TODO: The policy for eviction is up to you. */
    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_do_claim_page() 와 vm_claim_page() 함수 구현

/* 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))	// 유저페이지가 이미 매핑되었거나 메모리 할당 실패 시 false
    {
        return swap_in(page, frame->kva);
    }
    return false;
}

 

깃북을 보면서 Memory Management에서 하라는 부분들은 일단 구현 완료했다. 다음 파트도 언능 하즈아