Monday, 30 September 2013

Optimal Page Replacement

Since optimal page replacement is not used practically and is implement for comparing algos hence it doesn't need a dynamic queue or link list and hence here it has been implemented using arrays

let 70120304230321201701 be the sequence string
number of pages are 20
if frame size taken 3 number of page faults will be 9

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

int frame[100];//frame
int a[100];//to store pages
int Frame_size;//to store frame size;
int n;//to store number of pages to be input by user
int j=0;
int nulp()//function to return the index number of the page which will not be used for longest period ie..which is to removed from the frame
{
    int i=0;
    int jj=j+1;
    int max=-1;
    int pos;
  while(1)
  {
    while(1)
    {
      if(frame[i]==a[jj])
      {
        if(max<(jj-j))
        {
        max=jj-j;
        pos=i;
        }
        jj=j+1;  
        i++;
        break;    
      }
      else  
      {
             
               jj++;
               if(jj==n)
               {
               max=jj-n;
               pos=i;
               return i;
               jj=j+1;
               i++;
               break;
               }
      }
   
    }
    if(i==Frame_size)
      break;      
  }
  return pos;
}

int ifexist(int i)
{
    int j1;
    for(j1=0;j1<Frame_size;j1++)
    {
                             if(frame[j1]==i)
                             return 1;
    }
    return 0;
}
main()
{
      puts("Enter the number of pages");
      scanf("%d",&n);
      puts("Enter  pages");
      int i=0;
      for(i=0;i<n;i++)
      scanf("%d",&a[i]);
      puts("Eneter the Frame size");
      scanf("%d",&Frame_size);
   
   
   
      int Fault=0;//counting the number of page faults occur
      int counter=0;//to make sure size of frame is equal to the Frame_size as entered
   
      frame[counter]=a[j];
      counter++;
      j++;
      Fault++;//we can be sure when first element will be entered it will be a fault
      while(j<n)
      {
             if((counter<Frame_size)&&(!ifexist(a[j])))
             {
                frame[counter]=a[j];
                j++;
                counter++;
                Fault++;                          
             }
             if(ifexist(a[j]))
             j++;
             if((counter==Frame_size)&&(!ifexist(a[j])))
             {
             
               int i=nulp();//returns the index number of element which will not be utilized for longest period of time or page which has to be removed                                      
               frame[i]=a[j];
               j++;
               Fault++;
                                 
             }            
      }
      printf("%d",Fault);
      getch();    
}

No comments:

Post a Comment