Write a Program in C to Implement LRU Page Replacement Algorithm

by

Aim:

To write a program in C to Implement LRU Page Replacement Algorithm.

Description:

  • Page replacement algorithms are used to decide what pages to page out when a page needs to be allocated.
  • This happens when a page fault occurs and a free page cannot be used to satisfy the allocation

Types:

  • FIFO replacement
  • LRU replacement
  • Optimal replacement

LRU:

  • “Replace the page that had not been used for a longer sequence of time”.
  • The frames are empty in the beginning and initially no page fault occurs so it is set to zero. When a page fault occurs the page reference sting is brought into the memory.
  • The operating system keeps track of all pages in the memory, thereby keeping track of the page that had not been used for longer sequence of time.
  • If the page in the page reference string is not in memory, the page fault is incremented and the page that had not been used for a longer sequence of time is replaced. If the page in the page reference string is in the memory take the next page without calculating the next page.
  • Take the next page in the page reference string and check if the page is already present in the memory or not.
  • Repeat the process until all pages are referred and calculate the page fault for all those pages in the page references string for the number of available frames.

Algorithm:

  • 1- Start traversing the pages.
    1. i) If set holds less pages than capacity.
      • a) Insert page into the set one by one until the size of set reaches capacity or all page requests are processed.
      • b) Simultaneously maintain the recent occurred index of each page in a map called indexes.
      • c) Increment page fault
    2. ii) Else If current page is present in set, do nothing.
      • Else
        1. a) Find the page in the set that was least recently used. We find it using index array. We basically need to replace the page with minimum index.
        2. b) Replace the found page with current page.
        3. c) Increment page faults.
        4. d) Update index of current page.
  • 2 – Return page faults.

Program:

#include <stdio.h>
#include<stdbool.h>
int rs[100],count =0;
struct max{
int f[10];
bool lu[10];
}s;
struct min{
int buf[10];
int mat[10];
}nat;
bool dataavi(int n)
{
int i;
for(i=0;i<n;i++)
{
if(rs[count]==s.f[i])
return 1;
}

return 0;
}
int check(int n,int m)
{
int i,j=0;
for(j=0;j<n;j++)
{
int x=0;

for(i=count+1;i<m;i++)
{

if(s.f[j]==rs[i])
{
nat.buf[j]=i;
nat.mat[j]=j;
i=m+1;
x=1;
}
}
if(x==0&&s.lu[j]==0)
return j;
}

for (i = 0; i < n-1; i++)
{
for (j = 0; j < n-i-1; j++)
{
if (nat.buf[j] < nat.buf[j+1])
{
int temp=nat.buf[j];
nat.buf[j]=nat.buf[j+1];
nat.buf[j+1]=temp;
temp=nat.mat[j];
nat.mat[j]=nat.mat[j+1];
nat.mat[j+1]=temp;
}

}}
for(i=0;i<n;i++)
{
if(s.lu[nat.mat[i]]==0)
{
return nat.mat[i];
}
}
}

void lru (int n,int m)
{
int fs=0,i=0,in=0,kom=0;
for(i=0;i<n;i++)
s.lu[i]=false;
s.lu[n-1]=true;
while(count<m)
{
if(in<n)
{
if(dataavi(n)&&in>0)
{
count++;kom=0;
}
else
{
s.f[in++]=rs[count]; kom=1;
fs++;
count++;


}
}
else
{
if(dataavi(n))
{
count++; kom=0;
}
else
{
int j=check(n,m);
s.f[j]=rs[count++];
fs++; kom=1;
for(i=0;i<n;i++)
s.lu[i]=false;
s.lu[j]=true;
}
}
if(kom==1)
printf(" Page Fault :");
else
printf("            :");
for(i=0;i<n;i++)
printf(" %d",s.f[i]);
printf("\n");

}
printf("\n\npage faults =%d",fs);
}
int main()
{
int n ,m,i;
printf("ENTER THE NO OF FRAME AND REFERENCE STREAM\n");
scanf ("%d%d",&n,&m);
printf ("ENTER THE REFERENCE STREAM \n");
for(i=0;i<m;i++)
scanf("%d",&rs[i]);
lru (n,m);
return 0;
}

Execution:

Input:
3 20 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6


Output:

ENTER THE NO OF FRAME AND REFERENCE STREAM
ENTER THE REFERENCE STREAM 
 Page Fault : 1 0 0
 Page Fault : 1 2 0
 Page Fault : 1 2 3
 Page Fault : 4 2 3
            : 4 2 3
 Page Fault : 4 2 1
 Page Fault : 5 2 1
 Page Fault : 5 2 6
            : 5 2 6
 Page Fault : 1 2 6
            : 1 2 6
 Page Fault : 1 3 6
 Page Fault : 7 3 6
            : 7 3 6
            : 7 3 6
 Page Fault : 7 3 2
 Page Fault : 1 3 2
            : 1 3 2
            : 1 3 2
 Page Fault : 1 6 2


page faults =13

Result:

Thus LRU Page Replacement Algorithm program was executed Successfully.

Leave a Comment