The FIFO page replacement algorithm in C is a popular method used in operating systems. This algorithm employs the principle that the page that has been in memory the longest should be replaced first.
How FIFO Page Replacement Works ?
FIFO (First In First Out) page replacement is a memory management technique that operating systems use to keep track of all the pages in memory in a queue. Whenever a new page needs to be brought into memory, the page at the front of the queue, the oldest page, is removed to make space for the new page. The new page is then added to the back of the queue. This way, the operating system ensures that the pages that have been in memory for the longest time are replaced first, which can help improve system performance.
The key steps are:
- When a new page is referenced, check if it is already in memory. If yes, do nothing.
- If the page is not in memory, check for space to add it. If yes, add the new page to the back of the queue.
- If there is no free space in memory, remove the page at the front of the queue and add the new page to the back.
- Repeat steps 1-3 for every page reference.
The main advantage of FIFO is its simplicity – Unlike other algorithms, selecting which page to discard does not require complex calculations. However, it has a drawback. It must track how often each page is accessed to make intelligent decisions. As a result, if older pages are still frequently accessed, they will be replaced before newer ones.
FIFO Page Replacement Algorithm in C
Here is an algorithm for FIFO Page Replacement in C:
C Code
Dry Run
Let’s use the following example:
Number of Pages: 7
Reference String: 7 0 1 2 0 3 0
Total Number of Frames: 3
| Page | Frames After Insertion | Page Faults |
|---|---|---|
| Start | -1 -1 -1 | 0 |
| 7 | 7 -1 -1 | 1 |
| 0 | 7 0 -1 | 2 |
| 1 | 7 0 1 | 3 |
| 2 | 0 1 2 | 4 |
| 0 | 0 1 2 | 4 (no increment as page already in frame) |
| 3 | 1 2 3 | 5 |
| 0 | 2 3 0 | 6 |
Total Page Faults at the end = 6.
Let’s delve deeper into the advantages and disadvantages of FIFO Page Replacement Algorithm:
Advantages
- Simplicity: The primary allure of FIFO is its straightforward logic. The first page that enters the system is the first one to leave. No complex algorithms, no intricate calculations – just pure, simple logic.
- Predictability: Since FIFO follows a set pattern of replacing the oldest page, it offers a degree of predictability. This can be useful in systems where consistent behaviour is more desirable than optimal performance.
- Low Overhead: Due to its simplicity, the overhead, or the extra resources required to implement and maintain FIFO, is minimal.
Drawbacks
- Lack of Intelligent Decision Making: FIFO needs to consider the frequency of page accesses. This means a page loaded long ago but frequently accessed might be removed in favour of a newer, less-used page.
- Belady’s Anomaly: An interesting phenomenon associated with FIFO is Belady’s Anomaly. Increasing the number of page frames might lead to more page faults, which is counterintuitive and undesirable.
- Not Always Optimal: For many workloads, FIFO might not provide the best performance because it doesn’t adapt to the actual access patterns of the pages.
Conclusion
The FIFO page replacement algorithm in c provides a straightforward strategy for managing physical memory pages. While simple to implement, it does have limitations when frequently used pages are replaced before less used ones. Still, FIFO’s low overhead and predictability make it a commonly used page replacement policy in many operating systems.
This walkthrough demonstrates FIFO page replacement in action on a small scale. The core logic can be adapted to handle larger memory sizes and access patterns. Like any algorithm, FIFO has tradeoffs. However, its simplicity and efficiency ensure its place as a foundational memory management technique in historical and modern systems.
I hope You liked the post ?. For more such posts, ? subscribe to our newsletter. Check out more C tutorials.
