LRU Page Replacement Algorithm in C

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.

19 thoughts on “LRU Page Replacement Algorithm in C”

        1. 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.

  1. I love myself for this

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

  2. BetterProgrammerthanOP

    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.

  3. Hey,

    Thanks for the program. It helps.
    Was wondering how can I find total number of dirty bits(or pages) from the code above?

Leave a Comment

Your email address will not be published. Required fields are marked *