Least Page Replacement Algorithm

 // Program to implement Least Page Replacement Algorithm

 

//Experiment No. 8 :Least Recently Used :

#include <stdio.h>

# define infinite 1000

 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);
   }

void main()
 {
    int lruf[10],trace[30],ntrace,nframes;
    int i,j,loc,lrud[10];
    float lruh=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++)
     {
    lruf[i]=-1;
    lrud[i]=0;
     }

 /*allocation */

   printf("\nPage no.    LRU Allocation");
   for(i=0;i<ntrace;i++)
    {

      if(!search(lruf,nframes,trace[i]))
    {
       loc=findempty(lruf,nframes);
       if(loc!=-1) //Empty frame
         {
        for(j=0;j<nframes;j++)
            lrud[j]++;
        lruf[loc]=trace[i];
        lrud[loc]=0;
         }
      else
        {   //Page Fault
        loc=findmax(lrud,nframes);
        lruf[loc]=trace[i];
        for(j=0;j<nframes;j++)
            lrud[j]++;
        lrud[loc]=0;
        }
    }
       else
       {  //Page Hit,Adjust backward distance
        lruh=lruh+1;
        for(j=0;j<nframes;j++)
          {
            if(lruf[j]!=trace[i])
                lrud[j]++;
            else
                lrud[j]=0;
          }
//Print Report
       }

    printf("\n %d        ",trace[i]);
    for(j=0;j<nframes;j++)
    printf("%3d ",lruf[j],lrud[j]);
   }

 printf("\nHit ratio:   %.2f",lruh/ntrace);
 

 }
/*

************* OUTPUT *************

 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.            LRU Allocation
 2                  2  -1  -1
 3                  2   3  -1
 2                  2   3  -1
 1                  2   3   1
 5                  2   5   1
 2                  2   5   1
 4                  2   5   4
 5                  2   5   4
 3                  3   5   4
 2                  3   5   2
 5                  3   5   2
 2                  3   5   2
Hit ratio:   0.42
*/