PlayLogic
Unit 3 · Module 5

Page Replacement (FIFO & LRU)

When every frame is full and a new page must be loaded, the OS must choose a victim. Compare FIFO and LRU on the same reference string and measure the hit and fault ratios.

Page faults and replacement
Page fault — The referenced page is not in any frame, so the OS must fetch it from disk.
Page hit — The referenced page is already in a frame — no disk access.
FIFO — First In First Out: replace the page that has been in memory the longest.
LRU — Least Recently Used: replace the page that has not been used for the longest time.
Hit ratio — page hits ÷ total references (usually shown as a percentage).
Fault ratio — page faults ÷ total references = 1 − hit ratio.

Real-world analogy: Desk with three trays

Only three files fit on your desk. FIFO returns the file that arrived first, even if you were just reading it. LRU returns the file you have ignored the longest — usually the smarter guess.
Experiment: FIFO / LRU page replacement simulator
Number of frames: 3
Ready — press Next step
ReferenceFrame 1Frame 2Frame 3Hit / Fault
Press Next step or Auto play to start.

Total references

0

Page hits

0

Page faults

0

Hit ratio

0.00%

Fault ratio

0.00%

Final result for the whole string

Page Hits   : 3
Page Faults : 9
Hit Ratio   : 25.00%
Fault Ratio : 75.00%

  1. Step 1 · What is happening?

    The CPU asks for the next page in the reference string; the OS checks whether that page is already in a frame.

  2. Step 2 · Why this decision?

    FIFO evicts the page that entered memory earliest, regardless of how often it is used.

  3. Step 3 · What changes in memory?

    On a hit nothing moves (LRU only updates the recency stamp). On a fault the page is loaded into an empty frame, or the victim frame is overwritten.

  4. Step 4 · Resulting state

    The frame row is recorded, hit/fault counters update, and the hit and fault ratios are recalculated.

Practice problem

Reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 3 frames using FIFO. Find the number of page faults and the hit ratio.

Quick quiz

1. Belady's anomaly (more frames → more faults) can occur with…

2. A page hit means…

3. If there are 12 references and 8 faults, the hit ratio is…

Finished Unit 3? Test everything you have learnt.

Unit 3
Take the quiz