GATE 2025 CS (CS1) – Question 54
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)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 6
Explanation
Reference string: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4 with 3 frames. At a fault the OS looks only at the **next 4 references including the current one**; it evicts the resident page that is not used in that window, or whose use is the farthest in it.
| Ref | Frames after | Fault? | Reason |
|---|---|---|---|
| 1, 3, 2 | 1 3 2 | 3 faults | frames start empty |
| 4 | 4 3 2 | fault | window 4,2,3,1: next use of 1 is farthest → evict 1 |
| 2, 3 | 4 3 2 | hits | |
| 1 | 4 1 2 | fault | window 1,2,4,3: next use of 3 is farthest → evict 3 |
| 2, 4 | 4 1 2 | hits | |
| 3 | 4 1 3 | fault | window 3,1,4: page 2 is not used → evict 2 |
| 1, 4 | 4 1 3 | hits |
Total faults $=3+1+1+1=\mathbf{6}$.