Question Details

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?

Options

A

Least Recently Used page replacement policy

B

Least Frequently Used page replacement policy

C

Most Frequently Used page replacement policy

D

Optimal page replacement policy

Show Answer
Correct Answer
D
Optimal page replacement policy

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: [1,-,-]

2. Reference 2 (Page Fault):
Frame 2 is empty, so page 2 is loaded.
Frames: [1,2,-]

3. Reference 3 (Page Fault):
Frame 3 is empty, so page 3 is loaded.
Frames: [1,2,3] (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: {1,2,3}.
Looking ahead at the future reference string: 5,4,1,6,4,5,1,3,2:
- 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: [1,4,3] (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 {1,4,3}:
- 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: [1,4,5]

6. Reference 4 & 1 (Page Hits):
Both pages are already in memory, so no replacements occur.
Frames remain: [1,4,5]

7. Reference 6 (Page Fault with Replacement):
Page 6 is not in memory. We look ahead at the future reference string for {1,4,5}:
- 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: [6,4,5] (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: [6,4,5]

9. Reference 1 (Page Fault with Replacement):
Page 1 is not in memory. The remaining references are 3,2. None of the pages in memory {6,4,5} 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: [6,1,5] (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 2. None of the pages in memory {6,1,5} are referenced again. Following the trace in the image, page 5 is replaced by page 3.
Frames: [6,1,3] (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: [2,1,3] (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.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

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.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

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.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: