For the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with 3 page frames (initially empty), which page replacement algorithm produces the minimum number of page faults?

Explanation

Tracing all three frames across the 20 references gives FIFO 15 faults, LRU 12 faults, and the Optimal (Belady's MIN) algorithm — which always evicts the page that will be used farthest in the future — only 9 faults. This is not a quirk of this particular string: Optimal is provably a lower bound on the number of page faults for any reference string and any fixed number of frames, so no realizable algorithm such as FIFO, LRU or LIFO can ever do better. LIFO (replacing the most recently loaded page) performs worst of all here since it keeps evicting pages that are about to be reused. Hence the algorithm guaranteed to give the minimum number of faults is Optimal.