Memory Management is one of the crucial topics from Operating System subject and is often asked in interviews of companies such as Amazon, Microsoft, Google, Adobe, Walmart Global Tech, and many others.
From all the page replacement algorithms, the LRU (Least Recently Used) Page Replacement Algorithm is among the most commonly used algorithm due to its superior performance as compared to FIFO.
In this blog, we will discuss the LRU page replacement algorithm, how does it work, its pros and cons, and a solved example to make this concept crystal clear for you.
What is the LRU Page Replacement Algorithm?
The LRU (Least Recently Used) Page Replacement Algorithm replaces the page which has not been used for the longest duration of time in case of a page fault where all page frames are occupied.
The working principle of LRU page replacement algorithm is very easy to grasp and is based on following concepts:
If a page has not been recently used, chances are very rare that it may be used soon.
This algorithm uses the principle of locality, which states that recently accessed pages are more likely to be accessed again.
Why Do We Need LRU Page Replacement?
The operating system has a finite amount of physical memory (RAM). In case all the page frames are filled and a new page is to be brought in, then the operating system has to choose a page which it will remove.
A good page replacement technique will help in:
→ Reducing page faults
→ Improving memory utilization
→ Increasing system performance
→ Improving the speed of execution of applications
LRU is one of the best techniques to do so as it takes into account the access pattern of the memory.
Memory management involves more than page replacement. Learn how Segmentation in Operating System organizes memory and how it differs from paging.
How Does the LRU Page Replacement Algorithm Work?
Steps involved are:
- Find out whether the desired page is in memory or not.
- If it is present then it is called a page hit.
- If it is not present then it is a page fault.
- In case of empty frames, load the new page.
- If all frames are occupied then remove the least recently used page.
- Load the new page and rearrange the access sequence.
Always the least recently used page is removed.
Preparing for software engineering interviews? Practice more with our curated Operating System Interview Questions covering memory management, processes, deadlocks, paging, and more.
Example of LRU Page Replacement
Consider we have 3 page frames and the following reference string:
7, 0, 1, 2, 0, 3, 0, 4
| Page | Frames | Result |
|---|---|---|
| 7 | 7 | Fault |
| 0 | 7 0 | Fault |
| 1 | 7 0 1 | Fault |
| 2 | 2 0 1 | Fault(7 removed) |
| 0 | 2 0 1 | Hit |
| 3 | 2 0 3 | Fault (1 removed) |
| 0 | 2 0 3 | Hit |
| 4 | 4 0 3 | Fault (2 removed) |
Total number of Page Faults = 6
It should be noted that whenever the memory becomes full, the least recently used pages are replaced.
Advantages of LRU Page Replacement Algorithm
Following are some of the advantages of LRU page replacement algorithm:
- Better performance compared to FIFO in many cases
- Reduces unnecessary page faults
- Uses recent history of memory accesses
- Useful for systems having locality of reference
- Commonly used in operating systems and caching systems
Disadvantages of LRU Page Replacement Algorithm
Some of the drawbacks of LRU are as follows:
- Maintaining the record of the pages used
- Greater implementation difficulty than FIFO
- Extra memory space is required for storing timestamp or linked list
- May lead to higher overhead in a big system
LRU vs FIFO Page Replacement
| Feature | LRU (Least Recently Used) | FIFO (First In First Out) |
|---|---|---|
| Replacement Basis | Least recently used page | First page loaded |
| Performance | Often better | May cause more page faults |
| Complexity | Higher | Simple |
| Need of Memory Record | Yes | No |
While appearing for an interview, you need to keep in mind that LRU is superior to FIFO regarding performance.
LRU is one of several page replacement techniques. Explore our complete blog on Page Replacement in OS to compare FIFO, LRU, Optimal, and other algorithms.
Time Complexity of LRU Page Replacement
Time Complexity depends upon the implementation being done.
- Using Hash Map + Doubly Linked List: O(1) average case complexity
- Using Arrays or Lists: O(n)
Modern-day Operating systems use efficient data structures to enhance the efficiency of LRU algorithm.
Applications of LRU Page Replacement Algorithm
Applications of LRU page replacement algorithm include:
→ Operating Systems
→ Cache Management in CPU
→ Browser Cache
→ Database Buffer Management
→ Distributed Systems
→ Web Servers
→ Content Delivery Network (CDN)
Efficiency in managing frequently accessed data makes it a highly practical caching algorithm.
LRU Page Replacement Algorithm - Interview Questions
Some interview questions include:
- What is the LRU Page Replacement Algorithm?
- How is LRU different from FIFO?
- Why is LRU better than FIFO?
- What is principle of locality?
- What is page fault and page hit?
- What is the time complexity of LRU?
- Where LRU is used in real world?
Such type of questions are generally asked in Operating System Interviews.
Learn Operating Systems for Product-Based Companies
Operating Systems is among the topics assessed in technical interviews. Apart from OS, companies also test candidates on Data Structures & Algorithms, DBMS, Computer Networks, and System Design.
At Bosscoder Academy, experienced mentors from top product-based companies help working professionals master these concepts through structured learning, mock interviews, and practical problem-solving. In case you are getting ready for a coding interview or looking forward to moving into a product-based company, enhancing your OS fundamentals is a good point to start with.
Want to learn another important OS interview topic? Read our guide on Deadlock Avoidance in Operating System to understand how operating systems prevent deadlocks using popular avoidance techniques.
Conclusion
The Least Recently Used (LRU) Page Replacement Algorithm replaces the least recently used page. With the use of access history, it is usually more efficient than FIFO and helps minimize the page faults, which makes it one of the most common page replacement algorithms.
Having knowledge of how LRU algorithm works, practicing examples, and understanding the pros, cons, and interview application will be helpful in answering OS questions in coding interviews.
Ready to check your Operating System concepts? Take our Operating System MCQ Test and practice questions on memory management, paging, deadlocks, scheduling, and more.
Frequently Asked Questions (FAQs)
Q1. Explain the LRU Page Replacement Algorithm?
LRU (Least Recently Used) is a page replacement algorithm that eliminates the least recently used page when there is no space left in memory.
Q2. How is LRU better than FIFO?
As LRU considers the use of pages recently used, it is more efficient in reducing page faults compared to FIFO.
Q3. What is the time complexity of LRU?
Using Hash Map and Doubly Linked List, LRU works with O(1) time complexity on an average basis.
Q4. Is LRU asked in software engineering interviews?
Yes, LRU is one of the most common topics in Operating System interviews for software engineering internship or role at product-based companies.
