Let us learn how to implement FIFO Page Replacement Algorithm in C programming language. This code for First In First Out Page Replacement makes use of arrays.
What is FIFO Page Replacement Algorithm?
When a page fault occurs, the OS has to remove a page from the memory so that it can fit in another page in the memory.
These page replacement algorithms are used in operating systems that support virtual memory management.
FIFO Page Replacement technique is one of the simplest one to implement amongst other page replacement algorithms. It is a conservative algorithm.
It is a low-overhead algorithm that maintains a queue to keep a track of all the pages in a memory.
When a page needs to be replaced, the page at the FRONT of the Queue will be replaced. The FIFO page replacement technique is not implemented in operating systems nowadays.
C Program To Implement FIFO Page Replacement Algorithm in OS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include<stdio.h> int main() { int reference_string[10], page_faults = 0, m, n, s, pages, frames; printf("\nEnter Total Number of Pages:\t"); scanf("%d", &pages); printf("\nEnter values of Reference String:\n"); for(m = 0; m < pages; m++) { printf("Value No. [%d]:\t", m + 1); scanf("%d", &reference_string[m]); } printf("\nEnter Total Number of Frames:\t"); { scanf("%d", &frames); } 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(reference_string[m] == temp[n]) { s++; page_faults--; } } page_faults++; if((page_faults <= frames) && (s == 0)) { temp[m] = reference_string[m]; } else if(s == 0) { temp[(page_faults - 1) % frames] = reference_string[m]; } printf("\n"); for(n = 0; n < frames; n++) { printf("%d\t", temp[n]); } } printf("\nTotal Page Faults:\t%d\n", page_faults); return 0; } |
Output
If you have any doubts or compilation errors in this C program to implement First In First Out Page Replacement Algorithm in operating system, let us know about it in the comment section below.
Does this program work in Windows OS?
I don’t find any reason that will hamper its execution in Windows operating system.
What is meant by a conservative algorithm?
If on any consecutive request sequence containing n or fewer distinct page references, the conservative algorithm will incur n or fewer page faults.
Amazing code. Finally I got a working code for fifo replacement. Thanks.
The FIFO Page Replacement Algorithm is used by the VMX/VAX Operating Systems, along with some modifications.
Nice explanation of the FIFO Page replacement program in OS.
I need fifo replacement algorithm program with arrival time
showing errors in system
why use -lm at the end of program name?
Showing this errors:
FIFO.c: In function ‘main’:
FIFO.c:12: error: ‘i’ undeclared (first use in this function)
FIFO.c:12: error: (Each undeclared identifier is reported only once
FIFO.c:12: error: for each function it appears in.)
——
I have declared “i” as an int , but shows funny results. Please fix it!!
Hi Sam. I’ve modified the code. You should not see any error now.
Hi Tushar, Thank you for your quick reply.
No problem! 🙂
I am trying to get Page Fault Percentage.
I have added the below code but it shows 0 !! Can you help
double fault_Per = page_faults/pages;
printf(“\nPage Fault Percentage:\t%f\n”,fault_Per);
Use higher values in the output. You will get proper results. I’ve validated it at my end.
Could u plz explain this program.?!
This algorithm is incorrect:
Try this: Frames = 3, Pages = 12, ref. sequence 2,3,2,1..
The problem is here:
temp[m] = reference_string[m];
When the cycle reaches m = 3, it will try to put ‘1’ in temp[m=3] which would be frame #4 and that exceeds the size of the number of specified frames.
The code has some mistake in line
if((page_faults <= frames) && (s == 0))
{
temp[m] = reference_string[m];
}
Suppose the ref. sequence is 1,1,2,3,4
then 1 is at temp[0] i.e temp is: 1,-1,-1, again 1 is a hit so nothing is done ,temp is again:1,-1,-1
and 2 is at reference_string[2], here m=2, but it should be put at temp[1] not at temp[2];
So below is the modified code;
we take a variable k and initialize it to 0 in 1st line of main() function;
int k=0;
//loops
if((page_faults <= frames) && (s == 0))
{
temp[k++] = reference_string[m];
}
//this worked for me
Hey, thanks. I was noticing the same issue and I was trying to figure out where I should put the “pointer” for which frame to replace. I appreciate it!
constant expression required—line 18
Can you run this code for 3frames,20 strings,
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 it should give 16 as page fault but it’s giving 8 so I didn’t understand.
can u please explain the steps how it is being entered into the array and the use of page fault and s