C code to implement Optimal Algorithm

The optimal policy selects for replacement that page for which the time to
the next reference is the longest.

/* C program to implement Optimal Algorithm */

#include<stdio.h>

int main()
{
int page[20],frame[10][2],i=0,j,k=0,l=0,n,num,a,found,pf=0,x,max,ch;
char c;
FILE *fp;

fp=fopen("fifo.txt","r");
while(fscanf(fp,"%d%c",&a,&c)!=EOF)
page[i++]=a;
n=i;
while(1)
{
i=0,found=0;
printf("\nEnter the frame size:");
scanf("%d",&num);
for(i=0;i<num;i++)
{
frame[i][0]=0;
frame[i][1]=-1;
}

for(i=0;i<n;i++)
{
found=0;
for(j=0;j<num;j++)
if(page[i]==frame[j][1])
{
found=1;
//x=j;
//frame[x][0]=k++;
}
if(found==0)
{
pf++;
for(j=0;j<num;j++)
if(frame[j][1]==-1)
break;
if(j!=num)
frame[j][0]=1,frame[j][1]=page[i];

else
{
for(j=0;j<num;j++)

{
for(k=i+1;k<n;k++)
if(frame[j][1]==page[k])
break;

frame[j][0]=k-i;
}
max=0;
for(j=0;j<num;j++)
if(max<frame[j][0])
{
max=frame[j][0];
x=j;
}

frame[x][1]=page[i];
//frame[x][0]=k++;
}

}

for(l=0;l<num;l++)
{
if(frame[l][1]==-1)
printf("|  ");
else
printf("|%d ",frame[l][1]);
}
if(found==0)
printf("Page Fault\n");
else
printf("No page fault\n");
printf("\n\n");
}
printf("\nTotal page faults=%d",pf);
pf=0;
printf("\nPress 1 to continue:");
scanf("%d",&ch);

if(ch!=1)
break;
}
return 0;
}

Input File:

7,7,4,4,2,1,4,1,5,3,2,1,4,7,6,1,9,8,0,1

//Output Of the above program:-

1 comment:

1. I would have named the variables with more intuitive names and also commented what each block of code does, but it does seem to work. Here is C++ code for Fifo, Lru and Optimal page replacement algorithms by Doug Purinton.