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: Page offset bits
Page size \(=4\,\text{KB}=2^{12}\) bytes \(\Rightarrow\) offset \(=12\) bits.
Step 2: Virtual page number (VPN) bits
Total VA bits \(=57 \Rightarrow\) VPN bits \(=57-12=45\).
Step 3: Index bits per level
PTE size \(=8\) bytes, page size \(=4096\) bytes \(\Rightarrow\) entries per page \(=4096/8=512=2^{9}\).
Therefore each level uses \(9\) bits of the VPN for indexing.
Step 4: Number of levels
We need \(9L = 45 \Rightarrow L = 5\).
\[ \boxed{5} \]