1. Introduction
FIFO ignores how pages are actually used, while Optimal requires future knowledge that is impossible to obtain in real systems.
A practical solution is to use information about the past.
This leads to the Least Recently Used (LRU) Page Replacement Algorithm.
LRU replaces the page that has not been used for the longest time in the past.
2. What is LRU?
LRU (Least Recently Used) is a page replacement algorithm that replaces the page that was accessed least recently.
Key Idea
Replace the Page
That Has Not Been Used
For the Longest Time
3. Why LRU Works
LRU is based on the principle of Locality of Reference.
Programs tend to:
Reuse recently accessed pages
Access nearby pages repeatedly
Therefore:
Recently Used Page
↓
Likely Needed Again Soon
while
Long-Unused Page
↓
Less Likely Needed Soon
Key Insight
Past Behavior
≈
Future Behavior
4. Working Principle
When a page fault occurs:
Find the page that was used farthest back in time.
Remove that page.
Insert the new page.
5. LRU Algorithm
For each page reference:
If page exists:
Page Hit
Update recent usage
Else:
Page Fault
If free frame exists:
Insert page
Else:
Replace least recently used page
6. Example
Given
Reference String:
1 2 3 4 1 2 5 1 2 3 4 5
Frames = 3
7. Step-by-Step Execution
| Ref | Frames | Fault? | Page Removed |
|---|---|---|---|
| 1 | 1 - - | Yes | - |
| 2 | 1 2 - | Yes | - |
| 3 | 1 2 3 | Yes | - |
| 4 | 4 2 3 | Yes | 1 |
| 1 | 4 1 3 | Yes | 2 |
| 2 | 4 1 2 | Yes | 3 |
| 5 | 5 1 2 | Yes | 4 |
| 1 | 5 1 2 | No | - |
| 2 | 5 1 2 | No | - |
| 3 | 3 1 2 | Yes | 5 |
| 4 | 3 4 2 | Yes | 1 |
| 5 | 3 4 5 | Yes | 2 |
8. Result
Total Page Faults = 10
Total Hits = 2
9. Understanding LRU Decisions
Consider memory:
1 2 3
Suppose recent usage history is:
Most Recent → 3
Then → 2
Least Recent → 1
New page request:
4
LRU removes:
1
because it has not been used for the longest time.
10. Timeline View
Suppose page accesses occurred as:
Time →
1 2 3 4
Page Accesses:
A B C B
Current memory:
A B C
Page A was used earliest.
Therefore:
A = Least Recently Used
and is selected for replacement.
11. Characteristics of LRU
Uses past history
Exploits locality of reference
Practical algorithm
Approximates Optimal
Widely used in operating systems
12. Why LRU Approximates Optimal
Optimal uses:
Future Information
LRU uses:
Past Information
Because programs exhibit locality:
Recent Past
↓
Good Predictor
↓
Near-Optimal Decisions
13. Implementation Methods
13.1 Counter (Timestamp) Method
Each page stores:
Last Access Time
Whenever page is accessed:
Update Timestamp
During replacement:
Remove Smallest Timestamp
Problem
Requires continuous timestamp updates.
13.2 Stack Method
Maintain pages in order of use.
Top → Most Recently Used
Bottom → Least Recently Used
When page is accessed:
Move Page To Top
Replacement:
Remove Bottom Page
Problem
High maintenance overhead.
14. Hardware Support
Many systems use hardware support such as:
Reference bits
Access bits
Usage counters
to approximate LRU efficiently.
15. Advantages of LRU
15.1 Good Performance
Usually performs much better than FIFO.
15.2 Uses Locality of Reference
Matches real program behavior.
15.3 Near Optimal
Often close to Optimal Page Replacement.
15.4 No Belady's Anomaly
LRU is a Stack Algorithm.
Therefore:
More Frames
↓
Never Increase Faults
16. Disadvantages of LRU
16.1 Expensive Implementation
Must track page usage history.
16.2 Additional Overhead
Requires:
Counters
Stacks
Hardware support
16.3 Difficult Exact Implementation
Most systems implement approximations rather than true LRU.
17. LRU vs FIFO
| Feature | FIFO | LRU |
|---|---|---|
| Basis | Arrival Time | Recent Usage |
| Locality Awareness | No | Yes |
| Performance | Moderate | Better |
| Belady's Anomaly | Yes | No |
| Complexity | Low | Higher |
18. LRU vs Optimal
| Feature | LRU | Optimal |
|---|---|---|
| Uses Past | Yes | No |
| Uses Future | No | Yes |
| Practical | Yes | No |
| Performance | Near Optimal | Best |
| Implementation | Possible | Impossible |
19. LRU as a Stack Algorithm
A very important exam point:
LRU ∈ Stack Algorithms
Property:
Pages with n Frames
⊆
Pages with (n+1) Frames
Because of this:
Belady's Anomaly
Cannot Occur
20. Real-World Analogy
Think of apps on your phone.
Recently opened apps:
WhatsApp
Chrome
Maps
Unused app:
Calculator
When memory becomes full:
Close Calculator
Keep Recently Used Apps
This is exactly how LRU works.
Most Important Point
LRU approximates Optimal Page Replacement by assuming that pages not used recently are less likely to be used soon. It provides good performance, exploits locality of reference, and does not suffer from Belady's Anomaly.