(2022.02.23) Memory Mgmt 가이드라인 (2/2)

지난 시간 설명 요약:

와 간단!

이번 포스팅에서는 Supplemental Page Table(후술 SPT)과 Frame Table(후술 FT)의 구조를 설계하는 것을 목표로 한다.

1) SPT

SPT는 크게 제약 조건이 없다. 지난 포스팅에 설명한 것과 같이 struct page의 삽입, 탐색, 삭제 3개의 작업만 효율적으로 할 수 있으면 되는 구조를 선택한다. 이에 해당하는 자료구조가 바로 hash 테이블이며 이제 필연적으로 hash.c와 놀게 되었다. 매뉴얼의 hash 테이블에 해당하는 문서와 hash.c를 읽어본다.

 

일단 나에게 친숙한 형태의 hash 테이블은 구조체가 주어지면 해당 구조체를 어떤 hash 함수에 넣어 hash 값을 계산하고, 해당 hash 값을 토대로 O(1)의 탐색 과정을 거쳐 원하는 위치에 삽입/삭제가 이루어진다. 이를 구현하기 위해 pintos의 hash는 리스트 구조의 bucket의 array를 가지고 있다. 구조체의 hash 값을 계산해서 해당 hash 값을 기반으로 들어갈 bucket을 결정하고, 해당 bucket 내에서는 단순 리스트 구조로 엔트리가 관리된다. 구조체를 삽입/제거를 한 뒤에는 한 bucket 내에 너무 적거나 많은 엔트리가 있는 것을 방지하기 위해 적절한 수의 bucket을 갖도록 rehash 함수가 호출되어 나중에 탐색 과정이 너무 지체되는 것을 방지한다. 이런 식으로 이상적인 hash 테이블과 유사한 동작을 하도록 관리가 되고 있다.

 

해당 hash 테이블을 구현함에 있어 가장 중요한 것은 hash 함수이다. 구조체 내에 웬만해서는 변할 일이 없으면서 각 구조체마다 다른 값을 가진 멤버를 토대로 hash 값을 계산하도록 구현해야 한다. 또한 다른 객체에 대해서 같은 hash 값이 계산되는 collision이 발생하지 않도록 하는 함수일수록 좋다. pintos에서는 이러한 함수를 각 구조체에 맞게 구현할 수 있도록 기본 hash 함수인 hash_bytes, hash_string, hash_int 함수를 제공한다.

 

주어진 hash.c의 구현은 굉장히 기초적이기에 걸리는 것이 몇 개 있다. 위에서 언급한 hash collision과 더불어 만약 rehash를 한다고 해도 일정 bucket에 너무 많거나 적은 객체가 들어간다면 효율성의 문제가 발생할 수 있다. 이는 한 bucket 내에서는 단순 리스트 형태로 엔트리가 관리되기 때문에 최악의 경우 O(n)의 시간복잡도가 발생할 수 있기 때문이다. hash.c에는 MAX_ELEMS_PER_BUCKET와 MIN_ELEMS_PER_BUCKET의 리미트가 정의되어 있긴 하지만 함수 내에서는 어디에서도 사용되지 않는다. 따라서 해당 문제가 "우연히" 발생할 경우 hash 테이블의 효율이 떨어지는 것은 당연하다. 일단 지금은 기초 구현상태로 두고 나중에 효율성의 문제가 심해진다고 하면 hash.c를 고쳐보도록 하자.

 

일단 우리의 매뉴얼은 정말 친절하게도 SPT를 구현할 때 hash를 쓸 것이라고 예상했는지 예시 코드를 다 준다. 이렇게 혜자로울수가! 살펴보면:

struct page {
    struct hash_elem hash_elem; /* Hash table element. */
    void *addr; /* Virtual address. */
    /* . . . other members. . . */
};

위와 같이 hash_elem을 추가하고,

/* Returns a hash value for page p. */
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->addr, sizeof p->addr);
}

/* Returns true if page a precedes page b. */
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->addr < b->addr;
}

이와 같은 함수들로 struct page를 hash 처리한다는 것이다. 영리하게도 hash_insert에서 충돌을 판별하는 것은 hash 함수가 아닌 less 함수이기에 hash_byte 등의 변수가 아닌 그냥 주소값을 비교함으로서 발생할 수 있는 모든 충돌을 피했다. 중복된 주소를 넣는 것은 명백히 안 되는 행동이므로 충돌이 날 경우 해당 insert가 invalid하다고 판별할 수 있다.

 

이런 hash와 less를 기반으로 hash 테이블을 만들어 운용하면 spt는 거의 완성될 것이다. 매뉴얼에서는 보너스로 spt_find_page에 해당하는 함수까지 거저로 준다.

struct hash pages;
hash_init (&pages, page_hash, page_less, NULL);

/* Returns the page containing the given virtual address, or a null pointer if no such page exists. */
struct page *
page_lookup (const void *address) {
  struct page p;
  struct hash_elem *e;

  p.addr = address;
  e = hash_find (&pages, &p.hash_elem);
  return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

물론 수정해야 할 필요가 있긴 하겠지만 적극적으로 참조하도록 한다.

 

아무튼 여기까지 봤을 때, SPT는 다음과 같이 정의해도 충분할 것으로 보인다.

struct supplemental_page_table {
	struct hash pages;
};

이제 FT를 살펴보자.

2) FT

FT는 물리 메모리가 부족해지면 특정 프레임을 골라 메모리에서 쫓아내는 frame eviction policy, 또는 page replacement algorithm을 담당해야 하기 때문에 SPT보다는 형태에 제약이 생긴다. page replacement algorithm에는 수업 시간에 배울 여러 방식이 있는데 대표 주자로는 FIFO, LRU(least recently used), NFU(not frequently used)등이 있다. 더 여러가지 방법에 대해서는 여기를 참조하였다. 

 

우선 기억나는 방식은 second-chance, 또는 clock 알고리즘이다. 해당 방식은 예전 pintos를 짰을 때 사용했던 page replacement algorithm으로, 구체적인 설명은 다음과 같다.

 

second-chance (clock) algorithm

현재 메모리에 올라와 있는 프레임을 원형으로 늘어놓고 포인터를 한 프레임을 가리키도록 한다. 만약 해당 프레임의 reference bit가 0이라면 해당 프레임을 evict할 프레임으로 고른다. 만약 1이라면 해당 reference bit를 0으로 초기화하고 다음 프레임으로 넘어가 검사를 계속한다. 이런 식으로 evict될 프레임이 선택될 때까지 반복하며, 다음 번에 다시 evict될 프레임을 고를 때는 멈췄던 그 자리부터 다시 검사를 시작한다. reference bit가 1인 프레임에는 기회를 한 번 더 준다고 하여 second-chance라 하며, 설정한 포인터가 시계바늘처럼 움직인다고 하여 clock 알고리즘이라고 한다. 이 둘의 차이를 굳이 꼽자면 second-chance의 경우 포인터를 고정시키고 조사된 프레임을 pop-front, push-back 하는 것을 반복하는 것이고 clock은 포인터 자체가 움직인다는 점이다. 

 

문제는 이런 식으로 page replacement algorithm을 구현하려면 FT는 hash로 만드는 것이 불가능하다. 왜냐하면 hash에서 각 엔트리를 순회하는 방식은 rehash를 할 때마다 엔트리의 순회 순서가 바뀌어 순서를 일정하게 유지하는 것이 불가능하기 때문이다. 그래서 당시에도 단순 리스트로 만들어 관리했었던 것으로 기억한다. 일단 리스트로 만든다고 해도 이는 내가 예전에 구현한 방식이기 때문에 코딩 방식이 겹쳐서 다소 위험한 방식이다. 자가 표절도 표절이니.... 썩을

 

예전 pintos 매뉴얼에는 다음과 같은 말이 있지만 지금 pintos 매뉴얼을 비교한 결과 현재는 없다는 것을 알 수 있었다. 

Implement a global page replacement algorithm that approximates LRU. Your algorithm should perform at least as well as the simple variant of the “second chance” or “clock” algorithm.

 

그렇다고 해서 random eviction 같이 아무 방식이나 무작정 선택하면 안 되고, 꽤나 그럴듯한 알고리즘을 선택해야 한다. 때문에 조금의 구글링을 더 해서 선출한 다른 page replacement algorithm (후술 PRA) 후보들은 다음과 같다.

 

• NRU(not recently used)
• Two Handed Clock
• Aging

각 방식에 대한 설명은 아래와 같다.

A) NRU

일정 시간마다 타이머 인터럽트가 호출되는 특성을 이용해 모든 프레임의 reference bit를 0으로 초기화한다. evict할 때가 되면 (reference bit, dirty bit) 순서쌍을 고려하여 (0, 0), (0, 1), (1, 0), (1, 1)의 순서로 evict할 프레임을 선택한다. reference bit가 1이라는 것은 타이머 인터럽트로 해당 bit가 초기화된 이후 비교적 최근에 사용되었다는 것을 의미하므로 납득이 되는 선별 기준이다.

 

문제는 해당 방식을 선택하면 앞으로 프로젝트 4에서나 진행할 timer_sleep()을 쓰기 시작해야 한다는 것이며, 해당 방식은 evict할 프레임 선택에 있어 반드시 모든 프레임을 순회 후, 적당한 후보를 골라 그 중에서 선택해야 한다는 단점이 있다. 또한 page_fault가 일어나는 시점에 따라 효율성이 갈린다는 단점도 생긴다.

B) Two Handed Clock

여기서 가장 처음 알게 됐는데, UNIX에서 사용되는 방식이라고 한다. 더 자세히 조사해보니 동작 원리가 설명된 그림이 나와서 첨부한다:

출처 : Operating Systems : A Concept-Based Approach by Dhananjay M. Dhamdhere

구체적인 동작 원리의 설명은 다음과 같다. Clock 알고리즘과 유사하게 각 프레임이 원형 큐 안에 놓인 것으로 취급하되 이번에는 가리키는 포인터를 그림에서 나온 것처럼 EP, RP 2개로 만든다. EP는 Examing Pointer의 약자, RP는 Resetting Pointer의 약자다. 두 포인터는 일괄적으로 움직이므로, 위 그림에서 (a)에서 (b)로 진행했을 때 포인터의 사이 간격이 일정한 것을 볼 수 있다. EP는 현재 가리키는 프레임의 reference bit를 확인하고 1이라면 진행한다. RP는 현재 가리키고 있는 프레임의 reference bit를 0으로 초기화한다. 만약 EP가 reference bit가 0인 프레임에 도달한다면 해당 프레임을 evict한다. 

 

이런 방식으로 (a)에서 (b)까지 진행할 동안의 과정을 설명하면:

 

• EP가 가리키는 7의 ref가 1이니 진행, RP가 가리키는 6의 ref를 0으로 초기화
• EP가 가리키는 18의 ref가 1이니 진행, RP가 가리키는 2의 ref를 0으로 초기화
• EP가 가리키는 9의 ref가 0으로 evict될 프레임으로 선택, RP가 가리키는 3의 ref를 0으로 초기화
• 마지막으로 EP와 RP를 시계방향으로 한 칸 옮기고 종료. 다음 탐색 때는 머물러 있는 지점부터 다시 시작한다.

이다.

 

해당 알고리즘의 동작에 따른 결과가 납득이 가는 이유는 RP가 지나가고 나서 EP가 도착할 때까지 프레임에 대한 참조가 없으면 그만큼 참조가 덜 됐다는 뜻이기 때문이다. 따라서 해당 과정을 거쳐 evict 되기 위해 선택된 프레임은 비교적 참조가 덜 된 프레임이 된다. 이를 생각하면 두 포인터의 간격에 따라 일반적인 Clock 알고리즘과의 유사성이 결정되는데, RP가 EP에서 멀리 떨어져 있을수록 일반적인 Clock 알고리즘과 유사해진다. EP와 RP가 너무 가까이 붙어있으면 정말 최근에 사용된 프레임만 eviction에서 살아남기 때문에 효율이 떨어질 가능성이 있다.

C) Aging (NFU)

NRU와 비슷하게 타이머 인터럽트를 활용하는 것은 같지만 프레임 구조 자체에 카운터를 넣어 참조될 때마다 카운터를 늘리고, 타이머 인터럽트 마다는 카운터를 줄인다. 참조될 때는 카운터의 MSB (most significant bit)를 하나 올리고, 타이머 인터럽트 때는 카운터를 한 자리씩 오른쪽으로 bit shift하여 aging 과정을 겪게 한다. evict될 프레임을 고를 때는 해당 카운터 중 가장 작은 값을 가진 프레임을 고르면 된다.

 

문제는 NRU와 마찬가지로 timer_sleep()의 이른 사용, 모든 프레임 구조체를 순회해야 하는 점이다. 

 

---

 

다 살펴봤을 때는 구현 비용 - 성능 가성비를 고려할 대 Two Handed Clock가 압도적으로 높다. 무엇보다 아직 나는 timer_sleep 건드리기에는 무섭다. 좀 걸리는 것은 그냥 Clock 알고리즘에서 포인터 하나 늘어났다는 것이지만... 그래도 4년 전에 코딩한건데 다른 코딩 방식이 나오지 않을까? 일단 Two Handed Clock 방식으로 구현하도록 하자.

 

이제 PRA 선택이 끝났으니 이를 효율적으로 구현하기 위한 FT의 구조를 찾아야 한다. 일단 hash는 봉인당했으니 list로 struct frame을 엮도록 한다. Two Handed Clock에서 요구하는 구조인 원형 큐 형태는 주어진 리스트를 순회할 때 list_end에 다다르면 다시 list_begin으로 가도록 설정하여 기능상 구현이 가능하다. 이를 자주 사용할 것 같기에 함수를 따로 만들어 포인터 전진 함수로 사용하기로 하자.

 

또한 EP, RP를 나타내는 구조가 필요하다. 해당 구조를 만들 때 생각이 든 게 몇 가지 있다. 해당 구조는 eviction이 일어날 때만 사용이 된다. 만약 eviction이 일어나야 해서 EP, RP가 생성이 됐다가 몇 개의 프로세스가 종료하여 물리 공간이 충분해진 뒤, 다시 eviction이 필요해진 상황을 생각해보자. EP, RP의 위치는 어디여야 하는건가? EP가 가리키던 프레임이 없어진다면? 이를 해결하기 위해 일반적인 Clock 알고리즘에서는 어떻게 대처하는지 검색을 했다. 나오는 것이 마땅히 없어 그냥 내 스스로 이 상황을 타파할 방법을 찾아보았다.

 

만약 FT에 있는 struct frame이 빠진다면 문제가 생긴다. eviction이 일어나기 전 기존에 없었던 struct frame이 FT를 채우는 것은 문제가 없지만 프로세스 종료 등의 이유로 몇 개의 프레임이 없어져 버리면 EP와 RP가 dangling 포인터가 될 가능성이 있다. 따라서 이에 대한 해결을 위해서는 프로세스가 종료해 프레임 정보를 날리더라도, 그 정보가 담겨져 있던 struct frame 구조는 없애지 않아야 한다는 결론을 내렸다. 이를 고려하면 FT는 채워진 이후에는 항상 가득 차 있게 될 것이다.

 

이제 어느 정도 필요한 것들은 다 넣었다. 마지막으로 필요한 것은 FT에 접근할 때 acquire해야 할 lock이다. 지난 포스팅에서도 언급했듯, 동기화 문제 해결을 위해 global 자원인 FT는 lock을 가진채 접근하는 것만 허용한다. 해당 lock은 pintos 전체가 init이 될 때 lock_init해 주면 문제 없을 것이다.

 

위의 설명을 종합해 최종적으로 들어가야 할 것을 모두 포함한 FT의 구조는 아래와 같다. 이름 등은 아직 모두 임시다.

#define HANDSPREAD ?

struct frame_table {
	struct list frames;
	struct list_elem *EP;
	struct list_elem *RP;
	struct lock ft_lock;
};

물론 아직은 eviction 등을 구현하기에는 멀었다. 매뉴얼에서 구현하라는 사항들을 순서를 맞춰서 철저히 따라가도록 하자. 안 그러면 정말 어디서부터 어떻게 구현할지가 막막하기 때문이다...

 

우선 매뉴얼에서는 SPT의 구조를 설계하고 다음의 세 함수를 구현하라고 한다.

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 관련 함수를 활용하면 간단할 것이다. 다음.

 

아래의 함수를 구현한다.

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

차례대로 프레임 할당, 페이지 - 프레임 연동, 주어진 va에 대응하는 페이지를 프레임에 연동하는 기능을 한다. 아직 FT를 구현할 차례는 아닌 것 같으니 일단 묵혀두자. 마지막 vm_claim_page의 경우, va에 해당하는 페이지를 spt에서 찾아본 뒤, 만약 없으면 새롭게 페이지를 생성해 연동하면 될 것이다.

 

다음 포스팅(대전을 간 뒤)에서는 실제 코딩을 들어갈 것이다. 이제 포스팅 방식을 좀 바꿔서 예-전처럼 목적을 정해놓고 그걸 하루만에 다 해치우지 말고 그날그날 한 내용을 포스팅하는 방식으로 바꾸겠다. 수업 들어가면 바빠서 아마 길게 글을 못 쓸듯.. 프로젝트 3의 경우 각 매뉴얼에서 원하는 함수의 코딩이 정해져 있으므로 해당 함수를 해치우면 다음 주제로 넘어가는 방식으로 진행하도록 하자. 일단 Memory Mgmt에서는 위의 6개가 주 목표이다.