GATE2025_CS1_Q54

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)

✅ Final Answer:

The correct answer is 6.

🔹 Short Answer:

The problem is solved by tracing the page references and applying the modified optimal replacement rule. The first three references (1, 3, 2) cause 3 faults to fill the empty frames. Subsequently, faults occur for references to pages 4, 1, and 3, requiring replacement. By evicting the page whose next use is furthest in the future within the limited 4-page lookahead window, we get 3 additional faults, totaling 6 page faults.

🔸 Long Answer:

We need to simulate the page replacement process with 3 frames and a limited lookahead of 4 references. When a page fault occurs and all frames are full, we must evict the page that will not be used for the longest time, looking only at the next 4 references in the string (including the current one).

Step-by-Step Trace

The page reference string is: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4

Step	Page Req.	Lookahead Window (4 pages)	Frames Before	Result	Victim	Frames After	Reason for Eviction
1	1	(1, 3, 2, 4)	[ , , ]	Fault	-	[1, , ]	Empty frame available.
2	3	(3, 2, 4, 2)	[1, , ]	Fault	-	[1, 3, ]	Empty frame available.
3	2	(2, 4, 2, 3)	[1, 3, ]	Fault	-	[1, 3, 2]	Empty frame available.
4	4	(4, 2, 3, 1)	[1, 3, 2]	Fault	1	[4, 3, 2]	In window, uses are: 2 (soonest), 3, 1 (latest). Evict 1.
5	2	(2, 3, 1, 2)	[4, 3, 2]	Hit	-	[4, 3, 2]	Page 2 is in memory.
6	3	(3, 1, 2, 4)	[4, 3, 2]	Hit	-	[4, 3, 2]	Page 3 is in memory.
7	1	(1, 2, 4, 3)	[4, 3, 2]	Fault	3	[4, 1, 2]	In window, uses are: 2 (soonest), 4, 3 (latest). Evict 3.
8	2	(2, 4, 3, 1)	[4, 1, 2]	Hit	-	[4, 1, 2]	Page 2 is in memory.
9	4	(4, 3, 1, 4)	[4, 1, 2]	Hit	-	[4, 1, 2]	Page 4 is in memory.
10	3	(3, 1, 4)	[4, 1, 2]	Fault	2	[4, 1, 3]	In window, uses are: 1, 4. Page 2 not used. Evict 2.
11	1	(1, 4)	[4, 1, 3]	Hit	-	[4, 1, 3]	Page 1 is in memory.
12	4	(4)	[4, 1, 3]	Hit	-	[4, 1, 3]	Page 4 is in memory.

Conclusion

By counting the occurrences of "Fault" in the result column, we find there are a total of 6 page faults.

Bibliography:
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts. Wiley. (Chapter 9: Virtual Memory).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.