GATE CS 2023 Q47 — Memory Management and Virtual Memory

To find the total number of page faults, let us analyze the array layout, page allocation, and the memory access pattern.

1. Array Layout and Page Mapping:

• The array D[128][128] is stored in row-major order and contains $128 \times 128 = 16,384$ integer elements.
• Each physical page frame holds $512$ elements.
• Number of rows per page = $\frac{512 \text{ elements}}{128 \text{ elements/row}} = 4$ rows.
• Thus, the array is divided into $32$ pages:
  • Page $0$ contains rows $0$ to $3$.
  • Page $1$ contains rows $4$ to $7$.
  • $\dots$
  • Page $31$ contains rows $124$ to $127$.

2. Memory Access Pattern:

The nested loops access the array in column-major order: D[j][i].

For any fixed column $i$, as $j$ goes from $0$ to $127$, the pages are accessed in the following sequence: $$\underbrace{0, 0, 0, 0}_{j=0..3}, \underbrace{1, 1, 1, 1}_{j=4..7}, \dots, \underbrace{31, 31, 31, 31}_{j=124..127}$$ This means for each of the $128$ columns, the program accesses pages $0, 1, 2, \dots, 31$ in sequence.

3. Page Fault Analysis (LRU with 30 Frames):

• For the first column ($i = 0$), pages $0$ to $29$ are loaded into the $30$ available frames, causing $30$ page faults.
• When page $30$ is accessed, it replaces page $0$ (LRU). When page $31$ is accessed, it replaces page $1$. This results in $32$ page faults for the first column.
• At the start of the second column ($i = 1$), page $0$ is accessed, which is no longer in memory. It is loaded, replacing page $2$. Next, page $1$ is accessed and loaded, replacing page $3$.
• Because the working set of $32$ pages is larger than the $30$ allocated frames, this cyclic access pattern causes thrashing. Every single distinct page access in every column results in a page fault.

Thus, for each of the $128$ columns, there are exactly $32$ page faults.