The GATE Grind

GATE 2023 CS – Question 57

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

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

More Memory Management and Virtual Memory questions

All Memory Management and Virtual Memory questions →