# Write a Program in C to Implement Optimal Page Replacement Algorithm

#### 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,count =0,f;
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,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,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.