Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2. The contents of the frames are as follows initially and after each reference (from left to right):
The *-marked references cause page replacements.
Which one or more of the following could be the page replacement policy/policies in use?
Solution :
The correct answer is: Optimal page replacement policy.
Detailed Step-by-Step Analysis:
The Optimal Page Replacement algorithm (also known as MIN or Belady's Optimal algorithm) replaces the page that will not be used for the longest period of time in the future.
Given:
- Number of frames = 3 (initially empty: )
- Page reference string: 1, 2, 3, 4, 5, 4, 1, 6, 4, 5, 1, 3, 2
Let us trace the frame contents step-by-step using the Optimal Page Replacement policy:
1. Reference 1 (Page Fault):
Frame 1 is empty, so page 1 is loaded.
Frames:
2. Reference 2 (Page Fault):
Frame 2 is empty, so page 2 is loaded.
Frames:
3. Reference 3 (Page Fault):
Frame 3 is empty, so page 3 is loaded.
Frames: (This corresponds to column 3 in the image, where the bottom frame is filled with page 3).
4. Reference 4 (Page Fault with Replacement):
Page 4 is not in memory. We must replace one of the active pages in the frames: .
Looking ahead at the future reference string: :
- Page 1 is referenced next at index 7.
- Page 2 is referenced next at index 13.
- Page 3 is referenced next at index 12.
Since page 2 is referenced furthest in the future, it is replaced by page 4.
Frames: (This matches the column under header 5* in the image, where page 4 replaces page 2 in the second row).
5. Reference 5 (Page Fault with Replacement):
Page 5 is not in memory. We look ahead at the future reference string for :
- Page 4 is referenced next (immediately at index 6).
- Page 1 is referenced next at index 7.
- Page 3 is referenced next at index 12.
Since page 3 is referenced furthest in the future, it is replaced by page 5.
Frames:
6. Reference 4 & 1 (Page Hits):
Both pages are already in memory, so no replacements occur.
Frames remain:
7. Reference 6 (Page Fault with Replacement):
Page 6 is not in memory. We look ahead at the future reference string for :
- Page 4 is referenced next at index 9.
- Page 5 is referenced next at index 10.
- Page 1 is referenced next at index 11.
Since page 1 is referenced furthest in the future, it is replaced by page 6.
Frames: (Matches the column under header 6* in the image, where page 6 replaces page 1 in the top row).
8. Reference 4 & 5 (Page Hits):
Both pages are in memory, so no replacements occur.
Frames remain:
9. Reference 1 (Page Fault with Replacement):
Page 1 is not in memory. The remaining references are . None of the pages in memory are referenced again. In case of ties, any page can be replaced. Following the trace in the image, page 4 is replaced by page 1.
Frames: (Matches the column under header 1* in the image, where page 1 replaces page 4).
10. Reference 3 (Page Fault with Replacement):
Page 3 is not in memory. The remaining reference is . None of the pages in memory are referenced again. Following the trace in the image, page 5 is replaced by page 3.
Frames: (Matches the column under header 3* in the image).
11. Reference 2 (Page Fault with Replacement):
Page 2 is not in memory. No remaining references exist. Following the trace, page 6 is replaced by page 2.
Frames: (Matches the final column under header 2* in the image).
Conclusion:
Since the state transitions of the frames and the positions of all page replacements (marked with asterisks ) perfectly match the execution of the Optimal page replacement strategy, the policy in use is the Optimal page replacement policy.
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.
Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.