In optimal page replacement algorithm, information about all future page…
2025
In 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 ________ . (Answer in integer)?
Attempted by 83 students.
Show answer & explanation
Correct answer: 6
Improved solution (modified optimal with 4-reference lookahead):
Rule used: When a page must be replaced, the OS correctly predicts only the current and next 3 page references (a 4-reference window). Among pages currently in frames, evict the page whose next use is farthest inside that 4-reference window. If a page is not used within the window, evict that page.
Access page 1. Frames become [1, -, -]. Page fault (total faults = 1).
Access page 3. Frames become [1, 3, -]. Page fault (total = 2).
Access page 2. Frames become [1, 3, 2]. Page fault (total = 3).
Access page 4. Lookahead window (current + next 3): pages [4, 2, 3, 1]. Next uses of pages in frames: 1 at position 7, 3 at position 6, 2 at position 5 (all inside window). Evict the page used farthest in the window (page 1). Frames become [4, 3, 2]. Page fault (total = 4).
Access page 2. Page 2 is already in frames. Hit (total faults = 4).
Access page 3. Page 3 is in frames. Hit (total faults = 4).
Access page 1. Lookahead window: [1, 2, 4, 3]. Next uses of pages in frames [4, 3, 2]: 4 at position 9, 3 at position 10, 2 at position 8 (all inside window). Evict the page used farthest in the window (page 3). Frames become [4, 1, 2]. Page fault (total = 5).
Access page 2. Page 2 is in frames. Hit (total faults = 5).
Access page 4. Page 4 is in frames. Hit (total faults = 5).
Access page 3. Lookahead window: [3, 1, 4] (sequence ends after these). Pages in frames: [4, 1, 2]. Page 2 is not used inside this window, so evict page 2. Frames become [4, 1, 3]. Page fault (total = 6).
Access page 1. Page 1 is in frames. Hit (total faults = 6).
Access page 4. Page 4 is in frames. Hit (total faults = 6).
Answer: 6
A video solution is available for this question — log in and enroll to watch it.