가상화 - 메모리 가상화 : 더 작은 페이지 테이블

페이징의 두 번째 문제점은 페이지 테이블의 크기이다. 페이지 테이블이 크면 많은 메모리 공간을 차지한다.

앞선 예와 같이 페이지 크기가 4KB이고, 배열 형태를 가지는 선형 페이지 테이블의 각 항목이 4바이트인 32비트 주소 공간을 가정해보자.

하나의 페이지 테이블 크기가 약 4MB가 된다. 그런데 페이지 테이블은 프로세스마다 존재한다.

프로세스가 100개만 되어도 페이지 테이블을 위해 400MB가 필요하다. 이는 엄청난 메모리 부담이다.

간단한 해법 : 더 큰 페이지

페이지 크기를 증가시키면 페이지 테이블의 크기를 간단하게 줄일 수 있다. 그런데 페이지 크기의 증가는 부작용을 수반한다.

가장 큰 문제는 페이지 내부의 낭비 공간이 증가하는 것이다. 이를 내부 단편화라 한다.

만약 프로그램이 커다란 페이지를 할당받고 그중 일부분만 사용한다면, 그리고 여러 페이지를 할당받는다면 메모리는 금방 고갈될 것이다.

이런 연유에서 많은 컴퓨터 시스템들이 비교적 작은 페이지 테이블을 사용한다. x86 시스템에서는 일반적으로 4KB 페이지를 사용한다.

하이브리드 접근 방법 : 페이징과 세그먼트

페이징 기법과 세그멘테이션 기법을 적절히 결합하면 페이지 테이블의 크기를 줄일 수 있다.

전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신, 논리 세그먼트마다 따로 페이지 테이블을 두는 것이다.

4KB 페이지를 갖는 32비트 가상 주소 공간을 4개의 세그먼트로 나누어보자.

세그먼트를 표시하기 위해 주소 공간의 상위 두 비트를 사용하면(미사용 세그먼트 : 00, 코드 : 01, 힙 : 10, 스택 : 11),

가상 주소를아래와 같이 Seg, VPN, Offset으로 나누어 표현할 수 있다.

 

이제 하드웨어에 코드와 힙, 스택 각각을 위한 페이지 테이블과 베이스, 바운드 레지스터 쌍이 있다고 가정하자. 

각 세그먼트의 베이스 레지스터는 각 세그먼트 페이지 테이블의 시작 물리 주소를 갖는다. 

문맥 전환 시 이 레지스터들은 새로 실행되는 프로세스의 페이지 테이블 위치 값으로 변경된다.

하이브리드 기법에서 핵심은 세그먼트마다 바운드 레지스터가 따로 존재한다는 것이다.

각 바운드 레지스터의 값은 세그먼트의 최대 유효 페이지 개수를 나타낸다. 

예를 들어, 첫 세 개의 페이지들을 코드 세그먼트로 사용 중이라면, 코드 세그먼트 페이지 테이블은 세 개의 항목을 할당받고,

바운드 레지스터는 3으로 설정된다. 해당 세그먼트의 범위가 넘어가는 메모리 접근은 예외를 발생시킨다.

이와 같은 방식으로 하이브리드 기법은 메모리 사용을 개선할 수 있다.

하지만 이 기법 역시 문제가 없는 것은 아니다. 여전히 빈 공간이 많은 힙의 경우에는 페이지 테이블의 낭비를 발생시킨다.

또한, 외부 단편화 역시 피해 갈 수 없다. 이런 이유로 페이지 테이블 크기를 감소시키는 더 나은 방법을 찾는 노력들이 지속되었다.

멀티 레벨 페이지 테이블

멀리 레벨 페이지 테이블에서는 선형 페이지 테이블을 트리 구조로 표현한다. 기본 개념은 간단하다.

먼저, 페이지 테이블을 페이지 크기 단위로 나눈다.

그다음, 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면 해당 페이지를 할당하지 않는다.

페이지 디렉터리라는 자료 구조를 사용하여 페이지 테이블 각 페이지의 할당 여부와 위치를 파악한다.

페이지 디렉터리는 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치 정보를 가지고 있다.

 

위의 좌측 그림은 전형적인 선형 페이지 테이블이다.

페이지 테이블의 중앙부에 해당하는 주소 공간은 사용되고 있지 않다.

그러나 사용되지 않는 주소 공간도 PFN 202, PFN 203으로 할당되어 있다.

 

우측 그림은 동일한 주소 공간을 다루는 멀티 레벨 페이지 테이블이다.

페이지 디렉터리는 PFN 200에 할당되어 있다.

페이지 디렉터리의 각 항목(PDE)은 페이지 테이블의 한 페이지를 나타내며, 현재 항목 두 개가 유효하다.

PDE가 유효하다는 것은 그 항목의 PFN에 할당된 페이지 내에서 최소한 하나의 항목이 유효하다는 의미이다.

PFN 201에 할당된 페이지를 보면 3개의 항목이 유효하고 각각이 PFN 12, 13, 100에 할당되어 있다.

선형 페이지 테이블에서 할당되었던 PFN 202, PFN 203은 멀티 레벨 페이지 테이블에서 할당되지 않았다.

 

멀티 레벨 페이지 테이블은 몇 가지 장점이 있다.

첫 번째, 멀티 레벨 페이지 테이블은 사용된 주소 공간 크기에 비례하여 페이지 테이블 공간이 할당된다.

그렇기 때문에 보다 작은 크기의 페이지 테이블로 주소 공간을 표현할 수 있다.

두 번째, 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 매우 용이하다.

페이지 테이블을 할당하거나 확장할 때, 운영체제는 사용 가능한 페이지 풀에 있는 빈 페이지를 가져다 쓰면 된다.

선형 페이지 테이블은 연속된 물리 메모리 공간을 차지한다.

큰 페이지 테이블의 경우 해당 크기의 연속된 빈 물리 메모리를 찾는 것이 쉽지 않다.

멀티 레벨 페이지 테이블에서는 페이지 디렉터리를 사용하여 각 페이지 테이블 페이지들의 위치를 파악한다.

페이지 테이블의 각 페이지들이 물리 메모리에 산재해있더라도 페이지 디렉터리를 이용하여 그 위치를 파악할 수 있다.

 

멀티 레벨 페이지 테이블에도 단점이 있다.

우선, 멀티 레벨 페이지 테이블에서는 TLB 미스 시, 주소 변환을 위해 두 번의 메모리 접근이 발생한다.

페이지 테이블 크기를 줄이는 데 성공하였으나 메모리 접근 비용이 증가했다. 

또 하나의 단점은 복잡도이다. 멀티 레벨 페이지 테이블의 경우, 검색이 단순 선형 페이지 테이블의 경우보다 복잡하다.

멀티 레벨 페이징 예제

64바이트(2의 6승) 페이지를 갖는 16KB(2의 14승) 크기의 14비트 가상 주소 공간을 가정해보자.

VPN에 8비트, 페이지 오프셋에 6비트가 필요하다. 선형 페이지 테이블은 256개(2의 8승)의 엔트리로 구성된다.

각 PTE를 4바이트라고 가정했을 때, 페이지 테이블의 크기는 1KB(256 x 4바이트)가 된다.

이 1KB 크기의 페이지 테이블은 16개의 64바이트 페이지들로 분할된다. 각 페이지에는 16개의 PTE가 있다.

 

이를 2단계 페이지 테이블로 구성해 보자. 먼저 페이지 디렉터리의 인덱스를 만들어보자.

페이지 디렉터리는 페이지 테이블의 각 페이지마다 하나씩 있어야하기 때문에 총 16개의 항목(PDE)이 있어야 한다.

결과적으로 VPN의 4개의 비트를 사용하여 디렉터리를 구성할 수 있다. 

페이지 디렉터리의 항목이 유효하다면 추가 작업을 해야 한다.

해당 항목이 가리키고 있는 페이지에서 원하는 페이지 테이블 항목(PTE)을 읽어들여야 한다.

PTE를 찾기 위해서 VPN의 나머지 4개의 비트를사용한다.

 

해당 과정을 이해하기 위해 멀티 레벨 페이지 테이블에 실제 값들을 넣은 후에 하나의 가상 주소를 변환해 보자.

아래 그림을 보면 맨 왼쪽의 Page Directory가 총 16개의 항목으로 구성되어 있는 것을 알 수 있다.

그 중 2개의 항목, 즉 2개의 페이지만 유효하다. 유효한 항목은 페이지 테이블의 페이지에 대한 정보, PFN을 갖고 있다.

유효한 항목들을 살펴보자. 우선 PFN 100에 할당된 페이지 테이블의 페이지의 경우, 총 16개의 페이지 테이블 항목으로 구성되어 있으며,

그 중 4개의 항목이 유효하다. PFN 101에 할당된 페이지의 경우, 2개의 페이지 테이블 항목만이 유효하다.

선형 페이지 테이블의 경우, 유효한 페이지 테이블 항목을 위해 16개의 페이지들을 모두 할당해야 한다.

멀티 레벨 페이지 테이블의 경우 아래와 같이 페이지 디렉터리를 위해 한 페이지,

유효한 매핑 정보를 갖고 있는 페이지 테이블 내의 두 페이지 총 3페이지만 할당하면 된다. 

 

이제 가상 주소 1111 1110 000000를 변환해보자. 우선, 상위 4비트(1111)를 이용하여 페이지 디렉터리 항목을 구해보자.

이진수 1111은 십진수로 15이다. 페이지 디렉터리 항목이 0부터 시작한다면 16개 중 마지막 항목에 해당한다.

마지막 항목에는 PFN 101이 저장되어 있다. VPN의 다음 4비트(1110)을 이용하여 페이지 테이블 항목을 구해보자.

이진수 1110은 십진수로 14이다. PFN 101에 할당된 페이지의 항목이 0부터 시작한다면 마지막에서 두 번째 항목에 해당한다.

해당 항목에는 PFN 55(00110111)가 저장되어 있다. 해당 PFN과 오프셋(000000)을 결합하면 물리 주소를 구할 수 있다.

정리하자면, 가상 주소 11 1111 1000 0000은 물리 주소 00 1101 1100 0000에 해당한다.

 

2단계 이상 사용하기

앞선 예제에서 2단계 페이지 테이블을 가정하였다. 경우에 따라서 단계를 더 증가시키는 것도 가능하다.

사실, 64비트 환경으로 넘어오면서 2단계로 페이지 테이블을 구성하는 것이 충분하지 않게 되었다.

간단한 예제를 통해 2단계 이상의 멀티 레벨 페이지 테이블을 구현해보고자 한다.

이 예제에서는 512바이트(2의 9승) 크기의 페이지와 30비트 가상 주소 공간을 가정한다.

해당 경우, 가상 주소는 21비트의 가상 페이지 번호와 9비트의 오프셋을 갖게 된다.

한 페이지에 몇 개의 페이지 테이블 항목을 저장할 수 있을지 계산해보면 한 페이지에 128개의 PTE를 넣을 수 있다.

페이지 테이블의 페이지를 인덱스로 쓰려면 VPN의 하위 7비트가 필요하다.

페이지 디렉터리를 위해서 총 14개의 VPN 비트가 남았다. 즉, 페이지 디렉터리에 2의 14승개의 항목이 있다는 의미이다.

이는 페이지 디렉터리를 위한 메모리가 많이 필요하다는 뜻으로, 페이지 디렉터리 자체를 다시 나누어 단계를 늘려야 한다.

아래와 같이 가상 주소를 분할 할 수 있다. 

 

변환 과정 알고리즘

2단계 페이지 테이블 사용 시, 전체 주소 변환 과정을 아래와 같이 알고리즘 형태로 정리할 수 있다.

멀티 레벨 페이지 테이블 접근을 거치기 전에 TLB를 검사하는 과정이 있다. 히트가 되면 페이지 테이블 참조 없이 물리 주소를 구한다.

TLB 미스시에만 멀티 레벨 페이지 테이블의 모든 단계를 거쳐 물리 주소를 구하게 된다.

 

페이지 테이블을 디스크로 스와핑하기

이제까지는 페이지 테이블이 커널 소유의 물리 메모리 영역에 존재한다고 가정하였다.

페이지 테이블 크기를 최대한 줄이더라도 여전히 모든 페이지 테이블을 메모리에 상주시키기에는 메모리 요구량이 너무 클 수 있다.

어떤 시스템들은 페이지 테이블들을 커널 가상 메모리에 위치시키고, 메모리가 부족할 경우, 페이지 테이블들을 디스크로 스왑한다.

이는 향후 VAX/VMS에 대한 사례 연구를 다루는 장에서 다시 다루도록 하겠다.