1. Introduction to Page Replacement:

In virtual memory systems, page replacement algorithms are essential for managing the limited physical memory efficiently. When a page fault occurs, and the required page is not in memory, the operating system must select a page to replace. FIFO is one such page replacement algorithm that follows the principle of replacing the oldest page in memory.

2. FIFO Page Replacement Algorithm:

Working:

Maintain a queue of pages in memory, tracking the order in which they were brought into memory.

When a page fault occurs:

If the page is not in memory, bring it in.

If there is no space, remove the page at the front of the queue (oldest page).

Add the new page to the back of the queue.

Advantages:

Simple and easy to implement.

Provides a fair approximation of least recently used (LRU).

Disadvantages:

May suffer from the Belady's Anomaly (increasing the number of frames may not always decrease page faults).

3. Example Scenario:

Consider a memory system with three frames (A, B, C) and a sequence of page requests: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3.

Initial state: | - | - | - |

Page 1 is requested: | 1 | - | - |

Page 2 is requested: | 1 | 2 | - |

Page 3 is requested: | 1 | 2 | 3 |

Page 4 is requested: | 4 | 2 | 3 | (Page 1 is replaced, as it was the first one in)

Page 1 is requested: | 4 | 2 | 1 | (Page 3 is replaced)

... and so on.

4. Conclusion:

FIFO is a straightforward page replacement algorithm based on the principle of replacing the oldest page in memory. While simple to implement, it may not always provide optimal results in terms of minimizing page faults.

Notes From The Slides:

First-In-First-Out (FIFO) Algorithm

Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
3 frames (3 pages can be in memory at a time per process)

15 page faults

Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5
Adding more frames can cause more page faults!

Belady’s Anomaly

How to track ages of pages?

Just use a FIFO queue

First-In-First-Out (FIFO) Algorithm

Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
3 frames (3 pages can be in memory at a time per process)

15 page faults

Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5
Adding more frames can cause more page faults!

Belady’s Anomaly

How to track ages of pages?

Just use a FIFO queue

FIFO Illustrating Belady’s Anomaly