GATE CS 2023 Set 1 — Question 58

Here is the step-by-step calculation to find the number of levels (L) in the page table structure:

• Virtual Address (VA) size = 57 bits
• Page Size (PS) = 4 KB = $4 \times 1024$ Bytes = $2^2 \times 2^{10}$ Bytes = $2^{12}$ Bytes
• Page Table Entry (PTE) size = 8 Bytes = $2^3$ Bytes

2. Calculate Page Offset bits:
The page offset is determined by the page size. It represents the address within a page.
Number of Page Offset bits = $\log_2(\text{Page Size}) = \log_2(2^{12}) = 12$ bits. The virtual address is split into the Virtual Page Number (VPN) and the Page Offset.
Number of VPN bits = Total VA bits - Page Offset bits
Number of VPN bits = $57 - 12 = 45$ bits.
These 45 bits are used to index the multi-level page tables. In a multi-level paging system, each page table must fit within a single physical page frame.
Number of PTEs per page = $\frac{\text{Page Size}}{\text{PTE Size}} = \frac{2^{12} \text{ Bytes}}{2^3 \text{ Bytes}} = 2^{12-3} = 2^9 = 512$ entries. Each level of the page table uses a part of the VPN to index into its table. The number of bits required to index 512 entries is:
Bits per level = $\log_2(\text{Number of PTEs per page}) = \log_2(512) = \log_2(2^9) = 9$ bits. The total 45 bits of the VPN are distributed among the L levels of the page table structure. Since each level requires 9 bits for indexing, we can find L by dividing the total VPN bits by the bits per level.
L = $\frac{\text{Total VPN bits}}{\text{Bits per level}} = \frac{45}{9} = 5$.Therefore, the value of L is 5.