Virtual Memory: Introduction to Virtual Memory

What is Virtual Memory?

매우 단순한 임베디드 시스템과 초기 컴퓨터에서는 프로세스가 메모리에 직접 접근했습니다. 예를 들어, 주소 1234는 특정한 physical memory에 저장되어 있는 특정한 바이트를 의미했습니다. 

현대 시스템에서는 더 이상 이런 방법을 사용하지 않습니다. 대신 각각의 프로세스는 분리되어 있어서, 특정한 CPU instruction이나 프로세스의 데이터의 주소와 실제 Physical memory(RAM)이 전환되는 프로세스가 필요합니다. 메모리 주소는 더 이상 실제가 아닙니다. 프로세스는 가상 메모리 안에서 동작합니다. 가상 메모리는 프로세스를 안전하게 지킬 뿐만 아니라(왜냐하면, 프로세스가 다른 프로세스의 메모리를 직접적으로 읽거나 수정할 수 없기 때문입니다), 시스템이 각각 다른 프로세스들에게 메모리를 효율적으로 할당하거나 재할당 할 수 있게 해줍니다.

What is MMU?

MMU(Memory Management Unit)은 CPU의 한 부분입니다. MMU는 가상 메모리 주소를 Physical memory 주소로 변환해 줍니다. 또한 MMU는 현재 특정한 가상 메모리와 physical memory가 매칭되어 있지 않거나 현재 CPU instruction이  read-access만 가지고 있는 프로세스에 쓰려고 시도할 때 interrupt됩니다.

So how do we convert a virtual address into a physical address?

32비트 머신을 가지고 생각해봅시다. 포인터는 32bit를 저장할 수 있습니다. 즉, 포인터는 2^32의 주소를 가질 수 있고 그 주소가 1 바이트를 가리킨다고 할 때 4GB의 메모리를 가리킬 수 있습니다.

메모리에 저장되어 있는 큰 표를 하나 생각해봅시다. 이 표에 Physical address에 저장 가능한 모든 주소(4^30)를 담을 것입니다. 각각의 physical address는 4바이트를 필요로 합니다.  이 모든 것을 저장하려면 16^30바이트가 필요합니다. 이런 방식은 모든 메모리를 소모할 것입니다. 

lookup table은 메모리보다 작아야 실제 프로그램과 OS data가 사용할 메모리가 남을 것입니다. 

이러한 문제점은 메모리를 page라고 불리는 작은 영역으로 나누고 각각의 page를 탐색하기 위해 frame을 사용하는 것으로 해결할 수 있습니다.

What is a page? How many of them are there?

페이지는 가상 메모리의 블록입니다. 더 큰 블록을 사용하는 예도 있지만 리눅스 OS에서 일반적으로 block size는 4KB(2^12 addresses)입니다. 

각각의 바이트 대신에 page라고 불리는 4KB 블록을 사용합니다.  각각의 페이지에는 page 0, page 1등과 같이 넘버링을 합니다.

EX: How many pages are there in a 32bit machine(assume page size of 4KB)?

전체 주소의 수는 2^32개이고, 하나의 페이지는 2^12이므로, 총 페이지의 수는 2^20개 입니다.

2^10이 1024이므로, 2^20은 백만을 조금 넘습니다.

만약 64bit machine이라면, 2^64 / 2^12 이므로 2^52개의 페이지가 있습니다.

What is a frame?

프레임(페이지 프레임이라고 부르기도 함)은 physical memory나 RAM의 블록입니다. 이러한 메모리는 때때로 primary storage라고 불립니다.

프레임은 가상 페이지와 같은 크기의 바이트를 가지고 있습니다. 만약 32bit machine이 4GB의 RAM을 가지고 있다면, 같은 숫자의 접근 가능한 공간을 가지고 있을 것입니다. 

What is a page table and how big is it?

페이지 테이블은 페이지와 프레임을 매핑합니다. 예를 들어 page 1이 프레임 45와 매핑되고, page 2가 프레임 30과 매핑되는 것처럼 말입니다. 다른 프레임들은 현재 사용되지 않거나 다른 동작중인 프로세스에 할당되거나, OS 내부적으로 사용됩니다.

단순한 페이지 테이블은 배열입니다. int frame = table [ page_num]과 같은 방식입니다.

4KB 페이지를 가진 32비트 머신에서 각각의 엔트리는 프레임 번호를 가지고 있습니다. 즉, 2^20개의 프레임을 계산해야 하기 때문에 엔트리에는 20비트(2.5바이트)가 필요합니다. 실제로는 엔트리당 4 바이트를 사용해 여분의 비트는 다른 사용처를 찾습니다. 각각의 엔트리에 4바이트가 필요하고, 엔트리는 2^20개가 필요하므로 페이지 테이블을 저장하기 위해 실제로 필요한 physical memory는 4*2^20 = 4MB입니다. 

4KB 페이지를 가진 64비트 머신에서는 각각의 엔트리는 52bit가 필요합니다. 52비트를 8바이트로 올림해서 사용할 때, 2^52개의 엔트리가 8바이트를 사용하므로 페이지 테이블은 2^55만큼의 크기를 필요로 합니다. 이 크기는 너무 큽니다.

그러므로 64비트 구조에서 메모리 주소는 드물기 때문에, 대부분의 엔트리가 사용되지 않는다고

가정하고 페이지 테이블 크기를 줄이는 메커니즘이 필요합니다.

위에 보이는 페이지 테이블이 그 예입니다. array에 접근하여 그 array의 원소를 찾는 것을 생각해보세요.

What is the offset and how is it used?

페이지 테이블가 페이지와 프레임을 매핑한다는 것을 기억하세요. 각각의 페이지는 연속된 메모리의 블록입니다. 특정한 프레임 안에 사용한 특정한 바이트를 어떻게 계산할 수 있을까요? 해결책은 가상 메모리 주소의 낮은 비트들을 직접적으로 재사용하는 것입니다. 예를 들어, 프로세스가 

VirtualAddress = 11110000111100001111000010101010(binary)를 읽어왔을 때,

페이지 사이즈가 256byte라면 아래의 8비트, 즉 (1010101010)은 offset으로써 사용됩니다. 나머지 위의 111100001111000011110000은 page number입니다.

Multi-level page tables

multi-level page table은 64비트 아키텍쳐의 페이지 테이블 사이즈를 해결하기 위한 방법 중에 하나입니다. 이를 위한 가장 간단한 구현인 two level page table을 살펴보겠습니다.

각각의 테이블은 다음 레벨의 테이블을 가리키는 포인터의 테이블입니다. 모든 sub-table이 존재할 필요는 없습니다. 다음은 32비트 아키텍쳐의 two level page table입니다.

VirtualAddress = 11110000111111110000000010101010 (binary)
                 |_Index1_||        ||          | 10 bit Directory index
                           |_Index2_||          | 10 bit Sub-table index
                                     |__________| 12 bit offset (passed directly to RAM)

위의 이론대로라면 frame number를 결정하는 데 두 번의 memory read가 필요합니다. 상위 10 비트가 페이지 테이블 디렉토리에 사용됩니다. 만약 각각의 엔트리에 2byte가 사용된다면, 디렉토리 전부를 저장하는데 2KB만이 사용됩니다. 각각의 서브테이블은 physical frame을 가리킵니다(즉, 20 비트를 저장하기 위해 4바이트가 필요합니다). 하지만 적은 메모리만을 필요로 하는 프로세스들에게는 낮은 메모리 주소(Heap과 프로그램 코드를 위해)와 높은 메모리 주소(스택을 위해)를 특정하는 엔트리만이 필요합니다. 1024개의 엔트리와 각각 엔트리당 4바이트를 할당해서 4KB가 적당합니다.

그러므로 multi-level page table에서 총 메모리 오버헤드는 4MB(레벨이 1인 구현)에서 3 프레임의 메모리(12KB)로 줄어듭니다. 3 프레임이 필요한 이유는 한 프레임을 높은 레벨 디렉토리에 사용하고 나머지 두개의 프레임을 두 sub-table에 사용해야 하기 때문입니다. sub-table 하나는 낮은 주소를 위해 사용하고(프로그램 코드, 상수, 힙), 다른 하나는 스택과 environment에 사용되는 높은 주소를 위해 사용합니다. 실제로 프로그램은 더 많은 sub-table entry를 필요로 하기도 하는데, 각각의 subtable의 적당한 크기는 4MB의 메모리 공간입니다. 하지만 중요한 점은 페이지 테이블을 찾는데 필요한 메모리 오버헤드가 확실히 줄어든다는 것입니다.

Do page tables make memory access slower?(And what's a TLB)

똑똑한 하드웨어 덕분에 보통은 그렇지 않지만, 확실히 page table은 메모리에서 직접적으로 읽거나 쓰는 것에 비해 메모리 접근을 더 느리게 만듭니다.  1개의 페이지 테이블에서이 메커니즘은 두 배만큼 느려집니다.(두 번의 메모리 접근이 필요하기 때문) two-level page table의 경우, 메모리 접근이 3번 필요하므로 3배만큼 느려집니다.

이러한 overhead를 극복하기 위해서 MMU는 최근 사용된 가상페이지-프레임 참조를 위한 associative cache를 포함하고 있습니다. 이 캐시는 TLB(Translation Lookaside Buffer)라고 불립니다.가상 메모리가 physical memory로 매칭될 때, TBL는 페이지 테이블에 병렬적으로 쿼리합니다. 대부분의 프로그램의 대다수의 메모리 접근에서 TLB가 결과를 저장하는 중요한 기회가 있습니다. 하지만 만약 프로그램이 좋은 cache coherence를 가지지 못한다면(예를 들면, 많은 다른 페이지의 random memory location에서 읽어오는 경우), TLB는 결과 캐시를 가지지 못하므로 MMU는 physical frame을 결정하기 위해 훨씬 더 느린 페이지 테이블을 사용해야 합니다.

위 그림은 multi-level page table을 어떻게 나누는지 보여줍니다.