Optimal Page Replacement Algorithm

// Program to Implement Optimal Page Replacement Algorithm

#include <stdio.h>

# define infinite 1000


int fdistance(int trace[],int ntrace, int start,int pageno )

  {
    int i;

    for(i=start+1;i<ntrace ;i++)

     if(pageno==trace[i])

       return(i-start);

      return(infinite);
   }


 int search(int a[],int n, int pageno)
   {
     int i;

     for(i=0;i<n;i++)

       if(a[i]==pageno)

     return(1);

     return(0);
   }



  int findmax(int a[],int n)

   {
     int i,j;
     j=0;

     for(i=1;i<n;i++)

      if(a[i] > a[j])

     j=i;

     return(j);
   }

 int findempty(int a[],int n)
   {
     int i;
     for(i=0;i<n;i++)
       if(a[i]==-1)
        return(i);
     return(-1);
   }

int main()
 {
    int optf[10],trace[30],ntrace,nframes;

    int i,j,loc,optd[10];

    float opth=0.00;

    printf("\n Enter no. of frames : ");
    scanf("%d",&nframes);

    printf("\n enter no of entries in the page trace : ");
    scanf("%d",&ntrace);

    printf("\nEnter page trace : ");

    for(i=0;i<ntrace;i++)
    scanf("%d",&trace[i]);

    /** initialize frames */

    for(i=0;i<nframes;i++)
     {
    optf[i]=-1;
    optd[i]=0;
     }

 /*allocation */
   printf("\nPage no.     OPT Allocation");

   for(i=0;i<ntrace;i++)

    {

 //OPT
      if(!search(optf,nframes,trace[i]))

    {
        loc=findempty(optf,nframes);

        if(loc!=-1)//Empty Frame

            optf[loc]=trace[i];

        else
           {  
              //Page fault

            loc=findmax(optd,nframes);

            optf[loc]=trace[i];
           }
    }

     else

       //Page Hit,Adjust forward distance

    opth=opth+1;

   for(j=0;j<nframes;j++)

    optd[j]=fdistance(trace,ntrace,i, optf[j]);

//print report

     printf("\n %d        ",trace[i]);

     for(j=0;j<nframes;j++)

       printf("%3d ",optf[j]);


  }

 printf("\npage fault:   %.2f" ,ntrace-opth);
 return (0);

 }

-------------------------------------------------------------------------------------------

output:

[root@localhost ~]# cc opt.c
[root@localhost ~]# ./a.out

 Enter no. of frames : 3

 enter no of entries in the page trace : 12

Enter page trace : 2
3
2
1
5
2
4
5
3
2
5
2

Page no.     OPT Allocation
 2          2  -1  -1
 3          2   3  -1
 2          2   3  -1
 1          2   3   1
 5          2   3   5
 2          2   3   5
 4          4   3   5
 5          4   3   5
 3          4   3   5
 2          2   3   5
 5          2   3   5
 2          2   3   5
page fault:   6.00[root@localhost ~]#