📄 Page Replacement
LRU, FIFO & Optimal
Step 0 / 0
Policy: FIFO
Policy
Reference string
Controls
Stats
Page faults
0
Hits
0
Hit ratio
0%
Status
Ready
Note
Info & Theory

A page-replacement algorithm decides which page to evict from a fixed set of memory frames when a new page must be loaded. A reference not in a frame is a page fault; one that is already present is a hit.

FIFO

Evict the page loaded earliest, like a queue. Simple, but it ignores usage and can show Bélády's anomaly.

LRU

Evict the least recently used page. It uses recent history as a predictor and is a stack algorithm, so more frames never increase faults.

Clock

A cheap LRU approximation: frames sit on a circle with a reference bit. The hand skips and clears set bits, giving pages a second chance before eviction.

Optimal (Bélády)

Evict the page used furthest in the future. It is the provable minimum-fault policy but needs future knowledge, so it is a benchmark, not a real algorithm.

Bélády's anomaly

For FIFO with the string 1 2 3 4 1 2 5 1 2 3 4 5, going from 3 to 4 frames raises faults from 9 to 10. Load the preset, run with 3 frames, then 4, and watch the fault count rise. LRU and Optimal never do this.

Frequently asked questions

What is a page-replacement algorithm?

A page-replacement algorithm decides which page to evict from physical memory frames when a new page must be loaded and all frames are full. Good choices minimise page faults.

What is a page fault?

A page fault occurs when a referenced page is not currently in a memory frame, so it must be fetched from disk. The fault count is the primary metric for comparing page-replacement policies.

How does FIFO page replacement work?

FIFO (First-In, First-Out) evicts the page that has been in memory the longest, regardless of how often it is used. It is simple but can perform poorly and famously exhibits Bélády's anomaly.

How does LRU page replacement work?

LRU (Least Recently Used) evicts the page that has not been accessed for the longest time, approximating the idea that recently used pages will be used again. It never suffers Bélády's anomaly.

What is the Optimal (Bélády) algorithm?

The Optimal algorithm evicts the page that will not be used for the longest time in the future. It gives the provably minimum number of faults but is unimplementable in practice because it needs to know future references.

What is the Clock algorithm?

Clock (the second-chance algorithm) arranges frames in a circle with a reference bit per page. On a fault the hand advances, clearing reference bits and giving recently used pages a second chance, approximating LRU at lower cost.

What is Bélády's anomaly?

Bélády's anomaly is the surprising case where increasing the number of frames causes FIFO to produce more page faults, not fewer. It violates the intuitive expectation that more memory is always better.

Which algorithms avoid Bélády's anomaly?

Stack algorithms such as LRU and Optimal never suffer Bélády's anomaly, because the set of pages held with n frames is always a subset of the set held with n+1 frames. FIFO and Clock are not stack algorithms.

What is the hit ratio?

The hit ratio is the fraction of references that are already in memory (hits) out of all references. It equals one minus the fault ratio and is a convenient way to compare policy effectiveness.

What is a reference string?

A reference string is the sequence of page numbers a process accesses over time. Page-replacement algorithms are evaluated by running them against the same reference string and counting faults.

About this simulation

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 5 July 2026

This simulator drives a fixed set of memory frames through a user-supplied reference string under four classic page-replacement policies — FIFO, LRU, Clock (second chance), and Bélády's Optimal — animating the frame table one reference at a time and colouring each cell red on a fault. A built-in preset reproduces Bélády's anomaly: the counter-intuitive case where giving FIFO more frames produces more page faults, not fewer.

🔬 What it shows

A frame-by-frame simulation of virtual-memory paging: each column is one reference from the string, each row is a physical frame, hits are marked green and faults red, and the evicted slot is highlighted whenever a fault forces a replacement. Page faults, hits and the resulting hit ratio update live as the animation advances.

🎮 How to use

Pick a policy from the dropdown, edit the reference string or click Randomise, and drag the Frames slider to change how many pages fit in memory at once. Press Play to animate step by step or Step to advance one reference, and click the Bélády's anomaly preset button to load the classic string 1 2 3 4 1 2 5 1 2 3 4 5 with FIFO selected — then compare the fault count at 3 frames versus 4.

💡 Did you know?

Bélády's anomaly, discovered by László Bélády in 1969, was a genuine surprise to early operating-system designers who assumed more memory could never make a caching policy perform worse. It is only possible with non-stack algorithms like FIFO; LRU and Optimal are provably immune because the set of pages held with n frames is always a subset of the set held with n+1 frames.

Frequently asked questions

What exactly does this simulator animate?

It takes the reference string you provide — a sequence of page numbers a process accesses over time — and replays it one reference at a time against a fixed number of memory frames, using whichever page-replacement policy you select. Each column in the frame table represents one reference, each row one physical frame, and every step is marked as either a hit (page already resident) or a fault (page had to be loaded, possibly evicting another).

How do FIFO, LRU, Clock and Optimal differ in this simulation?

FIFO evicts whichever page has been resident longest, tracked with a simple rotating pointer. LRU evicts the page least recently referenced, using a timestamp recorded on every hit. Clock approximates LRU cheaply with a circular reference-bit scan that gives recently touched pages a second chance before eviction. Optimal looks ahead in the reference string and evicts the page whose next use is furthest in the future — the provably best possible choice, though it needs knowledge no real system has.

How do I reproduce Bélády's anomaly in the simulator?

Click the "Bélády's anomaly preset" button, which loads the reference string 1 2 3 4 1 2 5 1 2 3 4 5 and selects FIFO. Run it with the Frames slider at 3, note the fault count, then increase Frames to 4 and run again: FIFO produces 10 faults with 4 frames versus 9 with 3, even though it was given more memory. Switching the policy to LRU or Optimal on the same string shows faults only ever decrease or stay flat as frames increase.

Why can only some algorithms suffer Bélády's anomaly?

LRU and Optimal are "stack algorithms": the set of pages they keep resident with n frames is always a subset of what they would keep with n+1 frames, which mathematically guarantees faults never increase when memory grows. FIFO and Clock do not have this stack property — the specific page a FIFO policy chooses to evict can change in ways that are not simply "keep everything from the smaller-frame case plus one more," which opens the door to anomalous behaviour.

What do hit ratio and page fault count actually measure?

Every reference in the string is classified as a hit (page already in a frame) or a fault (page absent, requiring a load and possibly an eviction). The hit ratio is simply hits divided by total references, and it is the standard way operating-systems textbooks compare replacement policies on the same workload: a higher hit ratio for a given amount of memory means fewer expensive disk fetches.