Page Replacement Algorithm Calculator (FIFO, LRU, Optimal)

When memory is full and a program needs a page that is not loaded, the operating system must choose a page to throw out. The choice decides how many page faults happen. This calculator runs the classic replacement algorithms — FIFO, LRU, Optimal, LFU and Clock (second chance) — on a reference string, shows the frames after every reference with hits and faults, gives the hit ratio, and compares all algorithms for every number of frames, which reveals Belady's anomaly when it occurs.

How to use this tool

1. Type the reference string: the page numbers in the order they are used.
2. Set the number of frames.
3. Choose the algorithm.
4. Read the frame table, the fault count and the comparison by number of frames.

Formula

hit ratio = hits ÷ references · fault ratio = faults ÷ references · faults include the first loads into empty frames

FIFO evicts the page loaded earliest; LRU the page used least recently; Optimal the page whose next use is farthest away (or that is never used again); LFU the page used least often since it was loaded (ties: loaded earliest); Clock goes round the frames clearing reference bits and evicts the first page whose bit is already clear. Every algorithm counts the initial loads as faults, as textbooks do. The comparison table repeats the run for 1 to 12 frames.

Example

With the textbook string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 and 3 frames, LRU gives 12 page faults and 8 hits (40% hit ratio), FIFO gives 15, Clock 14 and Optimal 9 — the lower bound. With the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with 3 frames but 10 with 4: Belady's anomaly.