Virtual Lab
Log InSign Up

Page Replacement Algorithms Simulator: FIFO, LRU and Optimal

When memory is full and a page that is not loaded is needed (a page fault), the OS must evict a page. FIFO evicts the oldest, LRU the least recently used, and Optimal the one that will not be needed for the longest time (a benchmark that needs the future).

About this simulator

When memory is full and a needed page is not loaded (a page fault), the OS must evict a page. FIFO evicts the oldest, LRU the least recently used and Optimal the one needed furthest in the future. Enter any reference string and number of frames, step through each reference and compare the page-fault counts of all three algorithms.

How it works

  1. Each reference is a hit if the page is already in a frame, otherwise a page fault.
  2. On a fault with all frames full, the algorithm picks a victim: oldest (FIFO), least recently used (LRU) or furthest next use (Optimal).
  3. Hit ratio =hits/references= \text{hits} / \text{references}. FIFO can even get worse with more frames (Belady's anomaly).

Formulas used

  • Hit ratio=hitsreferences\text{Hit ratio} = \dfrac{\text{hits}}{\text{references}}
  • Fault ratio=faultsreferences\text{Fault ratio} = \dfrac{\text{faults}}{\text{references}}

Worked example

For the reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 with 3 frames, FIFO causes 15 page faults, LRU 12 and Optimal 9. For 1,2,3,4,1,2,5,1,2,3,4,5 FIFO gives 9 faults with 3 frames but 10 faults with 4 frames — Belady's anomaly.

Enter these numbers in the simulator above to see every step.

When to use it

  • Checking page-fault counts and hit ratios for operating-systems homework.
  • Demonstrating Belady's anomaly.
  • Comparing realistic LRU with the unattainable Optimal benchmark.

Frequently asked questions

How do you calculate hit ratio in page replacement?

Hit ratio=hitsreferences\text{Hit ratio} = \dfrac{\text{hits}}{\text{references}}. Page-fault ratio=faultsreferences\text{Page-fault ratio} = \dfrac{\text{faults}}{\text{references}}.

What is Belady's anomaly?

A surprising effect where giving FIFO more frames causes more page faults. LRU and Optimal never show it.

Why can't Optimal be used in practice?

It needs to know future page references. It is used as a benchmark to judge other algorithms.