Page Replacement Algorithms
• First-In First-Out (FIFO)
– keep a queue of pages, discard from head .
– performance difficult to predict: have no idea whether page replaced will be used again or not.
– discard is independent of page use frequency
– in general: pretty bad, although very simple.
• Optimal Algorithm (OPT)
– replace the page which will not be used again for longest period of time
– can only be done with an oracle, or in hindsight
– serves as a good comparison for other algorithms .
• Least Recently Used (LRU)
– LRU replaces the page which has not been used for the longest amount of time .
– (i.e. LRU is OPT with -ve time)
– assumes past is a good predictor of the futureCounting Algorithms: keep a count of the number of references to each page
– LFU: replace page with smallest count
– MFU: replace highest count because low count
⇒ most recently brought in.
• Page Buffering Algorithms:
– keep a min. number of victims in a free pool
– new page read in before writing out victim.
• (Pseudo) MRU:
– consider access of e.g. large array.
– page to replace is one application has just finished with, i.e. most recently used.
– e.g. track page faults and look for sequences.
– discard the kth in victim sequence.
– stop trying to second guess what’s going on.
– provide hook for app. to suggest replacement.
– must be careful with denial of service. . .