How does FIFO page replacement work?

Question

I'm trying to understand the FIFO page replacement algorithm, but all the information I can find amounts to what's below. Can you explain how you use a reference string to evaluate a page replacement algorithm, using the particular example of FIFO?

When a page must be replaced, the oldest page is chosen.

In all our examples, the reference string is

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

3 frame (9 page faults) 4 frame (10 page faults)

Answer 1

A page fault is when a page is not present in a frame of memory so a trap has to be sent to the OS and the page has to be added to a frame. If there is no room then something needs to be removed. FIFO is one method to determine what page will get removed.

The concept is that whatever page got added first to the frame will get removed first. This is what FIFO stands for. Using your first example. I will go down the reference string list and show you what the memory will look like.

1:  1      +1 fault
2:  1,2    +1 fault
3:  1,2,3  +1 fault
4:  2,3,4  +1 fault - 1 gets removed because it was the first added
1:  3,4,1  +1 fault - 2 gets removed because it was the first on the list
2:  4,1,2  +1 fault - 3 got removed..
5:  1,2,5  +1 fault - 4 got removed..
1:  1,2,5  No change - 1 is already present so no page fault was required
2:  1,2,5  No change - 2 is already present in the frame
3:  2,5,3  +1 fault - 1 was removed because it is first
4:  5,3,4  +1 fault - Now 2 got removed
5:  5,3,4  No change - No change because 5 is present in one of the frames.

This gives the total of 9 faults.

You can also think of it as the oldest page gets removed.

Hopefully I made no mistakes :D