Suppose there are 3 frames and the reference string is:

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

FIFO page replacement

FIFO algorithm is the simplest page replacement algorithm. The FIFO page replacement algorithm records the time to memory for each page and selects the oldest page when pages must be replaced.

Note that there is no need to keep track of the exact time a page is brought in, and a FIFO queue can be created to manage all the in-memory pages. It is the first page of the queue that is replaced. When a page needs to be called into memory, it is added to the end of the queue.

For the sample reference string, the 3 frames start blank. The first three references (7,0,1) cause a page missing error and are turned to these empty frames. These free frames are then called in.

The next reference (2) replaces 7, because page 7 comes in first. Since 0 is the next reference and is already in memory, there is no page missing error for this reference.

The first reference to 3 causes page 0 to be replaced because it is now the first in the queue. Because of this substitution, the next reference to 0 will have a page missing error, and then page 1 will be replaced by page 0. thr picture shows which pages are in these three frames each time there is a page missing error. There were 15 missing page errors.



Optimal page replacement

This page replacement algorithm ensures the lowest possible page missing error rate for a given number of frames.

For example, for the example reference string, the optimal permutation algorithm produces nine page missing errors.



The first three references generate a page missing error to fill the three free frames. A reference to page 2 replaces page 7, because page 7 is not used until the 18th reference, page 0 for the 5th reference, and page 1 for the 14th reference. A reference to page 3 replaces page 1, because page 1 is the last page to be referenced again among the three pages in memory.

The optimal page replacement algorithm with nine page missing errors is better than FIFO replacement with 15 page missing errors (if we ignore the first three, which is what all algorithms suffer, the optimal replacement is twice as good as FIFO replacement). In fact, no permutation algorithm can handle the sample reference string with only three frames and fewer than nine missing page errors.

LRU page replacement

The key difference between FIFO and OPT is that, in addition to backward or forward in time, FIFO uses the time when the page is brought into memory, while OPT uses the time when the page will be used in the future.

LRU permutation associates each page with the last time it was used. When a page needs to be replaced, LRU selects the page that has not been used for the longest time. This strategy can be used as an optimal page replacement algorithm for looking backwards in time rather than forward.

The LRU algorithm produced 12 page missing errors.