Optimal Replacement
Chapter Eighty-Six
Syllabus topic Module 2, "Virtual Memory Management - Page Replacement: Optimal"
Pages 345 to 347 of 452
In one line
Throw out the page that will not be needed for the longest time to come, which gives the fewest possible faults and cannot be implemented because it needs the future.
The rule
Replace the page that will not be used for the longest time. Among the resident pages, look forward through the rest of the reference string; the victim is the one whose next use is furthest away, and a page that is never used again is the best victim of all.
It is provably the best possible. No algorithm can have a lower fault rate on the same string with the same number of frames. That is why it is called optimal, and it is also called MIN and OPT in the literature.
And it cannot be implemented, because at the moment of the fault the operating system does not know what the program will do next. A program's future references are not knowable in general: they depend on its input.
So what is it for
Two real uses, and a question sometimes asks exactly this.
| Use | How |
|---|---|
| a yardstick | run the real algorithm and the optimal one on the same recorded reference string, and the gap is how much there is left to win |
| a bound in an argument | if optimal takes nine faults, no algorithm anybody invents will take eight |
The comparison this chapter sets up: on the string below, optimal takes 9 faults and FIFO takes 15. FIFO is therefore doing two thirds again as much work as the best possible, and Chapter eighty seven's LRU comes in between at 12.
Worked on the standard string
The same twenty references and the same three frames as Chapter eighty five.
Replacement: optimal, 3 frames
Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
| Reference | Frame 1 | Frame 2 | Frame 3 | Fault | Evicted |
|---|---|---|---|---|---|
| 7 | 7 | F | |||
| 0 | 7 | 0 | F | ||
| 1 | 7 | 0 | 1 | F | |
| 2 | 2 | 0 | 1 | F | 7 |
| 0 | 2 | 0 | 1 | H | |
| 3 | 2 | 0 | 3 | F | 1 |
| 0 | 2 | 0 | 3 | H | |
| 4 | 2 | 4 | 3 | F | 0 |
| 2 | 2 | 4 | 3 | H | |
| 3 | 2 | 4 | 3 | H | |
| 0 | 2 | 0 | 3 | F | 4 |
| 3 | 2 | 0 | 3 | H | |
| 2 | 2 | 0 | 3 | H | |
| 1 | 2 | 0 | 1 | F | 3 |
| 2 | 2 | 0 | 1 | H | |
| 0 | 2 | 0 | 1 | H | |
| 1 | 2 | 0 | 1 | H | |
| 7 | 7 | 0 | 1 | F | 2 |
| 0 | 7 | 0 | 1 | H | |
| 1 | 7 | 0 | 1 | H |
Page faults: 9
Hits: 11
Nine faults and eleven hits.
hit ratio = 11 / 20 = 0.55
fault rate = 9 / 20 = 0.45
Optimal Replacement
How to do it in the hall
The method is mechanical, and writing the three distances down is what stops the mistakes.
| Step | What to do |
|---|---|
| 1 | at a fault, list the pages in the frames |
| 2 | for each, look forward in the string and write down how many references away its next use is |
| 3 | evict the one with the largest distance; a page that never appears again has an infinite distance and wins |
| 4 | if two are never used again, either may go: the fault count is the same |
Work the fourth reference of the table above as the example. The frames hold 7, 0 and 1, and the reference is 2. Looking forward from there: 0 is used at the very next reference, 1 is used much later, and 7 is not used again until the last three references. So 7 is the victim, which is what the table shows.
Look forward, never backward. Optimal is about the future; the algorithm that looks backward is LRU, and it is the next chapter. Writing the previous uses down by mistake is the commonest way to lose the marks in this question.
Optimal is a stack algorithm
Chapter eighty five needed this property to explain why FIFO can get worse with more memory. Optimal has it, so it never can.
On Chapter eighty five's anomaly string, optimal at one to six frames gives:
Faults: frames 1 to 6
Reference string: 1 2 3 4 1 2 5 1 2 3 4 5
| Frames | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Optimal | 12 | 9 | 7 | 6 | 5 | 5 |
| FIFO | 12 | 12 | 9 | 10 | 5 | 5 |
Never rising. FIFO on the same string went 12, 12, 9, 10, 5, 5, and the rise from 9 to 10 is the anomaly.
Distinctions that carry marks
| Optimal | FIFO | |
|---|---|---|
| Looks | forward | at arrival order |
| Needs | the future, so it cannot be built | a queue |
| Fault rate | the lowest possible | high |
| Belady's anomaly | impossible | possible |
| On the standard string, 3 frames | 9 faults | 15 faults |
| Optimal | LRU, Chapter eighty seven | |
|---|---|---|
| Direction | the next use | the last use |
| Implementable | no | yes, with hardware help |
| Relationship | the ideal | the mirror image: LRU assumes the recent past predicts the near future |
What it does not mean
Optimal is not the best algorithm to use. It is the best result any algorithm could get. It cannot be used at all.
It is not clairvoyance about the program's data. It is defined on a given reference string; that is why it can be computed afterwards from a recording and not while the program runs.
Zero faults is not what optimal means. The first reference to a page must always fault, so on the standard string even optimal pays six faults for the six distinct pages; its nine is six unavoidable faults and three more.
Optimal Replacement
A tie does not change the answer. When two resident pages are never used again, either choice gives the same total.
Quick revision
- Optimal replaces the page whose next use is furthest in the future, and a page never used
again first of all.
- It has the lowest possible fault rate, which is why it is the yardstick, and it
cannot be implemented because the future is unknown.
- On the standard string with three frames: 9 faults, 11 hits, a hit ratio of
11 / 20 = 0.55, against FIFO's 15 faults.
- Method: at each fault, write the forward distance of each resident page and evict the
largest.
- Look forward. Looking backward is LRU.
- Optimal is a stack algorithm: on the anomaly string it gives 12, 9, 7, 6, 5, 5 as frames
rise, never more faults with more frames.
- Its floor is the number of distinct pages: six of its nine faults on the standard string
are first references.
Test yourself
- State the optimal rule. Replace the resident page that will not be used for the longest
time to come.
- Why is it called optimal, and why can it not be used? No algorithm can fault less on the
same string with the same frames; and it needs to know the program's future references, which the operating system cannot.
- What are its two real uses? As a yardstick against which a real algorithm is measured on a
recorded reference string, and as a bound in an argument about what any algorithm could achieve.
- Work optimal on 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with three frames. Nine faults and
eleven hits, a hit ratio of 0.55. 5. At the fourth reference the frames hold 7, 0 and 1 and page 2 is wanted. Which page goes, and why? Page 7: 0 is needed at the very next reference and 1 later, but 7 is not needed again until near the end, so its forward distance is the largest.
- Can optimal show Belady's anomaly? No: it is a stack algorithm, and on the anomaly string
its faults fall steadily as frames rise.
- Why can optimal not reach zero faults? Every page must be brought in the first time it is
referenced, so the number of distinct pages is a floor.
- How does optimal relate to LRU? LRU is its mirror image: optimal looks forward to the next
use, LRU looks back to the last use and assumes the recent past predicts the near future.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.