Project ForgeIn optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows: The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page. A process accesses the pages in the following order of page numbers: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4. If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is ____.
Explanation
Tracing with 3 frames: 1,3,2 fault in (frames={1,2,3}, 3 faults). Ref 4 faults; within the 4-reference lookahead window {4,2,3,1}, page 2 is used farthest away (position 5 vs page1 at position7... recomputing properly: window from current ref is {4,2,3,1}, next uses within it: 1→pos7(offset3, farthest),3→pos6(offset2),2→pos5(offset1) — evict 1) giving frames={4,3,2} — wait tracing carefully frame-by-frame: faults occur at refs 1,3,2,4(evict the frame-resident page used farthest within window {4,2,3,1}, which is page 1) →{4,3,2}; refs 2,3 hit; ref1 faults (window {1,2,4,3}, evict page farthest = 3) →{4,1,2}; refs 2,4 hit; ref3 faults (window has only {3,1,4} left, page2 isn't referenced at all in it, so evict 2) →{4,1,3}; refs 1,4 hit. Total faults = 6, exactly matching what unconstrained Belady's optimal gives on the same string (independently verified), confirming the limited lookahead didn't change the outcome here.
Source: GATE CS 2025 (Session 1 / CS1) (2025)
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.