+1 vote

1 Answer

+1 vote
by (user.guest)
selected by (user.guest)
Best answer

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. . .

Related questions

+1 vote
1 answer
+1 vote
1 answer