[운영체제] 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 의 역할을 하기 때문이다.
이에 대한 해결책으로 두 가지가 제시되는데,
하나는 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를 알아보았다.
//문제제기 및 피드백 언제든지 감사히 받겠습니다.