LRU Page Replacement Algorithm C

In this article, we will discuss the LRU Page replacement in C with its pseudocode.

Any page replacement algorithm's main goal is to decrease the amount of page faults. The LRU page replacement algorithm substitutes a new page for the least recently used page when one is needed. This approach is predicated on the idea that, among all pages, the least recently used page won't be utilized for a very long time. It is a well-liked and successful page replacement method.

How does the LRU Page Replacement Algorithm work?

LRU is an acronym for Least Recently Used. This algorithm is built on the principle that whenever a page fault happens, the least recently used page will be replaced with a new page, as the name of the program suggests. Consequently, the memory page that has been idle the longest (in relation to all the other pages) is changed. LRU paging is the practice that uses LRU page replacement method.

When a program in use attempts to access a page of memory that isn't already in the main memory (RAM), a page fault occurs. On the other hand, it is referred to as a page hit if that page is already existent in the memory. At the time of a page fault, the LRU page replacement method enters the scene.

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.

1. 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.
2. else
   • Increment page faults.
   • If pages have fewer pages than it can hold, then:
   • Current page will be added to pages.
3. Else
   • Remove the first page from pages if necessary.
   • At the end of pages, append the current page.
4. Return the total number of page hits and faults.

Program for LRU Page Replacement Algorithm in C:

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 worst-case time complexity for set and map operations is O(n), but O(n) is the dominant term. The average time complexity is O(1).

Space Complexity:

O(capacity) is a constant that changes according to the size of the input array and the memory buffer.

LRU Page Replacement Algorithm Advantages:

The LRU page replacement algorithm has the following benefits:

1. The page that has been inactive the longest is changed.
2. The algorithm produces fewer page faults than any other.
3. The Belady's anomaly never affects the algorithm.
4. The algorithm can perform a thorough analysis.

LRU Page Replacement Algorithm disadvantages:

LRU's page replacement algorithm has the following drawbacks:

1. This algorithm's usage is challenging.
2. The hardware may have a significant role in the execution of this algorithm.

Conclusion:

The memory's least recently utilized page is replaced with a new page by the LRU page replacement mechanism.

The least recently used page in the RAM will not be used for a considerable amount of time, according to the LRU page replacement method.

When a program tries to access a memory page that isn't already in the memory, a page fault happens.

When a program tries to access a memory page that is already in the memory, a page hit occurs.

When compared to alternative page replacement methods, the LRU algorithm produces the fewest page faults.

Hardware assistance is needed for the LRU algorithm to run.