역 페이지 테이블

32비트 가상 주소 공간에서 다단계 페이지 테이블은 적절한 성능을 보이며 잘 동작한다. 하지만 64비트 시스템이 등장하면서 상황은 크게 변하였다.
주소 공간이 2^64바이트라면 4KB 페이지를 사용할 경우 2^52개의 엔트리가 요구된다.
각 엔트리의 크기를 8바이트로 잡으면 페이지 테이블의 크기가 30PB가 된다..;; 에바임 이 크기의 테이블을 유지하는 것은 좋은 생각이 아니다.

그래서 역 페이지 테이블이 나옴!
역 페이지 테이블은 더 큰 페이지 테이블을 위한 솔루션이다.

이 방법에서는 가상 주소 공간의 각 페이지마다 엔트리가 하나씩 존재하는 것이 아니라, 물리 메모리의 각 페이지 프레임 마다 하나의 엔트리가 존재한다.

위의 예에서 처럼 64비트 가상 주소 공간이라 할 지라도, 만일 물리 메모리의 크기가 1GB라면 262,144 개의 엔트리만 있으면 된다(1GB/4KB=256KB).

• 각 엔트리는 각 페이지 프레임에 어떤 프로세스의 페이지가 존재하는지에 대한 정보. 즉, (프로세스 번호, 페이지 번호) 정보를 유지한다.

• 가상 주소 공간이 물리 주소 공간에 비해 상당히 클 경우, 역페이지 테이블은 주소 변환을 위한 메모리 공간의 사용을 크게 줄일 수 있다.

• 반면, 가상-물리 주소 변환이 복잡해 진다는 단점이 있다.

프로세스 n이 가상 페이지 p를 접근할 때 MMU는 더이상 p를 페이지 테이블의 인덱스로 사용하여 물리 페이지 프레임을 알아낼 수 없다.

그 대신, 역페이지 테이블 전체를 검색하여 (p,n)를 갖는 엔트리가 있는지 검사한다.

• 이 검색은 페이지 폴트가 발생했을 때 만이 아니라 메모리 참조가 있을 때 마다 발생한다.

매 메모리 참조마다 256KB 크기의 테이블을 검색하는 것은 컴퓨터 시스템을 매우 느리게 할 것이다.

이 문제를 해결하는 방법 중 하나는 TLB를 사용하는 것이다.
TLB가 자주 접근하는 페이지들의 정보를 유지하고 있으면 주소 변환은 다단계 페이지 테이블 기법 만큼의 속도로 실행 될 수 있다.

하지만 TLB 미스의 경우 역 페이지 테이블 검색은 여전히 요구된다.

검색을 빠르게 하는 한가지 방법은, 가상 주소를 기반으로 해쉬 테이블을 이용하는 것이다.
메모리 상에 존재하는 페이지들 중 같은 해쉬 값을 갖는 페이지들은 그림 3-14에 나타는 것처럼 체인으로 연결된다.
만일 해쉬 테이블이 물리 페이지 프레임 크기 만큼의 슬롯을 가지고 있다면, 각 체인은 평균 하나의 엔트리를 가지게 되며 따라서 매핑 속도가 증가한다.
일단 페이지 프레임 번호가 발견되면 새로운 (가상,물리) 정보는 TLB에 적재된다.