ITPEC FE Morning April 2019 Question 19
On a virtual memory computer, the number of pages that can be allocated to the real memory is three (3), and the two (2) algorithms of FIFO and LRU are used for selecting the page to be removed. When a page reference string shown below accesses the three (3) pages, which of the following is an appropriate combination of the number of page replacement operations? Here, the three (3) pages are initially empty and filling of an empty page is not considered as a page replacement operation.
1, 3, 2, 1, 4, 5, 2, 3, 4, 5
Explanation
FIFO 3, LRU 6 — FIFO evicts the page loaded earliest; LRU evicts the page whose last reference is oldest, so a hit changes LRU's order but not FIFO's.
References 1, 3, 2 fill the three empty frames, which counts as no replacement.
FIFO (order of loading):
- •1 hit; 4 replaces 1; 5 replaces 3; 2 hit; 3 replaces 2; 4 hit; 5 hit
- •3 replacements
LRU (order of last reference, oldest first: 3, 2, 1 after the hit on 1):
- •4 replaces 3; 5 replaces 2; 2 replaces 1; 3 replaces 4; 4 replaces 5; 5 replaces 2
- •6 replacements
Answer (b)
Why not others:
- •(a) — FIFO 3 is right, but LRU misses on every reference after the hit on 1, giving 6, not 2
- •(c) and (d) — FIFO has three hits in the second half (2, 4, 5), so it makes only 3 replacements, not 4 or 5; their LRU counts are also too low
Key rule: LRU is not always better than FIFO: on a reference string that cycles through more pages than there are frames, LRU evicts exactly the page needed next.
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.