가상 메모리에 대한 이해
가상 메모리 영역은 실제 물리메모리 크기에 비해 매우 크다. 실제로 핀토스는 x86-64기반이라 64비트 체계를 사용하는데, 주소표현에는 총 48bit를 사용한다. 즉 가상메모리의 최대 크기는 2^48 = 256TB에 달한다는 것을 알 수 있다. 그런데 놀랍게도 현재 핀토스에게 단 20MB만의 물리메모리를 할당했는데도 불구하고 프로그램이 잘 돌아간다. 아래의 그림은 핀토스에서 가상 메모리(왼쪽)와 실제 물리 메모리(오른쪽)를 나타낸 모식도이다.
가상메모리 덕분에 유저(프로그램)는 마치 자신이 대용량의 사적인 메모리를 가지고 있다고 착각하고 있다. 그러나 실제로는 유저들마다 유저영역이 존재하고, 혼자서 메모리를 무한정 사용하지도 않는다. CPU는 MMU에게 가상주소를 전달하고 물리주소를 요청하며, 페이지 테이블을 참고하여 VM시스템이 실제 물리메모리에서 값을 갖다준다.
사실 ‘가상주소’라는 것은 실제로는 존재하지 않고 개념적으로만 존재한다. 가상주소 공간에는 데이터가 없으며, 실제 데이터는 물리 메모리에만 있다. 가상주소는 실제 데이터가 위치한 물리메모리로 찾아가기 위해 사용하는 임시주소 같은 것이며, 관리하기 편하게 범위를 엄청나게 크게 잡은 거라고 생각하면 편하다.
유저는 실제 RAM의 크기보다 훨씬 더 많은 메모리를 사용하는 프로그램들을 동시에 돌리는 것처럼 보인다. 예를 들어서 실제 RAM의 크기가 8GB이고, 메모리를 1GB씩 사용하는 프로그램을 동시에 10개 실행시키더라도 10개 모두 문제없이 실행할 수 있다. 이를 가능하게 하는 핵심적인 기능 중 하나가 바로 Demand Paging의 Lazy Loading 기법이다.
기존 Project2까지는 Eager Loading 방식을 사용했는데, 이는 프로세스가 실행할 모든 page를 가상 메모리에 할당하는 동시에 물리 메모리에도 곧바로 올리는 방식으로, 당장 읽거나 쓰지 않는 page까지 전부 올라가게 된다. Project3에서 사용하는 lazy loading 방식은 page가 실제로 필요한 그 순간에 물리 메모리로 올림으로써 가상메모리 시스템의 효율을 극대화시킨다.
이를 구현하기 위해서 page 할당 요청이 오면 처음에는 uninit type의 page로 만들고 물리메모리에 올리지 않는다. 이후 CPU가 해당 가상주소를 요청하면 물리메모리에 올라와있지 않으므로 page fault가 발생하고 이제서야 요청된 type으로 initialize한 뒤에 물리메모리로 load한다.
좀 더 자세히 설명하자면 처음에 virtual page가 생성되지만 physical frame은 할당되지 않은 상태로 있다가, CPU가 해당 가상주소를 요청하면 pml4에서 그에 연결되는 frame이 없으므로 page fault가 발생한다. page fault가 발생하면 page에 해당하는 frame을 할당하여 데이터를 물리메모리에 올려줘야 하는데, 이에 대한 정보를 supplemental page table에 미리 저장해두고 있다.
이제 함수별로 따라가보면서 실행파일이 load되는 과정을 살펴보자.
Load 흐름
init.c의 main() 실행
→ run_actions()
→ run_task()
→ process_create_initd()
→ initd()
→ process_exec()
→ load()
→ load_segment()
→ vm_alloc_page_with_initializer()
→ uninit_new()
load()
- 입력으로 넣어준 file_name에 해당하는 실행 파일을 현재 스레드에 load
load_segment()
- 실행파일인 ELF file을 load한다.
- 불러올 데이터를 file에서 page 크기단위로 나눠서 가져오는 역할
- container 구조체 생성해 해당 구조체에 파일 메타데이터(파일 구조체, page_read_byte, offset)를 저장한 뒤에,
- vm_alloc_page_with_initializer() 를 호출하여 uninitialized된 Page를 생성한다.
- 이 page는 나중에 page fault가 발생하면 설정한 type으로 변경되고, 실제로 파일에서 로드된다.
vm_alloc_page_with_initializer()
- 전달된 vm_type에 따라 적절한 initializer를 가져와서 uninit_new()의 인자로 넘겨준다.
- uninit_new()를 호출하여 uninit type의 page를 생성하고, 나중에 바뀔 page의 정보를 넣어준다.
여기서 의문이 하나 들었는데, 왜 load_segment에서 vm_alloc_page_with_initializer를 호출할 때, page의 type을 항상 VM_ANON으로 설정하는지가 궁금했다. 단순히 생각했을 때는 Disk에 있던 file을 가져왔으니 file-backed type으로 처리해야하는게 아닐까라고 생각했는데 잘못된 생각이었다. 이를 알기 위해서는 먼저 ELF 파일에 대해서 알아야 한다.
ELF파일
우리가 load하는 일반적인 ELF 파일은 Read-Only segment와 Read/Write segment로 나뉜다. Read-only segment에는 init, text, rodata가 있고 Read/Write segment에는 data, bss가 있다. write가 가능한 data, bss의 경우에는 file에 변경사항이 업데이트되는 것을 막기 위해 반드시 anon type(VM_ANON)으로 관리해야 한다. ELF 파일은 load될 때마다 초기화되어야 하므로, write가 일어났더라도 이를 file에 반영하면 안되기 때문이다. 반대로, Read-only segment의 경우에는 애초에 write할 수 없으니 File-backed type(VM_FILE)로 관리할 수 있다. 실제로 Linux에서는 Read-only segment에 해당하는 page를 file-backed page로 관리한다고 한다. 아마도 PintOS에서 복잡성을 줄이고자 ELF에 load되는 모든 page를 anon type으로 관리하는 디자인을 채택한 것으로 보인다.
Page Fault 흐름
exception 발생
exception_init()
→ page_fault()
→ vm_try_handle_fault()
→ vm_claim_page()
→ vm_do_claim_page()
→ vm_get_frame()
→ install_page()
→ swap_in()
→ uninit_initialize()page_fault()
- page fault handler 함수로 vm_try_handle_fault()를 호출한다.
vm_try_handle_fault()
- illegal reference인 경우에는 return false
- illegal reference가 아닌 bogus fault인 경우에는 vm_claim_page()를 호출한다.
vm_claim_page()
- 인자로 받은 address에 해당하는 page를 가져온 뒤에 vm_do_claim_page()을 호출한다.
vm_do_claim_page()
-
- 물리 frame을 새로 할당받고 이를 인자로 넘겨준 page와 연결함
- 또한 page table entry에 해당 정보를 매핑함
- 여기서 swap_in()을 호출한다.
- swap_in()함수는 page의 type에 따라 실행하는 함수가 달라진다.
#define swap_in(page, v) (page)->operations->swap_in ((page), v)- load 흐름에서는 uninit operation을 타고 가서 uninit_ops의 swap_in에 있는 uninit_initialize가 실행된다.
/* DO NOT MODIFY this struct */ static const struct page_operations uninit_ops = { .swap_in = uninit_initialize, .swap_out = NULL, .destroy = uninit_destroy, // uninit type의 page는 lazy loading을 지원하기 위해 있다. // 모든 페이지는 우선 uninit type으로 생성 .type = VM_UNINIT, };
uninit_initialize()
- uninit page에 저장되어 있는 initializer()와 lazy_load_segment()를 실행
anon_initialize()
- anon page 초기화
lazy_load_segment()
- disk에 있는 file의 내용을 메모리로 읽어온다. (드디어 여기서)
Memory Mapped File
핀토스에서는 memorry mapped 영역이 없고 힙 영역도 없다. 따라서 mmap() 실행 시 kva 영역의 커널풀에 할당이 되고, 유저 옵션을 주면 유저풀에 할당이 된다.
Swap in/out
앞서 말했듯이 물리 메모리 공간은 매우 한정적이다. 물리 프레임에 할당 요청이 왔으나 이미 모든 물리 메모리가 할당된 상태일 수 있다. 이 때, 지금 당장 필요하지 않은 page 중 일부를 물리 메모리에서 제거하고, 빈 frame에 지금 필요한 page를 할당하는 것을 swapping이라고 한다. 없애지게 될 page(victim page)는 Eviction Policy에 따라 정해지며, Disk의 swap area로 쫒겨나게 된다. 이러한 Eviction Policy에는 LRU, LFU 등 다양한 방법이 가능하지만, 핀토스에서는 상대적으로 구현이 간단한 Clock Algorithm을 사용했다.
Swapping에서 eviction을 구현하기 위해서는 frame들을 관리해야 한다. pml4와 spt의 경우, 프로세스마다 자신의 것을 가지고 있기 때문에 쉽게 다룰 수 있지만, frame은 여러 프로세스가 함께 사용하기 때문에 그렇지 않다. 관리를 위해서 모든 프로세스를 탐색하는 것은 너무나 비효율적이므로 핀토스에서는 다른 방법을 사용했다. frame_table list를 전역으로 선언하여 frame을 관리했으며, swap table 또한 전역으로 선언하여 swap된 victim page를 관리했다. swap table은 alloc/free 상태만 표현하면 되기 때문에 bitmap 자료구조를 사용하여 메모리 측면에서 효율적으로 관리했다.
Swapping은 page의 type마다 다르게 일어난다. Anonymous page의 경우에는 file에 저장할 수 없으므로 Disk에 Swap area를 만들어서 swap out된 page들이 그 곳에 백업된다. 반대로 File-backed page의 경우에는 Disk에 연결된 file이 있으므로 Swap out을 할 때 단순히 file에 변경사항을 Disk에 업데이트하면 된다.
PintOS project3를 구현한 모든 코드는 아래의 github 링크의 main branch에 올라와있다.
https://github.com/PintOS-secondhalf-team3/pintos_kaist_jungle
GitHub - PintOS-secondhalf-team3/pintos_kaist_jungle
Contribute to PintOS-secondhalf-team3/pintos_kaist_jungle development by creating an account on GitHub.
github.com
'sw 사관학교 정글' 카테고리의 다른 글
| PintOS - Project2 - UserProgram (0) | 2022.11.29 |
|---|