Consider the virtual page reference string 1, 2, 3, 2, 4, 1, 3, 2, 4, 1 on a…
2012
Consider the virtual page reference string
1, 2, 3, 2, 4, 1, 3, 2, 4, 1
on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then
Answer: B. OPTIMAL < FIFO < LRU — Answer: OPTIMAL < FIFO < LRU. Page-fault counts: OPTIMAL = 5, FIFO = 6, LRU = 9. OPTIMAL (5 faults): Load 1,2,3 (three faults). When 4 appears evict the page…
- A.
OPTIMAL < LRU < FIFO
- B.
OPTIMAL < FIFO < LRU
- C.
OPTIMAL = LRU
- D.
OPTIMAL = FIFO
Attempted by 69 students.
Show answer & explanation
Correct answer: B
Answer: OPTIMAL < FIFO < LRU.
Page-fault counts: OPTIMAL = 5, FIFO = 6, LRU = 9.
OPTIMAL (5 faults): Load 1,2,3 (three faults). When 4 appears evict the page whose next use is farthest (evict 2), and later evict 3 which is not used again; total 5 faults.
FIFO (6 faults): Load 1,2,3 (three faults). FIFO evicts the oldest loaded page when 4 arrives (evict 1), then later causes faults when 1 and 2 are reloaded — total 6 faults.
LRU (9 faults): Many references become faults because the least-recently-used page is often not the best choice to keep for future accesses; counting misses gives faults at positions 1,2,3,5,6,7,8,9,10 = 9 faults.
Therefore the correct ordering is OPTIMAL < FIFO < LRU.
A video solution is available for this question — log in and enroll to watch it.