Why FIFO page replacement?

Page replacement is used to manage the limited physical memory resources efficiently. In systems with virtual memory, not all pages of a process need to be in memory at once. When the system encounters a page fault, it needs to decide which page to replace in order to bring in the required page from secondary storage. This decision is based on various page replacement algorithms.
FIFO page replacement

FIFO which is also known as First In First Out is one of the types of page replacement algorithm. The FIFO algorithm is used in the paging method for memory management in an operating system that decides which existing page needs to be replaced in the queue.

FIFO algorithm replaces the oldest (First) page which has been present for the longest time in the main memory.

In simple words, When a new page comes in from secondary memory to main memory, It selects the front of the queue which is the oldest page present, and removes it.

Q) Why do we need to swap the pages?

since we have a fixed number of frames and all the processes cannot be stored in the

main memory at a single time we use page replacement algorithms to store pages of

a process instead of the whole process.

Terminology Required for page replacement

  • Page Fault: It occurs when the requested page is not found in memory and needs to be brought in from secondary storage (like disk) into main memory.
  • Page Hit: It happens when the requested page is found in memory, thus no need to retrieve it from secondary storage.
  • Page Replacement: This is the process of selecting a victim page from memory when a new page needs to be brought in. The victim page is then replaced with the new page.
How Algorithm work ?

 

  • Maintaining a List of Pages: The operating system keeps track of all pages currently residing in the memory. This list essentially serves as a queue, with the oldest pages at the front (head) of the queue and the newest at the back (tail).
  • Bringing in a New Page: When a new page needs to be loaded into memory from the secondary storage (such as the hard disk), the operating system checks if there is space available in the physical memory. If there is available space, the new page is loaded into memory. However, if the memory is already full, a page replacement decision needs to be made.
  • Handling Page Fault: In case of a page fault (when the requested page is not found in memory), the operating system selects a page to evict from the memory to make room for the incoming page. In FIFO, the decision is straightforward: the oldest page in memory, which is at the head of the list, is selected for replacement.
  • Removing the Oldest Page: The page at the head of the list, which is the oldest page in memory, is removed to make space for the new page. This removal is performed regardless of the importance or frequency of use of the evicted page.
  • Adding the New Page: Once the oldest page is removed, the new page is added to the memory and placed at the tail of the list, signifying it as the newest addition to the memory.
  • The FIFO algorithm operates on a simple principle: the page that has been in memory the longest is the first to be replaced when a new page needs to be brought in.

Advantages & Disadvantages

Advantages :

  • Simplicity: FIFO is one of the simplest page replacement algorithms to implement.
  • Fairness: It provides a fair treatment to all pages, as it replaces the oldest page first, regardless of its access frequency or importance..

Disadvantages :

  • Belady's Anomaly: FIFO can suffer from Belady's Anomaly, which means increasing the number of frames might increase the number of page faults. This is contrary to intuition and against the principle of optimality.
  • Poor Performance: FIFO may not always provide the best performance in terms of minimizing page faults, especially if the program's access pattern doesn't align well with FIFO's replacement strategy.
  • Doesn't Consider Page Access Frequency: FIFO doesn't take into account how frequently pages are accessed. It might replace a frequently used page just because it's the oldest, leading to unnecessary page faults.