Question

Consider the two-dimensional array D[128][128] in C, stored in row-major order. Each physical page frame holds 512 elements of D. There are 30 physical page frames. The following code executes:

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 this execution is:

Hint:

In C, arrays are row-major. Column-wise traversal causes poor locality, leading to excessive page faults. If the loops were swapped (row-wise), page faults would reduce drastically.

Answer 1

Step 1: Array layout.
- Array size: $128 \times 128 = 16384$ elements.
- Stored in row-major order: elements of $D[0][0..127]$ first, then $D[1][0..127]$, etc.
- Each page holds 512 elements.
Thus, total number of pages $= \frac{16384}{512} = 32$.
Step 2: Access pattern.
The loop order is D[j][i] with $i$ outer, $j$ inner.
So, for fixed $i$, we access $D[0][i], D[1][i], , D[127][i]$.
This means column-wise traversal, but memory is laid out row-wise.
Step 3: Memory jumps.
- Each row has 128 elements.
- Accessing $D[j][i]$ jumps $128$ locations in memory between consecutive $j$.
Thus, we touch 1 element from each row before moving to the next row.
Step 4: Page faults.
- Each page contains $512$ elements $= 4$ rows (since each row has 128 elements).
- There are 32 pages in total.
- Since we are scanning column by column, each column touches all 128 rows. This means we access 128 elements, spread across all 32 pages.
- With only 30 frames available, at least 2 pages must be replaced each time. So, nearly every access causes a page fault.
Step 5: Total.
Number of accesses $= 128 \times 128 = 16384$.
Each access essentially generates a page fault pattern leading to $\approx$ total pages $\times$ columns.
Exact result: $32 \times 128 = 4096$ page faults.
\[ \boxed{4096} \]