GATE 2024 CS (CS2) – Question 64
Consider a 32-bit system with 4 KB page size and page table entries of size 4 bytes each (1 KB = $2^{10}$ bytes). The OS uses a 2-level page table with an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation, and uses demand paging for the inner page table (a page of the inner page table is allocated only if it contains at least one valid entry). An active process accesses 2000 unique pages and none are swapped out. After it completes the accesses, let $X$ denote the minimum and $Y$ the maximum number of pages across the two levels of the page table of the process. The value of $X+Y$ is ________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 1028
Explanation
Page size 4 KB $=2^{12}$ bytes and PTE size 4 B, so one page holds $2^{12}/4=1024$ entries. A 32-bit address has $2^{32}/2^{12}=2^{20}$ virtual pages, so the 2-level table has a directory of 1024 entries and inner tables of 1024 entries each (each is exactly one page). One inner table maps 1024 pages $=4$ MB.
**Minimum $X$:** pack the 2000 pages into as few inner tables as possible: $\lceil2000/1024\rceil=2$. Pages in total $=1$ (outer directory) $+\,2=3$.
**Maximum $Y$:** spread the 2000 pages over as many different inner tables as possible. The directory has only 1024 entries, so at most 1024 inner tables can exist: $1+1024=1025$.
$$X+Y=3+1025=\mathbf{1028}.$$