pintOS project3: virtual memory - 이론

Ethereal·2021년 10월 14일

pintOS

목록 보기

6/9

주요 링크:
https://www.youtube.com/watch?v=KNUJhZCQZ9c&list=PLMuepVGJo9rZJLUAG_HVC5QUf8TUbCWo0&index=1&ab_channel=DavidBlack-Schaffer
https://casys-kaist.github.io/pintos-kaist/project3/introduction.html

운영체제 three easy pieces의 VM파트 정리본
https://realbro.tistory.com/58

📖VM 개요

메모리 관리법

우테코 메모리 관리 관련 영상
https://www.youtube.com/watch?v=qxmdX449z1U&t=9s&ab_channel=%EC%9A%B0%EC%95%84%ED%95%9CTech

🙄VM이란?

가상 메모리란, OS가 추상화하는(abstraction) 컴퓨터 혹은 머신의 세가지 주 영역 CPU, file, memory 중 memory를 추상화시키는 메모리 관리 기법 중 하나이다.

각 프로세스는 하나의 가상 메모리를 할당 받으며, 프로세스 내에서 실행되는 여러 쓰레드들은 이 하나의 가상메모리 공간을 공유한다.

이러한 방식은 멀티태스킹 운영 체제에서 흔히 사용되며, 실제 주기억장치 (physical memory)보다 큰 메모리 영역을 제공하기위한 방법이기도 하다.

😃paging 기법이란? page/frame

페이징이란 고정 크기로 분할된 페이지(page)를 통해 가상 메모리를 관리하는 기법이다.

페이지(page) : 가상 메모리를 고정 크기로 나눈 블록
프레임(frame) : 실제 메모리를 페이지와 같은 크기로 나눈 블록 (= 페이지 프레임)

프레임과 페이지는 메모리를 일정한 크기의 공간으로 나누어 관리하는 가장 작은 단위이며, 프레임과 페이지의 크기는 같다. pintOS에서는 이를 4096 byte (4KB) 로 되어있다.

page-alligned?
가상 메모리(VA)는 page size로 균일하게 나뉘어 있어야한다는 뜻.
ex) | VM | => | 4kb | 4kb | 4kb (=page size)| .... | 4kb | 4kb |

pintOS(x86-64)에서 우리는 4-level page table (page-map level 1-4 offset/pml4) 을 사용한다. 이를 통해 virtual address 는 아래와 같은 형식을 띈다.

4 level page table? go to multi level page table

위는 추상화된 가상메모리 주소의 구조, 그리고 아래는 물리 메모리 주소의 구조이다.
가상메모리는 0~11bit에 Page Offset을 , 물리 메모리는 0~11에 Frame Offset이 담겨있다.

offset?
offset is the location difference between the byte address you want and the start of the page.
So: Streets = Page number, house number = offset address.
따라서 VM(도시)에 특정 집의 주소(VA)를 위해, Page number or Frame Number인 거리 이름(혹은 구, 동 등으로 비유가능)과 해당 거리에서 몇번째에 있는지를 Offset에 담아 하나의 unique한 집 주소를 만든다.
https://www.cs.swarthmore.edu/~kwebb/cs31/s15/bucs/virtual_addresses.html

You require enough bits in the offset to be able to get to any byte in the page.
For a 4K page you require (4K == (4 * 1024) == 4096 == 2^(12)==) 12 bits of offset.
pintOS 프로젝트와 동일하다.

x86-64 운영체제는 물리 메모리로 직접 접근하는 것을 지원하지 않는다. 다만 아래 vitual memory layout에서 설명하듯이 kernel virtual memory 영역을 물리메모리와 1대1 매핑을 통해 접근을 지원한다. 따라서 kernel VM의 첫번째 page는 물리 메모리의 첫번째 frame과 대응된다. 이는 계속해서 이어진다.

📑virtual memory layout

주소 등은 pintOS와 무관하다. 형태, 배치만을 참고하자.

아래 그림에서 최상단에 argv, environ이라는 project 2에서 구현한 argument passing을 위한 공간이 눈에 띈다.

PintOS에서는 가상메모리의 주소 체계는 아래 그림을 참고하면 좋다.

직접 만든 자료😃

KERN_BASE 부터는 physical memory 와 1대1 매핑이 되어있다.

	KERN_BASE => 0 in PM , 
	KERN_BASE + 0x1234 => 0x1234 in PM.

📑Page Table

페이지 테이블은 자료구조의 일종으로 CPU가 가상 주소를 요청할때 MMU가 가상 주소를 물리 주소로 번역하는 과정에 사용한다. 페이지 테이블에는 VA가 PA로 매핑된 정보가 저장되어있는 page table entry(PTE)로 구성된다. page, frame을 사용할 경우 page(VA)가 frame(PA)과 매핑되어있다.
https://en.wikipedia.org/wiki/Page_table

PTE에는 단순한 page to frame mapping 정보 뿐만 아니라 보조적인 정보들 또한 포함한다. 예를 들어 해당 page에 대응하는 frame이 수정되었지만 디스크에는 아직 반영되지 않은 dirty 상태인지, 해당 page를 점유하는 process의 ID, 주소 공간 정보 등을 가진다.

ex) page to frame

간단한 page table을 이용한 VA(vitual address) to PA(physical address) 번역 과정의 추상화다. offset은 그대로 넘어가고 앞의 page nr가 frame nr로 page table을 통해 번역됨을 알 수 있다.

page table transltaion 예시:

위 그림은 page table을 통해 Disk로 접근하는 경우를 보여준다.
VA가 0일 경우 page table은 disk로 접근하는 것임을 알려준다.

번역은 MMU (memory management unit)이라 불리는 하드웨어에서 처리한다.
매핑에는 paging 뿐만 아니라 segmentation, 혹은 둘다 사용하는 segmented paging이라는 기법이 있다.

📲TLB

위 그림은 TLB를 사용하는 번역과정이다.

TLB(translation lookaside buffer)은 page table의 일부분을(많이 사용되는 부분을) 캐싱해두어, 많이 사용되는 주소일 경우 번역과정을 더욱 빠르게 하기 위해 존재한다. TLB에 logical address(virtual address)에 대응하는 page table이 있을 경우 HIT가 발생하며, 아닐 경우 miss로 일반적인 page table로 넘어간다.

TLB는 process가 일반적으로 한번 참조 한 곳을 다시 참조할 가능성이 아주 높다는 점에서 착안한 속도 증가 기법.

where is the page tables stored?
kernel space
The page table of the process is held in the kernel space. The kernel may have several page tables in RAM, but only one is the active page table. In x86 CPUs, it's the page table pointed by register CR3.
https://stackoverflow.com/questions/56619431/where-is-page-table-located

📑page, frame로 관리하는 이유!

page table 크기를 줄이기 위해, page table의 각 행(page table entry)가 하나의 주소를 가르키지 않고, 한 뭉터기 즉 page, frame을 가르키게 한다.

we have had one PTE for every VA.
page table size was for 32bit system, 1 billion roughly 1gb.
lets make it smaller .

now PTE handles each 4kb page, now we need less PTE and smaller page table roughly 4mb.

nowadays, some 64bit system use 2mb size page.

🙄Multi-level page table

Page Table은 각 프로세스마다 가지고 있으며 Memory내에 OS가 관리할 수 있는 영역에 저장이 된다.
Paging에서 고려해야 되는 것은 Page Table의 크기를 줄이는 것일 것이다.

Multi-Level Page Table의 핵심은 Page Table을 위한 Page Table을 만드는 것이다.
프로세스마다 Page Table은 Memory에 저장이 되는데, page table을 Page 단위로 나누어서 생각해 보자는 것이다.
즉 선형구조가 아닌 Tree구조로 Page Table을 만든다.

위 두 그림으로 multi level page table이 어떻게 요구된 page를 가르키는지 알 수 있다.

🛑page fault handling

페이지 폴트란 프로그램이 자신의 주소 공간에는 존재하지만 시스템의 RAM에는 현재 없는 데이터나 코드에 접근 시도하였을 경우 발생하는 현상을 말합니다.
페이지 폴트가 발생하면 운영 체제는 그 데이터를 메모리로 가져와서 마치 페이지 폴트가 전혀 발생하지 않은 것처럼 프로그램이 계속적으로 작동하게 해줍니다.

RAM에 (메모리에) 우리가 원하는 데이터가 없다면? 디스크엔 있겠지.

따라서 아래 그림처럼 PM에 배정되지 않은 VA를 요청할 경우, processor 즉 CPU는 I/O controller에게 disk의 특정 block을 읽어 메모리에 저장해달라고 요청한다.

CPU는 우선 원하는 주소 (ex.12374)를 MMU에게 보냅니다. 그러나 MMU에는 이 주소 변환 과정에서 페이지 테이블에 이 주소에 대한 항목이 없다고 표시되어 있습니다. 따라서 MMU는 CPU를 인터럽트한 후 페이지 폴트 처리기라는 소프트웨어가 실행되도록 합니다. 이 페이지 폴트 처리기는 다음과 같은 기능을 이용하여 이 페이지 폴트 문제를 해결하기 위한 방법을 찾습니다:

위 그림에서 secondary memory는 disk가 되겠다.

원하는 페이지가 디스크 상 어디에 위치하는지 찾은 후 읽어오기 (일반적으로 페이지 폴트가 코드 페이지일 경우)
원하는 페이지가 이미 RAM에 존재하지만 아직 현재 프로세스에는 할당되지 않았는지 확인 후 MMU가 그 주소를 찾도록 재설정하기(page table 업데이트)
🛑(이해불가) 0만 담고 있는 특수 페이지를 지정 후 프로세스가 이 특수 페이지에 쓰기 시도할 경우에만 새 페이지를 할당하기 (이러한 특수 페이지는 copy on write 페이지라고 부르며, 종종 0으로 시작된 데이터를 담고 있는 페이지에 사용됩니다)
원하는 페이지를 다른 곳에서 가져오기 (이 기능에 대해서는 아래 링크를 참조)

http://web.mit.edu/rhel-doc/4/RH-DOCS/rhel-isa-ko-4/s1-memory-virt-details.html

위 그림 설명 ⬇

load M 즉 page table을 사용해 번역을 진행하려는 MMU는 주어진 VA을 통해 적절한 PTE를 찾아 확인. RAM에 해당 VA에 대응하는 메모리가 할당되어있지 않기에 page fault 발생!
page fault에 의해 trap이라는 실행을 통해 OS으로 복귀 -> page fault handler 가동
page fault handler에서 더 많은 정보를 담은 page table(pintOS에서는 Supplemental page table)을 참조해 단순히 디스크에 있는데 RAM에 할당되지 않은 것인지, 이미 RAM에 할당 되었지만 아직 현재 프로세스에 할당되지 않았는지, (... 추가적인 경우는 추후 추가🛑) 를 판별하고 적절한 행동을 실행.
그림의 경우는 첫번째 케이스. 디스크에서 주어진 VA가 가르키는 데이터를 찾는다.
디스크에서 찾은 데이터를 RAM의 빈 frame에 할당.
page table을 reset.
업데이트 된 page table을 가지고 instruction을 재실행 시킨다!