GATE CS 2008 Q67 — Memory Management and Virtual Memory

To find the number of bits required to address the next level page table or page frame, we first determine the size and alignment requirements of each level's page table.

1. Size of each level's page table:

• Level 1: Index has $2$ bits (bits $30\text{--}31$). Number of entries = $2^2 = 4$.
  Size = $4 \times 4\text{ bytes} = 16\text{ bytes}$.
• Level 2: Index has $9$ bits (bits $21\text{--}29$). Number of entries = $2^9 = 512$.
  Size = $512 \times 4\text{ bytes} = 2\text{ KB}$ ($2^{11}\text{ bytes}$).
• Level 3: Index has $9$ bits (bits $12\text{--}20$). Number of entries = $2^9 = 512$.
  Size = $512 \times 4\text{ bytes} = 2\text{ KB}$ ($2^{11}\text{ bytes}$).
• Physical Page Frame: Size = $4\text{ KB}$ ($2^{12}\text{ bytes}$).

2. Addressing bits required in each level:

• First Level PTE points to a Level 2 page table. Since a Level 2 page table is $2\text{ KB}$ in size, its starting physical address must be aligned to a $2\text{ KB}$ boundary (the lowest $11$ bits are $0$). Thus, the number of bits required to address it is: $$36 - 11 = 25\text{ bits}$$
• Second Level PTE points to a Level 3 page table. Since a Level 3 page table is also $2\text{ KB}$ in size, its starting physical address must be aligned to a $2\text{ KB}$ boundary (the lowest $11$ bits are $0$). Thus, the number of bits required to address it is: $$36 - 11 = 25\text{ bits}$$
• Third Level PTE points to a physical page frame. Since a page frame is $4\text{ KB}$ in size, its starting physical address must be aligned to a $4\text{ KB}$ boundary (the lowest $12$ bits are $0$). Thus, the number of bits required to address it is: $$36 - 12 = 24\text{ bits}$$

Therefore, the required bits are 25, 25, and 24 respectively.