GATE CS 2003 Q26 — Memory Management and Virtual Memory

To understand why a single-level page table is impractical here, let us calculate the size of the page table required for a single process:

• Virtual Address Space: $32\text{ bits}$, which means the virtual address space size is $2^{32}\text{ bytes}$.
• Page Size: $1\text{ KB} = 2^{10}\text{ bytes}$.
• Number of Pages: $$\text{Number of Pages} = \frac{\text{Virtual Address Space Size}}{\text{Page Size}} = \frac{2^{32}}{2^{10}} = 2^{22}\text{ pages}$$

In a single-level page table, there must be one Page Table Entry (PTE) for every page in the virtual address space.

• Assuming a standard entry size of $4\text{ bytes}$ ($32\text{ bits}$) to store the frame number and control bits, the size of the page table is: $$\text{Page Table Size} = 2^{22} \times 4\text{ bytes} = 16\text{ MB}$$

Since every active process in the system requires its own page table, dedicating $16\text{ MB}$ of contiguous physical memory per process solely for address translation is a massive memory overhead.

Why other options are incorrect:

• Option A: A smaller page size ($1\text{ KB}$) actually reduces internal fragmentation (which is, on average, half of the page size, i.e., $512\text{ bytes}$ per process).
• Option B: Paging completely eliminates external fragmentation.
• Option D: A single-level page table lookup is a simple $O(1)$ array indexing operation, which has minimal computational overhead. Multi-level paging actually increases the translation computation/lookup overhead to save memory.