해시 페이지 테이블

이전에 설명한 방법들을 통해서 주소 공간이 매우 클 때는 일반적인 페이지 테이블은 문제가 발생함을 알 수 있었다.(페이지 테이블 크기가 너무 크다거나, 메모리 접근시 메인 메모리에 여러번 접근해야한다던가) 이 문제를 해결하기 위해 가상 주소를 해시로 사용하는 헤시 페이지 테이블 방법이 있다.

자료 구조

해시 페이지 테이블의 각 항목은 해시 충돌 방법을 체이닝 기법으로 해결한다. 그렇기에 각 항목마다 연결리스트로 구현한다. 각 원소는 세개의 필드를 가진다.

1. 가상 페이지 번호
2. 맵핑되는 프레임 번호
3. 연결리스트 상의 다음 원소 포인터

동작 방식

1. 논리 주소에서 페이지 번호 영역을 추출한다.
2. 페이지 번호를 해시 하여 해시 페이지 테이블에 확인한다.
3. 사상되는 해시 페이지 테이블 엔트리의 원소의 갯수(연결리스트 이므로)가 1개면 첫번째 원소의 프레임 번호를 반환한다.
4. 사상되는 해시 페이지 테이블 엔트리의 원소의 갯수(연결리스트 이므로)가 2개 이상이면 연결리스트를 조회하면서 나의 논리주소와 같은 원소를 찾고 해당 원소의 프레임 번호를 반환한다.
5. 사상되는 해시 페이지 테이블 엔트리가 없다면 프로세스에 할당 된 주소 범위를 초과한것이므로 오류를 반환한다.

클러스터 페이지 테이블

64비트 시스템에서 사용하기 위해 해시 테이블 기법을 변형한것이다. 해시 페이지 테이블의 각 항목이 한개의 페이지만 가리키는 것에 반해 클러스터 페이지 테이블의 각 항목은 여러 페이지를 가리킨다. 따라서 한개의 페이지 테이블 항목이 여러 프레임에 대한 변환 정보를 가질 수 있다. 클러스터 페이지 테이블은 퍼져 있는 주소 공간에 유용하게 사용된다. 즉 메모리 엑세스가 비연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우에 유용하다.