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: Page-wise organization of the array

The array has 128 × 128 = 16,384 elements and is stored in row-major order.

Each page holds 512 elements, so:

16,384 / 512 = 32 pages

Since each row contains 128 elements, one page contains:

512 / 128 = 4 complete rows

---

Step 2: Observe how pages are grouped

Rows are grouped into pages as follows:

• Page 0 → Rows 0–3
• Page 1 → Rows 4–7
• …
• Page 31 → Rows 124–127

Thus, every column element from rows 0–127 spans all 32 pages.

---

Step 3: Analyze one column access

For a fixed column index i, the loop accesses:

D[0][i], D[1][i], … , D[127][i]

This results in exactly one access per page, because each page contributes 4 rows.

Hence, one column access touches 32 distinct pages.

---

Step 4: Effect of limited frames

The system has only 30 page frames, which is fewer than the 32 pages needed for one column.

Therefore, during column access, pages cannot all remain resident, and page replacement occurs continuously.

As a result, each column causes 32 page faults.

---

Step 5: Compute total page faults

There are 128 columns in total.

Total page faults = 128 × 32 = 4096

---

Final Answer:

4096