[OS] multi-level page tables (2)

지금까지는 two-level page table을 보았는데

그 이상의 level의 경우는 어떻게 되는 것인지 알아보자

 

level이 계속해서 늘어나게 되는 경우는 logical address space 크기가 클 수록 page 단위로 잘랐을 때도 여전히 크기가 크고 사용되지 않는 부분이 많게 되면 level을 더 늘리게 된다.

 

-three level page table

위와 같은 경우는 VPN이 21 bit이다 보니 2^21개의 entry를 가지게 되고 page table만 해도 2^23바이트 8MB의 크기가 되므로 너무 크다는 문제가 있다. 

page size가 512바이트이고 한 entry 크기가 4바이트이니 512/4 = 128(2^7)개의 entry를 한 페이지당 갖고 있는 것이다.

즉 한 페이지는 7비트로 표현이 가능하다는 것이다.

 

page table를 페이지 단위로 나누어도 2^21 / 2^7 = 2^14 개의 페이지가 나오게 되고 14비트면 한 페이지에 들어갈 수 없다.

즉 two-level로 했을 때의 page directory 하나로 표현이 불가능하게 되고

three-level로 가야하는 것이다. 

 

이를 그림으로 나타내어 보면 다음과 같다.

가장 오른쪽이 page table을 page 단위로 쪼갠 것이다. 2^21 / 2^7 = 2^14개의 page로 나눈 것이다

가운데는 2^14개의 page를 다시 Page 단위로 묶어서 2^14 / 2^7 = 2^7개의 page로 나타낸 것이다.

가장 왼쪽은 마지막 2^7개의 page를 나타낸 page directory이다.

이를 비트로 표현하면 다음과 같다. 각 level 마다 7bit 씩 표현이 되므로

다음과 같이 표현이 되는 것이다.

 

그렇다면 page 개수는 몇개가 필요한 것일까? 

1+2^7+2^14 개가 필요하다

 

만약 multi-level로 하지 않았다면

2^21개의 page가 필요하다

 

TLB miss 가 일어나면 몇 번의 access가 필요한가

-> level이 3개면 4번의 access 가 필요하다.(각 level 마다 access + 실제 메모리 frame access 1번)

 

 

코드로 표현하면 다음과 같다.

TLB hit 일때는 기존의 방법의 코드와 동일하다.

 

 

TLB MISS 일때 코드가 달라진다.

기존에는 바로 PTE를 찾아내었지만 multi-level 에서는

PDE로 먼저 접근을 하고 그 안에서 PTE를 찾아내는 것을 확인할 수 있다.