Virtual Memory
Page Repalcement Algorithm
OPT

OPT

What it does

Replace the page that will not be used for the longest time in the future This gives the minimum number of page faults possible

How it works

  • On page fault, look ahead in the reference string.
  • Remove the page that will not be needed for the longest time

Pros

  • Best possible performance
  • Used as a benchmark

Cons

Not implementable in practice (you can’t predict future references).

Example

Same reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Frames: 3

StepPageFramesPage Fault?Explanation
177 _ _✅Load 7
207 0 _✅Load 0
317 0 1✅Load 1
420 1 2✅ (7 out)7 used never again
500 1 2❌Already in
630 2 3✅ (1 out)1 used far later
700 2 3❌In memory
840 3 4✅ (2 out)2 used soon, but 2 is best to evict here
920 3 2✅ (4 out)4 used never again
1030 3 2❌In memory
1100 3 2❌In memory
1230 3 2❌In memory
1320 3 2❌In memory
  • Total Page Faults: 9
Last updated on
FIFOLRU