🌌[Pintos] 3-2. VIRTUAL MEMORY

이강욱·2022년 12월 12일

pintos 정글

🌌 Pintos

목록 보기

4/6

세 번째 프로젝트가 끝났다.
지금과 나중을 위해 구현하면서 알게된 것들을 적어둔다.

이번주의 주요 키워드

lazy load (demand paging)

프로세스가 load 될 때, 해당 프로세스가 가지는 memory segment (code(or text), data, bss, heap, stack) 들은 곧 바로 물리 메모리(DRAM)에 배정되지 않는다. 실제로는 그 프로세스가 해당 메모리 영역(page)을 요구할 때(demand), 그제서야 kernel은 현재 가용한 물리 메모리의 영역(frame)을 하나 찾은 후, load할 때 구성해 두었던 page table을 가지고 필요한 정보를 물리 메모리에 적어준다.

좀 더 정확히 말하자면, kernel은 프로세스의 요구(demand)를 처리한다기 보다는, 프로세스가 일으킨 오류 (fault)를 처리해 준다. 프로세스의 수행에 따라 메모리 영역에 접근하게 될 것인데, 해당 영역은 아직 물리 메모리에 배정되지 않았으므로 이러한 접근은 page fault라는 interrupt를 (하드웨어적으로) 일으킨다. 이 때 kernel mode에 진입하게 되면서, kernel은 프로세스가 접근하고자 했던 가상 주소를 CR2 register에서 읽은 후 (하드웨어가 적어준다), 그 프로세스의 page table을 참고해 그제서야 물리메모리에 lazy 하게 load 해주는 것이다.

이렇게 하면, 프로세스가 접근하지 않고 있는 메모리 크기 만큼을 실제 물리메모리 상에서 다른 프로세스에게 할당해 줄 수 있다. 이는 storage 공간을 활용하는 swap 기능과 함께하면서 (뒤에서 설명하겠다), OS가 자신의 key role 중의 하나인 Sharing (특히, space sharing)을 실현할 수 있도록 해준다.

`mmap`

kernel이 mmap system call을 받으면, 요청 파일의, 요청 offset에서 시작하는, 요청 크기만큼의 연속되는 메모리 영역을(물리 메모리 상에서 연속될 필요는 없다. 어차피 page 단위로 관리하기 때문에.), 요청 프로세스의 가상 메모리 상에 할당해 준다. 이 때 또한 demand paging이 적용되어 mmap 호출만으로는 실제 물리 메모리에 파일 내용이 적히지 않고, 프로세스가 요구해야만 (fault가 발생해야만) 그제서야 파일을 읽어서 물리 메모리에 적어준다.

mmap system call은 file system에 대한 일종의 interface라고도 볼 수 있다. 프로세스가 mmap으로 할당받은 메모리 공간에 write하면 그 변경사항이 실제로 storage의 file에 저장(write-back) 된다. 프로세스가 명시적으로 read 또는 write를 하지 않고도 file에 대한 작업을 할 수 있게 도와주는 것이다. 변경사항이 저장되는 순간은, 프로세스가 명시적으로 munmap system call을 호출하거나, 해당 영역에 포함된 page가 swap out 되거나 (뒤에서 설명하겠다), 명시적 munmap 호출 없이 프로세스가 종료될 때이다.

swap in/out

Memory swapping 은 앞서 언급된 space sharing을 가능하게 하기 위한 기법으로, storage의 공간을 활용한다. demand paging을 통해 물리 메모리에 각 페이지들이 들어 찰텐데, demand가 감지되었을 때 물리메모리에 더 이상 페이지를 배정해 줄 수 없다면, 가장 오래 접근되지 않은 page(victim page: 희생자 페이지)를 골라 해당 페이지를 storage로 evict(swap out)한다. 희생자 페이지의 type (anonymous memory vs file-backed memory)에 따라 swap out되는 공간(backing storage)이 나뉘게 된다 (swap dist vs backing file).

그리고 이렇게 swap out 된 page에 대하여 다시 demand가 감지된다면, 그때 그 page를 swap in 한다. 즉, storage에 해당 페이지가 존재하는 부분을 읽어 물리 메모리에 적어준다. 참고로 위의 그림처럼 process 의 memory가 통째로 swap out 되지 않음을 유의하자. page 단위로 swap in/out 이 일어난다.

CSAPP에서는 이러한 상황에 대하여 "메인메모리는 디스크에 대한 캐시" 라고 정의한다. 우리는 프로세스가 실행될 때 항상 메인 메모리를 생각하지만, 맨 처음 프로그램을 실행하기 위해서는 디스크에서 그 파일을 읽어오는 작업이 선행되어야 함을 떠올려보면, 프로세스가 수행되면서 읽고 쓰는 모든 정보가 디스크에 있다는 관점으로 생각해 볼 수도 있다 (네트워크 통신 제외). 그래서 프로세스는 storage를 직접 읽고 쓰며 작업하고 싶지만, disk I/O는 매우 느리다. 따라서 "메인메모리를 디스크에 대한 캐시"처럼 사용하기 위해 swap in/out을 활용한다고 이해할 수도 있겠다.

나를 잠 못 들게 한 질문들

이번 주차는 특히 동기 형들로부터 여러 유익한 질문들을 많이 듣고, 같이 생각해보는 시간이 많았다. 각각에 대해 알게된 내용을 정리해보고자 한다.

Anonymous vs File-backed (by prodyou and jw3215)

"code segment랑 data segment는 분명히 실행 파일에서 읽어오잖아,
근데 왜 anonymous memory로 type을 지정해주지?"

pintos는 process를 load할 때, 해당되는 executable file에서 segment들을 읽어서 page table에 기록한다 (pintos의 구현 상으로 정확히는 Supplemental page table(spt)에 기록).

vm_alloc_page_with_initializer 가 바로 segment의 page 들을 각각 spt에 등록하는 과정을 수행하는 함수이다. 근데 질문처럼 page의 type을 file-backed memory에 해당하는 VM_FILE이 아닌, VM_ANON으로 지정하여 등록한다.

질문에 답하기 위해서는 왜 굳이 메모리를 anonymous memory와 file-backed memory로 나누어 관리하는지를 먼저 알아야 한다. 둘의 차이점은 (너무나 당연하지만) 이름에서부터 알 수 있는데, 그 둘의 이름은 각각 그들이 swap out 되는 공간인 backing store 의 이름과 같다. anonymous memory는 disk의 swap disk에 존재하는 익명의 file에, file-backed memory는 disk에 존재하는 자신의 원래 file에 swap out 된다.

사실 모든 메모리를 anonymous memory로 관리할 수도 있을 것이다. 즉, 모든 swap out을 swap disk를 향하게 할 수도 있을 것이다. 하지만, 원래 그 메모리에 해당하는 정보를 지닌 file이 disk에 존재한다면 이는 swap disk라는 공간자원의 낭비이다. 더불어, anonymous memory는 swap out 시 필연적으로 write back 이 일어난다. 다시 요구가 감지되어 swap in 되어야 할 때까지 그 정보를 저장해 두어야 하기 때문이다.

하지만 file-backed memory의 swap out은 반드시 write back을 포함하지는 않는다. 이미 disk 상에 해당 메모리의 정보를 저장해둔 file이 미리 존재하고 있었기에, write back을 해두지 않아도 다음 요구가 감지되었을 때 그 file을 읽어 바로 swap in을 할 수 있기 때문이다. 단, swap out되는 시점에서 그 메모리 상의 정보가 변경되었을 경우 (== modified == dirty), 해당 file에 write back해주어야 한다. 그래야 swap out된 시점의 정보를 그대로 간직한 채 이후에 swap in 될 수 있기 때문이다.

이러한 특성을 유념하면서 다시 pintos의 구현을 살펴보자. load_segment가 수행되는 segment는 두 가지 인데, code segment와 data segment가 그것이다. code segment는 말그대로 수행될 코드 (cpu가 읽고 실행할 수 있는 binary)가 적혀있을 것이고, data segment는 그 과정에서 사용되는 변수들의 정보가 적혀 있을 것이다. 질문의 요지는 file에서 읽어왔는데 왜 file-backed memory가 아니냐는 것이었다.

아까 언급한 두 memory type의 차이를 다시 떠올려 보자. -> backing store의 차이.
사실, data segment는 file에 정보가 존재하지 않는다. run-time 시점에서 초기화 되는 변수들(bss)은 그 변수의 크기가 아닌, 변수의 내용이 file에 이미 적혀있다는 말 자체가 어불성설이다. compile 시점에 초기화된 변수라고 해도, run time에 그 변수의 값이 충분히 바뀔 수 있다. 따라서 data segment는 다시 file에 적히면 곤란하다. 즉, file에 swap out되면 안된다. 그 '내용'이 file에 이미 없었거니와, 있었다 하더라도 그 내용을 바꿔서는 안되기 때문이다. (compile이 되던 시점에 이미 정해진 내용이기 때문) 그래서 swap disk로 swap out 하기 위해 (swap out이 file을 향한다는 건 write back이 언제든 일어날 수 있다는 말이다), anonymous memory로 관리한다.

다만, code segment는 swap out이 file을 향하도록 해도 문제가 없다. 왜냐하면 code segement 는 read-only 메모리기 때문에 프로세스의 동작중에 modify 될 일이 전혀 없기 때문이다. 하지만 pintos skeleton에서 구현의 복잡성을 피하기 위해 data segment와 동일하게 anonymous memory로 지정했다고 판단했다.

kernel code & data segment (by markchck)

"프로세스의 code segment와 data segment에 대한 물리메모리를 할당받는 부분은 존재하는데, kernel의 code와 data segment에 대한 물리메모리는 언제 할당받는 거지?"

질문의 시작은, 커널의 code segment와 data segment에 대하여 palloc_get_page 함수의 호출을 찾지 못하면서부터였다. 의문을 해소하기 위해서는, pintos가 물리메모리를 어떻게 관리하는 지를 알아야 한다.

pintos는 물리메모리를 2등분하여 한쪽은 kernel이 사용할 영역, 한쪽은 user '들'이 사용할 영역으로 나누어 관리한다. 나누어 관리한다는 말은 kernel 자신이 지니고 있는 페이지 할당기가, 물리 메모리를 kernel pool과 user pool로 나누어 관리하도록 한다는 것이다. 그래서 test case가 지정하는 물리메모리 크기인 20MB를 기준으로, kernel pool과 user pool에 가용한 page 개수는 다음과 같다.

하지만 이는 물리 메모리의 전체 크기를 단순하게 반으로 나누어 가능한 페이지의 개수를 계산한 것 뿐이고, 실제로 이 두 개의 pool이 초기화 되는 과정을 거치고 난 뒤의 페이지 개수는 다음과 같다.

user pool의 페이지 개수는 그대로지만, kernel pool의 페이지 개수는 감소했다.
결론부터 말하자면 우리는 이 감소된 463개의 페이지 (463 = 2496 - 2033) 들이 kernel code segment와 kernel data segment에 할당되었다고 판단했고, 1번째 그림과 같이 표준 출력을 통해 실제 경계값들을 확인하여, 2번째 그림과 같은 도식을 완성했다.

(확대해서 보면 좋다 😅)
(mem_end가 정확히 20MB가 되지 않는 이유는 여러가지 가능성(MB, MiB 차이 등)을 생각해 봤지만, 현재의 논의에서 크게 중요하지 않다고 판단해 설명하지 않는다.)
(새로 알게된 점은, kernel의 code segment와 data segment의 memory 상의 layout이 user process의 그것과 거의 동일했다는 것이다.)

kernel 부팅 시 user pool과 kernel pool을 관리하는 페이지 할당기를 palloc_init () 호출로 초기화 하는데, 이 초기화 이후에 가장 처음으로 할당되는 페이지가 바로 base_pml4 를 위한 한 개의 페이지다 (paging_init (mem_end) 호출 안에서 base_pml4 를 위한 페이지 한 개를 얻기 위해 palloc_get_page(0)를 호출한다). 그래서 kernel pool의 시작지점은, 가장 처음으로 할당된 페이지의 시작주소, 즉 base_pml4 의 시작주소인 0x8004230000 라고 볼 수 있다. 이를 통해, 앞서 언급한 감소된 463개의 페이지가 0x8004000000 ~ 0x8004230000 사이에 포함되는 것이라고 추론해 볼 수 있다. 실제로 계산을 해보면, 0x230000 은 560개 페이지 크기에 해당하는 값인데, 나머지 97개(560 - 463) 페이지에 해당하는 영역은 표준 출력에서 보이는 base_mem의 끝과 ext_mem의 시작 사이에 해당하는 영역이라고 추론해 볼 수 있다(0x100000 - 0x9fc00 == 385KB == 96.25 pages).

원래의 질문으로 돌아오자면, kernel의 code와 data segment에 대한 물리메모리 할당은, 해당 영역들을 페이지 할당기의 초기화 시에 이미 kernel pool 에서 occupied된 상태라고 지정함으로써 이루어지고 있는 것이다.

clock vs LRU (by jjaeny)

"희생될 페이지를 찾는 page replacment policy로 LRU를 적용하고 싶은데 어떻게 해야하지?"

메인메모리에 더 이상 가용한 프레임이 없을때 희생자 페이지를 선택하는 page replacment policy 에는 여러가지가 있다. ➡ Optimal, LRU, Clock, Belady's anomaly

우리는 캐싱에 흔히 사용되는 LRU (Least Recently Used)를 사용하고자 했다. 왜냐하면 page replacment policy 의 성능은, 유저가 접근하려고 시도하는 페이지가 물리 메모리 상에 없는 상황이 얼마나 적게 발생하는가, 즉 page fault가 얼마나 적게 발생하는가 로 측정할 수 있기 때문에, 이것이 cache miss를 줄이는 과정과 비슷하게 느껴졌기 때문이다. ("메인메모리는 디스크에 대한 캐시이다.") 하지만 이를 코드로 구현할 방법이 도저히 떠오르지 않았다. 왜 그랬을까?

사실 관리해야할 list에 LRU를 적용하는 것은 어렵지 않다. 어떤 원소가 'Used'될 때마다 그 원소를 list의 head로 보내준다면, 항상 list의 tail에 존재하는 원소가 Least Recently Used인 원소가 된다. 그래서 이 'Used'라는 개념을, 유저가 페이지에 해당하는 주소에 '접근' 하는 것으로 대치해서 생각해 방법을 고안하려다가 불가능함(~~가능한 방법이 있을지도 모른다~~)을 깨달았다.

왜냐하면 유저 프로그램이 어떤 메모리에 접근 했을 때 그 사실을 커널이 ‘알아야’ 그 페이지를 관리 리스트 상에서 head로 옮길 수가 있을 텐데, 커널이 유저가 어떤 메모리에 접근했음을 ‘아는’ 방법은 인터럽트 밖에 없다. 커널이 ‘안다는’건 커널 모드가 '켜져야'(비유하자면 의식이 있어야) 알텐데 유저 모드에서 커널 모드가 켜지려면(커널을 깨우려면) 인터럽트가 발생해야 한다. 이말은 결국 LRU 구현을 위해서는 유저 프로그램이 메모리에 접근하는 모든 순간에 인터럽트를 발생시켜야 한다는 말과 같아진다. 말도 안되는 얘기.

그래서 대부분의 kernel 구현에서 page replacment policy 로 clock 알고리즘을 활용한다.
clock 알고리즘은 하드웨어의 도움을 받는다. 유저프로그램이 메모리에 접근했을 때, 해당 페이지의 PTE에 해당 페이지가 접근 되었다고 하는 비트(accessed)를 하드웨어가 켜준다. 이 과정에서 페이지 폴트는 일어나지 않는다. 그리고 나중에 evict가 필요한 시점이 되서야 커널이 이 비트를 참고해서 희생자 페이지를 정한다.

그림에서 보이는 것과 같이, 프레임 포인터가 시계의 초침처럼 테이블을 순회하면서 희생될 페이지를 찾는다. 해당 페이지의 참조 비트(accessed bit)가 1이라면 (켜져있다면) 0으로 만들고 다음 페이지로 넘어간다. 이를 반복하다 참조 비트가 0인 페이지를 만난다면 그 페이지를 희생자 페이지로 삼고 남은 evict 과정을 이어서 진행한다.

그 이후로 프로그램이 계속 실행되다가 다시 evict가 필요한 순간이 발생했다고 하자. 하드웨어는 이전 evict가 처리된 이후부터, 다시 매 접근마다 해당 PTE의 비트를 켜주고 있었을 것이다. 이번에도 kernel은 위의 과정을 반복한다. 이때 참조 비트가 0인 페이지는 이전 evict 발생 순간과 현재의 evict 발생 순간 사이에 전혀 접근되지 않았음을 추론해 낼 수 있다. 이를 통해 우리는 그 페이지가 recently 하게 used되지 않았다고 판단할 수 있다.

clock 알고리즘은 LRU를 approximate 할 수 있다. 왜냐하면 우리는 어떤 페이지가 가장 최근에 사용되었는지에 대해서는 알 필요가 없기 때문이다. 다시 말해, list로 LRU가 구현된 상황이라도, list의 head에 어떤 페이지가 있는지 보다는 tail에 어떤 페이지가 있는지에만 관심을 두면 된다. 즉, 어떤 페이지가 가장 ‘콜드’한 페이지 인지만 알면된다. 그래서 클락을 사용하면 LRU에 근접한 수행을 할 수 있게 된다.

CR0 register (by ubs4939)

"writable 하지 않은 페이지에 계속 쓰기를 하고 있었는데 여태껏 아무런 문제가 없었어.
이게 뭐지...???"

lazy load를 수행해주는 do_lazy_load 함수이다. 중간 라인 정도의 file_read_at을 보면 user buffer로 page의 va를 주고있다. 하지만 만약 이 page가 read-only라면? page fault in kernel context 가 발생해 커널이 죽게 될 것이다. 사실 이러한 의심없이 계속 이 코드로 test를 돌리고 있었는데, 아무 문제가 없었다는 걸 뒤늦게야 발견했다.

하나의 물리주소는 두가지 경로로 접근될 수 있다. 하나는 유저의 virtual address (page->va) 에 해당하는 PTE, 다른 하나는 커널의 virtual address (frame->kva) 에 해당하는 PTE. 그렇기 때문에 do_lazy_load 실행되기 전, 유저 페이지의 PTE가 pml4_set_page을 통해 not writable 로 지정되더라도, 커널 kva를 통해 write할 수 있다. 커널 PTE는 (커널 text 영역 제외) 모두 writable 하기 때문이다. 따라서 위 경우에는 file_read_at 의 user buffer 주소로 frame->kva 를 전달하면 문제 없이 lazy load를 수행할 수 있게 된다. 하지만 page->va 를 전달했을 때도 왜 아무 문제가 없었던 것일까?

skeleton 코드를 한참동안 뜯어보고, stack overflow도 뒤져보고, 조교님께 질문도 해본 결과, 이는 pintos 부팅 시의 기본 설정 덕분이었음을 알게 되었다.

x86-64 아키텍쳐에는 Control Register가 존재한다. 페이지 테이블 계층에서 최상위 테이블인 pml4의 시작 주소를 저장해둬야 하는(그래야 mmu가 이 주소를 보고 walking 할 수 있다) CR3 (PDBR : Page Directory Base Register), page fault 발생 시 cpu가 fault address 를 적어두는 CR2 모두 이 Control Register 이다.

지금 문제가 되었던 레지스터는 CR0. 특히 Write Protection (WP) bit 였다. WP bit가 꺼져 있다면, ring 0 (kernel mode) 코드는 쓰기에 대한 접근 제한을 무시할 수 있다. 그리고 pintos의 부팅 과정에서 CR0의 WP bit는 켜지지 않는다.

따라서 kernel code는 write 접근제한을 무시하고 메모리에 접근할 수 있었던 것이다.

그렇다면 왜 이러한 설정이 필요할까? kernel은 유저 프로세스들의 supervisor 이다. user에게 read-only인 page도 supervisor는 필요하다면 읽고 쓸 수 있어야 한다 (e.g. lazy loading의 .text 영역). 그렇기 때문에 일반적으로는 WP bit가 set되어 있지 않다.

하지만 이 WP bit가 set 되어있으면 편리한 경우가 있다 : Copy on write.

여러 프로세스가 단 하나의 물리 공간을 바라보면서 그 메모리 내용을 공유하다가 (그 메모리는 read-only로 설정해둔다), 어느 한 프로세스가 해당 영역에 쓰기(write)를 시도하면 그제서야(on) 시도한 프로세스 만을 위한 물리 공간을 할당하여 원래 내용을 복사해준다 (copy). 이 때 커널은 write에 대한 시도를 page fault를 통해 인지하게 되는데, WP bit가 set 되어 있지 않다면, (유저의 write 시도는 유저가 일으키는 page fault를 통해 충분히 인지할 수 있지만) 커널 자기자신이 write 시도를 하는 상황에 대해서는 인지할 수 없게 된다 (시스템 콜로 인해 유저의 요청을 처리하다가 해당 메모리 공간에 write를 시도하게 될 수도 있기 때문에, 커널은 자기 자신이 일으키는 page fault도 인지할 수 있어야 한다). 그래서 WP bit를 set 함으로써 커널은 자기 자신의 write 시도에 대해서도 충분히 인지할 수 있게 된다. 리눅스에서도 이 경우를 처리하기 위해 WP bit을 set해 주고 있다.

이번 프로젝트를 통해 항상 이론으로만 공부해 잘 와닿지 않았던 가상메모리의 실제 동작방식을 아주 명쾌하게 이해할 수 있었다. pintos의 구현이 general하다고 보기엔 어렵기 때문에 아직 공부해야 할 것이 많이 남았지만, 어쨌든 직접 코드를 쳐보면서 공부하는 것이 정말 중요하구나, 사람들이 괜히 그렇게 말했던 것이 아니구나 하고 느끼게 된 2주였다.