GATE CS 2025 Set 1 Q.54: Memory Management and Virtual Memory

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)

Your answer

Official answer and solution

Official answer: 6
From: Official GATE 2025 answer key

Solution

Simulate the 3-frame page table step-by-step, using the 4-reference lookahead window (starting at the faulting reference) to evict the page whose next use is farthest or absent in that window.

Tracing the 12 page references 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4 with 3 initially empty frames:

Ref 1 (1): Miss (Fault #1) $\to$ Frames: {1}
Ref 2 (3): Miss (Fault #2) $\to$ Frames: {1, 3}
Ref 3 (2): Miss (Fault #3) $\to$ Frames: {1, 3, 2}
Ref 4 (4): Miss (Fault #4). The next 4 references (including current) are [4, 2, 3, 1]. Among {1, 3, 2}, 2 appears next at step 5, 3 at step 6, and 1 last at step 7 $\implies$ evict 1. Frames: {4, 3, 2}.
Ref 5 (2): Hit!
Ref 6 (3): Hit!
Ref 7 (1): Miss (Fault #5). The next 4 references (including current) are [1, 2, 4, 3]. Among {4, 3, 2}, 2 appears at step 8, 4 at step 9, and 3 last at step 10 $\implies$ evict 3. Frames: {4, 1, 2}.
Ref 8 (2): Hit!
Ref 9 (4): Hit!
Ref 10 (3): Miss (Fault #6). The remaining references are [3, 1, 4]. Among {4, 1, 2}, page 2 is not referenced again $\implies$ evict 2. Frames: {4, 1, 3}.
Ref 11 (1): Hit!
Ref 12 (4): Hit!

Total number of page faults $= 6$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 54 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source