Chapter 9. Virtual Memory

Computer Systems : A Programmer’s Perspective (CSAPP)

시스템의 프로세스들은 다른 프로세스들과 CPU와 메인 메모리를 공유한다. 하지만 메인 메모리를 나눠 쓰려면 해결해야 할 문제가 있다. CPU의 부하가 늘면 프로세스는 점점 느려지고, 너무 많은 프로세스가 너무 많은 메모리를 요구하면 일부 프로세스는 작동하지 못하게 된다. 또한 메모리는 오염(corruption)에 취약하다. 어떤 프로세스가 실수로 다른 프로세스가 사용하는 메모리를 수정해버리면 그 프로세스는 자신의 프로그램과 전혀 관계 없는 이유로 정상적인 동작에 실패하게 된다.
메모리를 효율적으로 관리하고 에러를 줄이기 위해 현대 컴퓨터 시스템은 virtual memory 라는 메인 메모리의 추상적인 개념을 제공한다. 가상 메모리는 hardware exception, hardware address translation, 메인 메모리, 디스크 파일, 커널 소프트웨어의 명쾌하고 멋진 상호작용으로, 각 프로세스에게 넓고 일관된 자신만의 주소 공간(address space)를 제공한다. 가상 메모리라는 매커니즘 하나만으로 세 가지를 제공한다 :

1. 메인 메모리를 마치 디스크의 캐시(cache)로 취급해서 효율적으로 사용한다. 메인 메모리에는 사용 중인(active) 것만 저장하고 필요할 때만 디스크와 메모리 간에 데이터를 주고받는다.
2. 각 프로세스에게 동일한 주소 공간을 제공해서 메모리 관리를 단순화한다.
3. 각 프로세스의 주소 공간을 개인화함으로써 다른 프로세스에 의해 오염되는 것을 방지한다.

가상 메모리는 컴퓨터 시스템에서 가장 위대한 아이디어 중 하나이다. 조용하게 자동으로 작동하고, 응용 프로그램의 프로그래머의 간섭 없이 잘 작동한다. 무대 뒤에서 알아서 잘 일해주는데 왜 프로그래머가 그것을 이해해야 하는가? 여러 가지 이유가 있다.

• 가상 메모리는 핵심이다.
  가상 메모리는 컴퓨터의 모든 레벨에 녹아들어 있고 hardware exception, 어셈블러, 링커, loader, shared object, 파일, 프로세스의 디자인에서 핵심적인 역할을 한다. 가상 메모리를 이해해야 시스템이 돌아가는 것을 더 잘 이해할 수 있다.
  
• 가상 메모리는 강력하다.
  가상 메모리는 응용 프로그램이 메모리를 생성 및 소멸시키고, 디스크의 파일과 메모리를 짝짓고(map), 서로 다른 프로세스들이 메모리를 공유할 수 있는 강력한 도구가 된다. 예를 들어, 당신은 디스크 파일의 내용물을 단지 메모리의 어떤 곳을 읽고 쓰는 것으로 수정할 수 있다는 것을 알고 있었는가? 또, 명시적인 복사 없이도 메모리에 파일의 내용물을 로드해 올 수 있다는 것을 알고 있었는가? 가상 메모리를 이해하는 것은 당신의 응용 프로그램이 이러한 강력한 기능을 이용할 수 있도록 해 준다.
  
• 가상 메모리는 위험하다.
  응용 프로그램은 변수를 참조하고, 포인터를 역참조하고(주: 포인터 앞에 asterisk를 붙여서 해당 주소의 값을 읽는 것), malloc과 같은 동적 할당 함수를 사용할 때마다 가상 메모리와 상호작용한다. 가상 메모리를 부적절하게 사용하면 응용 프로그램은 모르는 사이에 발생한 무척 복잡한 메모리 관련 버그로 고통받게 된다. 다들 한번쯤은 segmentation fault, protection fault로 프로그램이 즉시 종료된 경험은 있을 것이고, 수 시간동안 문제 없이 돌아가다가 프로그램이 터지기도 하고 더욱 공포스러운 경우는 문제 없이 다 돌아갔는데 결과만 틀릴 때도 있다. 가상 메모리를 잘 이해하고, malloc과 같은 가상 메모리를 이용하는 함수를 잘 이해해야 이런 에러를 피할 수 있을 것이다.
  

이 장에서는 가상 메모리를 두 가지 각도에서 바라본다. 전반부에서는 가상 메모리가 어떻게 동작하는지 살펴본다. 후반부에서는 응용 프로그램이 가상 메모리를 어떻게 사용하고 관리하는지 살펴본다. 가상 메모리가 무척 복잡하다는 사실을 회피하지는 않을 것이고, 곳곳에서 이에 대한 논의를 통해 고찰할 것이다. 좋은 소식은, 당신이 이런 세부적인 부분을 모두 잘 익힌다면 직접 조그만 가상 메모리 매커니즘을 만들어 볼 수 있을 것다. 그러면 가상 메모리라는 아이디어는 더이상 신비 속의 존재가 아니게 될 것이다.

9.1 Physical and Virtual Addressing

컴퓨터에서 메인 메모리는 M개의 연속된 byte-size cell의 배열로 짜여 있다. 각 바이트는 고유한 physical address (PA)를 가진다. 이런 단순한 구성에서, CPU가 메인 메모리에 접근하는 가장 자연스로운 방법은 이 PA를 사용하는 것이다. 우리는 이런 접근 방법을 physical addressing 이라고 부른다. Physical address 4부터 시작해서 4바이트를 읽어 오라는 load instruction이 있다면 CPU가 memory bus로 물리 주소 4를 메모리에게 전달하고, 메인 메모리는 이를 받아서 물리 주소 4부터 4-바이트의 word를 fetch해서 CPU에게 보내주고, CPU는 이를 레지스터에 저장하게 된다.
초기의 컴퓨터는 이러한 physical addressing을 사용했고, 임베디드 마이크로컨트롤러나 디지털 신호 프로세서는 아직 이런 방식을 사용한다. 하지만 현대적인 프로세서는 이 방식이 아닌, virtual addressing 이라는 방식을 사용한다. 위 그림은 virtual addressing을 나타낸 그림이다. CPU는 물리 주소로 메모리에 접근하지 않고, virtual address (VA, 가상 주소)를 이용해 접근하게 된다. 가상 주소는 메모리에 가기 전에 적절한 물리 주소로 변환된다. 이런 변환 작업을 address translation 이라고 부르고, exception handling 때처럼 CPU 하드웨어와 운영 체제의 밀접한 협동을 필요로 한다. CPU 하드웨어 칩에서 memory management unit (MMU)라는 부분이 이를 전담하며, 운영체제가 내용을 관리하는 메모리의 lookup table을 보고 가상 주소에서 물리 주소로 변환해 준다.

9.2 Address Spaces

주소 공간은 음이 아닌 정수 주소의 ordered set이다.

{0, 1, 2, . . .}

만약 주소 공간의 정수들이 연속적이라면 우리는 이를 linear address space , 선형 주소공간이라고 부른다. 논의를 단순화하기 위해 항상 선형 주소공간을 가정한다. 가상 메모리가 있는 시스템에서는 CPU는 $N=2^n$ 개의 가상 주소공간을 생성한다.
주소 공간의 크기는 가장 큰 주소를 표현하기 위한 비트 수로 표현되는데, $N=2^n$ 개의 주소가 있는 가상 주소공간은 n-bit 공간이라고 불린다. 현대의 시스템은 보통 32-bit나 64-bit의 가상 주소공간을 지원한다.
시스템은 M바이트의 물리 주소공간도 가진다. M은 2의 지수일 필요는 없지만 편의를 위해 $M=2^n$개라고 가정한다.
주소 공간의 개념은 data object(바이트)와 그들의 attribute(주소)를 명확히 분리해 주기 때문에 중요하다. 이 구분을 인식하면 우리는 각 data object가 다른 주소 공간에서 선택된 여러 개의 독립된 다른 주소를 가지게 할 수 있다. 이것이 가상 메모리의 기본적인 아이디어다. 메인 메모리의 각 바이트는 가상 주소공간의 주소를 가지고, 물리 주소공간의 주소도 가지게 된다.

9.3 VM as a Tool for Caching

개념적으로, 가상 메모리는 디스크에 저장된 N개의 byte-size cell의 배열로 구성된다. 각 바이트는 배열에서의 index가 되는 고유한 가상 주소를 가지고, 내용은 메인 메모리에 cache된다. 메모리 계층 구조의 다른 캐시들과 동일하게 디스크와 메인 메모리 간에 데이터는 block 단위로 나뉘어서 전송된다. 가상 메모리는 크기가 $P=2^p$인 virtual pages (VP)라는 단위로 나뉘고(partitioned), 메인 메모리도 동일한 크기의 physical page (PP)로 나뉜다.
각 page는 세 가지 상태 중 하나에 속한다.

• Unallocated : 가상 메모리 시스템이 page에 무언가를 할당하지 않았거나 생성하지 않은 상태이다. 이 page와 연관된 데이터도 없고, 이 page가 디스크에서 차지하는 공간도 없다.
• Cached : 해당 VP는 현재 physical memory, 즉 메인 메모리에 cache되어 있다.
• Uncached : 해당 VP에 어떤 디스크의 주소가 할당되긴 했지만 해당 데이터는 메인 메모리에 cache되어있지 않다.

9.3.1 DRAM Cache Organization

지금 cache가 여러 종류 계속 등장하는데, SRAM과 DRAM을 확실히 구분하고자 한다.
SRAM 캐시는 CPU와 메인 메모리 간의 L1, L2, L3 캐시를 의미하고 DRAM 캐시는 가상 메모리와 메인 메모리 간의 캐시를 의미한다.
DRAM은 SRAM보다 10배 정도 느리고, 디스크는 DRAM보다 10만 배 느리기 때문에 DRAM 캐시의 miss는 SRAM 캐시의 miss보다 훨씬 중대하다. DRAM 캐시의 miss penalty가 압도적으로 크고 first byte의 접근 비용이 크기 때문에 virtual page는 4KB~2MB 정도로 꽤 크게 만든다. 또한 miss penalty가 크기 때문에 DRAM 캐시는 fully associative하고, replacement policy도 운영 체제를 동원해서 아주 정교하게 짜여져 있다. 마지막으로, 디스크에 한번 쓰고 읽기가 무척 오래 걸리기 때문에 write-through보다는 write-back 방법을 사용한다.

9.3.2 Page Tables

캐시를 사용하려면, 내가 찾고 있는 게 캐시되어 있는지 안 되어 있는지를 먼저 알아야 한다. 즉 가상 메모리는 어떤 virtual page가 DRAM에 캐시된 상태인지 아닌지를 알아내야 한다.
만약 있다면 해당 virtual page가 physical page의 어디에 캐시되어 있는지를 알아내야 하고, 없다면 disk의 어디에 들어 있는지를 알아낸 다음에 physical memory의 기존 page 중에서 replace할 victim page를 고르고 disk에서 불러온 page로 갈아 끼워야 한다.
이런 기능은 1. 운영 체제의 소프트웨어, 2. MMU(memory management unit) 안의 address translation hardware, 3. physical memory 안의 page table 이라는 자료 구조의 조합으로 제공된다. page table 은 가상 주소에서 물리 주소로의 map이 담긴 자료 구조이고, address translation hardware는 page table 의 내용을 읽어서 가상 주소를 물리 주소로 바꿔 주는 역할을 한다. 운영 체제는 page table 의 내용을 관리하고 디스크와 DRAM간의 page의 전송을 담당한다.

아래 그림은 page table의 기본적인 구조를 나타낸다.

Page table의 각 entry는 page table entry (PTE) 라고 부르고, 그 내용은 valid bit 과 address로 이루어져 있다.
Page table의 각 entry는 하나의 virtual page에 대응는데, entry의 valid bit 이 1이면 해당 virtual page가 DRAM에 캐시되어 있음을 뜻하고 entry의 나머지 내용은 DRAM에서 그 physical page의 주소이다. valid bit 이 0인 경우 entry의 나머지 내용이 null이면 해당 virtual page가 할당되지 않았음을 뜻하고, null이 아니면 entry의 나머지 내용은 disk에서 해당 virtual page의 주소이다.

9.3.3 Page Hits

CPU가 가상 주소 VP2를 읽으려고 하면 address translation hardware는 table에서 VP2에 해당하는 2번 entry(왼쪽 초록색)의 내용을 읽는다(VP2에 해당하는 게 2번 entry인 것을 어떻게 알았는지는 9.6절에서 다룬다). entry의 내용을 보니 valid bit 은 1이므로 이 page는 DRAM에 캐시되어 있고, 그 물리 주소는 entry의 나머지 부분이다. 그 주소는 physical page 2(PP2, 오른쪽 초록색)를 향해 있고 CPU는 그곳에 담겨 있는 원하던 정보를 얻게 된다.

9.3.4 Page Faults

CPU가 VP3을 읽으려고 하면 address translation hardware는 table에서 VP3에 해당하는 3번 entry(왼쪽 빨간색)의 내용을 읽는다. entry의 내용을 보니 valid bit 가 0이므로 이 page는 DRAM에 캐시되어 있지 않다. 그리고 나머지 내용이 null이 아니니 disk에서의 주소를 의미한다.
여기서 page fault exception을 일으키고, 커널의 page fault handler가 작동한다. Handler는 DRAM의 page들 중에서 교체될 victim을 고른다. DRAM의 3번 entry(주황색)가 선택됐다고 하면, 만약 이 데이터가 캐시된 이후 수정된 적이 있으면 디스크에 복사해 준다.
한편으로는 VP3에 해당하는 디스크의 주소를 page table에서 얻었으니 디스크에서 그 page를 불러온다. 디스크에서 불러온 데이터를 DRAM의 3번 entry에 복사한 다음 page table의 내용도 알맞게 수정한다. 이제 page table의 3번 entry는 valid bit 가 1, address는 DRAM의 3번 entry의 주소가 되었다. 결과는 아래 그림과 같다. 변경이 있는 부분은 파란색 사각형이다.

가상 메모리는 1960년대 초에 고안되었는데 이 때는 SRAM같은 게 있기 훨씬 전이라 CPU와 메모리의 gap이 덜했을 때이다. 그래서 SRAM과 뜻은 비슷한데 다른 용어들을 쓴다. 캐시에서는 block이라고 부르는 것을 가상 메모리에서는 page라고 부르고, 디스크와 메모리 간 page의 전송은 paging 과 swapping 이라고 부른다.

9.3.5 Allocating Pages

malloc과 같은 함수를 이용하면 운영 체제는 가상 메모리에 새 공간을 만든다. 즉, entry 중에 null이었던 것을 하나 골라서 disk의 어떤 페이지 주소를 넣어 준다.

9.3.6 Locality to the Rescue Again

처음 가상 메모리를 배울 때 드는 생각은 무척 비효율적이라는 것이다. 하지만 locality 덕분에 가상 메모리는 잘 돌아간다.
DRAM(physical memory)는 disk(virtual memory)보다 훨씬 작지만 locality로 인해, 한 번 page를 불러 오면 추후의 작업은 대부분 그 page 내의 정보만을 필요로 한다. 그렇지 않은 프로그램의 경우 DRAM의 반복적으로 disk에서 불러오게 되는 thrashing 이 일어나기 때문에 프로그램을 현명하게 잘 짜야 한다.

9.6 Address Translation

9.4절과 9.5절은 잠시 미뤄 놓고, address translation을 보자. 이 절에서는 가상 메모리의 동작에서 하드웨어의 역할을 살펴본다. 주의할 점은, 여기서는 timing과 같이 하드웨어 디자이너들에게는 무척 중요한 요소를 생략하고 다루지 않는다는 것이다.

Symbol	Description
Basic parameters
$N=2^n$	가상 주소공간의 주소 수
$M=2^m$	물리 주소공간의 주소 수
$P=2^p$	page의 크기(바이트)
가상 주소(VA) 관련
VPO	Virtual page offset(바이트)
VPN	Virtual page number
TLBI	TLB index
TLBT	TLB tag
물리 주소(PA) 관련
PPO	Physical page offset(바이트)
PPN	Physical page number
CO	byte offset within cache block
CI	Cache index
CT	Cache tag

이 절에서 사용할 기호들이 위 표에 정리되어 있다.
딱딱하게 표현하면, address translation은 가상 주소공간의 N개 element에서 물리 주소공간의 M개 element로 가는 함수이다.

MAP : VAS $\rightarrow$ PAS $\cup$ $\emptyset$

MAP(A) =

$\begin{cases} A^{‘} & \text{해당 데이터가 물리 주소에 있을 경우}
\emptyset & \text{해당 데이터가 물리 주소에 없는 경우}
\end{cases}$

앞 절에서는 address translation hardware가 page table에서 가상 주소를 보고 해당하는 DRAM의 주소 혹은 disk의 주소를 찾는다고 했다. 자세하게 어떤 방식으로 찾는 지 살펴본다.

앞서 봤던 n비트의 가상 주소는 두 부분으로 나눌 수 있다.

• LSB $p$비트는 virtual page offset (VPO)이다. 각 페이지는 $P=2^p$개의 바이트로 되어 있기 때문에 같은 page의 바이트들은 LSB $p$비트가 같다. 이동하는 모든 데이터의 기본 단위가 page이기 때문에, LSB $p$비트는 offset이 된다.
  
• 나머지 MSB $(n-p)$비트는 virtual page number (VPN)이다. 가상 메모리에는 총 $2^{(n-p)}$개의 페이지가 있으므로 모든 페이지는 $(n-p)$비트로 고유하게 나타낼 수 있다.
  
  Page table에서 각 entry는 각 page와 대응되고, VPN을 index 삼아 table에서 정보를 찾을 수 있다. MMU는 가상 주소를 받아서, MSB $(n-p)$비트인 VPN을 index 삼아 page table의 적절한 entry의 내용을 읽는다. 그것이 바로 physical page number(PPN)이고, $(m-p)$비트 PPN에 $p$비트 VPO를 붙여서 최종적으로 $m$비트의 물리 주소(PA)를 얻게 된다.
  
  

그리고 DRAM에서 page table의 시작 주소는 CPU에 있는 page table base register (PTBR) 이라는 특별한 레지스터에 들어 있다.

Page hit의 경우의 하드웨어들의 동작이 위 그림에 나타나 있다.

• Step 1: CPU는 원하는 데이터의 virtual address를 MMU에게 전달한다.
• Step 2: MMU는 전달받은 VA에서 MSB를 떼 내서 VPN을 만들고, page Table Entry Address(PTEA)로 쓰라고 cache/main memory에게 전달한다.
• Step 3: Cache/main memory는 전달받은 PTEA를 이용해 page table에서 알맞은 entry를 찾아서 읽고, page Table Entry(PTE)를 MMU에게 전달한다.
• Step 4: MMU는 PTE의 valid bit 등을 확인한 후, PPN을 추출하고 VPO를 붙여서 물리 주소(PA)를 완성하고 cache/main memory에게 전달한다.
• Step 5: Cache/main memory는 전달받은 물리 주소로 data word를 읽어서 CPU에게 전달한다.

이와 같이 page hit의 경우 하드웨어만으로 CPU가 원하는 데이터를 읽어올 수 있다. 하지만 page fault의 경우 아래 그림과 같이 운영체제의 커널이 필요하다.

• Step 1~3: page hit의 경우와 동일
• Step 4: MMU가 전달받은 PTE의 valid bit을 확인했더니 0이다. Exception을 발동시키고, control은 커널의 page fault exception handler에게 넘어간다.
• Step 5: 커널은 physical memory에서 새 page와 교체될 victim page를 선정하고, victim page가 DRAM에서 수정됐을 경우 디스크에 복사한다.
• Step 6: 디스크에서 불러온 새 page를 physical memory에 써 넣고, page table의 PTE를 업데이트한다.
• Step 7: Control이 fault를 일으킨 instruction으로 돌아오고 다시 수행된다. 이번에는 page hit이 일어나서 CPU에게 원하는 데이터가 전달된다.

9.6.1 Integrating Caches and VM

가상 메모리와 SRAM 캐시를 모두 쓰는 시스템에서는 SRAM 캐시에 접근할 때 가상 주소를 쓸지 물리 주소를 쓸지 고민해야 한다. 상세한 논의를 거쳐서 나온 결론으로, 대부분의 시스템은 SRAM 캐시에는 physical addressing을 사용한다. Physical addressing을 써서 여러 프로세스들이 동시에 캐시에서 block을 가지고 같은 가상 페이지의 block을 공유하도록 하는 것이 명쾌하다. 또한 cache에 접근 권한은 앞의 address translation 과정에서 체크가 되기 때문에 protection issue를 고려하지 않아도 된다. 아래 그림은 MMU와 메인 메모리 사이에 L1 cache가 추가된 것을 나타낸다.

9.6.2 Speeding Up Address Translation witha TLB

앞 절에서 보았듯, CPU가 virtual address를 만들어서 접근할 때마다 MMU는 cache/main memory에 있는 page table을 참조해서 가상 주소를 물리 주소로 변환해야 한다. L1 캐시에서 hit이 나면 몇 사이클 수준의 손해가 있고, 운 없이 L1 캐시를 넘어 메모리까지 찾으러 간다면 수백 사이클의 손해를 볼 수 있다.
많은 시스템에서는 MMU 내에 또다른 cache를 운용해서 이 비용조차 줄이고자 한다. 이것을 우리는 translation lookaside buffer (TLB)라고 부른다.

TLB는 가상-주소화된 작은 cache로, 각 line은 PTE 하나를 담은 block이다. TLB는 보통 높은 associativity로 구현되는데, $T=2^t$개 set로 구성된다면 VPN의 LSB $t$비트는 TLBI(TLB index)로 사용되고 나머지 MSB부분이 TLBT(TLB tag)로 사용된다. 아래 그림과 같다.

TLB hit이 날 경우 CPU와 메모리의 동작은 아래 그림과 같다.

• Step 1: CPU가 가상 주소를 생성해서 MMU에게 전달한다.
• Step 2: MMU는 VA에서 VPN만 떼서 TLB에게 전달한다.
• Step 3: TLB는 해당 VPN의 PTE을 찾아서 MMU에게 반환한다.
• Step 4: PTE의 valid bit 등을 확인한 후 PPN에 VPO를 붙여 PA를 만들고, cache/memory에게 전달한다.
• Step 5: Cache/memory는 해당 PA의 data를 CPU에게 전달한다.

TLB miss가 날 경우, TLB와 MMU가 소통하는 과정만 중간에 추가되고 나머지는 TLB가 없을 때와 동일하다.

위와 같은 TLB miss에서 MMU가 cache/memory의 page table에서 PTE를 받아오면 이 값은 TLB에 새로 저장된다. 아마 이때 TLB의 어떤 victim이 overwrite될 수도 있겠다.

9.6.3 Multi-Level Page Tables

지금까지는 시스템이 address translation을 위해 딱 한개의 page table을 사용했다. 하지만 single page table은 무슨 문제점이 있는지 32-bit 시스템의 예시로 살펴보자.

Page size는 4KB(=$2^{12}$)라고 하고, PTE 하나는 4바이트라고 하자. 그러면 page table entry의 개수는 $2^{(32-12)}=2^{20} =$ 1M이고, 따라서 page table의 크기는 4MB가 된다. 응용 프로그램이 아주아주 조금의 가상 주소공간을 사용해도 메모리에 4MB가 고정으로 박혀 있는 것이다. 64-bit 시스템으로 계산해보면 page table의 크기가 페타바이트 단위로 어마어마하게 커진다.
Page table을 압축하기 위해서 우리는 page table에도 계층 구조를 적용한다. 구체적인 예시를 통해 살펴보자.

이렇게 생긴 32비트 가상 주소공간을 생각해 보자. 첫 2K개 page에는 코드와 데이터가 할당되어 있고, 다음 6K개 page는 미할당되어 있고, 그 다음 1023개 page는 미할당되어 있고 그 다음 한 page에 user stack이 할당되어 있다. 그 이후로는 쭉 미할당이다. Page 하나의 크기는 4KB이고 PTE는 4바이트인 것은 동일하다. 이 가상 주소공간에 2-level page table을 만들어 보자.

Level 1 page table에는 1K(=$2^{10}$)개의 entry(PTE)가 있다. 각 entry는 가상 주소공간의 4MB(=$2^{22}$바이트) 덩어리를 담당한다(총 $2^{(22+10)}=2^{32}$=4GB). 우리의 가상 주소공간은 32비트라서 $2^{32}$=4GB의 크기를 가지니까 딱 맞다.

가상 주소공간의 각 4MB 덩어리는 1024개의 page들로 되어 있는데, 만약 어떤 덩어리의 1024개 page들이 전부 미할당 상태라면 level 1 page table에서 해당 덩어리를 담당하는 entry는 null이다. 1024개 page 중에 하나라도 할당되어 있다면 그 entry는 어떤 level 2 page table을 가리키게 된다.

Level 2 page table에도 1K(=$2^{10}$)개의 entry(PTE)가 있다. 각 entry는 이제 가상 주소공간의 4KB, 즉 한 page를 담당하므로 single-level page table과 동일한 경우가 된다. 하지만 page table의 크기는 single에 비해 아주 작은데, $2^{(10+2)} = 2^{12} =$ 4KB밖에 되지 않는다. 마침 page와 크기가 같아 편리하다.

이 방법은 메모리 요구량을 두 가지 방법으로 줄이게 된다. 첫 번째로, level 1 page table의 PTE가 null이 되면 level 2 page table은 아예 존재하지도 않게 된다. 4GB 가상 주소공간의 대부분은 일반적으로 미할당 상태이므로, 이는 엄청난 절약이 된다. 두 번째로, 메인 메모리에 있어야 하는 건 level 1 page table뿐이다. Level 2 page table은 가상메모리 시스템으로 만들고 필요할때 page로 가져오면 되므로 메인 메모리의 부담을 덜 수 있다. 아주 자주 쓰이는 level 2 page table만 cache해놓으면 된다.

위 그림은 2-level page table을 전체적으로 나타낸 것이다. 가상 주소공간에 현재 뭔가 들어있는 덩어리는 첫 번째와 두 번째, 그리고 여덟 번째 덩어리이다. 따라서 level 1 page table의 1024개 entry 중에 3개를 제외한 나머지는 모두 null이고, 그 세 개의 entry에만 어떤 level 2 page table의 시작 주소가 들어 있다.
각 level 2 page table의 entry에는 가상 메모리의 어떤 page의 PPN과 같은 정보가 있을 것이다. 규모만 4MB로 줄었지, single level page table과 동일하게 작동한다.

한 걸음 더 나아가서 multi-level page table도 만들 수 있다. k-level page table을 쓰면 가상 주소를 k개의 VPN과 한 개의 VPO로 분할하게 된다. i번째 VPN 조각은 i번째 page table의 index로 사용되고, i번째 page table의 각 entry는 (i+1)번째 page table의 주소를 담고 있게 된다.
따라서 CPU가 어떤 가상 주소에 접근하려면 k개의 page table을 모두 거쳐야 한다. 이는 무척 비효율적으로 보이지만, 우리에게는 TLB가 있다. 그래서 일반적으로 multi-level page table은 single-level보다 그렇게 크게 느리진 않다. 메모리는 대신 엄청나게 줄이므로 쓸 만 하다고 할 수 있다.
위에서 32-bit 시스템의 2-level page table은 page table 하나의 크기가 page의 크기인 4KB라서 편리하다고 했다. 그러면 64-bit 시스템에서 한 page table가 page 하나(4KB) 크기가 되게 하려면 몇 레벨로 page table을 짜야 할까?
각 PTE는 4바이트이니 page table 하나당 1024개의 entry가 있다. 즉 page table 하나당 10비트의 VPN을 담당하게 되므로 $(64-12)/10 = 5.2$, 즉 6 level의 page table이 필요하다.

9.6.4 Putting It Together: End-to-End Address Translation

이제 구체적인 예시를 이용해서 처음부터 끝까지 address translation 과정을 따라가 본다. 한 눈에 보기 쉽도록 조금 작은 시스템을 가정해 보자.

• 메모리는 byte-addressable하다. (기존과 동일)
• 메모리 접근은 1-byte word 단위로 한다. (원래 word는 4-byte)
• 가상 주소는 14-bit이다. ($n=14$)
• 물리 주소는 12-bit이다. ($m=12$)
• page size는 64바이트이다. ($P=64=2^6, p=6$)
• TLB는 4-way associative이고, 전체 entry는 16개이다.
• L1 d-cache는 물리 주소로 되어 있고 direct mapped이다. 한 line은 4-byte이고 16개 set으로 되어 있다.

VA와 PA의 비트 구성은 위 그림과 같다.
page size가 $2^6$비트이니 VPO와 PPO는 6비트이고, VPN과 PPN은 각각 8비와 6비트가 된다.

위 그림은 page table의 일부이다. 각 entry에는 valid bit와 PPN이 들어 있다.

TLB는 위 그림과 같다. 4-way associative이니 VPN의 LSB 2비트가 TLBI이고 나머지 6비트가 TLBT가 된다.
MMU가 VPN을 TLB에게 전달하면 TLB는 2비트 index에 맞는 set에 가서 6비트 tag가 일치하는 entry가 있는지 쭉 탐색할 것이다.

cache는 위 그림과 같다. 한 line이 4바이트이니 PA의 LSB 2비트는 CO이고, 16개 set으로 되어 있으니 그다음 LSB 4비트는 CI가 된다. 나머지 6비트는 CT로 쓰이고 PPN과 일치한다.

이렇게 초기 세팅을 해놓고 CPU가 가상주소 0x0d34를 읽는 과정을 따라가보자. 우선 하드웨어가 읽는 것처럼 16진수 주소를 비트로 분석해본다.

가장 먼저 MMU가 VPN을 뽑아서 TLB에게 보낸다(0 0 0 0 1 1 1 1). TLB는 VPN에서 TLBI를 확인하고(1 1), TLB의 3번 set의 entry 중에 TLBT(0 0 0 0 1 1)가 일치하는 것을 찾는다(위 그림의 초록색 사각형). PPN이 0x0D로 TLB hit이 발생했으므로 MMU는 PPN과 VPO를 합쳐서 0 0 1 1 0 1 0 1 0 1 0 0 또는 0x354 라는 PA를 만들어서 cache로 보낸다.
cache는 PA에서 CI(0 1 0 1)를 보고, 5번 line를 살펴본다. 5번 line에서 CO(0 0), 즉 0번째 word는 0x36이다(빨간 사각형). cache hit가 났으므로 이 data word는 CPU로 전달된다.
TLB miss가 났다면 MMU는 VPN을 page table에게 보내서 PPN을 얻어올 것이고, cache miss가 났다면 exception handler가 작동해서 disk에서 data word를 불러왔을 것이다.

9.7 Case Study: The Intel Core i7/Linux Memory System

가상 메모리 매커니즘에 대한 논의는 실제 시스템(리눅스 운영체제의 Intel Core i7)의 사례 연구로 마무리한다.
마이크로아키텍쳐 Haswell은 full 64-bit 가상&물리 주소공간을 허용하긴 하지만, 현재 Core i7은 48-bit(256TB)의 가상 주소공간과 52-bit(4PB)의 물리 주소공간을 지원한다.

가장 바깥 점선(processor package)이 CPU chip이다. 4개의 코어(실선 부분)로 되어 있고, 모든 코어가 공통으로 갖는 L3 cache와 DDR3 memory controller가 있다. 각 코어는 data와 instruction을 따로 해서 레지스터와 L1 cache가 상위에 있고, L2 cache는 data와 instruction 공통으로 되어 있다. MMU 역시 data와 instruction 따로 L1 TLB를 가지고, L2 TLB는 공통이다.

address translation 과정을 전체적으로 나타낸 그림이다.

1. CPU가 생성한 VA는 48비트이다. MSB 36비트는 VPN, LSB 12비트는 VPO이다.
2. MMU는 VPN을 우선 TLB로 보낸다. L1 TLB는 16(=$2^4$)set로 되어 있으므로 48비트 중 LSB 4비트가 TLBI이다. 해당 set의 entry 중 32비트 TLBT와 일치하는 것이 있다면 TLB hit가 되고, PPN을 얻게 된다.
   그런 entry가 없다면 TLB miss이다. MMU는 VPN을 cache/main memory에 있는 page table로 보낸다. Core i7은 VPN을 4등분해서 page table이 각각 9비트씩 담당하는 4-level page table을 사용한다. 따라서 4단계의 탐색을 통해 PPN을 얻게 된다.
   Page table에서 해당 VP의 valid bit이 0이면, page fault handler가 동작한다. 그림에는 나와있지 않다.
3. MMU는 이렇게 얻은 PPN을 VPO와 합쳐서 PA를 생성하고, 먼저 L1 cache를 찾아본다. L1 d-cache는 64-set(CI=6비트)에 set당 line이 8개(즉, 8-way associative)이고 한 block은 64바이트(=$2^6$, CO=6비트)이다. CI로 몇 번 set인지 찾아가서 8개 entry 중에 40비트 CT와 일치하는 게 있다면 L1 hit이고, 그 line의 CO번째 byte를 읽어 오게 된다.
   CT와 일치하는 게 없다면 메인 메모리로 찾으러 간다. PA에 해당하는 데이터를 읽어 와서 CPU에게 전달한다.

9.7.1 Core i7 Address Translation

Core i7은 4-level page table을 사용하고 각 프로세스는 자신만의 page table hierarchy를 갖는다. 리눅스 프로세스가 실행 중이면 해당 프로세스의 page table에서 할당된 page들은 메모리 상에 존재하지만, Core i7 아키텍처는 page table들이 swapped in&out 될 수 있도록 한다(주: swapping은 디스크<->메모리 간 page의 전송을 뜻함). 위 그림의 CR3 control register는 L1 page table의 시작 주소를 가지고 있는데, 이 값은 process context로써 관리되고 context switch때마다 바뀐다.