Project ForgeAssume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is __________.
Explanation
Trace with Belady's optimal algorithm (evict the page used furthest in the future, or never used again): 1→fault{1}; 2→fault{1,2}; 3→fault{1,2,3}; 4→fault, evict 3 (next used furthest away, at position 8, vs 1 at position 6, 2 at position 5) →{1,2,4}; 2→hit; 1→hit; 5→fault, evict 1 (never used again) →{5,2,4}; 3→fault, evict 5 (never used again) →{2,4,3}; 2→hit; 4→hit; 6→fault (any eviction, none used again) →{...,6}. Total faults: 1,2,3,4,5,3,6 = 7 faults.
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.