The GATE Grind

GATE 2024 CS (CS2) – Question 64

Operating System · Memory Management and Virtual Memory · 2 marks · Numerical answer

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}.$$

More Memory Management and Virtual Memory questions

All Memory Management and Virtual Memory questions →