Concept: Replaces the oldest page in memory.
GATE Note: Suffers from Belady's Anomaly. Check the line graph below to see it!
Time Complexity: O(1) per step.
Concept: Replaces the page not used for the longest time.
GATE Note: Stack algorithm; guaranteed to never suffer from Belady's Anomaly.
Time Complexity: O(N) per step.
Concept: Replaces the page that will not be used for the longest time in the future.
GATE Note: Yields the theoretical minimum faults. Impossible to implement practically.
Time Complexity: O(N) per step.
Look for a bump in the FIFO line as frames increase! This proves Belady's Anomaly.
| Algorithm | Page Faults | Page Hits | Hit Rate | Fault Rate |
|---|