Project ForgeConsider a computer system with ten physical page frames. The system is provided with an access sequence (a1, a2, ..., a20, a1, a2, ..., a20), where each ai is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out (LIFO) page replacement policy and the optimal page replacement policy is ____.
Explanation
The first pass (a1..a20) causes 20 compulsory faults under ANY policy, ending with frames holding {a1..a9, a20} for both LIFO and Optimal (each new page's fault evicts the immediately-preceding one, since it's never needed again before the second pass). In the second pass, a1..a9 are hits for both (still resident), but they diverge from a10 onward: LIFO's rigid 'evict current stack-top' rule keeps discarding whatever was JUST loaded (evicting a20 first, then chaining a10→a11→...→a19 each replacing the last), causing 11 faults (a10 through a20) and losing a20 (needed again at the very last access) — a real miss at the end. Optimal instead recognizes a1..a9 are now permanently done (no future use) and evicts THOSE first while preserving a20 (needed once more, at the final access), causing only 10 faults (a10 through a19) and a final HIT on a20. LIFO total = 20+11 = 31; Optimal total = 20+10 = 30; difference = 1.
Source: GATE CS 2016 (Session 1 / Set A) (2016)
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.