Ch 9-1. Virtual Memory: Advantages, Page Table, Page Fault, Address Translation, TLB

Physical Address vs Virtual Address

컴퓨터 시스템의 메인 메모리(일반적으로 DRAM)는 byte 단위로 접근 가능한 하나의 연속적인 배열의 형태를 갖는다. 메인 메모리의 각 byte는 고유의 주소를 가지는데, 이를 physical address라고 한다. 예전의 컴퓨터 시스템은 CPU에서 physical address를 이용해 메모리에 접근했으며, 오늘날에도 MCU(마이크로컨트롤러)와 같은 임베디드 시스템에서는 physical address를 이용하기도 한다.

 

하지만, 최근 컴퓨터 시스템은 모두 CPU에서 virtual address를 사용하여 메모리에 접근하고, CPU chip에 함께 존재하는 Memory Management Unit(이하 MMU)라는 하드웨어에서 virtual address를 physical address로 바꿔주어 실제 메인 메모리는 physical address로 접근하는 구조를 갖는다. 이와 같은 virtual address에 대한 overview가 아래 그림에 잘 표현되어 있다.

출처: CSAPP 교재, FIgure 9.2

 

VM as a Tool of Caching

그렇다면 CPU에서 바로 physical address로 메모리에 접근하지 않고, virtual address를 도입해 한 단계 과정을 더 거치는 이유는 무엇인가? 여러 가지 이점이 있는데, 우선 첫 번째로는 메인 메모리가 하드 디스크의 캐시로서의 역할을 하는 것이다. Memory hierarchy에서 SRAM은 DRAM으로 이루어진 메인 메모리의 캐시 역할을 하여, 자주 사용되는 일부 정보들을 작지만 더 빠른 SRAM에 담아 두어 메모리 사용을 보다 효율적으로 만든다. 이와 비슷하게, 매우 큰 저장 용량을 갖는 하드 디스크의 일부 정보들을 메인 메모리에 캐시하여 사용하면 보다 효율적으로 메모리를 이용할 수 있게 된다.

 

Difference with SRAM cache

이 때, SRAM-DRAM과 DRAM-디스크의 차이점 중 하나는 디스크에 접근하는 데에 걸리는 시간이 상대적으로 더 크다는 것이다. 특히 디스크는 일련의 정보를 읽어오는 것보다 일단 한 번 읽기를 시도하는 데에 오랜 시간이 걸리는데, 이를 cache 관점에서 말하자면 miss penalty가 특히 더 크다는 것이다.

 

따라서, 접근 단위인 page는 4KB~2MB의 큰 크기를 갖고, fully associative 형태로 조직되어 있어 어느 virtual page든 어느 physical page에 대응될 수 있다. 또한, store 명령을 수행할 때 디스크에도 동시에 업데이트하는 write-through 방식을 사용하지 않고, 평소에는 메인 메모리에만 업데이트하다가 디스크로 replace될 때만 새로 쓴 정보를 업데이트하는 write-back 방식을 취한다.

 

참고로, 캐시에서 접근 단위를 block이라는 용어를 썼는데, virtual memory에서는 page라는 용어를 사용한다.

 

Page Table

메모리 접근 요청이 있을 때, 요청된 정보가 캐시에 있는지를 확인할 수 있어야 하는데, 여기서는 page table이 그 역할을 수행한다. Page table은 메인 메모리에 저장되어 있으며, virtual address를 physical address로 mapping 시킨다. 각각의 요소를 page table entry(이하 PTE)라고 하는데, 모든 virtual page마다 하나의 PTE에 대응된다.

 

PTE는 valid bit과 physical page number(이하 PPN)으로 구성된다. Valid bit은, 해당 virtual page가 현재 메인 메모리에 존재하는지의 여부를 표시한다. Virtual page는 메인 메모리에 존재하거나, 할당되었지만 디스크에만 존재하고 메인 메모리에 존재하지 않거나, 아예 할당되지 않았거나의 3가지 상태 중 하나이다. 만약 메인 메모리에 존재한다면, 메인 메모리의 physical page number를 가리키고, 디스크에 존재한다면 디스크의 위치를, 아예 할당되지 않은 경우 NULL 값을 갖는다.

출처: CSAPP 교재, FIgure 9.4

여기서 address, page number, page offset이라는 용어가 나오는데, address는 page number 부분과 offset 부분으로 나뉜다. 이들의 크기는 page size에 따라 정해지며, offset은 하나의 page 내에서 접근할 위치를 나타내는 것이다. Virtual address와 physical address 간에 page size는 같기 때문에, 일반적으로 address translation 과정에서 offset은 그대로 유지되고 address의 상위 bit인 virtual page number(이하 VPN)이 physical page number(이하 PPN)으로 바뀌는 것이라고 보면 된다.

When page fault occurs...

Cache miss에 대응되는 개념은 page fault이고, 이는 접근하고자 하는 메모리 주소의 정보가 메인 메모리에 없는 경우이다. 이 때 MMU는 요청된 virtual address에 대응되는 PTE를 참조하고, valid bit이 0인 것을 확인함으로써 page fault가 일어났음을 알게 된다. 그 후에는 page fault exception을 trigger하여, 제어 흐름을 kernel로 넘기게 된다. 그러면 kernel code는 메인 메모리에서 victim page를 골라서 디스크로 보내고, 디스크에서 새로운 page를 가져와 메인 메모리에 저장한다. 이 과정이 끝나면 다시 제어 흐름을 프로그램으로 돌려주는데, 이전의 faulting instruction부터 다시 실행한다. 이번에는 MMU에서 요청된 주소의 PTE를 참조했을 때 valid bit이 1일 것이기 때문에, exception 없이 메모리 접근 명령어를 실행할 수 있다.

 

참고로, C 라이브러리에는 현재 실행 중인 프로세스에서 자원들이 어떻게 사용되고 있는지를 monitor할 수 있는 getrusage() 함수가 있다.

#include <sys/times.h>
#include <sys/resource.h>

int who;
struct rusage usage;

/*
	Program code here
*/

getrusage(who, &usage);
printf("%ld\n", usage.ru_minflt);

링크: https://www.ibm.com/docs/en/aix/7.3?topic=g-getrusage-getrusage64-times-vtimes-subroutine 

getrusage, getrusage64, times, or vtimes Subroutine

 

VM as a Tool for Memory Management

VM의 이점 중 하나는 여러 개의 프로세스 간 메모리 관리가 용이하다는 것이다. 아래 그림과 같이, OS는 각 프로세스 별로 별도의 page table을 가지고 있고, 이를 통해 각 프로세스마다 하나의 독립적인 virtual address space를 제공할 수 있다.

출처: CSAPP 교재, Figure 9.9

프로세스들은 physical memory(메인 메모리)는 공유하기 때문에 위 그림처럼 서로 다른 프로세스에서 같은 메인 메모리 정보에 접근할 수 있다. 단, 각 프로세스마다 virtual address space가 다르기 때문에, CPU 입장에서 접근하는 virtual address는 다를 수 있다.

 

VM as a Tool for Memory Protection

VM은 OS가 메모리에 접근하는 권한을 제어하도록 한다. 예를 들어, user application에서 read-only 코드를 수정할 수 없으며, kernel의 데이터, 코드는 읽고 쓰기 모두 불가능하도록 해야 한다. 또한, 서로 다른 프로세스들 간에도 서로의 private한 메모리 공간을 접근할 수 없도록 해야 한다.

 

이에 대해 page table의 각 PTE에서 접근 권한을 나타내는 bit를 두는 방법을 사용할 수 있다. 아래 그림은 교재에서 예시를 든 것인데, SUP bit는 kernel mode 여부를 나타내며, 1인 경우 kernel에 대해서만 접근이 허용된다. 그렇지 않은 page에 대해서는 READ, WRITE이 각각 읽기, 쓰기에 대한 접근 권한을 나타낸다.

출처: CSAPP 교재, Figure 9.10

 

Address Translation

Address translation은 virtual address를 physical address로 바꾸는 과정이고, 이 때 page table을 참조하게 된다. Address를 좀 더 구체적으로 보자면, 위에서 언급한 바와 같이 page offset은 그대로 유지되기 때문에 address의 상위 bit인 VPN을 PPN으로 바꾸는 과정이 된다.

 

변환 과정을 살펴보도록 하자. 먼저, CPU에서 메모리 접근 명령어에 의해 virtual address로 MMU에 접근한다. MMU는 virtual address에 대한 PTE 주소 값을 계산하고, 메인 메모리로부터 PTE를 얻는다. 이 때, PTE의 base address 값은 PTBR이라고 하는 CPU control register 중 하나에 저장되어 있다. 만약 얻은 PTE의 valid bit이 1이라면 메인 메모리에서 해당 주소를 접근할 수 있다는 것이므로, PTE에 있는 PPN으로부터 PA를 얻어 메인 메모리 또는 캐시에 해당 주소로 접근하게 된다.

 

Page fault가 일어나는 경우, MMU가 PTE를 얻는 과정까지는 동일하지만, valid bit이 0인 것을 확인하기 때문에 여기서 exception을 trigger하여 kernel로 제어 흐름이 넘어가게 된다.

How about SRAM Cache?

SRAM 캐시는 virtual/physical address 중 어느 것으로 접근하느냐의 문제가 있는데, 이에 대한 여러 trade-off가 논의될 수 있다. 다만 교재에서는 자세히 다루지 않는데, 일반적으로는 physical addressing을 사용한다. 그러면 여러 프로세스 간 블록의 충돌 문제를 없앨 수 있으며, 캐시의 경우 정보를 캐시에 가져오기 전에 이미 접근 권한을 한 번 확인했을 것이므로 접근 권한 문제로부터도 자유로울 수 있기 때문이다.

 

TLB: Caching address translation

자주 사용되는 address translation에 대한 캐시를 만들면 이 과정을 더 빠르게 할 수 있는데, 이 캐시에 대해서는 Translation Lookaside Buffer(TLB)라는 별도의 이름이 붙어 있다. 여기에도 캐시에서와 마찬가지로 index와 tag bit 개념을 적용할 수 있으며, 여기서는 page offset을 제외한 VPN 부분이 index와 tag로 나뉘게 된다.

 

Multi-level Page Table

Virtual address space는 개념적으로 매우 크게 정의되는데, 그에 반해 프로그램에서 실제로 사용하는 메모리 공간을 훨씬 작을 수 있다. 그럼에도 page table은 모든 virtual page에 대해서 존재하게 되는데, 그러면 PT로 인한 추가적인 메모리 overhead가 너무 크다는 문제가 생긴다. 이를 multi-level page table을 통해 해결할 수 있다.

 

아래 그림은 교재에 소개된 Intel Core i7의 메모리 시스템이다. VPN이 총 36-bit인데, 9-bit씩 나누어서 page table이 4개의 hierarchical 구조로 되어 있다. 먼저, 상위 9-bit을 통해 첫 번째 계층의 PTE에 접근해 두 번째 계층에서 접근할 PT의 base address를 얻는다. 이 과정을 반복하다가 네 번째 계층에서 접근한 PTE에서는 비로소 PPN을 얻게 된다.

 

이렇게 하면 사용되지 않는 메모리 영역으로 인한 메모리 overhead를 낮출 수 있는데, 사용되지 않는 VPN에 대해서는 아예 하위 레벨의 PT가 할당되지 않기 때문이다. 

출처: CSAPP 교재, figure 9.22