With 3 initially empty frames, how many page faults does the optimal (OPT) algorithm cause for the reference string 1, 3, 0, 3, 5, 6, 3, 1, 0, 5, 6, 3?
Correct answer C. 7
Explanation
OPT replaces the page whose next use is furthest away. After faults on 1, 3 and 0 and a hit on 3, it faults on 5 (evicting 0), 6 (evicting 5), hits 3 and 1, faults on 0 (evicting 1, never needed again) and 5 (evicting 0), then hits 6 and 3: 7 faults. OPT gives the lowest possible count but needs future knowledge, so it serves as a benchmark.
Answer checked How we write and check questions
Discussion