[운영체제] 페이지 테이블 구조 (Hierarchical Page Table, 2-level Page Table, Hashed Page Table, Inverted Page Table)

Hierarchical Page Table

하나의 페이지 테이블 안에 여러개의 페이지 테이블을 넣은 페이지 테이블을 의미한다. 

이 중 대표적으로 2-level page table에 대해 알아보자.

 

logical address format

32-bit machine, 4K page size를 가정했을 때, 논리 주소는 아래와 같이 구성된다.

• page number : 20bit
  • p1-page number : 10bit
  • p2-page offset : 10bit
• page offset : 12bit

즉 p1은 outer page table(바깥 테이블)의 index이고, p2는 해당 바깥 테이블에서의 위치를 나타낸다.

이해가 쉽지 않다면 다음 그림을 살펴보자.

2-level page table

p1을 통해 outer-page table의 인덱스를 찾고, 해당 인덱스가 가리키는 page table에서 p2를 통해 physical 메모리의 frame번호를 찾는다. 마지막으로 d를 통해 physical 메모리에서의 위치를 찾는다.

 

2-level page table

위 그림을 보면 이해가 더 쉬울 것이다.

---

Hashed Page Table

해시 값이 가상 페이지 번호가 되는 형식의 페이지 테이블이다. 주로 주소 공간이 32bit보다 큰 경우 많이 사용한다.

해시형 테이블의 각 항목은 연결리스트를 가지고 있다.

Hashed page table

위 그림을 보며 이해해보자.

가상 주소 공간으로부터 페이지 번호가 오면 hash 함수를 통해 해시값을 추출한다.

해당 값을 hash 테이블에서 연결리스트를 따라가며 가상 페이지 번호와 일치하는 값이 있다면 그에 대응하는 프레임 번호를 가져와 물리적 주소를 계산한다.

 

+참고 : clustered page table

해시형 페이지에서 각 항목들이 한 개의 페이지만 가리키는 대신 64-bit에서는 해시 알고리즘을 변경하여 각 항목들이 여러개의 페이지를 가리킬 수 있다. 따라서 한 개의 페이지 테이블 항목이 여러 페이지 프레임에 대한 매핑 정보를 지닐 수 있다. clustered page table은 메모리 접근이 불연속적이면서 전 주소 공간으로 넓게 퍼져 나오는 경우 유용하다.

---

Inverted Page Table

Inverted Page Table은 메모리 프레임마다 한 항목씩을 할당한다. 각 항목은 프레임에 올라와 있는 페이지 주소, 그 페이지를 소유하고 있는 process id(pid)를 표시한다. 따라서 시스템에는 단 하나의 페이지 테이블만 존재하게 되어 공간을 절약할 수 있다.

Inverted Page Table

위의 그림을 보며 이해해보자.

 

1. 가상 주소는 <pid, page number, offset> 으로 구성된다.

2. 메모리 참조가 발생하면 페이지 테이블에서 <pid, page number>가 일치하는 항목을 찾는다.

3. 일치하는 것이 f번째 항목에서 발견되면 물리주소는 <f, offset>이 되고 일치하는 것이 없으면 잘못된 메모리로 간주한다.

 

---