LRU Page Replacement Algorithm

What is the LRU Page Replacement Algorithm?

LRU stands for Least Recently Used. As the name suggests, this algorithm is based on the strategy that whenever a page fault occurs, the least recently used page will be replaced with a new page. So, the page not utilized for the longest time in the memory (compared to all other pages) gets replaced. This strategy is known as LRU paging.

A page fault occurs when a running program tries to access a piece (or page) of memory that is not already present in the main memory (RAM). On the other hand, if that page is already present in the memory, it is called a page hit. The LRU page replacement algorithm comes into the picture whenever a page fault occurs.

Example of LRU Algorithm in OS

Consider a reference string 1, 2, 1, 0, 3, 0, 4, 2, 4. Let us say there are 3 empty memory locations (or slots) available.

Initially, since all slots are empty, pages 1, 2 will be allocated to the empty memory slots and we will get two page faults (because neither page 1 nor page 2 was present in the memory).

Now, page 1 is referenced again. Because it is already present in the memory, we get a page hit, and we do not need to allocate new memory to it. Also, we will not get a page fault.

Next, page 0 is referenced. The page 0 will be allocated to the third empty slot in the memory, and we will get a page fault.

Now, page 3 is referenced and there is no empty slot in the memory. So, the LRU page replacement algorithm will come into the picture and the least recent page, i.e. page 2 will be replaced by the newly referenced page, i.e., page 3.

Next, page 0 is referenced and it is already present in the memory, so we get a page hit.

Next, page 4 is referenced. As it is not present in the memory, the LRU algorithm will be used. Since page 1 is the least recently used page, it will be replaced by page 4.

Next, page 2 is referenced. Since page 2 is not in the memory, the least recently used page, i.e. page 3 will be replaced by page 2.

Finally, page 4 is referenced. Because page 4 is already present in the memory, we will get a page hit.

In the above example, we can conclude that we had 3-page hits and 6-page faults.

Pseudocode of LRU Algorithm in OS

Let us say that s is the main memory's capacity to hold pages and pages is the list containing all pages currently present in the main memory.

1. Iterate through the referenced pages.
   • If the current page is already present in pages:
     1. Remove the current page from pages.
     2. Append the current page to the end of pages.
     3. Increment page hits.
   • Else:
     1. Increment page faults.
     2. If pages contains fewer pages than its capacity s:
        • Append current page into pages.
     3. Else:
        • Remove the first page from pages.
        • Append the current page at the end of pages.
2. Return the number of page hits and page faults.

Implementation of LRU Algorithm in OS

Using Python Programming Language

Let us now understand the implementation of the LRU page replacement algorithm by taking an example.

Output:

Code Explanation: In the above example, we assumed the main memory's page holding capacity to be 3 pages. We created a list named pages to store the pages that are currently present in the memory. The variables faults and hits were made to count the number of page faults and page hits, respectively.

A for loop was used to iterate through the reference string (the reference string stores all the referenced pages). Firstly, we checked if the referenced page ref_page was already present in the pages list or not. If ref_page was present in the list, we removed ref_page from pages and appended the same ref_page to the end of the pages list. We did so in order to keep the most recently used pages at the end of the list and the least recently used pages at the start. Then, we incremented the value of hits by 1.

If ref_page was not in pages, we incremented the value of faults by 1. Then, we checked if the pages list had empty space or not. If the pages list had any empty space (i.e. length of pages list was less than the memory capacity), we appended the ref_page at the end of the list. Otherwise, we removed the first element of the pages list (the least recently used page), and then appended the ref_page at the end of the pages list.

Finally, we printed the number of hits and faults that occurred.

Advantages of LRU Page Replacement Algorithm

The following are the advantages of the LRU page replacement algorithm:

• The page that has not been used for the longest time gets replaced.
• It gives fewer page faults than any other algorithm.
• The algorithm never suffers from the Belady's anomaly .
• The algorithm is capable of complete analysis.

Disadvantages of LRU Page Replacement Algorithm

Following are the disadvantages of the LRU page replacement algorithm:

• The execution of this algorithm is complicated.
• This algorithm's execution may require significant assistance from the hardware.