Least Recently Used (LRU) Algorithm

January 21, 2023

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.

Example:

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.  

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