FIFO page replacement, explained

Memory is limited, so when a program needs a page that is not in memory and every frame is full, the system must remove one page. FIFO, which stands for first in, first out, makes the simplest possible choice: it removes the page that has been in memory the longest.

It works like a queue at a shop. The page at the front arrived first, so it leaves first, whether or not it is still being used.

How it works

• Read the next page request.
• If the page is already in a frame, it is a hit and nothing changes.
• If it is not, it is a page fault. If there is an empty frame, load the page there.
• If every frame is full, remove the oldest page (the front of the queue) and load the new page.

A small example

Request list, with 3 frames:

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

Result with FIFO:

15 page faults

Note that a page that is used often can still be removed, simply because it is the oldest one.

What to know about its cost

• It only needs a queue of the frames, so it is very cheap to run.
• It can show Belady's anomaly: with some request lists, more frames lead to more faults.
• It never looks at how recently or how often a page was used.

Where it works well

• Very simple to build and to understand.
• Almost no extra bookkeeping.

Where it struggles

• It can remove a page that is used all the time, just because it is old.
• Usually causes more faults than LRU on real programs.

Try it yourself

Open the Page Replacement experiment, enter the request list from this post with 3 frames, choose FIFO and step through it. Then switch to the other algorithms and compare the page faults.

Open the Page Replacement experiment