GATE 2025 CS1 Q.54: solution and answer

GATE 2025 · CS1Q.54 · 2 marks · NAT

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)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The process incurs 6 page faults.

Official answer: 6Source: Official answer key, GATE 2025 CS1 (IIT Roorkee)

Number the references $1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4$ as positions $1$ to $12$ . When a fault occurs and all frames are full, look only at the next $4$ references (the current one included). Evict the page whose next use in that window is farthest away, or which does not appear in the window at all.
Positions $1$ , $2$ and $3$ (pages $1, 3, 2$ ) fault into empty frames. That is $3$ faults, and the frames hold ${1, 3, 2}$ .
Position $4$ (page $4$ ) is a fault, making $4$ faults. The window is $4, 2, 3, 1$ , so the resident pages are next used at: page $2$ at position $5$ , page $3$ at position $6$ , page $1$ at position $7$ . Page $1$ is farthest, so evict it. The frames hold ${3, 2, 4}$ .
Positions $5$ and $6$ (pages $2, 3$ ) are hits.
Position $7$ (page $1$ ) is a fault, making $5$ faults. The window is $1, 2, 4, 3$ , so the resident pages are next used at: page $2$ at position $8$ , page $4$ at position $9$ , page $3$ at position $10$ . Page $3$ is farthest, so evict it. The frames hold ${2, 4, 1}$ .
Positions $8$ and $9$ (pages $2, 4$ ) are hits.
Position $10$ (page $3$ ) is a fault, making $6$ faults. Only $3, 1, 4$ remain, so the window is $3, 1, 4$ . Page $2$ does not appear in the window, so evict it. The frames hold ${4, 1, 3}$ .
Positions $11$ and $12$ (pages $1, 4$ ) are hits. The total is $6$ page faults.

KEY IDEA

Simulate optimal replacement with a limited lookahead. On a fault with full frames, evict the page whose next use inside the next 4 references (current included) is farthest, and treat a page absent from that window as farthest of all.

WATCH OUT FOR

Using full future knowledge, as in ordinary optimal replacement, instead of only the 4-reference window. Another slip is forgetting that the window shrinks near the end of the string, and so miscounting which page to evict at position 10.

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 6 Virtual memory questions, with notes

GATE 2025 CS1 Q.54: solution and answer

Answer and solution

More Virtual memory questions