페이지 테이블의 구조 - 계층적 페이징

현대 컴퓨터는 매우 큰 주소 공간을 사용한다. (2^64와 같은) 이러한 환경에서는 페이지 테이블도 상당히 커지게 된다.
예를 들어 32Bit 논리 주소 공간을 가진 시스템에 페이지 크기가 4KB(2^12)라면 페이지 테이블은 2^20(2^32/2^12)개 이상의 항목으로 구성될 것이다. 각 항목은 다시 32bit로 구성됨으로 페이지 테이블 하나당 최대 2^20*32bit = 4MB가 된다. 이러한 경우 모든 페이지 테이블들이 메인 메모리에서 연속적으로 할당 되기를 원하지 않을 것이다.
위와 같은 문제점을 해결하기 위해 페이지 테이블을 여러개의 조각으로 나누는 방법이 있다.

2단계 페이징 기법

간단하게 페이지 테이블 자체가 다시 페이징 되게 한다. 위에 설명한 시스템에서 예를 들어보자. 위에는 20bit의 페이지 번호와 12비트 offset이 필요하다. 페이지 테이블도 페이지로 나누면 페이지 번호는 10비트 짜리 페이지 번호와 10비트 짜리 페이지 오프셋으로 나누어진다. 아래와 같다.

여기서 p1은 바깥 페이지 테이블의 인덱스이며, p2는 안쪽 페이지 테이블의 페이지 내 오프셋이다. 이러한 방식을 for-ward-mapped 페이지 테이블이라고도 부른다. 아래와 같은 방식으로 주소가 변환 된다.

문제점

64bit 논리 주소 공간을 가진 시스템에서 페이지 크기가 4KB라고 하자. 2단계 페이징을 사용안하는 경우는 2^52 항목으로 구성되며 2^12개의 오프셋이 필요하다. 2단계 페이징을 사용하게 되면 2^42 항목으로 구성되며 각 페이지에 대한 오프셋 2^10개의 오프셋이 필요하며 나머지 오프셋 2^12이 필요하다.

여전히 바깥 테이블의 크기는 2^42 * 32bit = 2^44byte로 구성될 것이다. 이걸 하번 더 하여 3단계 페이징을 구현할 수도 있다. 물론 이렇게 너무 깊은 계층의 페이징은 여러번 메인 메모리를 접근해야하므로 큰 주소 공간 시스템에서는 부적합함을 알 수 있다.