LRU Page Replacement Algorithm in C++

June 30, 2023

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 Page Replacement Algorithm in C++

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.

Read More About LRU
LRU Page Replacement Algorithm in OS
OS dekstop gif
OS mobile gif

Priority Scheduling

CPU Scheduling

FCFS Scheduling

Preemptive Scheduling

LRU Program in C++ (Method-1)

Run 
#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)

Run 
#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 Prime
OS dekstop banner

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

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout
Operating systems Memory

      Read More

  1. Memory Management Introduction
  2. Partition Allocation Method
    1. First Fit in OS
      1. Program in C | C++ | Java | Python
    2. Best fit
      1. Program in C | C++ | Java | Python
    3. Worst fit
      1. Program in C | C++ | Java | Python
    4. Next fit
      1. Program in C | C++ | Java | Python
    5. First fit best fit worst fit in OS Example
  3. Buddy- System Allocator
  4. Paging
    1. Types of Paging
  5. Fragmentation
    1. internal fragmentation
    2. external fragmentation
    3. internal fragmentation vs external fragmentation
  6. Mapping Virtual address to Physical Address.
  7. Virtual Memory 
  8. Demand Paging
  9. Implementation of Demand paging and page fault
  10. Segmentation
  11. Page Replacement Algorithms
    1. LRU
    2. FIFO
    3. Optimal Page Replacement algorithm
  12. Thrashing
  13. Belady’s Anomaly
  14. Static vs Dynamic Loading
  15. Static vs Dynamic Linking
  16. Swapping
  17. Translational Look Aside Buffer
  18. Process Address Space
  19. Difference between Segmentation and Paging
Go to Operating System Tutorials Main Page