Page Replacement Algorithms

When a page fault occurs and no frame is free, the OS must choose a victim page to replace.

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 with 3 frames.

FIFO

Text
Ref:   7  0  1  2  0  3  0  4  2  3  0  3  2
F1:    7  7  7  2  2  2  2  4  4  4  0  0  0
F2:       0  0  0  0  3  3  3  2  2  2  2  2
F3:          1  1  1  1  0  0  0  3  3  3  3
Fault: *  *  *  *     *  *  *  *  *  *
Page faults = 10

Optimal (OPT)

Replace the page that won't be used for the longest time in the future. It gives the minimum possible faults but needs future knowledge, so it's used as a benchmark.

Text
Ref:   7  0  1  2  0  3  0  4  2  3  0  3  2
F1:    7  7  7  2  2  2  2  2  2  2  2  2  2
F2:       0  0  0  0  0  0  4  4  4  0  0  0
F3:          1  1  1  3  3  3  3  3  3  3  3
Fault: *  *  *  *     *     *        *
Page faults = 7

LRU (Least Recently Used)

Text
Ref:   7  0  1  2  0  3  0  4  2  3  0  3  2
F1:    7  7  7  2  2  2  2  4  4  4  0  0  0
F2:       0  0  0  0  0  0  0  0  3  3  3  3
F3:          1  1  1  3  3  3  2  2  2  2  2
Fault: *  *  *  *     *     *  *  *  *
Page faults = 9
Belady's anomalyWith FIFO, adding more frames can sometimes increase page faults. LRU and OPT are stack algorithms and don't suffer from it.
Track your progress through the Operating System course