FIFO Page Replacement Algorithm in C
What are Replacement Algorithms?
- When a new element needs to be added to a container that is already full or when a limited resource needs to be allotted to a new request, replacement algorithms are used in computer systems to determine which elements or entities should be removed or replaced. Operating systems use replacement algorithms that involve First-In-First-Out (FIFO), Least Recently Used (LRU), Least Frequently Used (LFU), and others.
- In general, paging is the approach most operating systems use the majority of operating systems to manage memory. When a new page is needed or appears in the picture, these algorithms are necessary for figuring out which page needs to be altered.
- When an Operating System requires a page for processing that isn't actually present in main memory, a demand is necessary. Another name for this issue is page fault.
- Page Fault: When the main program accesses a memory page that has been placed into virtual memory but is really mapped into a physical address space, a page fault takes place.
- A Page Fault happens when the Physical Memory is much smaller than the Virtual Memory.
What is FIFO Page Replacement Algorithm in C?
- Operating systems use the First-In-First-Out (FIFO) page replacement algorithm as an easy-to-understand method of managing memory and handling page faults. In this procedure, the page that has been in memory the longest will be changed.
- For an operating system, all of the pages in a queue are tracked and maintained by the simplest algorithm, FIFO.
- The more recent pages are stored at the back of the queue while the older ones are maintained up front. The pages that are requested are added once the front pages have been removed.
Example:
Consider the page reference strings 1, 3, 0, 3, 5, and 6 along with three-page slots. Since there are no spaces filled originally, the arrival of 1, 3, and 0 filled the empty spaces, resulting in 3 Page Faults.
- Since 3 are already present in the RAM when it arrives, there are no page faults. A 1Page Fault occurs when page number 5 emerges because it cannot fit in memory and takes up the oldest page slot, which is number 1.
- The last page to arrive is page 6, but it also isn't in memory, therefore it occupies the oldest page slot, which is 3 -> 1 Page Fault.
- Thus, the total page faults are 5.
Algorithm for FIFO Page Replacement:
- Begin turning the pages.
- Declare the size now relative to Page's length.
- Check the page to memory for replacement needs.
- Check whether switching from the old page to the new page in memory is necessary in a similar manner.
- Create a queue to hold all of the pages now.
- Add Require page memory to the waiting list.
- Check for page defects and bad replacements.
- Request that no processes be introduced.
- Declare the values.
- Stop
FIFO Page Replacement Algorithm in C Program:
#include <stdio.h>
#define MAX_FRAMES 3
void fifoPageReplacement(int pages[], int numPages)
{
int frames[MAX_FRAMES] = { -1 };
int pageFaults = 0;
int nextFrameIndex = 0;
for (int i = 0; i < numPages; i++)
{
int currentPage = pages[i];
int pageFound = 0;
for (int j = 0; j < MAX_FRAMES; j++)
{
if (frames[j] == currentPage)
{
pageFound = 1;
break;
}
}
if (!pageFound)
{
frames[nextFrameIndex] = currentPage;
nextFrameIndex = (nextFrameIndex + 1) % MAX_FRAMES;
pageFaults++;
}
}
printf("Total page faults: %d\n", pageFaults);
}
int main()
{
int pages[] = { 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 };
int numPages = sizeof(pages) / sizeof(pages[0]);
fifoPageReplacement(pages, numPages);
return 0;
}
Output:
![FIFO Page Replacement Algorithm in C](https://static.tutorialandexample.com/c/fifo-page-replacement-algorithm-in-c1.png)
- The FIFO page replacement technique is implemented in this case by the fifoPageReplacement function. It requires an array of pages that represents the number of pages and the order of page requests (numPages). Within a predetermined number of frames (MAX_FRAMES), the algorithm simulates page replacement.
- The frames array, which is initialised with -1 to indicate an empty frame, represents the frames in memory. The number of page faults that occur throughout the simulation is recorded by the pageFaults variable. The next frame that needs to be replaced is indicated by the nextFrameIndex variable.
- The algorithm sequentially processes each page in the pages array. It iterates across the frames to see if the page is already present in them. A page fault happens if the page cannot be found (pageFound is 0). The algorithm updates the nextFrameIndex, replaces the page at nextFrameIndex with the current page, increases the pageFaults count, and updates the nextFrameIndex.
- The total number of page errors is then printed.
- An example series of page requests is given in the main function, and the fifoPageReplacement function is then called with the necessary arguments.
- The FIFO page replacement method will be simulated for the specified page sequence when this programme is executed, and it will also indicate the overall number of page faults.