LRU Page Replacement Algorithm 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.
LRU Program in C++ (Method-1)
#include <bits/stdc++.h>
using namespace std;
int checkHit(int incomingPage, int queue[], int occupied) {
for (int i = 0; i < occupied; i++) {
if (incomingPage == queue[i])
return 1;
}
return 0;
}
void printFrame(int queue[], int occupied) {
for (int i = 0; i < occupied; i++)
cout << queue[i] << "\t\t\t";
}
int main() {
int incomingStream[] = {1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3};
int n = sizeof(incomingStream) / sizeof(incomingStream[0]);
int frames = 3;
int queue[frames];
int distance[frames];
int occupied = 0;
int pagefault = 0;
cout << "Page\t Frame1 \t Frame2 \t Frame3\n";
for (int i = 0; i < n; i++) {
cout << incomingStream[i] << ": \t\t";
if (checkHit(incomingStream[i], queue, occupied)) {
printFrame(queue, occupied);
} else if (occupied < frames) {
queue[occupied] = incomingStream[i];
pagefault++;
occupied++;
printFrame(queue, occupied);
} else {
int max = INT_MIN;
int index;
for (int j = 0; j < frames; j++) {
distance[j] = 0;
for (int k = i - 1; k >= 0; k--) {
++distance[j];
if (queue[j] == incomingStream[k])
break;
}
if (distance[j] > max) {
max = distance[j];
index = j;
}
}
queue[index] = incomingStream[i];
printFrame(queue, occupied);
pagefault++;
}
cout << endl;
}
cout << "Page Fault: " << pagefault;
return 0;
}
Output
Page Frame1 Frame2 Frame3 1: 1 2: 1 2 3: 1 2 3 2: 1 2 3 1: 1 2 3 5: 1 2 5 2: 1 2 5 1: 1 2 5 6: 1 2 6 2: 1 2 6 5: 5 2 6 6: 5 2 6 3: 5 3 6 1: 1 3 6 3: 1 3 6 Page Fault: 8
LRU Program in C++ (Method-2)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m, n, position, k, l;
int a = 0, b = 0, page_fault = 0;
int total_frames = 3;
int frames[total_frames];
int temp[total_frames];
int pages[] = {1, 2, 3, 2, 1, 5, 2, 1, 6, 2, 5, 6, 3, 1, 3, 6, 1, 2, 4, 3};
int total_pages = sizeof(pages) / sizeof(pages[0]);
for (m = 0; m < total_frames; m++)
{
frames[m] = -1;
}
for (n = 0; n < total_pages; n++)
{
cout << pages[n] << ": ";
a = 0, b = 0;
for (m = 0; m < total_frames; m++)
{
if (frames[m] == pages[n])
{
a = 1;
b = 1;
break;
}
}
if (a == 0)
{
for (m = 0; m < total_frames; m++)
{
if (frames[m] == -1) {
frames[m] = pages[n];
b = 1;
page_fault++;
break;
}
}
}
if (b == 0)
{
for (m = 0; m < total_frames; m++)
{
temp[m] = 0;
}
for (k = n - 1, l = 1; l <= total_frames - 1; l++, k--)
{
for (m = 0; m < total_frames; m++)
{
if (frames[m] == pages[k])
{
temp[m] = 1;
}
}
}
for (m = 0; m < total_frames; m++)
{
if (temp[m] == 0)
position = m;
}
frames[position] = pages[n];
page_fault++;
}
for (m = 0; m < total_frames; m++)
{
cout << frames[m] << "\t";
}
cout << std::endl;
}
cout << "\nTotal Number of Page Faults:\t" << page_fault << std::endl;
return 0;
}
Output
1: 1 -1 -1 2: 1 2 -1 3: 1 2 3 2: 1 2 3 1: 1 2 3 5: 1 2 5 2: 1 2 5 1: 1 2 5 6: 1 2 6 2: 1 2 6 5: 5 2 6 6: 5 2 6 3: 5 3 6 1: 1 3 6 3: 1 3 6 6: 1 3 6 1: 1 3 6 2: 1 2 6 4: 1 2 4 3: 3 2 4 Total Number of Page Faults: 11
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Read More
- Memory Management Introduction
- Partition Allocation Method
- Buddy- System Allocator
- Paging
- Types of Paging
- Fragmentation
- Mapping Virtual address to Physical Address.
- Virtual Memory
- Demand Paging
- Implementation of Demand paging and page fault
- Segmentation
- Page Replacement Algorithms
- Thrashing
- Belady’s Anomaly
- Static vs Dynamic Loading
- Static vs Dynamic Linking
- Swapping
- Translational Look Aside Buffer
- Process Address Space
- Difference between Segmentation and Paging
Login/Signup to comment