Search Tutorials

Saturday 1 June 2013

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:-

C code to implement Optimal Algorithm
 

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.

    https://drive.google.com/open?id=0B-OZwlW6jotRUGlSbjVSdFdVNVU

    ReplyDelete

Back to Top