Practice · Core CS simulator

Page replacement simulator

Type the reference string and the number of frames from your question. See the frames after every reference, the faults and hits, and why each page was replaced.

12 page faults, 8 hits out of 20 references · hit ratio 40%, fault ratio 60%

Page70120304230321201701
Frame 177722224440001111111
Frame 20000000033333300000
Frame 3111333222222222777
Hit / faultFFFFHFHFFFFHHFHFHFHH
Replaced712304032
Every step explained
  1. 7 is not in memory: a fault. A frame is free, so it goes there.
  2. 0 is not in memory: a fault. A frame is free, so it goes there.
  3. 1 is not in memory: a fault. A frame is free, so it goes there.
  4. 2 is not in memory: a fault. Memory is full; 7 was used least recently, so 2 replaces it.
  5. 0 is already in memory: a hit.
  6. 3 is not in memory: a fault. Memory is full; 1 was used least recently, so 3 replaces it.
  7. 0 is already in memory: a hit.
  8. 4 is not in memory: a fault. Memory is full; 2 was used least recently, so 4 replaces it.
  9. 2 is not in memory: a fault. Memory is full; 3 was used least recently, so 2 replaces it.
  10. 3 is not in memory: a fault. Memory is full; 0 was used least recently, so 3 replaces it.
  11. 0 is not in memory: a fault. Memory is full; 4 was used least recently, so 0 replaces it.
  12. 3 is already in memory: a hit.
  13. 2 is already in memory: a hit.
  14. 1 is not in memory: a fault. Memory is full; 0 was used least recently, so 1 replaces it.
  15. 2 is already in memory: a hit.
  16. 0 is not in memory: a fault. Memory is full; 3 was used least recently, so 0 replaces it.
  17. 1 is already in memory: a hit.
  18. 7 is not in memory: a fault. Memory is full; 2 was used least recently, so 7 replaces it.
  19. 0 is already in memory: a hit.
  20. 1 is already in memory: a hit.

Every algorithm, 3 frames

AlgorithmFaultsHitsHit ratio
15525%
12840%
91155%

LRU with more frames

Frames1234567
Faults2017128766

More frames, never more faults here. With FIFO, some strings get more faults with more frames: try "Belady's anomaly".

What's happening

Memory has a fixed number of frames. When a page is needed and it's already in a frame, that's a hit. When it isn't, that's a page fault: the page has to be loaded, and if every frame is full, a page has to go. The algorithm decides which one.

The three algorithms

  • FIFO replaces the page that has been in memory the longest. Easy to build, but it can throw out a page that's used all the time.
  • LRU (least recently used) replaces the page that hasn't been used for the longest time: a guess at the future from the past. It has to keep track of every use.
  • Optimal replaces the page that won't be used for the longest time from now. No system can know the future, so it can't be built, but it gives the fewest faults possible: it's the yardstick for the others.

Belady's anomaly

With FIFO, more frames can mean more page faults. For 1 2 3 4 1 2 5 1 2 3 4 5, FIFO has 9 faults with 3 frames and 10 with 4. LRU and Optimal never do this: they are stack algorithms, so the pages in memory with n frames are always among the pages in memory with n + 1.

Formulas

  • Hit ratio = hits ÷ references. Fault ratio = faults ÷ references = 1 − hit ratio.
  • Effective access time = (1 − p) × memory access time + p × page fault service time, where p is the fault ratio.

The rules this simulator follows

  • Frames fill from the top, and a new page takes the frame of the page it replaces.
  • Every fault counts, including the first ones that only fill empty frames. If your question leaves those out, subtract them.
  • Optimal: if several pages are never used again, the one that came in first goes. The number of faults is the same whichever goes.

More simulators: CPU scheduling, disk scheduling and the Banker's algorithm.