











Least Frequently Used (LRU) in C++


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.
2 | 3 | 4 | 2 | 1 | 3 | 7 | 5 | 4 | 3 |
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.
2 | 3 | 4 | 2 | 1 | 3 | 7 | 5 | 4 | 3 |
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.h> 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 numer 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 Numer 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
Login/Signup to comment