ToolSphere

Page Replacement Calculator

Computer science

Page faults for FIFO, LRU, Optimal, LFU, MFU and Second Chance: a frame table, the reason for every replacement, and a Belady's anomaly check.

Page replacement calculator

Type the page reference string and the number of frames. You get the page faults (a page that was not in memory) and hits for FIFO, LRU, Optimal, LFU, MFU and Second Chance, frame by frame, with the reason for every replacement.

15 page faults with FIFO and 3 frames. A fault means the requested page must be loaded into memory.

References
20
Page faults
15 (75.0%)
Page hits
5
Hit ratio
25.0%

Frame table (FIFO (First-In First-Out))

Reference70120304230321201701
Frame 177722224440000000777
Frame 2–0000333222221111100
Frame 3––111100033333222221
ResultFFFFHFFFFFFHHFFHHFFF
Evicted701230423012

F = page fault, H = hit. Highlighted cells show the page loaded on that fault.

Step-by-step working

  1. Step 17Fault: 7 is loaded into empty frame 1.
  2. Step 20Fault: 0 is loaded into empty frame 2.
  3. Step 31Fault: 1 is loaded into empty frame 3.
  4. Step 42Fault: 7 is replaced in frame 1 because it has been in memory longest (loaded at step 1).
  5. Step 500 is already in frame 2: hit.
  6. Step 63Fault: 0 is replaced in frame 2 because it has been in memory longest (loaded at step 2).
  7. Step 70Fault: 1 is replaced in frame 3 because it has been in memory longest (loaded at step 3).
  8. Step 84Fault: 2 is replaced in frame 1 because it has been in memory longest (loaded at step 4).
  9. Step 92Fault: 3 is replaced in frame 2 because it has been in memory longest (loaded at step 6).
  10. Step 103Fault: 0 is replaced in frame 3 because it has been in memory longest (loaded at step 7).
  11. Step 110Fault: 4 is replaced in frame 1 because it has been in memory longest (loaded at step 8).
  12. Step 1233 is already in frame 3: hit.
  13. Step 1322 is already in frame 2: hit.
  14. Step 141Fault: 2 is replaced in frame 2 because it has been in memory longest (loaded at step 9).
  15. Step 152Fault: 3 is replaced in frame 3 because it has been in memory longest (loaded at step 10).
  16. Step 1600 is already in frame 1: hit.
  17. Step 1711 is already in frame 2: hit.
  18. Step 187Fault: 0 is replaced in frame 1 because it has been in memory longest (loaded at step 11).
  19. Step 190Fault: 1 is replaced in frame 2 because it has been in memory longest (loaded at step 14).
  20. Step 201Fault: 2 is replaced in frame 3 because it has been in memory longest (loaded at step 15).

Total: 15 page faults and 5 hits out of 20 references. Fault ratio = 15/20 = 75.0%.

Compare algorithms (3 frames)

AlgorithmFaultsHit ratio
1525.0%
1240.0%
fewest955.0%
1335.0%
1525.0%
1145.0%

Faults vs frames (FIFO)

Frames123456
Faults2015151096

No Belady's anomaly for this string, but FIFO is not a stack algorithm, so it can happen. Load the Belady example to see FIFO get worse with more frames.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Page Replacement Calculator

  1. 1Enter the page reference string, separated by spaces or commas.
  2. 2Set the number of frames and choose FIFO, LRU, Optimal, LFU, MFU or Second Chance (Clock).
  3. 3Read the frame table and the step-by-step working, which says why each page was replaced, the way an exam answer should.
  4. 4Compare every algorithm's faults on the same string, and check the faults-vs-frames row for Belady's anomaly.

About Page Replacement Calculator

FIFO, LRU, and Optimal: Three Different Bets on the Future

When physical memory frames are full and a new page needs to be loaded, an operating system must evict something — page replacement algorithms are really different strategies for guessing which page is safest to remove. FIFO evicts whichever page has been in memory longest, regardless of how recently or often it's been used — simple to implement, but can evict a heavily-used page purely because it happened to load first.

LRU (Least Recently Used) evicts the page that hasn't been accessed in the longest time, on the reasonable assumption that recent access predicts near-future access — this generally performs better than FIFO but requires tracking access recency, which has real implementation overhead. Optimal evicts whichever page won't be needed again for the longest time in the future — provably the best possible strategy, but requires knowing the future reference sequence in advance, making it purely a theoretical benchmark other algorithms are measured against, not something implementable in a real running system.

Comparing hit/miss counts across all three on the identical reference string is exactly how operating systems courses illustrate why LRU's added complexity is usually worth it over FIFO's simplicity.

Worked example

The classic 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 gives:

  • FIFO: 15 page faults and 5 hits (25% hit ratio)
  • LRU: 12 page faults and 8 hits (40% hit ratio)
  • Optimal: 9 page faults and 11 hits (55% hit ratio)

Optimal is the lower bound that no real algorithm can beat, and LRU lands between it and FIFO.

Belady's anomaly

With the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO makes 9 faults with 3 frames but 10 faults with 4 frames: more memory, more faults. LRU and Optimal are stack algorithms, so adding frames never increases their faults (LRU goes from 10 faults to 8 on the same string). Load the Belady example to see it in the faults-vs-frames row.

LFU, MFU and Second Chance

LFU evicts the page referenced the fewest times since it was loaded; MFU evicts the one referenced the most, on the theory that a heavily used page has finished its work. Both need a tie-break, and this calculator uses loading order (the oldest of the tied pages goes), the usual exam convention. A page's count restarts at 1 each time it is loaded again. On the classic string with 3 frames, LFU makes 13 faults and MFU 15.

Second Chance (the Clock algorithm) is FIFO with a reference bit per frame. A hit sets the bit to 1. On a fault the clock hand sweeps the frames: a page with bit 1 gets a second chance (its bit is cleared and the hand moves on), and the first page with bit 0 is replaced. A newly loaded page starts with bit 0. The table shows every frame's bit after each step, and the working names each page that was spared. Some textbooks start a new page at bit 1 instead, which can change the count, so check which rule your course uses.

Showing your working

Exams give marks for the working, not just the fault count. The step-by-step list gives one line per reference, for example: "Fault: 7 is replaced in frame 1 because it is the least recently used (last used at step 1)". Copy that reasoning alongside the frame table.

Where this fits

Page replacement decides which page leaves RAM when a new one is needed. The same question comes up one level up, between cache and RAM, in the cache mapping calculator, and one level down, when a process first asks for memory, in the memory allocation calculator (first, best, worst and next fit). The rest of the operating-systems toolkit covers CPU scheduling and disk scheduling.

Guides and tutorials

Frequently asked questions

Why can FIFO perform worse than expected, sometimes even getting worse with more memory frames?

This counterintuitive behavior is called Belady's Anomaly — FIFO can, in specific reference patterns, produce more page faults with more available frames, a flaw LRU and Optimal don't share.

Why is the Optimal algorithm not actually usable in a real operating system?

It requires knowing the complete future sequence of page references in advance, which is impossible for a running system — it exists purely as a theoretical best-case benchmark to measure real algorithms against.

Why does LRU generally outperform FIFO?

LRU evicts based on actual usage recency, which correlates with likely near-future access far better than FIFO's arrival-order-only criterion — it costs more to track but usually pays for itself in fewer page faults.

How do you calculate the hit ratio and page fault rate?

Hit ratio = hits ÷ total references, and fault rate = faults ÷ total references. For the classic 20-reference string with 3 frames, LRU has 8 hits, so its hit ratio is 8/20 = 40% and its fault rate 60%.

How does the Second Chance (Clock) page replacement algorithm work?

Each frame has a reference bit that a hit sets to 1. On a fault, the clock hand checks frames in circular order: a page with bit 1 has the bit cleared and is skipped (its second chance), and the first page with bit 0 is replaced. This calculator starts new pages at bit 0 and shows every bit after every step.

What is the difference between LFU and MFU page replacement?

LFU replaces the page used the fewest times; MFU replaces the page used the most times, assuming it has finished its work. Ties go to the page loaded first. On the classic 20-reference string with 3 frames, LFU gives 13 faults and MFU 15.

Do the first page loads count as page faults?

Yes. Loading a page into an empty frame is a compulsory (cold-start) fault, so with 3 frames the first three distinct pages always fault. This matches how OS textbooks count them.

Have a suggestion for Page Replacement Calculator?Share your feedback ↗