Consider the following program fragment that deals with a table T with 17 rows…
2023
Consider the following program fragment that deals with a table T with 17 rows and 1024 columns, computing an average for each column and printing it to screen (i is row index and j is column index):
for j = [0 … 1023] {
temp = 0
for i = [0 … 16] {
temp = temp + T[i][j]
}
print (temp / 17.0);
}
T[i][j] and temp are 32-bit floating point values and memory is word addressable.
The temporary variable temp is kept in a processor register, so access to temp does not involve a memory reference.
The main memory is paged and holds 16 pages of size 1024 words.
The page replacement policy is Least Recently Used (LRU).
If T is stored in the virtual address space in row-major format, how many page faults will be encountered?
- A.
16,402
- B.
17,408
- C.
18,208
- D.
18,608
Attempted by 4 students.
Show answer & explanation
Correct answer: B
Concept: In a paged system with a fixed number of frames, if a program cyclically re-references a set of N distinct pages using only C page frames where C is less than N, then under LRU (or FIFO) every reference after the first pass becomes a page fault: by the time any page is revisited, all C frames have already been reloaded with the other N−1 pages, so the required page is never still resident.
Application: The page size is 1024 words, which is exactly the row length (1024 columns), so each of the 17 rows of T occupies one full page in row-major storage (taking the array as stored starting at a page boundary — the standard reading here, since the row length is deliberately made equal to the page size) — 17 distinct pages in total. For a fixed column j, the inner loop touches T[0][j] through T[16][j], i.e. it visits all 17 row-pages once, in the same fixed order (0,1,2,...,16), and this identical order repeats for every column from j=0 to j=1023. Tracing the access sequence with only 16 available frames under LRU:
Steps 1–16 of the first column (rows 0 to 15): each row-page is loaded for the first time — 16 compulsory faults, filling all 16 frames.
Step 17 of the first column (row 16): this page is not resident; the frames are full, so LRU evicts the least-recently-used page (row 0, touched longest ago) to load row 16 — a fault.
Step 1 of the second column (row 0 again): row 0 was just evicted, so this is a fault too; LRU now evicts row 1 (the next-oldest) to load row 0.
This pattern continues indefinitely: each row is evicted exactly one step before it is needed again, because between any two visits to the same row, all 16 other rows are always touched first — filling every available frame and displacing it.
Since every reference from step 17 onward is also a fault, the fault rate for the whole loop is 100%. The total number of memory references made to T equals the number of times T[i][j] is read, since temp is held in a processor register and never causes a memory access. Therefore, total page faults = total references to T = 17 × 1024.
Cross-check: This matches the known worst case for LRU (and FIFO) on a cyclic reference string of length C+1 over a cache of only C frames — because the working set per cycle (17 pages) exceeds the number of frames (16) by exactly one, no page can ever survive to be reused, so the miss rate is unavoidably 100%; no option larger than the total number of references to T is even possible, since page faults cannot exceed the number of memory references made.
Answer: 17,408.