Write a Program in C to Implement Optimal Page Replacement Algorithm

by

Aim:

To write a program in C to Implement Optimal 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

Types:

  • FIFO replacement
  • LRU replacement
  • Optimal replacement

Optimal:

  • “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.

Algorithm:

  1. If referred page is already present, increment hit count.
  2. If not present, find if a page that is never referenced in future. If such a page exists, replace this page with new page.

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;
}
int check(int n,int m)
{
int buf[10],i,j=0;
for(j=0;j<n;j++)
{
int x=0;
for(i=count+1;i<m;i++)
{

if(f[j]==rs[i])
{
buf[j]=i;
i=m+1;
x=1;
}

}
if(x==0)
return j;
}
int max =buf[0],maxi=0;
for(i=0;i<n-1;i++)
{
if(max<=buf[i+1])
{
max=buf[i+1];
maxi=i+1;
}
}
return maxi;
}
void optimal(int n,int m)
{
int fs=0,i=0,in=0,kom=0;
while(count<m)
{
if(in<n)
{
if(dataavi(n)&&in>0)
{
count++;
kom=0;
}
else
{
f[in++]=rs[count];
fs++;
count++;
kom=1;
}
}
else
{
if(dataavi(n))
{
count++;
kom=0;
}
else
{
int j=check(n,m);
f[j]=rs[count++];
fs++;
kom=1;
}
}
if(kom==1)
printf(" Page Fault :");
else
printf("            :");
for(i=0;i<n;i++)
printf(" %d",f[i]);
printf("\n");
}
printf("\n\npage fault =%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]);
optimal(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 : 1 2 4
            : 1 2 4
            : 1 2 4
 Page Fault : 1 2 5
 Page Fault : 1 2 6
            : 1 2 6
            : 1 2 6
            : 1 2 6
 Page Fault : 3 2 6
 Page Fault : 3 7 6
            : 3 7 6
            : 3 7 6
 Page Fault : 3 2 6
 Page Fault : 3 2 1
            : 3 2 1
            : 3 2 1
 Page Fault : 6 2 1


page fault =11

Result:

Thus Optimal Page Replacement Algorithm program was executed Successfully.

Leave a Comment