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.