[컴퓨터구조] Virtual Memory

Virtual Addressing

CPU에서 메모리의 데이터에 접근할 때, Physical address, 즉 메모리의 물리적 주소로 접근을 하게 되면 여러 가지 문제점이 발생한다.

먼저 물리적 메모리 크기를 벗어나는 프로그램의 작성 및 실행이 불가능하다. 또한 여러 개의 프로그램이 시스템에서 같이 실행되는 경우 메모리 관리를 하기가 매우 어려워진다. 이외에도 여러 문제점이 존재한다.

그래서 현대의 거의 모든 컴퓨터 시스템에서는 Virtual Addressing을 통해 메모리 접근이 이루어진다. CPU에서는 메모리의 가상 주소를 통해 모든 메모리 참조를 수행하고, Memory Management Unit(MMU)이 이를 시스템 상태에 맞추어 물리 주소로 바꾸고, 이 물리 주소를 이용해 실제 메모리 접근이 이루어진다. (일반적인 용어로 Indirection, 간접 참조를 수행한다고 말한다.)

VM as a Tool for Caching

개념적으로, 가상 메모리 (Virtual Memory)란 디스크에 저장된 바이트들의 배열을 의미한다. DRAM 등 메모리 장치에 저장된 내용은 이 가상 메모리에 대한 일종의 캐시로 볼 수 있는 것이다. 가상 메모리에서는 캐싱하는 데이터의 block 단위를 Page라고 부른다. 그래서 디스크의 데이터를 이루는 단위는 Virtual Page (VP), DRAM의 데이터를 이루는 단위는 Physical Page (PP)가 된다.

가상 메모리에 대한 DRAM 캐시는 Miss penalty가 매우 큰 캐시이다. 따라서 miss rate을 최소화하기 위해, page의 크기가 매우 크며 (4KB~4MB), fully-associative 캐시에 해당한다. 또한 Write-back 방식으로 데이터 업데이트가 이루어지는 캐시이다.

CPU가 이 page들에 접근할 수 있도록 하기 위해서, DRAM에 page table이라는 데이터 구조를 만들어 활용한다. Page table은 Page Table Entry(PTE)의 배열로, 각 VP에 해당하는 PP가 현재 DRAM에 올라와 있는지 여부(Valid bit), 그리고 올라와 있다면 그 PP의 주소가 무엇인지가 기록된 표이다. (* Page table 자체는 가상 주소가 아닌, Supervisor Page Table Base Register, SPTBR에 저장된 물리적 주소를 통해 접근할 수 있다.)

CPU가 요청한 가상 주소에 해당하는 PP의 주소가 Page Table에 존재하는 경우를 Page hit이라고 한다. (DRAM Cache hit이라고도 부를 수 있다.) 이와 반대로 PP 주소가 Page Table에 존재하지 않는 경우를 Page fault라고 한다.

Page fault가 발생한 경우, 원래 실행 중이던 프로세스는 exception을 발생시켜 멈추고 디스크에서 해당 VP를 메모리에 가져온 뒤 다시 프로세스를 실행한다. DRAM이 원래 PP로 꽉 차 있던 경우, DRAM에서 내보낼 PP를 결정해 내보낸다. 내보낼 PP는 주로 LRU와 유사한 정책으로 정한다.

가상 메모리는 (여느 캐시가 그렇듯) locality에 크게 의존한다. CPU는 프로그램을 실행하면서 일부 VP에만 집중적으로 접근하는 경향이 있다. 이러한 VP를 Working set이라 부른다. Working set의 크기가 메모리 장치 용량보다 작은 경우 가상 메모리는 잘 작동한다. 그러나 Working set의 크기가 메모리 장치 용량보다 크다면 Page fault가 빈번히 일어나 Thrashing이라는 심각한 성능 저하를 겪는다.

VM as a Tool for Memory Management & Protection

가상 메모리를 활용하면 여러 프로세스가 동시에 실행 중일 때 효과적으로 메모리를 관리할 수 있다. 각 프로세스마다 고유한 Virtual Address Space를 할당할 수 있기 때문에, 각 프로세스는 다른 프로세스와는 상관없이 자신의 가상 메모리 주소를 이용해 메모리에 접근하면 된다. 또한, 여러 프로세스의 VP를 공통적인 PP에 대응시킴으로써, 여러 프로세스에서 공통적으로 쓰이는 라이브러리의 linking 등을 효과적으로 수행할 수 있다.

또한 PTE에 valid bit와 PP 주소뿐만 아니라 해당 PP에 읽거나 쓸 수 있는지 등에 관한 permission 정보를 추가해 저장한다면, 매우 효과적인 메모리 보호 수단이 될 수 있다.

VM Address Translation

이제 MMU가 가상 주소를 물리 주소로 바꾸어 주는 과정을 자세히 살펴보자. 가상 주소는 VP number + Page offset, 물리주소는 PP number + Page offset으로 이루어져 있다. Page offset은 그대로이고, VP 번호만 Page Table에서 검색해 대응되는 PP 번호로 바꾸어 주면 된다. 그러나, Page Table의 크기가 매우 큰 경우에는 이러한 Translation이 한 cycle 안에 일어나기 어렵다. 이렇게 시간이 오래 걸리면 pipelining이 크게 지연되기 때문에 문제이다.

이 문제를 해결하기 위해 Page Table을 캐싱하는 방법을 생각해볼 수 있다. Translation Lookaside Buffer (TLB)는 하드웨어에 구현된 Page Table에 대한 캐시이다. 가상 주소는 VP number + Page offset이라고 했는데, 이는 다시 TLB tag + TLB index + Page offset으로 쪼개어 TLB에 접근하는 데 쓰이게 된다.

TLB Hit가 발생한 경우, 가상 메모리 주소를 물리 메모리 주소로 변환하는 데 메모리 접근이 필요하지 않게 된다. TLB Miss가 발생할 때만 메모리 속 PT에 접근하여 PTE를 읽어오게 된다. 그러나, 컴퓨터 프로그램의 Locality로 인해 TLB Miss는 자주 발생하지 않는다.

Multi-Level Page Tables

앞서 한 page의 크기는 4KB~4MB 정도라고 하였다. GB, TB 단위의 현대 메모리와 디스크 용량을 생각하면, Page Table에 저장된 PTE의 개수는 매우 커짐을 알 수 있다. PT가 너무 커지는 문제를 해결하기 위해, PT를 multi-level로 만드는 방법이 있다. Level 1 테이블의 PTE가 각각 서로 다른 Level 2 테이블을 가리키고, 각 Level 2 테이블에 page table이 구현되는 식이다.

multi-level page table에서 가상 메모리 주소는 다음과 같이 번역된다.

VP Number + Offset

= VPN 1 + VPN 2 + ... + VPN k + VP Offset

From CPU to Memory

Virtual addressing과 메모리 캐시를 종합하여 CPU가 메모리에 저장된 data word에 접근하는 방법을 정리해 보면 다음과 같다.

즉, Virtual address를 Physical address로 바꾼 후 그 주소를 이용해 L1, L2, L3, 메인 메모리 순으로 접근한다.

그런데, 여기에서 VPO와 PPO는 Page Offset인데, 이들은 서로 같아도 문제가 없다.

따라서 회로의 한쪽에서는 VPN을 PPN으로 번역하는 동안, 다른 한쪽에서는 VPO를 쪼개 얻은 CI와 CO를 이용해 캐시의 block을 탐색할 수 있다. 두 가지 작업을 동시에 수행하고, 두 작업이 끝나면 Cache Tag (즉, PPN)을 비교하여 Hit 여부를 판정하는 것이다. 이처럼 병렬적인 작업 수행을 통해 메모리 접근의 속도를 높일 수 있다.

References

1. D. Patterson, J. Hennessy (2021). Computer Organization and Design: RISC-V edition (2nd ed). Morgan Kaufmann.
2. Lecture Notes from SNU CSE Computer Architecture (김지홍 교수님 강의노트)