The GATE Grind

GATE 2025 CS (CS1) – Question 54

Operating System · Memory Management and Virtual Memory · 2 marks · Numerical answer

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.

RefFrames afterFault?Reason
1, 3, 21 3 23 faultsframes start empty
44 3 2faultwindow 4,2,3,1: next use of 1 is farthest → evict 1
2, 34 3 2hits
14 1 2faultwindow 1,2,4,3: next use of 3 is farthest → evict 3
2, 44 1 2hits
34 1 3faultwindow 3,1,4: page 2 is not used → evict 2
1, 44 1 3hits

Total faults $=3+1+1+1=\mathbf{6}$.

More Memory Management and Virtual Memory questions

All Memory Management and Virtual Memory questions →