Write a Program in C to Implement FIFO Page Replacement Algorithm

by

Aim:

To Write a Program in C to Implement FIFO Page Replacement Algorithm,

Description:

  • Page replacement algorithms are used to decide what pages to page out when a page needs to be allocated.
  • This happens when a page fault occurs and a free page cannot be used to satisfy the allocation

FIFO:

  • “Replace the page that had not been used for a longer sequence of time”.
  • The frames are empty in the beginning and initially no page fault occurs so it is set to zero. When a page fault occurs the page reference sting is brought into the memory.
  • The operating system keeps track of all pages in the memory, thereby keeping track of the page that had not been used for longer sequence of time.
  • If the page in the page reference string is not in memory, the page fault is incremented and the page that had not been used for a longer sequence of time is replaced. If the page in the page reference string is in the memory take the next page without calculating the next page.
  • Take the next page in the page reference string and check if the page is already present in the memory or not.
  • Repeat the process until all pages are referred and calculate the page fault for all those pages in the page references string for the number of available frames.

Exercise

Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, six, and seven frames?

Remember that all frames are initially empty, so your first unique pages will cost one fault each.

  • FIFO replacement
  • LRU replacement
  • Optimal replacement

Algorithm:

  • 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

Program:

#include <stdio.h>
#include<stdbool.h>
int rs[100],count =0,f[10];
bool dataavi(int n)
{
int i;
for(i=0;i<n;i++)
{
if(rs[count]==f[i])
return 1;
}
return 0;
}

void fifo(int n,int m)
{
int fs=0,i=0,j=0,kom=0;
while(count<m)
{
if(count<n)
{
f[count]=rs[count++];
fs++;
kom=1;
}
else
{
if(dataavi(n))
{
count++;
kom=0;
}
else
{
kom=1;
f[j]=rs[count++];
fs++;
j++;
if(j>=n)
j=0;
}
}
if(kom==1)
printf(" Page Fault :");
else
printf("            :");
for(i=0;i<n;i++)
printf(" %d",f[i]);
printf("\n");
}
printf("\n\nPAGE FAULTS = %d",fs);
}
int main()
{
int n ,m,i;
printf("ENTER THE NO OF FRAME AND REFERENCE STREAM\n");
scanf ("%d%d",&n,&m);
printf ("ENTER THE REFERENCE STREAM\n");
for(i=0;i<m;i++)
scanf("%d",&rs[i]);
fifo(n,m);
return 0;
}

Execution:

Input:
3 20 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

Output:

ENTER THE NO OF FRAME AND REFERENCE STREAM
ENTER THE REFERENCE STREAM
 Page Fault : 1 0 0
 Page Fault : 1 2 0
 Page Fault : 1 2 3
 Page Fault : 4 2 3
            : 4 2 3
 Page Fault : 4 1 3
 Page Fault : 4 1 5
 Page Fault : 6 1 5
 Page Fault : 6 2 5
 Page Fault : 6 2 1
            : 6 2 1
 Page Fault : 3 2 1
 Page Fault : 3 7 1
 Page Fault : 3 7 6
            : 3 7 6
 Page Fault : 2 7 6
 Page Fault : 2 1 6
            : 2 1 6
 Page Fault : 2 1 3
 Page Fault : 6 1 3


PAGE FAULTS = 16

Result:

Thus FIFO Page Replacement Algorithm program was executed Successfully.

Leave a Comment