[OS]Multi-level Page Tables (1)

page table이 너무 크고 invalid region에 대해 메모리가 낭비되는 부분이 있었다.

 

이것을 해결하기 위한 방법으로 이전에 보았던 것이 hybrid 방법, segment, paging을 섞어서 사용하는 것이었다.

하지만 이것 또한 heap 영역에서의 낭비되는 메모리가 문제가 되었다.

 

그렇다면 또 다른 방법으로 무엇이 있을까?

 

바로page table을 또다시  paging 해보는 방법이 있다.

multi-level page table이라고 한다. 

 

page table이 있다고 하면 이를 다시 page 단위로 잘라본다.

해당 page 중에 valid 한 page 영역을 track 하기 위한 또다른 page table을 만드는데 그것을 'page directory'라고 한다.

 

page directory는 하나의 entry에 하나의 page table의 page를 담고 있고 그 entry를 Page Directory Entry라고 해서 PDE라고 한다.

page directory entry에는 뭐가 들어가 있느냐?

entry에서 가리키고 있는 영역이 valid 한지 여부를 나타내어 주는 valid bit, 그리고 main memory에 올라가 있는 page table의 어떤 page가 어떤 frame에 저장되어 있느냐의 정보가 담겨 있다.

여기서 page frame number는 (PFN)이라고 한다.

 

아래 그림이 multi-level page table의 예시 그림이다.

 

왼쪽 그림이 일반적인 page table 그림이다.

 

PTBR(page table base register)에는 201번 frame에 table이 시작된다 라는 정보가 담겨있는 것이다.

PFN201 204 page 경우에는 valid invalid 가 섞여 있으므로 해당 page는 유지해야 하는 page 이다

PFN202 203 경우에는 invalid 만 있으므로 유지할 필요가 없는 page 이다.

 

이를 multi-level page table로 표현한 것이 오른쪽 그림이다.

PTBR에는 Page Directory의 위치의 주소 값을 가지고 있고 해당 주소로 이동하면 page directory가 나오게 된다.

page directory에 적혀 있는 것은 valid 여부의 valid bit과 해당 page의 frame number (PFN) 값이 적혀있다.

 

page directory에 적혀 있는 PFN201의 page 로 넘어가 보면

 

 

왼쪽 그림과 같은 데이터를 확인할 수 있다.

이때의 PFN은 이제 실제 데이터가 저장되어 있는 Page Frame number 를 의미한다.

 

 

 

 

비교해보면

왼쪽과 같이 linear page table의 경우로 간다면 4개의 frame이 사용이 되는 반면

오른쪽과 같이 multi-level page table의 경우 3개의 frame만 사용하는 것으로 메모리를 아끼는 것을 확인할 수 있다.

 

이렇게 장점만 있는 것은 아니다.

 

단점

1. time-space trade-off

:space 측면에서 좋음 but time 측면에서는 그렇지 않음

TLB Miss 가 발생하게 되면 기존에 linear page table에서 했던 것에 비해서 page directory를 한번 더 acceess 하게 되기 때문이다.

 

2. complexity

:복잡하다는 단점이 있다.

 

다시한번 예시를 보자.

-16KB address space : 2^14크기 이므로 14bit이 주소에 사용

-64-byte pages : 한 페이지에 64 byte = 2^6이므로 6bit 가 offset에 사용

-그럼 나머지 8bit가 VPN에 사용되는 것이다.

-> page table의 entry 개수가 2^8 = 256 개 있다는 것이다.

-하나의 page table entry 크기가 4바이트 라고 한다면 2^8x 4 = 1KB의 크기의 page table이 생성되는 것이다.

 

 

이를 single-level paging 기법으로 구현한 경우라면,

256개의 entry가 있는 page table 이 생성되는 것을 확인할 수 있다.

 

위 그림을 보다 시피 page가 중간 중간에 사용되지 않는 것들이 많다. 

page table을 다시 paging 해보자.

Two-level Page table로 만들어 보자는 것이다.

 

한 page 크기가 64바이트 이고 한 page entry 크기가 4바이트 이므로

하나의 page에 들어갈 수 있는 entry 수는 16개가 된다. -> 16개씩 잘려서 page가 256/16 = 16개의 page가 만들어 진다는 것.

16개의 page로 나누어서 비어있는 것과 아닌 것을 보자

위의 경우로 보자면 16개씩 잘랐을 때 맨 첫 page, 마지막 page만 valid 하고 나머지는 그렇지 않은 것을 볼 수 있다.

그럼 두 페이지만 할당하고 두 페이지를 관리하는 page directory만 할당해주면 되므로 3개의 page table만 생성하면 된다. 

 

addressing은 어떻게 할까?

vpn을 4bit 4bit를 각각 page directory, page table index로 사용한다.

구하는 방법은 Base Address에 index * sizeof(index)로 구한다.

linear page table을 사용했다면 16 개의 page를 사용하는 반면

two-level page tabel을 사용해서 3 개의 page만 사용하는 것을 볼 수 있다.