GATE 2023 CS Q.57: solution and answer

GATE 2023 · CSQ.57 · 2 marks · NAT

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The code generates 4096 page faults.

Official answer: 4096Source: Official answer key, GATE 2023 CS (IIT Kanpur)

Each page frame holds $512$ elements and a row has $128$ elements, so one page holds $512/128 = 4$ rows. The array occupies $128/4 = 32$ pages (taking D to start at a page boundary): page $p$ holds rows $4 p$ to $4 p + 3$ .
In D[j][i] the inner loop changes j, the row index. For a fixed i the references go down a column, through rows $0, 1, 2, \dots, 127$ .
Rows $4 p$ to $4 p + 3$ are on page $p$ , so one pass over j references pages $0, 0, 0, 0, 1, 1, 1, 1, \dots, 31, 31, 31, 31$ . The repeated references inside a block of 4 rows are on a page that was just used, so they are hits.
Every pass over j therefore touches the $32$ pages in the same cyclic order $0, 1, \dots, 31$ , and the next value of i starts again at page $0$ .
LRU with $30$ frames on a cyclic reference of $32$ distinct pages: the first $30$ pages $0$ to $29$ fill the frames. Page $30$ evicts page $0$ and page $31$ evicts page $1$ , so the frames hold $2, \dots, 31$ . The next pass asks for page $0$ , which is a fault and evicts the least recently used page, page $2$ . Page $1$ is then also absent (fault, evicts page $3$ ), and so on. The page that LRU evicts is always the one needed soonest, so every change of page is a fault.
Faults per value of i $= 32$ , one for each page; the other $96$ references in the pass are hits.
Total faults $= 128 \times 32 = 4096$ .

KEY IDEA

The inner loop walks down a column of a row-major array, so it visits all 32 pages in a fixed cyclic order. LRU with fewer frames (30) than pages (32) on a cyclic reference faults on every page change.

WATCH OUT FOR

Assuming the inner loop reads row by row, which would give only 32 faults in total. Another slip is assuming that 30 of 32 frames means most pages stay resident, when LRU on a cycle evicts exactly the page needed next.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 6 Virtual memory questions, with notes

GATE 2023 CS Q.57: solution and answer

Answer and solution

More Virtual memory questions