[OS] 페이지 테이블의 구조 (계층적 페이징, 해시 페이지 테이블)

 

계층적 페이징

.

 

요즘 컴퓨터는 큰 주소 공간을 가진다. (32bit, 64bit)

 

여기서 문제는 페이지 테이블이 용량이 너무 커진다는 것이다..

 

 

예로 32bit 컴퓨터는 2³² 주소 공간을 가진다.

 

만약 페이지 크기가 4KB이면 2¹²이고 총 주소 공간을 페이지 크기로 나누면

2³² / 2¹² = 2²⁰ 개 이상의 항목으로 구성된다.

 

행 하나 당 1 word 이고 32 bit이니깐 각 항목은 4B로 구성된다.

( 1 entry = 1 word = 32 bit = 8bit * 4 = > 4B)

 

한 행당 4 B.. 그럼 총 2²⁰ 개 이상의 항목으로 구성되니..

2²⁰ X 4B = 2²²

즉, 각 프로세스는 4MB 용량의 페이지 테이블이 필요한 것이다!

 

 

32bit 컴퓨터를 예로 들어 보았지만 만약 64bit라면?

프로세스 당 엄청 큰 용량의 테이블을 각각 가지고 있는 것이다.

 

이를 해결하기 위한 방법으로 계층적 페이징 기법이 있다.

 

페이지 테이블 자체를 다시 페이징하는 것이다.

 

 

 

 

위의 이미지를 보면 최상위 페이지 테이블을 'out page table'이라 하고,

하위 페이지 테이블을 'inner page table'이라 한다.

 

 

 

페이지 테이블을 하나만 사용할 땐 주소를

페이지 번호인 P와 프레임의 처음 위치에서 해당 주소까지의 거리인 D로 나눴지만

 

계층적 테이블에서는 페이지 번호의 주소 공간을 다시 나누어

P1은 상위 테이블의 인덱스, P2는 하위 테이블의 인덱스, D로 나뉜다.

 

나누는 횟수에 따라 2단계 페이징 기법, 3단계 페이징 기법.. 이라고 불린다.

 

단, 많이 나누면 메모리 접근을 그만큼 많이 해야 하므로 효율적이지 않다.

 

 

해시 페이지 테이블

.

 

계층적 페이징 기법은 많이 나누면 메모밀 접근을 많이 해야 하므로

효율성이 떨어진다고 했다.

 

64bit 컴퓨터에서의 페이지 테이블 용량을 계층적으로 나눈다면 7단계 페이징을 해야 한다.

 

 

이를 해결할 방안으로 주소 공간이 32bit보다 커지면

가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 쓴다.

 

 

해시 페이지 테이블은 연결 리스트를 사용한다.

 

 

 

해시 원소는 (가상 페이지 번호, 매핑 프레임 번호, 다음 원소 포인터)를 가지는데

 

가상 페이지 번호를 비교하여 맞으면 프레임 번호로 물리 주소를 반환하고

틀리면 다음 원소로 이동하여 동일하게 비교한다.

 

 

변형된 해시 테이블 기법으로 클러스터 페이지 테이블을 사용한다.

 

해시 테이블은 각 항목이 한 개의 페이지만 가리키지만

클러스터 페이지 테이블은 여러 페이지를 가리켜 더 유용하게 사용된다.

 

 

 

 

 

 

 

 

* 해당 글은 '쉽게 배우는 운영체제'와 '운영체제' 책을 참고하여 작성하였습니다. 출처: 쉽게 배우는 운영체제 (조성호), 운영체제 10판 (Abraham Silberschatz)