ITPEC FE Morning October 2022 Question 17
On a computer with virtual memory, the number of blocks in real memory is three (3). One of the two (2) algorithms of FIFO and LFU (least frequently used) is used for selecting the page to be removed from real memory. When five (5) pages are referenced in the page-reference sequence shown below as a string, which of the following is an appropriate combination of the number of page fault operations for each algorithm? Here, the three (3) blocks in the real memory are initially empty.
[Page reference string]
1, 3, 2, 1, 4, 5, 2, 3, 4, 5
Explanation
FIFO 6, LFU 9 — trace both algorithms with three frames.
FIFO evicts the page loaded earliest (F = fault):
LFU evicts the page referenced fewest times, the oldest on a tie. Page 1, referenced twice, is never evicted, so pages 2 to 5 share the other two frames. After 4 arrives (evicting 3), every later reference misses: 5 evicts 2, 2 evicts 4, 3 evicts 5, 4 evicts 2, 5 evicts 3. Only the reference to 1 is a hit: 9 faults.
FIFO alone settles it: only (d) has 6.
Answer (d)
Why not others:
- •(a), (b) and (c) — each contains a count below 5; five different pages are referenced and memory starts empty, so each first reference is a fault and any algorithm has at least 5
Key rule: A page's first reference is always a fault when memory starts empty, so the number of distinct pages is a floor on the fault count for any replacement algorithm.
Software · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.