Here you will get program for lru page replacement algorithm in C.
Least Recently Used (LRU) page replacement algorithm works on the concept that the pages that are heavily used in previous instructions are likely to be used heavily in next instructions. And the page that are used very less are likely to be used less in future. Whenever a page fault occurs, the page that is least recently used is removed from the memory frames. Page fault occurs when a referenced page in not found in the memory frames.
Below program shows how to implement this algorithm in C.
Program for LRU Page Replacement Algorithm in C
#include<stdio.h>
int findLRU(int time[], int n){
int i, minimum = time[0], pos = 0;
for(i = 1; i < n; ++i){
if(time[i] < minimum){
minimum = time[i];
pos = i;
}
}
return pos;
}
int main()
{
int no_of_frames, no_of_pages, frames[10], pages[30], counter = 0, time[10], flag1, flag2, i, j, pos, faults = 0;
printf("Enter number of frames: ");
scanf("%d", &no_of_frames);
printf("Enter number of pages: ");
scanf("%d", &no_of_pages);
printf("Enter reference string: ");
for(i = 0; i < no_of_pages; ++i){
scanf("%d", &pages[i]);
}
for(i = 0; i < no_of_frames; ++i){
frames[i] = -1;
}
for(i = 0; i < no_of_pages; ++i){
flag1 = flag2 = 0;
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == pages[i]){
counter++;
time[j] = counter;
flag1 = flag2 = 1;
break;
}
}
if(flag1 == 0){
for(j = 0; j < no_of_frames; ++j){
if(frames[j] == -1){
counter++;
faults++;
frames[j] = pages[i];
time[j] = counter;
flag2 = 1;
break;
}
}
}
if(flag2 == 0){
pos = findLRU(time, no_of_frames);
counter++;
faults++;
frames[pos] = pages[i];
time[pos] = counter;
}
printf("\n");
for(j = 0; j < no_of_frames; ++j){
printf("%d\t", frames[j]);
}
}
printf("\n\nTotal Page Faults = %d", faults);
return 0;
}
Output
Enter number of frames: 3
Enter number of pages: 6
Enter reference string: 5 7 5 6 7 3
5 -1 -1
5 7 -1
5 7 -1
5 7 6
5 7 6
3 7 6
Total Page Faults = 4
Video Tutorial
Comment below if you have doubts or found anything incorrect in above lru page replacement algorithm in C.
plz execute in manually the programming code..
can u please explain why `int time[10]’ is for?
For to store,how many times that particular page has been repeated
It is not executing
what problem you are getting?
For what purpose we are using flag1 and flag2
Under biggest for loop logic there are three conditions are there first one for checking page is is in frame or not second one is inserting the page in in frame where -1 are there, the third one for finding the lru
So if the first condition occurred then flag 1 flag 2 to become one then the control cannot go to the second or third condition ok.
If we are in second condition when the flag 1 and flag 2 is 0 , so after executing second condition flag 2 become 0. So that we cannot go to the 3rd condition.
If first and second condition not execute then we can go to the third condition.
Conclusion flag 1 and flag 2 used for executing any one condition out of 3rd condition.
dont no but the page faults are not showing in the output and no any error
*FCFS*
#include
#include
int main()
{
int i,j,sum=0,n;
int ar[20],tm[20];
int disk;
clrscr();
printf(“enter number of location\t”);
scanf(“%d”,&n);
printf(“enter position of head\t”);
scanf(“%d”,&disk);
printf(“enter elements of disk queue\n”);
for(i=0;i<n;i++)
{
scanf("%d",&ar[i]);
tm[i]=disk-ar[i];
if(tm[i]<0)
{
tm[i]=ar[i]-disk;
}
disk=ar[i];
sum=sum+tm[i];
}
/*for(i=0;i<n;i++)
{
printf("\n%d",tm[i]);
} */
printf("\nmovement of total cylinders %d",sum);
getch();
return 0;
}
*sstf*
#include
#include
#include
void main()
{
int queue[100],t[100],head,seek=0,n,i,j,temp;
float avg;
// clrscr();
printf(“*** SSTF Disk Scheduling Algorithm ***\n”);
printf(“Enter the size of Queue\t”);
scanf(“%d”,&n);
printf(“Enter the Queue\t”);
for(i=0;i<n;i++)
{
scanf("%d",&queue[i]);
}
printf("Enter the initial head position\t");
scanf("%d",&head);
for(i=1;i<n;i++)
t[i]=abs(head-queue[i]);
for(i=0;i<n;i++)
{
for(j=i+1;jt[j])
{
temp=t[i];
t[i]=t[j];
t[j]=temp;
temp=queue[i];
queue[i]=queue[j];
queue[j]=temp;
}
}
}
for(i=1;i<n-1;i++)
{
seek=seek+abs(head-queue[i]);
head=queue[i];
}
printf("\nTotal Seek Time is%d\t",seek);
avg=seek/(float)n;
printf("\nAverage Seek Time is %f\t",avg);
getch();
}
*scan*
#include
using namespace std;
int main()
{
clrscr();
int n,d[8],a,b,c=0,j,i=0;
char ch=’y’;
cout<>n;
cout<>a;
for(i=0;i<n;i++)
{
cout<<"Enter value of cylinder "<<i+1<>d[i];
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(d[i]<d[j])
{
b=d[i];
d[i]=d[j];
d[j]=b;
}
}
}
for(i=0;ia)
{
j=i;
break;
}
}
c=0;
b=0;
do
{
c+=abs(b-d[j]);
b=d[j];
j++;
}while(j<n);
c=c+a;
cout<<" \nTotal head movement = "<<c<<" cylinders";
getch();
}
*c-scan*
#include
#include
void scan(int left[],int right[],int i,int head,int n)
{
int ans[20];
int a,b,c,d;
a=i-1;
d=0;
c=n-1-i;
b=i;
while(a>-1)
{ cout<<“\n a is “<<a;
cout<<“\n left[a] is”<<left[a];
ans[d]=left[a];
cout<<“\n answer is”<<ans[d];
a–;
d++;
}
cout<<“d is”<<d;
while(d<n)
{
ans[d]=right[c];
cout<<“\n right c is”<<right[c];
cout<<“\n ans[d] is “<<ans[d];
c–;
d++;
}
cout<<“order is”;
getch();
for(int j=0;j<n;j++)
{
cout<<“\n”<<ans[j];
}
}
void divide(int d[],int n,int head)
{
cout<<“array is”;
for(int q=0;q<n;q++)
{
cout<<“\n “<<d[q];
}
int left[10],right[10];
for(int i=0;ihead)
{
cout<<“breaking at “<<d[i];
break;
}
}
cout<<“value of i”<<i;
int k,l,m;
l=1;
k=0;
m=n;
left[0]=d[0];
cout<<“left is”<<left[0];
while(l<i)
{
cout<<“\n d[l] value” <<d[l];
left[l]=d[l];
cout<<“\n left is “<<left[l];
l++;
cout<<“l is “<<l;
}
int o;
o=i;
while(o<m)
{
right[k]=d[o];
cout<<“\n right is”<<right[k];
cout<<“\n d[i] is”<<d[o];
k++;
o++;
}
scan(left,right,i,head,n);
}
void sort(int d[],int n)
{
int temp,small,pos;
for(int i=0;i<n-1;i++)
{
small=d[i];
pos=i;
for(int j=i+1;jd[j])
{
small=d[j];
pos=j;
}
}
temp=d[pos];
d[pos]=d[i];
d[i]=temp;
}
}
void main()
{
clrscr();
int head,d[20],n;
cout<>n;
cout<>head;
for(int i=0;i<n;i++)
{
cout<>d[i];
}
sort(d,n);
divide(d,n,head);
getch();
}
What data structures do we have to use in this …. Is it queue and hash ?
You must comment your code anyway, it was helpful thankyou for posting.
Thanks for the best code
It helped me alot
how to find a hits and misses of cache and generate sequance of page requests
what are the flags1 and flags2 used for?
This code does not work, the last if statement checking flag2 == 0 is not reachable. And the for loop under if(flag1 == 0) is just wrong and is not what LRU algorithm is supposed to be doing.
Hey,
Thanks for the program. It helps.
Was wondering how can I find total number of dirty bits(or pages) from the code above?
How to find the smallest frame ? Using a counter
Please explain the for loop for length and frames
This program doesn’t work.
Wasted a lot of time on this.