Least Recently Used (LRU) Algorithm

LRU in Operating System

Least Recently Used (LRU) Algorithm

Computer instructions use data and information present in chunks called pages. These pages are swapped between the main and the secondary memory during program execution. It is also estimated that the pages that have been most frequently used in the current instructions will again be used in the upcoming instructions.

In such a case, the operating system removes the unused pages from the main memory. It is based on the assumption that recent unused pages will remain unused for the next few instructions.

The concept is implemented through an algorithm to manage such a page fault. The algorithm retains a linked list of all the pages present in the memory retaining the most recently used page at high priority and the least recently used page at low priority. The priority is changed as per program executions.

Algorithm for LRU Page Replacement

  • Step 1. Start the process
  • Step 2. Declare the page size
  • Step 3. Determine the number of pages to be inserted.
  • Step 4. Get the value.
  • Step 5. Declare the counter and stack value.
  • Step 6. Choose the least recently used page by the counter value.
  • Step 7. Stack them as per the selection.
  • Step 8. Display the values.
  • Step 9. Terminate the process.


If the access sequence of the programs in the operating system is P Q R S T R U.

The sequence can be represented diagrammatically as follows.

                                                            LRU in OS

The boxes contain numbers of the sequence that needs to be followed. In the given case, P is the page that is least used. Hence, P will be replaced by Q.