GATE CS 2025 Set 1 Q44 — Memory Management and Virtual Memory

In the modified optimal page replacement algorithm, when a page fault occurs at time step $t$, the OS only has visibility of the next $4$ page references (from index $t$ to $t+3$, inclusive). It replaces the page in the memory frames whose next reference in this lookahead window is furthest in the future. If a page in the frames is not referenced in this window, its next reference is treated as being at infinity.

Let the reference string be indexed from $1$ to $12$:

$$\begin{array}{r|cccccccccccc} \text{Time } (t) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline \text{Page} & 1 & 3 & 2 & 4 & 2 & 3 & 1 & 2 & 4 & 3 & 1 & 4 \end{array}$$

Let's trace the execution with $3$ initially empty frames:

1. $t = 1$ (Page 1): Page fault. Frames: $\{1\}$
2. $t = 2$ (Page 3): Page fault. Frames: $\{1, 3\}$
3. $t = 3$ (Page 2): Page fault. Frames: $\{1, 3, 2\}$
4. $t = 4$ (Page 4): Page fault.
   • Lookahead window (indices $4$ to $7$): $[4, 2, 3, 1]$
   • Next references of current pages: $2$ is at $t=5$, $3$ is at $t=6$, and $1$ is at $t=7$.
   • Since $1$ is furthest, we replace $1$ with $4$.
   • Frames: $\{4, 3, 2\}$
5. $t = 5$ (Page 2): Hit. Frames: $\{4, 3, 2\}$
6. $t = 6$ (Page 3): Hit. Frames: $\{4, 3, 2\}$
7. $t = 7$ (Page 1): Page fault.
   • Lookahead window (indices $7$ to $10$): $[1, 2, 4, 3]$
   • Next references of current pages: $2$ is at $t=8$, $4$ is at $t=9$, and $3$ is at $t=10$.
   • Since $3$ is furthest, we replace $3$ with $1$.
   • Frames: $\{4, 1, 2\}$
8. $t = 8$ (Page 2): Hit. Frames: $\{4, 1, 2\}$
9. $t = 9$ (Page 4): Hit. Frames: $\{4, 1, 2\}$
10. $t = 10$ (Page 3): Page fault.
    • Lookahead window (indices $10$ to $12$): $[3, 1, 4]$
    • Next references of current pages: $1$ is at $t=11$, $4$ is at $t=12$, and $2$ is not in the window (infinity).
    • Since $2$ is not in the window, we replace $2$ with $3$.
    • Frames: $\{4, 1, 3\}$
11. $t = 11$ (Page 1): Hit. Frames: $\{4, 1, 3\}$
12. $t = 12$ (Page 4): Hit. Frames: $\{4, 1, 3\}$

The total number of page faults that occur during execution is 6.