Optimal replacement sounds simple until a trace begins. Mistakes happen when you look backward like LRU, replace a page needed sooner, or forget that filling an empty frame is also a page fault. Three of the six numericals here (Questions 5, 8 and 9) turn on comparing how far ahead each resident page is next needed; in the other three, every eviction is a page that never appears again. The questions come from GATE, ISRO, HTET, UPPSC and DSSSB papers between 2002 and 2025, each printed with its exam and year. Use the broader Page Replacement Algorithms MCQs: 12 solved questions (FIFO, LRU, Optimal) set for comparison, or place this topic within GATE CS Exam Preparation. For every numerical, draw the frame table and commit to an answer before reading the explanation.
1. Optimal page replacement: the farthest-future rule and a trace method
On a fault with full frames, Optimal evicts the resident page whose next use is farthest in the future. A page that never appears again is immediately a valid victim. OPT, also called MIN, therefore gives the theoretical minimum fault count for a fixed reference string, but a real system cannot know the complete future.
Use four columns: reference | frames after access | hit/fault | victim reason. Count initial loads as faults, change nothing on a hit, and write each resident page's next-use position before replacing it. If several pages never return, any of them can go without changing the minimum count.
For Question 10, the trace is:
Reference | Frames after access | Hit/fault | Victim reason |
|---|---|---|---|
4 | 4, -, - | Fault | Empty frame |
7 | 4, 7, - | Fault | Empty frame |
6 | 4, 7, 6 | Fault | Empty frame |
1 | 1, 7, 6 | Fault | 4 never returns |
7, 6, 1 | 1, 7, 6 | Hits | Frames unchanged |
2 | 1, 7, 2 | Fault | 6 never returns |
7, 2 | 1, 7, 2 | Hits | Frames unchanged |
That is 5 faults and 5 hits. Review Page Replacement Algorithms for GATE: FIFO, LRU, Optimal if you need complete comparison traces first.
2. Optimal replacement rule and future-information MCQs 1-4
Question 1
GATE 2002. Solve Question 1 on KnowledgeGate.
The optimal page replacement algorithm will select the page that
A. Has not been used for the longest time in the past.
B. Will not be used for the longest time in the future.
C. Has been used least number of times.
D. Has been used most number of times.
Correct answer: B. Optimal chooses the resident page whose next reference is farthest ahead. A describes LRU, while C and D confuse future distance with reference frequency.
Question 2
HTET 2022. Solve Question 2 on KnowledgeGate.
In _________ page replacement algorithm, the page that will not be used for the longest period of time is replaced whenever a page fault occurs.
A. LRU
B. Optimal
C. FIFO
D. LFU
Correct answer: B. The blank is Optimal because it chooses the farthest future use. LRU follows oldest past use, FIFO follows arrival order, and LFU follows the smallest access count.
Question 3
ISRO 2008. Solve Question 3 on KnowledgeGate.
The page replacement algorithm which gives the lowest page fault rate is
A. LRU
B. FIFO
C. Optimal page replacement
D. Second chance algorithm
Correct answer: C. Optimal postpones the next avoidable fault as much as possible by removing the page used farthest ahead. The other algorithms use queue or history information, so they cannot guarantee the minimum for every fixed reference string.
Question 4
UPPSC Polytechnic Lecturer 2018. Solve Question 4 on KnowledgeGate.
Which of the following page replacement algorithms requires futuristic information about page references?
A. FIFO
B. LRU
C. Second chance
D. Optimal
Correct answer: D. Optimal needs the future sequence to rank every resident page's next use. FIFO needs insertion order, LRU needs recent history, and Second Chance adds a reference bit to FIFO.
3. Three-frame Optimal traces MCQs 5-6
Question 5
GATE 2014, Set 1. Solve Question 5 on KnowledgeGate.
Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is__________.
This one is answered as an integer, not by picking an option.
Correct answer: 7. References 1, 2, 3 cause the first three faults. At 4, evict 3, whose next use is later than those of 2 and 1; 2, 1 then hit. At 5, evict 1, which never returns, and at 3, evict 5, which never returns; 2, 4 hit before the final 6 produces fault seven.
Question 6
GATE 2007. Solve Question 6 on KnowledgeGate.
A process has been allocated 3 page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): 1, 2, 1, 3, 7, 4, 5, 6, 3, 1 If optimal page replacement policy is used, how many page faults occur for the above reference string?
A. 7
B. 8
C. 9
D. 10
Correct answer: A, 7. The first 1, 2, and 3 fault, while the second 1 hits. At 7, evict 2 because it never returns; faults on 4, 5, and 6 can successively remove pages that never return while preserving 1 and 3. The final 3, 1 hit, leaving the count at 7.
4. Longer Optimal page-fault traces MCQs 7-8
Question 7
ISRO 2017. Solve Question 7 on KnowledgeGate.
Given reference to the following pages by a program 0, 9, 0, 1, 8, 1, 8, 7, 8, 7, 1, 2, 8, 2, 7, 8, 2, 3, 8, 3 How many page faults will occur if the program has three page frames available to it and uses an optimal replacement?
A. 7
B. 8
C. 9
D. None of these
Correct answer: A, 7. Faults occur on 0, 9, 1, 8, 7, 2, 3. At 8, evict 0; at 7, evict 9; at 2, evict 1; and at 3, evict 7, since each named victim never returns after that point. The other 13 references hit.
Question 8
ISRO 2025. Solve Question 8 on KnowledgeGate.
Consider the following reference strings and assume 3 frames are available, then the number of page faults that occur using Optimal page replacement algorithm is 6, 0, 5, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 5, 2
A. 15 Page Faults
B. 9 Page Faults
C. 12 Page Faults
D. 8 Page Faults
Correct answer: D, 8 Page Faults. Faults land on 6, 0, 5, 2, 3, 4, 0, 5. This is the one string where two victims are settled by comparing future distances rather than by spotting a page that never returns, which is what makes it harder than its length suggests. The full trace, in the four columns from section 1:
Reference | Frames after access | Hit/fault | Victim reason |
|---|---|---|---|
6 | 6, -, - | Fault | Empty frame |
0 | 6, 0, - | Fault | Empty frame |
5 | 6, 0, 5 | Fault | Empty frame |
2 | 2, 0, 5 | Fault | 6 never returns |
0 | 2, 0, 5 | Hit | No change |
3 | 2, 0, 3 | Fault | 5 next at 14, against 0 at 7 and 2 at 9 |
0 | 2, 0, 3 | Hit | No change |
4 | 2, 4, 3 | Fault | 0 next at 11, against 2 at 9 and 3 at 10 |
2, 3 | 2, 4, 3 | Hits | No change |
0 | 2, 0, 3 | Fault | 4 never returns |
3, 2 | 2, 0, 3 | Hits | No change |
5 | 2, 5, 3 | Fault | 0 never returns |
2 | 2, 5, 3 | Hit | No change |
Eight faults across fifteen references, so seven accesses hit.
5. Limited lookahead and compact three-frame trace MCQs 9-10
Question 9
GATE 2025, Set 1. Solve Question 9 on KnowledgeGate.
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)?
This one is also answered as an integer.
Correct answer: 6. The first 1, 3, 2 fill the frames. At 4, window [4, 2, 3, 1] makes 1 the farthest resident use; at the later 1, window [1, 2, 4, 3] makes 3 farthest. At the later 3, page 2 is absent from the remaining window [3, 1, 4], so the three initial fills plus these three replacements produce 6 faults.
Question 10
DSSSB 2021. Solve Question 10 on KnowledgeGate.
Consider a main memory with the capacity of 3 page frames which are initially empty. Page reference is: 4, 7, 6, 1, 7, 6, 1, 2, 7, 2. What is the number of page faults using the optimal page replacement algorithm?
A. 7
B. 6
C. 5
D. 4
Correct answer: C, 5. Loading 4, 7, 6 costs three faults, then 1 replaces 4 and 2 replaces 6, neither of which appears again. Section 1 traces this string column by column.
6. Optimal Replacement answer audit and common traps
Question | Correct answer | Fault count or decisive rule | Main trap |
|---|---|---|---|
Q1 | B | Farthest future use | future versus past |
Q2 | B | Optimal | algorithm-name confusion |
Q3 | C | Minimum-fault benchmark | benchmark versus approximation |
Q4 | D | Needs future references | why OPT is not implementable |
Q5 | 7 | 7 faults | count initial fills |
Q6 | A (7) | 7 faults | LRU on this string gives 9, not 7 |
Q7 | A (7) | 7 faults | the repeated 0, 8 and 7 accesses are hits, not faults |
Q8 | D (8) | 8 faults | two victims chosen by distance, not by absence |
Q9 | 6 | 6 faults | bounded lookahead is not full clairvoyance |
Q10 | C (5) | 5 faults | never-used-again victim |
Now recompute Questions 5, 7 and 9 from blank tables. Your written fault positions must agree with your final count, and the eviction you were least sure about is the one to redo first.
7. Where these Optimal Replacement MCQs fit, and the next step
A low score on Questions 1 to 4 points to a concept gap. A low score on the numericals usually points to trace discipline rather than missing knowledge, and the fix is writing next-use positions down instead of holding them in your head.
Before your next attempt:
Mark hits before considering eviction.
Count the first fill.
Write each resident page's next use.
Prefer a page that never returns.
Total faults only after the final reference.
Use GATE Guidance by Sanchit Sir for a sequenced Operating System study route, then use GATE Test Series for timed subject-wise practice.
