Multilevel page tables
Page the page table itself, so that unused parts of the address space need no table at all. About 14 minutes.
What is the main benefit of a two-level page table over a flat one for a small process?
- AInner tables are only built for the parts of the address space that are used, so the table is much smaller
- BEach translation is faster
- CIt removes the need for a TLB
Show the answer
Inner tables are only built for the parts of the address space that are used, so the table is much smaller. Unused regions are a single "not present" entry in the outer table.
Levels of a page table
Addresses have addressBits bits and pages have pageSizeBytes bytes (a power of two). Each page table entry is entryBytes bytes (a power of two), and every table must fit in exactly one page, so a table has pageSizeBytes / entryBytes entries. The page number is the address minus the offset bits. Return the number of levels needed so that the page number is covered by the indexes, which is the page number bits divided by the bits per index, rounded up, and at least 1.
addressBits = 32, pageSizeBytes = 4096, entryBytes = 4 → 2
12 ≤ addressBits ≤ 64 · pageSizeBytes and entryBytes are powers of two · entryBytes ≤ pageSizeBytes / 2 · pageSizeBytes ≤ 2^addressBits