Least Frequently Used (LRU) in C++

May 7, 2021

Least Recently Used (LRU) Algorithm

Operating systems use paging for memory management. Paging is a method to store or retrieve processes from the secondary memory into the main memory in the form of pages. Paging happens when a page fault occurs, and a free page cannot be used to satisfy the allocation. It is because there are none or the number of free pages is lower than the threshold.

LRU in C++ Language

It generates the need of page replacement algorithm which can lessen the waiting time for pages in. The Least Recently Used (LRU) page replacement algorithm, needs to decide which page is to be replaced when the new page comes in.

This LRU algorithm manages page fault. The algorithm maintains a linked list of all the pages in the memory, it keeps the most recently used page in the front and the least recently used page at the rear position. Let us understand LRU with an example.

Example

Pages = 2 3 4 2 1 3 7 5 4 3
Number of iteration = 10
Memory size = 3

The sequence can be represented diagrammatically as follows.

We will sequentially put the first three pages in the order given as we have sufficient space.

1	2	3	4	5	6	7	8	9	10
2	2	2
	3	3
		4

Now, comes 2. We will not replace 2 as it is already there.

We will sequentially put the first three pages in the order given as we have sufficient space.

1	2	3	4	5	6	7	8	9	10
2	2	2	2
	3	3	3
		4	4

Now remove 3 as it the least recent page used.

1	2	3	4	5	6	7	8	9	10
2	2	2	2	2
	3	3	3	1
		4	4	4

Now remove 4 as it the least recent page used out of all.

1	2	3	4	5	6	7	8	9	10
2	2	2	2	2	2
	3	3	3	1	1
		4	4	4	3

Now remove 2 as it the least recent page used out of all.

1	2	3	4	5	6	7	8	9	10
2	2	2	2	2	2	7
	3	3	3	1	1	1
		4	4	4	3	3

Now remove 1 as it is the least recent page used out of all.

1	2	3	4	5	6	7	8	9	10
2	2	2	2	2	2	7	7
	3	3	3	1	1	1	5
		4	4	4	3	3	3

Similarly, remove 3 as it is the least recent page used.

1	2	3	4	5	6	7	8	9	10
2	2	2	2	2	2	7	7
	3	3	3	1	1	1	5	5
		4	4	4	3	3	4

Last we will remove 7 as it is least recent page used.

1	2	3	4	5	6	7	8	9	10
2	2	2	2	2	2	7	7	7	3
	3	3	3	1	1	1	5	5	5
		4	4	4	3	3	3	4	4

Read Also – LRU in Java

LRU code in C++

   
  #include<iostream>
    using namespace std;
    int main()
    {
            int nopages, nofaults, page[20],i ,count=0;
            cout<<“\n\t Enter no of pages for which you want to calculate page faults:>”; 
            cin>> nopages;  //it will store the number of Pages
            cout<<“\n\t Enter the Reference String:”;
            for(i=0;i< nopages;i++)
            {
            cout<<“\t“; 
            cin>>page[i];
            }   
            cout<<“\n\t Enter the Number of frames:”; 
            cin>> nofaults;
            int frame[nofaults],fcount[nofaults];
            for(i=0;i< nofaults;i++)
            {
            frame[i]=-1;
            fcount[i]=0; //it will keep the track of when the page was last used
            }
            i=0;
            while(i< nopages)
            {
                int j=0,flag=0;
                while(j< nofaults)
                {
                if(page[i]==frame[j]){  //it will check whether the page already exist in frames or not
                flag=1;
                fcount[j]=i+1;
                }
                j++;
                }   
                j=0;  
                cout<<“\n\t***\n“;
                cout<<“\t“<<page[i]<<“–>”;   
                if(flag==0)
                {
                int min=0,k=0;
                while(k<nofaults-1) 
                { 
                    if(fcount[min]>fcount[k+1]) //It will calculate the page which is least recently used
                    min=k+1;
                    k++;
                    }
                frame[min]=page[i]; 
                fcount[min]=i+1;  //Increasing the time
                count++;           //it will count the total Page Fault
                while(j< nofaults)
                {
                cout<<“\t|”<<frame[j]<<“|”;
                j++;
                }
                }
            i++; 
            }
            cout<<“\n\t***\n“;
            cout<<“\n\t Page Fault:”<<count;
            return 0;
    } 

Output

Enter no of pages for which you want to calculate page faults: 8 
Enter the Reference String: 7 
0
1
2
0
3
0
5
Enter the Number of frames: 3
7 7 -1 -1
0 7 0 -1
1 7 0 1
2 2 0 1
0
3 2 0 3
0
5 4 0 3
Page faults: 6