Consider the following two-dimensional array D in the C programming language,…
2023
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 ______ .
Attempted by 58 students.
Show answer & explanation
Correct answer: 4096
Key insight: compute how many pages the array occupies and how the access pattern touches those pages.
The array has 128 × 128 = 16,384 elements. Each page frame holds 512 elements, so the array occupies 16,384 / 512 = 32 pages.
Each page therefore contains 512 / 128 = 4 full rows. For a fixed column i, the inner loop over j visits the 4 elements of a page consecutively, so at most one page fault can occur per page per column (the first access to that page), and the next three accesses to that page are hits.
There are 32 distinct pages touched when processing any single column. Only 30 physical frames are available, so the working set (32 pages) is larger than physical memory.
Because accesses repeat the same sequence of 32 pages for each column, and between two consecutive uses of the same page there are 31 other page references (>30 frames), LRU will evict that page before it is needed again. Therefore each page causes a fault once per column.
Fault count: 32 page faults per column × 128 columns = 32 × 128 = 4,096 total page faults.
Total page faults = 4096.