FIF0 :
- Pages are loaded into memory in the order they arrive.
- When a new page must be loaded and memory is full, the oldest page (the one that came in first) is removed.
Easy to implement, but does not take locality into account. Further problem : Increase in number of frames can cause increase in the number of page faults (Belady’s anomaly).
Optimal Algorithm :
Select page which will be re-used at the latest time (or not at all) not implementable, but good for comparisons.
Least-recently used :
Use past as guide for future and replace page which has been unused for the longest time.
Problem : Requires a lot of HW support Possibilities:
- Stack in microcode.
- Approximation using reference bit : HW sets bit to 1 when page is referenced.