Page replacement algorithms

First In First Out

First-in-first-out is not a good page replacement algorithm. It assumes that whatever page was first brought into memory should be the first to be evicted. This ignored the fact that the first page to be brought in may also be the most heavily used page. Supermarket example.

It is however, very simple to implement. The pages in memory are arranged in a queue. When a page is brought in to a frame, it is placed on the tail of the queue, pages to be evicted are taken from the head of the queue.

Exhibits belady's anomaly: in some cases, having more free pages causes more swapping to occur. Not generally used.

last updated 6 March 1998