- FIFO is a simplest page replacement algorithm.
- In this algorithm arrival time of the page into the memory is recorded.
- When there are no free frames available in the memory and a page must be replaced, the oldest page is chosen to be replaced with new page.
- In other words, the first or earliest page that was loaded into the memory will be selected for replacement.
- FIFO algorithm can be implemented by creating a FIFO queue to store all pages in memory.
- We replace the page from the top of the FIFO queue. When a page is brought into memory, it will be inserted at the end of the FIFO queue.
- In our example reference string (7, 0, 1) the three frames are empty.
- The first three reference page generates page fault and brought into memory.
- The next page reference is page 2. Now we have no free frame available to load this page into memory. So we will replace page 7 with page 2 because page 7 was the first page loaded in memory.
- Since 0 is the next page reference but as it is already available in memory, it does not generate any page fault.
- Similarly page 3 will replace page 0 and so on.
Example:
- Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
- No. of frames: 3
- Total No. of page fault in FIFO is 15.
- FIFO page replacement algorithm is easy to understand and program but its performance is not good.
- It has the higher level of page fault than other method.