멀티레벨페이지테이블(Multi-level Page Table)

/*

본 내용은 학교 수업내용을 바탕으로 하고 OSTEP(Operating Systems: Three Easy Pieces) 교재를 참고하여 정리한 내용입니다.

*/

 

 

CISC(Complex Instruction Set Computing)체계에서는 하드웨어가 TLB미스를 처리하도록 설계하였고 RISC(Reduced Instruction Set Computing)체게에서는 TLB미스를 소프트웨어가 처리하도록 설계했다.

 

프로세스마다 별도의 테이블페이지를 가지고 있다. 그렇기 때문에 TLB를 사용하게 되면 프로세스 간  Context Switching이 발생할 시에 기존에 있던 TLB의 내용들을 모두 비우고 새로운 TLB내용을 저장해야하는데 이때 큰 성능저하를 가져올 수 있다.

 

그리고 페이징의 두 번째 문제점은 페이지테이블의 크기이다. 페이지테이블의 크기가 커질수록 메모리공간을 많이 차지하게 된다. 이 문제는 페이지의 크기를 키움으로써 해결할 수 있지만 내부단편화라는 문제가 여전히 해결되지 않게 된다.

 

예를 들면 32비트 주소공간에서의 4KB크기의 페이지일 때는 약 (2의 32제곱 / 2의 12제곱) 100만 개의 페이지가 존재하게 되고 4Bytes 페이지테이블이 100개 존재한다면(100개의 프로세스가 존재한다면) 약 400MBytes의 메모리공간이 필요하게 된다. 

 

그러나 페이지의 크기를 16KB로 늘린다면 약 (2의 32제곱 / 2의 14제곱) 26만 개의 페이지가 존재하게 되며 4Bytes의 페이지테이블이 100개가 존재한다면(100개의 프로세스가 존재한다면) 100MBytes의 메모리공간이 필요하게 되고 페이지의 크기가 4KB일때 보다 약 1/4정도의 메모리공간이 절약된다.

하지만 페이지크기를 키우게 되면 내부단편화 문제는 증가하게 될 것이다.

 

그 해결책으로 세그멘테이션과 페이징을 조합하여 하이브리드기법을 사용하지만 이 또한 세그멘테이션 사용으로 인한 외부단편화문제를 유발하므로 세그멘테이션을 사용하지 않고 페이지테이블크기를 줄이는 방법인 멀티레벨페이지테이블 기법을 사용한다.

 

 

멀티레벨페이지(Multi-Level page table)은 선형페이지테이블을 트리구조로 표현한다.  

멀티레벨페이지는 우선 페이지테이블을 페이지의 크기로 나눈다음 페이지가 유효하지 않은 항목만 있으면 그 페이지를 할당하지 않는다.

 

 

선형페이지테이블(좌) 멀티레벨페이지테이블(우)

 

좌측의 선형페이지테이블을 보면 PFN202, 203부분은 사용되고 있지 않지만 페이지테이블에 할당되어 있다.

우측의 멀티레벨페이지테이블은 페이지디렉터리에 유효한 두 개의 페이지가 어떤 페이지테이블의 페이지들이 할당되어있는지 저장한다.

 

페이지디렉토리의 항목은(Page Directory Entry) Valid비트와 PFN이 있으며 PED항목이 유효하다는 것은 PDE가 가리키고 있는 페이지 내의 페이지테이블에 최소한 하나의 PTE의 Valid비트가 1로 설정되어 있다는 것이다.

 

멀티레벨페이지테이블을 사용하면 사용된 주소공간의 크기에 비례하여 페이지테이블공간이 할당되고 페이지테이블을 페이지 크기로 분할함으로써 메모리 관리가 매우 용이해진다.

 

선형페이지테이블은 연속된물리메모리공간을 차지하지만 멀티레벨페이지테이블은  페이지테이블의 각 페이지들이 물리메모리에 산재해 있어도 페이지디렉토리를 사용하여 그 위치를 비교적 쉽게 알 수 있다.

 

하지만 멀티레벨페이지테이블을 사용하면 주소변환을 위해 페이지디렉토리와 PTE에 총 두 번 접근해야 함으로 선형페이지테이블보다 많은 비용이 발생하게 된다.