Question

A computer uses 57-bit virtual addresses with multi-level tree-structured page tables (L levels). Page size = 4 KB and each page-table entry (PTE) = 8 bytes. Find \(L\).

Hint:

For multi-level paging: \( \text{levels} = \dfrac{\text{VPN bits}}{\log_2(\text{entries per page})}\). Here VPN bits \(= \text{VA} - \text{offset}\) and entries/page \(= \dfrac{\text{page size}}{\text{PTE size}}\).

Answer 1

Step 1: Express all quantities in powers of two

Page size = 4 KB = 4096 bytes = 2¹²
Virtual address size = 57 bits
Page table entry (PTE) size = 8 bytes = 2³

---

Step 2: Determine how many entries fit in one page table page

Number of PTEs per page:
2¹² / 2³ = 2⁹ entries

Thus, each page table level can be indexed using 9 bits.

---

Step 3: Determine how many bits must be indexed by page tables

The page offset consumes 12 bits.
Remaining bits used for translation:

57 − 12 = 45 bits

---

Step 4: Compute the number of levels

Each level accounts for 9 bits.
So the number of levels required is:

45 / 9 = 5

---

Final Answer:

Number of page table levels = 5