GATE 2023 CS – Question 57
Consider the following two-dimensional array D in the C programming language, which is stored in row-major order: int D[128][128]; Demand paging is used for allocating memory and each physical page frame holds 512 elements of the array D. The Least Recently Used (LRU) page-replacement policy is used by the operating system. A total of 30 physical page frames are allocated to a process which executes the following code snippet:
for (int i = 0; i < 128; i++)
for (int j = 0; j < 128; j++)
D[j][i] *= 10;The number of page faults generated during the execution of this code snippet is ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 4096
Explanation
$D$ is $128\times128$ ints stored row by row. A page frame holds 512 elements $=4$ rows. So the array occupies $\dfrac{128}{4}=32$ pages.
The loop accesses `D[j][i]` with `j` in the inner loop, i.e. **down a column**. For fixed $i$, $j=0,\dots,127$ visits rows $0$–$127$: row $r$ is in page $\lfloor r/4\rfloor$. So the inner loop touches pages $0,0,0,0,1,1,1,1,\dots,31$: it moves through all 32 pages in order, and each page is used 4 times in a row.
With only **30 frames** and LRU, the 32 pages cycle through memory: when page 30 is needed, the least recently used pages (0 and 1) are evicted, and so on, so every new page is a fault. Each value of $i$ therefore causes 32 faults.
$$128\times32=\mathbf{4096}\text{ page faults}.$$