GATE CS 2023 Q.57: Memory Management and Virtual Memory

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 _______.

Your answer

Official answer and solution

Official answer: 4096
From: Official GATE 2023 answer key

Solution

Trace the memory layout of $D[128][128]$ and the column-major access pattern against 30 page frames under LRU.

Array size: $128 \times 128 = 16384$ integer elements stored in row-major order.
Page size: each page frame holds $512$ $512$ elements, which corresponds to exactly $512 / 128 = 4$ $512/128 = 4$ rows of array $D$ $D$ .
- Total pages needed by $D$ : $16384 / 512 = 32$ pages ( $P_0$ to $P_{31}$ ).
- Page $P_k$ contains rows $4k, 4k+1, 4k+2, 4k+3$ .
Memory allocation: 30 physical page frames are allocated ( $30 < 32$ ).
Code access pattern:
The outer loop runs for $i = 0$ to $127$ (columns), and the inner loop runs for $j = 0$ to $127$ (rows), accessing $D[j][i]$ in column-major order.
In each column pass (fixed $i$ $i$ ):
- As $j$ increases from $0$ to $127$ , it accesses row $0$ , then $1, 2, 3$ (all on page $P_0$ ), then rows $4, 5, 6, 7$ (page $P_1$ ), $\dots$ , up to rows $124..127$ (page $P_{31}$ ).
- Thus, every column pass accesses all 32 pages in sequence: $P_0, P_1, P_2, \dots, P_{31}$ .
LRU cache behavior:
Because the working set is 32 pages and the frame buffer holds only 30 pages, by the time $P_{30}$ and $P_{31}$ are accessed, $P_0$ and $P_1$ have been evicted from memory. When the next column pass begins at $P_0$ , it misses, evicting the next oldest page. Thus, every single page access in every column pass results in a page fault!
Total page faults:
Each column pass accesses 32 pages, generating 32 page faults. With 128 column iterations: $\text{Total Page Faults} = 128 \times 32 = 4096$

Final answer

4096

Common trap

Assuming only the first column faults and subsequent columns hit, missing that LRU thrashes completely because $32 > 30$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 57 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source