Page Replacement Algorithms

This page gives you, the listing of all page replacement algorithms, which you can use as you like.Page replacement is used as an alternative to the older methods of keeping the entire big program in memory although majority of it's pages are not used.


All the programmes below are in "C" and use file handling.There will be sub headings related to the Page replacement algorithms and below them are the corresponding code snippets.The code once compiled runs automatically using the data from text file and displays the output.Tested for DevCPP and codeblocks in Windows.Just be careful to keep the input text file in the same folder as programmes and change the name of the input file in the programme to correspond to the text file.If you have doubts, comment, will clarify them, with in at max two days.

Input file (Input.txt – same for all algorithms)

20

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1


1.FIFO

#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21];//To take the input of reference string
int frame[SIZE];//This is for frames
int repptr=0;//The pointer for the page that needs to be replaced
int count=0;//For counting number of page faults
int display()//To display the elements of the frame
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
    }
int Pagerep(int ele)
{
 int temp;
                    
 temp=frame[repptr];
 frame[repptr]=ele;
 repptr++;//The pointer moves to the next frame since the current frame became the newest
  if(repptr==SIZE)
 repptr=0;
 return temp;   //Returns the victim page
}
int Pagefault(int ele)
{if(full!=SIZE)
               frame[full++]=ele;//Untill all the frames fill, there is no call for page replacement
else
printf("The page replaced is %d",Pagerep(ele));//Displaying of victim page
}
int Search(int ele)//This would search and return the flag that tells whether the page is already //present in the frame or not
{int i,flag;
    flag=0;
    if(full!=0)
    {
    for(i=0;i<full;i++)
    if(ele==frame[i])
 {   flag=1;
    break;
}}
 return flag;   
}
int main()
{int n,i;
    FILE *fp;//For taking input from a file
    //Start
    fp=fopen("Input.txt","r");
    printf("The number of elements in the reference string are :");
    fscanf(fp,"%d",&n);
    printf("%d",n);
    for(i=0;i<n;i++)
    fscanf(fp,"%d",&a[i]);
    fclose(fp);
    printf("\nThe elements present in the string are\n");
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    printf("\n\n");
    //End
    for(i=0;i<n;i++)
    {
                    if(Search(a[i])!=1)
                    {Pagefault(a[i]);
                    display();
                    count++;
                    }
                                        }
                    printf("\nThe number of page faults are %d\n",count);
                    getche();//For waiting
return 0;
}

2.Optimal Page Replacement Algorithm

#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
static int f=0;
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
  }
int Longestopt()
{int temp[SIZE]={0};/*This is for checking the occurence of nearest possible future pages, considering no page is nearest in the beginning*/
int c=0;//Counter to break the loop once we get two nearest future pages
int id,i,k,j=SIZE;
id=0;
    for(i=f+1;i<n;i++)//Checking from the current time of use till the end of string for future references
    {  for(k=0;k<j;k++)  //Checking whether a page occurs in future or not
 {   if(a[i]==frame[k])
{if(temp[k]!=1)
{temp[k]=1;
               c++;
}

    break;}}
if(c==2)
break;//Once we get two future pages then we may break
}
id=2;
while(id!=0)
{if(temp[id]==0)//Checking for the page which is not the nearest future reference
break;
    id--;
}
repptr=id;
return repptr;//Returning the replacement pointer with the value of victim page
}
int Pagerep(int ele)
{
 int temp;
 repptr=Longestopt();
 temp=frame[repptr];
 frame[repptr]=ele;
  return temp;   
}
int Pagefault(int ele)
{if(full!=SIZE)
frame[full++]=ele;
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
    flag=0;
    if(full!=0)
    {
    for(i=0;i<full;i++)
    if(ele==frame[i])
 {   flag=1;
    break;
}}
 return flag;   
}
int main()
{int i;
    FILE *fp;
    fp=fopen("Input.txt","r");
    printf("The number of elements in the reference string are :");
    fscanf(fp,"%d",&n);
    printf("%d",n);
    for(i=0;i<n;i++)
    fscanf(fp,"%d",&a[i]);
    printf("\nThe elements present in the string are\n");
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {f=i;
                    if(Search(a[i])!=1)
                    {Pagefault(a[i]);
                    display();
                    count++;
                    }
                                        }
                    printf("\nThe number of page faults are %d\n",count);
                    getche();
return 0;
}
    
    
3.LRU using Stack

#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
int stk[SIZE];//Stack for storing the page numbers as per their reference criteria
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",stk[i]);    
}
/* A function for removing the referenced element from the stack and keeping it in the top, while moving all
the elements up or down corresepondingly*/
int LRstackopt(int p)//The input to this function is the referenced page
{int temp;
int i;
for(i=0;i<n;i++)
if(stk[i]==p)
break;
temp=stk[i];//Storing the referenced value in temp
while(i!=SIZE-1)//Moving the other elements so that the TOP is empty
{stk[i]=stk[i+1];i++;
}
stk[i]=temp;//Storing the element in the TOP from temp
}
int Pagerep(int ele)
{
 int temp;
 repptr=stk[0];//Always the victim page is selected as the first element of stack
 temp=frame[repptr];
 frame[repptr]=ele;
 LRstackopt(repptr);//Now the page that is brought is the latest referenced one, so it is moved to TOP
 return temp;   
}
int Pagefault(int ele)
{if(full!=SIZE)
{stk[full]=full;//First stack is populated till all the pages are full
               frame[full++]=ele;}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
    flag=0;
    if(full!=0)
    {
    for(i=0;i<full;i++)
    if(ele==frame[i])
 {   flag=1;LRstackopt(i);//When ever reference is made, but pae fault doesn't occur, the referenced page is moved to TOP
    break;
}}
 return flag;   
}
int main()
{int i;
    FILE *fp;
    fp=fopen("Input.txt","r");
    printf("The number of elements in the reference string are :");
    fscanf(fp,"%d",&n);
    printf("%d",n);
    for(i=0;i<n;i++)
    fscanf(fp,"%d",&a[i]);
    printf("\nThe elements present in the string are\n");
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {
                    if(Search(a[i])!=1)
                    {Pagefault(a[i]);
                                      count++;
                    }
                      display();
                    }
                    printf("\nThe number of page faults are %d\n",count);
                    getche();
return 0;
}
    
 4.LRU using Counter

#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
int ctr[SIZE]={0};
static int f=0;//This is a counter that keeps track of current time
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
int Longestopt()//Fucntion for discivering the least recently used page using their corresponding counter values
{int i,min;
    min=0;
    for(i=0;i<SIZE;i++)
    if(ctr[min]>ctr[i])
    min=i;
        repptr=min;
return repptr;
}
int Pagerep(int ele)
{
 int temp;
 repptr=Longestopt();//Gets the LRU page from a function
 temp=frame[repptr];
 frame[repptr]=ele;
 ctr[repptr]=f;//When ever a page is brought it's counter is kept as per the current time of use
  return temp;   
}
int Pagefault(int ele)
{if(full!=SIZE)
{ctr[full]=f;//Setting the counter as per current time of use
               frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
    flag=0;
    if(full!=0)
    {
    for(i=0;i<full;i++)
    if(ele==frame[i])
 {   flag=1;ctr[i]=f;//If page fault doesn't occur, but the element is referenced, it's counter is set to the current time of use
    break;
}}
 return flag;   
}
int main()
{int i;
    FILE *fp;
    fp=fopen("Input.txt","r");
    printf("The number of elements in the reference string are :");
    fscanf(fp,"%d",&n);
    printf("%d",n);
    for(i=0;i<n;i++)
    fscanf(fp,"%d",&a[i]);
    printf("\nThe elements present in the string are\n");
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {f++;//Time of use is incremented
                    if(Search(a[i])!=1)
                    {Pagefault(a[i]);
                    display();
                    count++;
                    }
                    
                    }
                    printf("\nThe number of page faults are %d\n",count);
                    getche();
return 0;
}

5.LFU

#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
int ctr[SIZE]={0};//Counter to know the frequency, intially all have zero frequency of use
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
}
int Longestopt()
{int i,min;
    min=0;
    for(i=0;i<SIZE;i++)//The page with least frequency is selected as victim
    if(ctr[min]>ctr[i])
    min=i;
        repptr=min;
return repptr;
}
int Pagerep(int ele)
{
 int temp;
 repptr=Longestopt();//The victim page is selected with the help of a function
 temp=frame[repptr];
 frame[repptr]=ele;
 ctr[repptr]=1;//A new page is brought, hence it's counter is set to 1
  return temp;   
}
int Pagefault(int ele)
{if(full!=SIZE)
{ctr[full]++;//The counters will increase initially for all frames till they are full
               frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
    flag=0;
    if(full!=0)
    {
    for(i=0;i<full;i++)
    if(ele==frame[i])
 {   flag=1;ctr[i]++;//Whenever a reference is made the counter is incremented
    break;
}}
 return flag;   
}
int main()
{int i;
    FILE *fp;
    fp=fopen("Input.txt","r");
    printf("The number of elements in the reference string are :");
    fscanf(fp,"%d",&n);
    printf("%d",n);
    for(i=0;i<n;i++)
    fscanf(fp,"%d",&a[i]);
    printf("\nThe elements present in the string are\n");
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {
                    if(Search(a[i])!=1)
                    {Pagefault(a[i]);
                    display();
                    count++;
                    }
                    }
                    printf("\nThe number of page faults are %d\n",count);
                    getche();
return 0;
}
    
    


6.MFU

#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21],n;//To take the input
int frame[SIZE];
int ctr[SIZE]={0};
static int f;
int repptr;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
      }
int Longestopt()
{int i,max;
    max=0;//The increment of counter value here is same as that for of LFU
    for(i=0;i<SIZE;i++)//The page with maximum frequency is selected
    if(ctr[max]<ctr[i])
    max=i;
        repptr=max;
return repptr;
}
int Pagerep(int ele)
{
 int temp;
 repptr=Longestopt();
 temp=frame[repptr];
 frame[repptr]=ele;
 ctr[repptr]=1;
  return temp;   
}
int Pagefault(int ele)
{if(full!=SIZE)
{ctr[full]++;
               frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
    flag=0;
    if(full!=0)
    {
    for(i=0;i<full;i++)
    if(ele==frame[i])
 {   flag=1;ctr[i]++;
    break;
}}
 return flag;   
}
int main()
{int i;
    FILE *fp;
    fp=fopen("Input.txt","r");
    printf("The number of elements in the reference string are :");
    fscanf(fp,"%d",&n);
    printf("%d",n);
    for(i=0;i<n;i++)
    fscanf(fp,"%d",&a[i]);
    printf("\nThe elements present in the string are\n");
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {f=i;
                    if(Search(a[i])!=1)
                    {Pagefault(a[i]);
                    display();
                    count++;
                    }
                                        }
                    printf("\nThe number of page faults are %d\n",count);
                    getche();
return 0;
}

7.Second Chance Algorithm

#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21];//To take the input
int ref[SIZE];//This is for reference bits for each frame
int frame[SIZE];
int repptr=0;//Initialised to first frame
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]);
 }
int Pagerep(int ele)
{
 int temp;
 /*When ever a page needs to be replaced the repptr moves from page to page checking whether it's reference bit is 0 or not, if it is 0 it
 coomes out of the while loop and if it is one, it gives a second chance setting the reference bit to 0*/
 while(ref[repptr]!=0)
{ ref[repptr++]=0;
 if(repptr==SIZE)
 repptr=0;
}                     
 temp=frame[repptr];
 frame[repptr]=ele;
 ref[repptr]=1;//The latest page reference, hence it is set to 1
 return temp;   
}
int Pagefault(int ele)
{if(full!=SIZE)
{ref[full]=1;//All the ref bits are set to 1 as each frame is being filled firstly
               frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
    flag=0;
    if(full!=0)
    {
    for(i=0;i<full;i++)
    if(ele==frame[i])
 {   flag=1;ref[i]=1;//When ever page reference occurs, it's rference bit is set to 1
    break;
}}
 return flag;   
}
int main()
{int n,i;
    FILE *fp;
    fp=fopen("Input.txt","r");
    printf("The number of elements in the reference string are :");
    fscanf(fp,"%d",&n);
    printf("%d",n);
    for(i=0;i<n;i++)
    fscanf(fp,"%d",&a[i]);
    printf("\nThe elements present in the string are\n");
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {
                    if(Search(a[i])!=1)
                    {Pagefault(a[i]);
                    display();
                    count++;
                    }
                                        }
                    printf("\nThe number of page faults are %d\n",count);
                    getche();
return 0;
}
    
8.Additional Reference Bits Algorithm

#include<stdio.h>
#define SIZE 3
int full=0;//To check whether all frames are filled
int a[21];//To take the input
int ref[SIZE];
char r=1;
 int frame[SIZE];
unsigned char addref[SIZE]={0};
int repptr=0;
int count=0;
int display()
{int i;
printf("\nThe elements in the frame are\n");
for(i=0;i<full;i++)
printf("%d\n",frame[i]); 
}
//For showing bits
int bitrep(char f)//Program for showing the bits
{char p,fl;
int j;
 char i=1;
 for(j=7;j>=0;j--)
 {p=i<<j;
 fl=p&f;
 if(fl==0)
 printf("0");
 else
 printf("1");
}
  printf("\n");     
}
//For showing bit wise
int additionalreference()
{
 int i,min;
 min=0;
 for(i=1;i<SIZE;i++)
 if(addref[min]>addref[i])//Finding the smallest decimal value from all the strings available
 min=i;
 repptr=min;
 return repptr;
}
int Pagerep(int ele)
{
 int temp;
repptr=additionalreference();                   
 temp=frame[repptr];
 frame[repptr]=ele;
 ref[repptr]=1;
 return temp;   
}
int Pagefault(int ele)
{if(full!=SIZE)
{ref[full]=1;
               frame[full++]=ele;
}
else
printf("The page replaced is %d",Pagerep(ele));
}
int Search(int ele)
{int i,flag;
    flag=0;
    if(full!=0)
    {
    for(i=0;i<full;i++)
    if(ele==frame[i])
 {   flag=1;ref[i]=1;
    break;
}}
 return flag;   
}
int main()
{int n,i,k;
r=r<<7;
bitrep(r);
    FILE *fp;
    fp=fopen("Input.txt","r");
    printf("The number of elements in the reference string are :");
    fscanf(fp,"%d",&n);
    printf("%d",n);
    for(i=0;i<n;i++)
    fscanf(fp,"%d",&a[i]);
    printf("\nThe elements present in the string are\n");
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    printf("\n\n");
    for(i=0;i<n;i++)
    {
                    if(Search(a[i])!=1)
                    {Pagefault(a[i]);
                    display();
                    count++;
                    }
                      printf("\nThe values in shift registers related to three frames are\n");  
                  //Shifing of registers
                    for(k=0;k<SIZE;k++)
                    {
                                       addref[k]=addref[k]>>1;//Shifting all the shift registers by one bit
          
                    if(ref[k]==1)
                    { addref[k]=(r|addref[k]);//Bit OR operation for shifting
                    ref[k]=0;
                    }
    bitrep(addref[k]);
                     }
                    //End of shifting
                    }
                    printf("\nThe number of page faults are %d\n",count);
                    getche();
return 0;
}
    
    


8 comments:

  1. Which one is inexpensive implementation of LRU, stack or counter?

    ReplyDelete
  2. #include
    int n,nf;
    int in[100];
    int p[50];
    int hit=0;
    int i,j,k;
    int pgfaultcnt=0;

    void getData()
    {
    printf("\nEnter length of page reference sequence:");
    scanf("%d",&n);
    printf("\nEnter the page reference sequence:");
    for(i=0;imax)
    {
    max=near[j];
    repindex=j;
    }
    }
    p[repindex]=in[i];
    pgfaultcnt++;

    dispPages();
    }
    else
    printf("No page fault");
    }
    dispPgFaultCnt();
    }

    void lru()
    {
    initialize();

    int least[50];
    for(i=0;i=0;k--)
    {
    if(pg==in[k])
    {
    least[j]=k;
    found=1;
    break;
    }
    else
    found=0;
    }
    if(!found)
    least[j]=-9999;
    }
    int min=9999;
    int repindex;
    for(j=0;j<nf;j++)
    {
    if(least[j]<min)
    {
    min=least[j];
    repindex=j;
    }
    }
    p[repindex]=in[i];
    pgfaultcnt++;

    dispPages();
    }
    else
    printf("No page fault!");
    }
    dispPgFaultCnt();
    }

    void lfu()
    {
    int usedcnt[100];
    int least,repin,sofarcnt=0,bn;
    initialize();
    for(i=0;i<nf;i++)
    usedcnt[i]=0;

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

    printf("\n For %d :",in[i]);
    if(isHit(in[i]))
    {
    int hitind=getHitIndex(in[i]);
    usedcnt[hitind]++;
    printf("No page fault!");
    }
    else
    {
    pgfaultcnt++;
    if(bn<nf)
    { p[bn]=in[i];
    usedcnt[bn]=usedcnt[bn]+1;
    bn++; }
    else
    { least=9999;
    for(k=0;k<nf;k++)
    if(usedcnt[k]<least) { least=usedcnt[k]; repin=k; }
    p[repin]=in[i];
    sofarcnt=0;
    for(k=0;k<=i;k++)
    if(in[i]==in[k])
    sofarcnt=sofarcnt+1;
    usedcnt[repin]=sofarcnt;
    }

    dispPages();
    }



    }
    dispPgFaultCnt();
    }

    void secondchance()
    {
    int usedbit[50];
    int victimptr=0;
    initialize();
    for(i=0;i<nf;i++)
    usedbit[i]=0;
    for(i=0;i<n;i++)
    {
    printf("\nFor %d:",in[i]);
    if(isHit(in[i]))
    {
    printf("No page fault!");
    int hitindex=getHitIndex(in[i]);
    if(usedbit[hitindex]==0)
    usedbit[hitindex]=1;
    }
    else
    {
    pgfaultcnt++;
    if(usedbit[victimptr]==1)
    {
    do
    {
    usedbit[victimptr]=0;
    victimptr++;
    if(victimptr==nf)
    victimptr=0;
    }while(usedbit[victimptr]!=0);
    }
    if(usedbit[victimptr]==0)
    {
    p[victimptr]=in[i];
    usedbit[victimptr]=1;
    victimptr++;
    }
    dispPages();

    }
    if(victimptr==nf)
    victimptr=0;
    }
    dispPgFaultCnt();
    }




    int main()
    {
    int choice;
    while(1)
    {
    printf("\nPage Replacement Algorithms\n1.Enter data\n2.FIFO\n3.Optimal\n4.LRU\n5.LFU\n6.Second Chance\n7.Exit\nEnter your choice:");
    scanf("%d",&choice);
    switch(choice)
    {
    case 1:
    getData();
    break;
    case 2:
    fifo();
    break;
    case 3:
    optimal();
    break;
    case 4:
    lru();
    break;
    case 5:
    lfu();
    break;
    case 6:
    secondchance();
    break;
    default:
    return 0;
    break;
    }
    }
    }

    ReplyDelete
  3. A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
    website: geeksforgeeks.org

    ReplyDelete
  4. A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
    website: geeksforgeeks.org

    ReplyDelete
  5. A Computer Science portal for geeks. It contains well written, well thought and well
    explained computer science and programming articles, quizzes and practice/competitive
    programming/company interview Questions.
    website: geeksforgeeks.org

    ReplyDelete
  6. A Computer Science portal for geeks. It contains well written, well thought and well
    explained computer science and programming articles, quizzes and practice/competitive
    programming/company interview Questions.
    website: geeksforgeeks.org

    ReplyDelete