How does the LRU Page Replacement Algorithm work?
LRU stands for Least Recently Used. This method operates on the concept that the page that has not been accessed for the longest time will be swapped out when a page fault occurs, in line with its name. Hence, the memory page that has been inactive for the most extended period (compared to other pages) is swapped out. LRU paging involves implementing the LRU page replacement strategy.
When an active program tries to retrieve a memory page not currently in the primary memory (RAM), it triggers a page fault. Conversely, if the page is already present in memory, it is termed as a page hit. In the event of a page fault, the Least Recently Used (LRU) page replacement technique comes into play.
Pseudocode of LRU Algorithm in OS
Let's assume that s is the main memory's page holding capacity, and that page is a list of all the pages that are currently present there.
- Go through the pages that are referenced again. The current page should be removed from pages if it is already there. The current page will be added to the list of pages. Increase page hits.
- else Increment page faults. If pages have fewer pages than it can hold, then: Current page will be added to pages.
- Else Remove the first page from pages if necessary. At the end of pages, append the current page.
- Return the total number of page hits and faults .
- The current page should be removed from pages if it is already there.
- The current page will be added to the list of pages.
- Increase page hits.
- Increment page faults.
- If pages have fewer pages than it can hold, then:
- Current page will be added to pages.
- Remove the first page from pages if necessary.
- At the end of pages, append the current page.
Program for LRU Page Replacement Algorithm in C:
#include <stdio.h>
// Function to find the index of the least recently used page in frames
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], 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;
time[i] = 0; // Initialize the time array to 0
}
for (i = 0; i < no_of_pages; ++i) {
int page = pages[i];
int page_found = 0;
// Check if the page is already in frames
for (j = 0; j < no_of_frames; ++j) {
if (frames[j] == page) {
time[j] = counter++; // Update the time of use
page_found = 1;
break;
}
}
// If the page is not in frames, find the LRU page to replace
if (!page_found) {
pos = findLRU(time, no_of_frames);
frames[pos] = page; // Replace the LRU page
time[pos] = counter++; // Update the time of use
faults++;
}
// Print the current state of frames
printf("Current frames: ");
for (j = 0; j < no_of_frames; ++j) {
printf("%d\t", frames[j]);
}
printf("\n");
}
printf("\nTotal Page Faults = %d\n", faults);
return 0;
}
Output:
Enter number of frames: 3
Enter number of pages: 10
Enter reference string: 7 0 1 2 0 3 0 4 2 3
Current frames: 7 -1 -1
Current frames: 7 0 -1
Current frames: 7 0 1
Current frames: 2 0 1
Current frames: 2 0 1
Current frames: 3 0 1
Current frames: 3 0 4
Current frames: 3 2 4
Current frames: 3 2 4
Current frames: 3 2 4
Total Page Faults = 7
Analysis of Complexity:
Time Complexity:
The maximum time complexity for set and map operations is O(n), with O(n) being the primary factor. On the other hand, the typical time complexity is O(1).
Space Complexity:
The value of O(capacity) is a fixed quantity that adjusts based on the dimensions of the input array and the memory buffer.
LRU Page Replacement Algorithm Advantages:
The LRU page replacement algorithm has the following benefits:
- The page that has been inactive the longest is changed.
- The algorithm produces fewer page faults than any other.
- The Belady's anomaly never affects the algorithm.
- The algorithm can perform a thorough analysis.
LRU Page Replacement Algorithm disadvantages:
LRU's page replacement algorithm is associated with the following limitations:
Implementing this algorithm can be quite complex.
The hardware configuration may significantly impact the performance of this algorithm.
Conclusion:
The LRU page replacement algorithm swaps out the page that has been least recently accessed from memory with a new page.
The page that has not been accessed for a long period will be considered as the least recently used page in the RAM based on the LRU page replacement technique.
When a program attempts to retrieve data from a memory page that is not currently stored in the main memory, a page fault occurs.
When a program attempts to retrieve data from a memory page that is already present in the memory, it results in a page hit.
When contrasted with other page replacement techniques, the Least Recently Used (LRU) algorithm results in the lowest number of page faults.
Hardware support is essential to enable the LRU algorithm to function properly.