FIFO Page Replacement Algorithm In C
FIFO Page Replacement Algorithm In C
FIFO Page Replacement Algorithm In C is a concept that comes into play when the operating system manages memory using a method called paging. In simple terms, the system breaks memory into small sections called pages.
One common situation is called a page fault, which happens when the required page isn’t found in memory. To handle this, the OS uses algorithms like FIFO (First In, First Out), which removes the oldest page first. These methods help ensure the system runs smoothly by managing memory efficiently behind the scenes.
Understanding FIFO Page Replacement
- The FIFO (First-In-First-Out) page replacement algorithm is a memory management technique that evicts the oldest page in memory when a new page is needed.
- It uses a queue structure to track page insertion order, ensuring the first page loaded is the first removed during replacements. Here’s a detailed explanation with a C implementation:
- In this situation, the operating system replaces an existing page from the main memory by bringing a new page from the secondary memory.
- In such situations, the FIFO method is used, which is also refers to the First in First Out concept.
- This is the simplest page replacement method in which the operating system maintains all the pages in a queue.
- Oldest pages are kept in the front, while the newest is kept at the end. On a page fault, these pages from the front are removed first, and the pages in demand are added.
Algorithm for FIFO Page Replacement
- Step 1. Start to traverse the pages.
- Step 2. If the memory holds fewer pages, then the capacity else goes to step 5.
- Step 3. Push pages in the queue one at a time until the queue reaches its maximum capacity or all page requests are fulfilled.
- Step 4. If the current page is present in the memory, do nothing.
- Step 5. Else, pop the topmost page from the queue as it was inserted first.
- Step 6. Replace the topmost page with the current page from the string.
- Step 7. Increment the page faults.
- Step 8. Stop
FIFO Page Replacement Algorithm in C
// C program for FIFO page replacement algorithm
#include<stdio.h>
int main()
{
int incomingStream[] = {4, 1, 2, 4, 5};
int pageFaults = 0;
int frames = 3;
int m, n, s, pages;
pages = sizeof(incomingStream)/sizeof(incomingStream[0]);
printf("Incoming \t Frame 1 \t Frame 2 \t Frame 3");
int temp[frames];
for(m = 0; m < frames; m++)
{
temp[m] = -1;
}
for(m = 0; m < pages; m++)
{
s = 0;
for(n = 0; n < frames; n++)
{
if(incomingStream[m] == temp[n])
{
s++;
pageFaults--;
}
}
pageFaults++;
if((pageFaults <= frames) && (s == 0))
{
temp[m] = incomingStream[m];
}
else if(s == 0)
{
temp[(pageFaults - 1) % frames] = incomingStream[m];
}
printf("\n");
printf("%d\t\t\t",incomingStream[m]);
for(n = 0; n < frames; n++)
{
if(temp[n] != -1)
printf(" %d\t\t\t", temp[n]);
else
printf(" - \t\t\t");
}
}
printf("\nTotal Page Faults:\t%d\n", pageFaults);
return 0;
}Output –
Incoming Frame 1 Frame 2 Frame 3 4 4 - - 1 4 1 - 2 4 1 2 4 4 1 2 5 5 1 2 Total Page Faults: 4
Prepare for Interview with us:
FIFO Page Replacement in C Explained with Example Scenario
For page reference string 1, 3, 0, 3, 5, 6 with 3 frames:
1 | 3 | 0 → 3 faults (initial load) 3 → already in memory (no fault) 5 → replaces 1 → +1 fault 6 → replaces 3 → +1 fault
C Program Implementation
// C program for FIFO page replacement algorithm
#include<stdio.h>
#define MAX_FRAMES 3
void fifo(int pages[], int num_pages) {
int frames[MAX_FRAMES] = {-1};
int page_faults = 0, next_frame = 0;
for (int i = 0; i < num_pages; i++) {
int current_page = pages[i];
int found = 0;
// Check if page exists in frames
for (int j = 0; j < MAX_FRAMES; j++) {
if (frames[j] == current_page) {
found = 1;
break;
}
}
// Handle page fault
if (!found) {
frames[next_frame] = current_page;
next_frame = (next_frame + 1) % MAX_FRAMES;
page_faults++;
}
// Print frame state
printf("%d → [", current_page);
for (int j = 0; j < MAX_FRAMES; j++) {
frames[j] != -1 ? printf(" %d ", frames[j]) : printf(" - ");
}
printf("]\n");
}
printf("Total Page Faults: %d\n", page_faults);
}
int main() {
int pages[] = {1, 3, 0, 3, 5, 6};
int n = sizeof(pages)/sizeof(pages[0]);
fifo(pages, n);
return 0;
}
Key Components:
- Frame Initialization: Frames are set to -1 (empty).
- Circular Queue Index: next_frame cycles through frames using modulo arithmetic.
- Page Fault Handling: Replaces oldest page when a fault occurs.
Execution Output
1 → [ 1 - - ] 3 → [ 1 3 - ] 0 → [ 1 3 0 ] 3 → [ 1 3 0 ] 5 → [ 5 3 0 ] 6 → [ 5 6 0 ] Total Page Faults: 5
Closing remarks
The FIFO Page Replacement Algorithm offers a simple yet effective way to manage memory using the First-In-First-Out principle. By replacing the oldest loaded page during a fault, it ensures a basic level of efficiency in memory allocation. Although it’s easy to implement, FIFO may not always be the most optimal compared to advanced methods like LRU. Still, it’s a great starting point for understanding memory management concepts in operating systems.
FAQs
FIFO does not consider how frequently or recently a page is used, which can lead to unnecessary replacements and increased page faults.
A queue is typically used, as it helps maintain the order of page entries for easy removal of the oldest page.
Yes, FIFO is prone to Belady’s Anomaly, where increasing the number of frames can sometimes lead to more page faults.
FIFO is generally not preferred in real-time systems due to its lack of adaptability and poor worst-case performance.
Login/Signup to comment
if((pageFaults <= frames) && (s == 0))
{
temp[m] = incomingStream[m];
}
these lines cause erroneous output when input is 4 4 2 3 5
this can be rectified by changing the argument of temp[m] to the next empty space where the value is -1 in the array
if((pageFaults <= frames) && (s == 0))
{
int i =0;
while(temp[i]!=-1)
i++;
temp[i] = incomingStream[m];
}
If I am wrong about this I'm so sorry in advance!