As we already discussed that a page replacement algorithm determines how the victim page (the page to be replaced) is selected when a page fault occurs. The ultimate aim is to minimize the page fault rate. There have various algorithms that work as page replacement; one of them is First In First Out (FIFO). FIFO is one of the simplest page replacement algorithms. A FIFO page replacement algorithm associates with each page the time when that page was brought into memory. At the point when a page must be replaced, the most experience door oldest page is selected. Note that it is not important to record the time when a page is acquired. We can create a FIFO queue to keep all pages in memory. We hit the page at the head of the queue. At the point when a page is brought into memory, we embed it on the tail of the queue.
FIFO Page Replacement Algorithm
For our model consider reference string, our first three frames are empty. The first three references (7, 0, 1) cause page faults and are brought into these empty frames. The following reference (2) replaces page 7, since page 7 was previously obtained. Since 0 is the following reference and 0 is now in memory, we have no fault for this reference. The first reference to 3 results in replacement of page 0, since fault. Page 1 is then replaced by page 0. This process continues as shown in figure 1. Every time a fault occurs, we show which pages are in our three frames. There are fifteen page faults altogether.
The FIFO page-replacement algorithm is easy to understand and program. However, its performance is not always good. On the one hand, the page replaced may be an initialization module that was used a long time ago and is no longer needed. On the other hand, it could contain a heavily used variable that was initialized early and is in constant use.
Also check: segmentation in os
Notice that, even if we select for replacement a page that is in active use, everything still works correctly. After we replace an active page with a new one, a fault occurs almost immediately to retrieve the active page. Some other page must be replaced to bring the active page back into memory. Thus, a bad replacement option increases the page-fault rate and slower process execution. However, this does not lead to incorrect execution.
Also See: Demand Paging in Operating System
To understand the problems with the FIFO page-replacement algorithm, we consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
Figure 2 shows the curve of page faults for this reference string vs. the number of frames available. Note that the number of defects for four frames (ten) is greater than the number of defects for three frames (nine). This most unexpected result is known as Belady’s anomaly: for some page-replacement algorithms, the page-fault rate may increase as the number of allocated frames increases. We would expect that giving more memory to a process would improve its performance. In some early research, investigators observed that this assumption was not always true. This was discovered as a result of Belady’s anomaly.
Also check: Page Replacement Algorithm in Operating system
Calculation of Page Hit ratio:
∵we have;
Total number of reference strings = 20
Total number of page misses or page faults = 15
∵We know that;
Total number of page hits = Total number of reference strings – Total number of page misses or page faults
∴ Total number of page hits (from figure 1) = 20 – 15 = 5
Thus, Page Hit ratio = Total no. of page hits/Total no. of reference = 5/10
= 0.25 = 25%
FIFO page replacement algorithm Advantages:
- Easy to understand
- Simple to program
Also check: Optimal page replacement algorithm
FIFO page replacement algorithm disadvantages:
- This algorithm is not highly effective
- The system is required to keep track of each frame
- Sometimes it behaves abnormally named Belady’s anomaly
- Poor replacement options increase page fault rate and slow process execution.
