Consider a computer system with 57-bit virtual addressing using multi-level tree-structured page tables with L levels for virtual to physical address translation. The page size is 4 KB (1 KB = 1024 B) and a page table entry at any of the levels occupies 8 bytes.
The value of L is ______.
ANSWER
Official answer: 5Source: Official answer key, GATE 2023 CS (IIT Kanpur)
The page size is bytes, so the page offset takes bits.
The virtual page number has bits.
Each page-table node is stored in one page. A page holds entries, so one node holds 512 entries.
Each level therefore resolves bits of the virtual page number.
The number of levels needed is . The 45 bits divide exactly into five groups of 9, so every level is completely full and no level can be dropped.
Check: with 4 levels only bits are covered. With 5 levels bits are covered exactly. So .
KEY IDEA
Each page-table node fits in one page, so each level resolves bits of the virtual page number. The number of levels is the ceiling of (virtual page number bits) divided by (bits per level).
WATCH OUT FOR
Dividing all 57 address bits by 9 instead of first removing the 12 offset bits. This gives , which is wrong. Another slip is using the entry size as 4 bytes, or forgetting that the top level must also fit in one page.
From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 10 Memory management questions, with notes
