정글[Week_11-12]: Pintos의 VM 구현하기

2주에 걸쳐 Pintos의 project 3를 수행하였다. 이전에는 1 주당 한 번의 프로젝트를 수행하였으나, 분명 이번에는 2주를 준 이유가 있겠지.. 생각하였고, 이유는 진행하면서 깨닫게 되었다. 결론은.. 개념이 상당히 난해하고 이를 scratch에서 머릿속에 지도를 그려가는데 꽤나 곡선을 그렸다는 것이다.

 

 

부족한 RAM 공간을 가상으로 넓히다

물리 법칙상 램의 속도는 CPU가 어찌 감당할 정도이나, 디스크.. Pintos에서 칭하는 file은 매우 느리다는 것이 특징이다. 문제는, 램의 용량은 상당히 한정적인 반면에 디스크는 대규모 정보를 저장이 가능하다. 기술이 발전하면서, 컴퓨터 설계 구조는 대규모 정보를 저장하는 디스크에는 실제 정보를 저장하되 곧바로 실행은 안되는 것과, 여기에 있는 실행 파일들을 램에 띄워서 CPU와 소통하는 이른바 살아있는 상태로 나뉘게 되었다.

여기서 엔지니어는 한정적인 램을 어떻게 "가상으로라도 확장하는" 방법을 생각해 냈는데, 이것이 말 그대로 VM(Virtual Memory).. 한국어로 가상 메모리이다. 즉, 물리적으로 읽기/쓰기가 매우 느린 디스크를 어떻게라도 램 처럼 사용하려고 만든 방법이다. 이번에 우리는 이 시스템의 골격을 구현하는 것이었다.

디스크와 램.. 익숙한 사진이다

 

 

디스크와 램을 수시로 왕복하는 Swap In/Swap Out

이 가상 메모리는 디스크 상에서 존재한다. 말 그대로 가상이기 때문에, 실제 그 메모리가 "메모리로서 기능"을 하려면 램으로 들어와야 한다. 그리고 이렇게 램으로 들어오는 것을 swap in이라고 한다. In이 있으면 Out도 있는 법! 램에서 특정 메모리는 다시 디스크 상으로 퇴출 시키기도 하는데, 퇴출이라는 어감에서도 느끼는 이는 swap out이다.

 

페이지(Page)단위로 작동하는 swap in/swap out
이렇게 램에서 퇴출 혹은 나간 것을 들여오려면 일정한 단위가 있어야 하는데, 이를 Page라고 한다. 한 페이지는 4096byte이며, 이는 구현 시 상당히 중요한 역할을 한다. 그렇다면, 만약 램이 꽉 차 있어 누군가를 퇴출해야 한다면 누굴 퇴출해야 할까? 이에 대해서는 다양한 알고리즘이 있는데, 대표적인 몇몇을 표로 정리해보고자 한다.

알고리즘 명	특징	효율과 비용
FIFO	선입선출, 가장 먼저 들어온 페이지가 퇴출	연산 비용은 적으나, page fault가 많음
LRU	가장 늦게까지 사용 안한 페이지를 퇴출	연산 비용 큼, 현대 os에서 주로 사용
LFU	사용 빈도가 가장 낮은 페이지를 내보냄	연산 비용 큼, 현대 os에서 주로 사용
Clock Algorithm	시계와 같이 원형으로 돌면서 체크 및 퇴출	연산 비용 비교적 저렴, page fault 타협

 

우리가 선택한 알고리즘은 Clock Algorithm
위의 표에서 보듯, 현대적인 OS에서는 LRU/LFU 알고리즘을 사용하여 기존 페이지를 디스크에 퇴출시킨다. 그러나, 우리가 현재 구현하는 Pintos는 하나의 단일 코어만 존재한다는 것을 고려해야 하며, 이는 연산 비용 면에서 감당하기 힘들다는 결론이 나왔다. 이유는 비교적 간단하다. 각 페이지 마다 사용 빈도/최근까지 사용 시간 등을 매번 저장/업데이트를 해야 하고, 이에 맞게 정렬을 해야 하는데 비용이 막대하기 때문이다.

Clock 알고리즘은 매번 이러한 정렬을 할 필요도 없고, second chance 라는 기법을 사용하여, 앞으로 사용될 페이지를 굳이 퇴출시켜 page fault 발생 빈도를 낮춘다. 우리 팀이 구현한 코드를 대략 요약하자면 다음 아래와 같다:

do {
    victim = list_entry (i, struct frame, frame_elem);
    struct page *page = victim->page;
    uint64_t *owner_pml4 
    = page != NULL && page->current_thread != NULL ? page->current_thread->pml4 : pml4;

    if (page != NULL &&
        page->operations != NULL &&
        page->operations->swap_out != NULL &&
        owner_pml4 != NULL &&
        !pml4_is_accessed (owner_pml4, page->va)) {
        clock_stop_framelum = list_next (i);
        if (clock_stop_framelum == list_end (&frame_table))
            clock_stop_framelum = list_begin (&frame_table);
        return victim;
    }
    if (page != NULL && owner_pml4 != NULL)
        pml4_set_accessed (owner_pml4, page->va, false);
    clock_stop_framelum = list_next (i);
    if (clock_stop_framelum == list_end (&frame_table))
        clock_stop_framelum = list_begin (&frame_table);

    i = list_next (i);

    if (i == list_end (&frame_table))
        i = list_begin (&frame_table);
} while (i != e);

먼저, 알고리즘은 원형 시계와 같이 순환을 하지만 정작 다뤄야 하는 list는 시작과 끝이 있다는 것을 기억할 필요가 있다. 이에 접근하기 위해 do while 문을 사용하였으며, clock_stop_framelum과 같이 시침(가리키는 페이지)가 어디인지 저장하는 변수도 선언을 해 두었다. 순회하면서 각 페이지 또한 조건을 만족하는지 체크하는 것은 덤!

 

 

페이지 예약되고 게으르게(lazy load) 로드가 된다

일단.. 말이 어렵다. 이 개념을 이해하려면, 각 함수의 꼬리에 꼬리를 물어서 어떤 분기에서 처리가 되는 지 이해를 할 필요가 있다. 위의 설명에서는 마치 페이지의 데이터들이 램과 디스크를 왕복만 한다고 생각할 수 있다. 그러나, 페이지는 struct Page 구조체를 통해 page 골격 및  정보를 담고 있으며, 실제 본체, 즉 4096bytes의 데이터들은 frame이라는 구조체를 통해서 할당이 된다.

 

페이지 구조체를 담는 장부: SPT(supplemental page table)
이러한 페이지 구조체는 spt라는 장부를 통해서 등록이 되고 해제가 된다. 하나의 프로세스에는 하나의 spt 장부가 존재하는데, 그 프로세스에 어떠한 페이지가 구성되는 지 명확히 할 수 있기 때문이다. 이해를 위해 아래 도식화를 살펴보자:

spt 장부와 페이지들

다만, 앞에서 기술하였듯 장부에 등록이 된다는 것은 실제 램에 메모리가 할당이 된다는 것을 의미하지 않는다. "예약된다"라는 단어가 혹시 기억이 나는가?.. 페이지는 vm_alloc_page_with_initializer()라는 함수를 통해 장부에 등록(이미 등록되어 있으면 패스)되고, 페이지 타입에 맞춰 예약이 된다.

이후 필요에 따라, page fault가 발생할 때.. 즉 뒤늦게 필요한 상황이 올 때서야 lazy_load 함수를 통해 실제 램에 해당 페이지 내용이 채워지게 된다.

 

 

이것 이외에도.. 너무 적을 내용이 많다. 2주에 걸친 규모있는 프로젝트인 만큼, 핵심 포인트만 정리를 하였다. 이후 머릿속에 내용이 정리되면 추후 작성을 하고자 한다. 그럼 이만~