[운영체제] Smaller Tables -Page Directory

본 내용은 [Operating Systems : Three Easy Pieces]를 참고하였습니다.

 

paging도 좋고, page table도 좋고 다 좋다.

근데 한가지 문제점이 있다.

아래의 예를 보자.

32-bit address space에서 Page 하나의 크기가 4kB이고, page table entry 가 4-byte 라고 하자.

그렇다면 page 의 개수는 2^32 / 2^12 = 2^20 = 1M 개가 된다.

page table entry 하나당 4-byte이므로 page table size 는 4MB 가 된다.

 

그런데 process 하나 당 page table 을 위해 이렇게 큰 메모리를 차지한다면, 실제로는 정말 많은 양의 메모리가 필요할 것이다.

 

page의 크기를 4KB에서 16KB로 늘린다면 1MB로 page table의 크기는 줄어들겠지만, 큰 page는 internal fragmentation(내부 단편화)를 유발한다.

 

 

 

Problem

 

Linear 한 single page table 이 있다고 하자.

위의 그림과 같이 address space의 0, 4, 14, 15page 만이 할당되었고 나머지는 page가 모두 비어있다.

오른쪽의 Page Table을 잘 보면 실제로 0, 4, 14, 15번 page는 PFN 9, 15, 3, 23으로 mapping 이 된 것을 확인할 수 있고, 그 이외 나머지 page 들은 실제로 사용하지도 않지만, page table 내에서 굳이 자리를 차지하고 있다.

이유는 이와 같은 single page table은 linear 하기 때문에 page table 내에서 address space의 page number가 index 의 역할을 하기 때문이다.

Most of the page table is unused

 

이에 대한 해결책으로 두 가지가 제시되는데,

하나는 Paging과 Segement 를 결합한 Hybrid Approach 인데 이는 실제로 external fragmentation을 유발할 수 있기 때문에 좋은 해결책이 되지 못한다.

 

그 다음이 바로 Multi-level page Table 즉, Page Directory 이다.

 

Page Directory

 

page table을 일정 크기로 자르고, 그 자른 단위 내에 만약 valid 한 page table entry 가 없다면 해당 "page 들의" page를 할당하지 않는다. 아래의 예를 보자.

 

왼쪽은 기존의 single page table 방법이고, 우측이 multi-level page table 방법이다.

좌측의 PTBR은 해당 프로세스의 page table의 시작 주소를 가리키고, 우측의 PTBR은 page table 이 아닌 page directory의 시작 주소를 가리킨다.

200번째 PF에는 4가지 PDE(Page Directory Entry)가 존재하는데, 각 엔트리는 4개의 Page table entry를 가지고 있는 page를 가리키고 있다. 이와 같은 계층 구조를 잘 생각하자.

그래서 page directory의 장점은 사용하지 않는 VP에 대한 page entry 묶음(페이지, 만약 그 묶음 안에 모두 valid 하지 않다면), 즉 그 페이지를 할당하지 않기 때문에 메모리를 절약할 수 있다.

 

하지만 컴퓨터의 대부분이 그런 것처럼 memory를 아끼는 대신 page table 뿐만 아니라 그에 앞서 page directory를 먼저 접근해야 하므로 time-space trade-off 가 존재하기 마련이다.

 

Page directory 에 대한 깊은 이해를 위해 아래의 예를 생각해보자.

Page size는 64바이트라고 하였으므로 offset이 6비트를 차지하게 되고, 나머지가 VPN이 된다.

이제 우리는 Page directory에 대한 접근을 위한 index를 만들어야 하는데, 위의 예에서 PTE가 4 바이트의 크기를 가진다고 가정해보자.

페이지의 크기는 64바이트인데 PTE가 4바이트이므로 한 페이지당 16개의 PTE가 존재하고, 즉 이 PTE를 구분하기 위해 4비트가 필요하므로 6,7,8,9번째 비트를 PTE에 대한 index로 사용을 한다. 이렇게 page directory의 한 page 당 16개의 PTE가 저장이 되고, 원래 Page table entry는 256개 였으므로 page directory에는 16개의 페이지가 있고, 그 페이지 하나 당 16개의 PTE를 저장하게 되는 것이다. 따라서 8비트의 VPN을 PDI로 4비트를 사용하고 나머지 4비트를 Page table entry를 위한 index로 사용을 하는 것이다.

 

아래는 이를 도식화한 것이다.

 

위의 과정을 도식화한 것

 

현대의 컴퓨터는 32 bit 혹은 64비트의 memory를 사용하기 때문에 하나의 page directory 로도 부족하기 때문에 이와 같은 계층 구조는 더 깊어지기 마련이다.

 

 

Control Flow

 

control flow다. 1~9는 TLB 캐시에서 hit한 경우이고, 15번 줄에서는 PDE가 비어있어서(address space의 page가 비어있어서 page table entry의 묶음 page를 애초에 할당하지 않음) exception이 일어났고, 12번 줄이 PDI 의 비트 대조, 18번이 PTI의 비트 대조가 일어난다.

 

이로써 기존의 Single(linear) page table의 문제점을 해결할 수 있는 Multi-level page table 즉 page directory를 알아보았다.

 

//문제제기 및 피드백 언제든지 감사히 받겠습니다.