앞선 TLB는 페이징에서 주소변환의 시간단축을 위해 제안되었다. 다음 두번째 페이징의 문제는 바로 page table의 크기이다.

앞선 TLB는 페이징에서 주소변환의 시간단축을 위해 제안되었다. 다음 두번째 페이징의 문제는 바로 page table의 크기이다. page table은 메모리 공간을 많이 차지한다. 이를 해결하기 위해 제안된 Multi-level page table을 배워보자.

Page table 크기

  • Linear page table page table크기를 한번 계산해보자. 예를들어 32-bit 주소공간과 4KB의 페이지들로 구성되어있다.(12비트가 offset, 20비트가 VPN이 되겠다.) PTE가 4바이트이므로, page table은 4MB(4B * 2^20)가 된다. 상당히 큰 크기를 요구한다.

Simple Approch

페이지 테이블을 간단하게 줄일 수 있는 방법은 페이지 크기를 키우는 것이다. 예를들어 32비트 주소공간에 페이지 크기가 16KB라고 하자.(14비트의 오프셋과, 18비트의 VPN을 갖게 된다.) PTE가 4바이트라면 page table은 1MB(4B * 2^18)이므로 아까보다 4분의1로 줄어든다. 하지만 페이지 내부의 낭비공간이 증가하는 내부단편화문제가 발생한다.

Hybrid Approach

페이징과 세그먼트를 동시에 쓰는 방법이다. 세그먼트마다 하나의 페이지 테이블이 존재하도록 하여 코드, 스택, 힙을 위한 페이지 테이블이 있는 것이다. 이를 위해 추가로 각 테이블의 베이스, 바운드 레지스터가 필요하다. 하이브리드의 경우 세그먼트마다 바운드 레지스터가 따로 존재하여 메모리 사용을 개선시킬 수 있다. 하지만 이 기법역시 문제점이 있다. 첫째는 여전히 세그멘테이션을 사용에서 오는 외부단편화 문제가 따라온다. 둘째는 페이지 테이블 사이즈가 들쭉날쭉해서 공간을 확보하는게 더 복잡해진다는 것이다.

🔗 Multi-level page tables

기존의 페이지 테이블 정보를 page table과 page directory로 나눠 저장한다. - page table 페이지 크기 만큼으로 쪼개져 있다. 모든 entry가 다 invalid하면 그 페이지테이블은 메모리에 아예 없다. - page directory 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치 정보를 가지고 있다.

왼쪽은 Linear Page Table, 오른쪽은 Multi-level page tables이다. 같은 정보를 이렇게 다르게 나타내는 것이다. 페이지 테이블을 페이지 크기로 분할함으로 메모리 관리가 용이한 것을 볼 수 있다. PDBR은 page directory base register이고 Multi-level page tables에는 PTBR이 없다.

🔗 주소 변환

  • TLB미스가 발생했을때 두번의 메모리 접근이 필요하다. (page directory, page table)
  • TLB미스가 발생하면 훨씬 복잡한 과정을 거쳐야한다.

Exmaple

예를 들어 주소공간이 16KB고, 페이지가 64바이트, PTE는 4바이트라고 하자. 이를 통해 다음의 것들을 알아낼 수 있다.

  • 14비트의 addressing이고, 8비트의 VPN, 6비트의 오프셋이다.
  • 페이지 테이블의 크기는 1KB(2^8 * 4)이다.
  • 페이지 테이블은 16개의 64바이트 페이지들로 분할된다. (1KB/64B)
  • Linear page table에서는 2^8개 만큼의 entry가 존재한다.
  • Multi-level에서는 2^8개가 16개의 페이지로 나뉘어 있다. 따라서 상위 VPN 4비트는 page directory를 나머지 4비트는 page table을 가리킨다.