OS | FIFO Page Replacement Algorithm | Exp - 6
FIFO
FIFO (First in First out) Page Replacement Algorithm − It is one of the simplest page replacement algorithm. The oldest page, which has spent the longest time in memory is chosen and replaced. This algorithm is implemented with the help of FIFO queue to hold the pages in memory. A page is inserted at the rear end of the queue and is replaced at the front of the queue.
In the fig., the reference string is 5, 4, 3, 2, 5, 4, 6, 5, 4, 3, 2, 6 and there are 3 frames empty. The first 3 reference (5, 4, 3) cause page faults and are brought into empty frames. The next reference (2) replaces page 5 because page 5 was loaded first and so on. After 7 page faults, the next reference is 5 and 5 is already in memory so no page fault for this reference. Similarly for next reference 4. The + marks shows incoming of a page while circle shows the page chosen for removal.
Advantages
- FIFO is easy to understand.
- It is very easy to implement.
Disadvantage
- Not always good at performance. It may replace an active page to bring a new one and thus may cause a page fault of that page immediately.
- Another unexpected side effect is the FIFO anomaly or Belady's anomaly. This anomaly says that the page fault rate may increase as the number of allocated page frames increases.
e.g. The following figure presents the same page trace but with a larger memory. Here number of page frame is 4.
Here page faults are 10 instead of 9.
No comments: