Introduction
Modern operating systems support:
Multitasking
Virtual memory
Concurrent process execution
Since physical memory (RAM) is limited, operating systems often cannot keep all process pages in memory simultaneously.
When a process references a page that is not currently in RAM:
A page fault occurs
The operating system must then:
Load the required page
Possibly remove another page from memory if RAM is full
The strategy used to decide:
Which page should be removed
is called a:
Page Replacement Algorithm
One important page replacement strategy is:
LFU (Least Frequently Used)
LFU attempts to keep frequently accessed pages in memory while removing rarely used pages.
Understanding LFU is important because it demonstrates how operating systems use:
Access patterns
Memory locality
Historical usage statistics
to optimize memory performance.
What is LFU?
LFU stands for:
Least Frequently Used
LFU is a page replacement algorithm that removes the page with:
Lowest access frequency
Core Idea
Pages used least often are considered least important and replaced first
Important Insight
LFU assumes frequently accessed pages are likely to be used again
Why LFU is Necessary
Suppose RAM full and new page required.
Operating system must choose:
Victim page for replacement
Poor replacement choices increase:
Page faults
Disk I/O
Performance degradation
LFU attempts to improve efficiency by:
Preserving heavily used pages
Relationship with Virtual Memory
LFU works within:
Demand paging systems
Pages loaded:
Only when needed
When RAM becomes full:
LFU selects page for eviction
How LFU Works
Operating system maintains:
Frequency counter for each page
Each page access:
Counter increases
When replacement needed:
Page with smallest count removed
Example
Suppose memory contains:
| Page | Frequency |
|---|---|
| A | 10 |
| B | 2 |
| C | 5 |
| D | 7 |
If new page needed:
Page B removed
because:
Lowest frequency
LFU Workflow
Step 1
Page referenced.
Step 2
Frequency counter updated.
Step 3
Page fault occurs when page absent.
Step 4
If memory full:
Lowest-frequency page selected
Step 5
Victim page removed.
New page loaded.
Important Insight
LFU replacement decisions depend entirely on historical access counts
Example of LFU Step-by-Step
Suppose:
Memory capacity = 3 pages
Reference string:
A B A C B A D
Step-by-Step Table
| Step | Memory | Frequencies |
|---|---|---|
| A | A | A=1 |
| B | A B | A=1 B=1 |
| A | A B | A=2 B=1 |
| C | A B C | A=2 B=1 C=1 |
| B | A B C | A=2 B=2 C=1 |
| A | A B C | A=3 B=2 C=1 |
| D | A B D | A=3 B=2 D=1 |
Page removed:
C
because:
Lowest frequency
Frequency Counters
LFU requires:
Per-page counters
Counter updated:
Every memory access
Hardware/Software Support
Counters may be implemented using:
Software tracking
Hardware assistance
Problem: Tie Situations
Suppose multiple pages have:
Same lowest frequency
Need:
Tie-breaking strategy
Common approaches:
FIFO among tied pages
LRU among tied pages
Important Insight
LFU often combines with secondary policies for tie resolution
Advantages of LFU
1. Keeps Important Pages
Frequently used pages preserved.
2. Exploits Locality
Applications repeatedly access hot pages.
3. Good for Stable Workloads
Repeated-access patterns handled well.
Example
Database index pages frequently accessed:
Remain cached
Disadvantages of LFU
1. Historical Bias Problem
Old heavily-used pages may remain forever even if no longer useful.
Example
Page heavily used earlier:
Keeps high frequency permanently
even if:
Not recently accessed
2. Counter Maintenance Overhead
Tracking frequencies expensive.
3. Slow Adaptation
LFU may respond poorly to workload changes.
Important Insight
LFU may incorrectly preserve stale pages because of old historical usage
Aging Problem in LFU
Very important LFU weakness.
Suppose:
Page used heavily long ago
Rarely used now
LFU still favors it because:
Counter remains high
Solution: Aging Mechanisms
Operating systems may:
Periodically reduce counters
Example:
frequency = frequency / 2
Advantages:
Recent accesses become more important
LFU vs LRU
Students commonly confuse these algorithms.
LFU
Uses:
Frequency of access
LRU
Uses:
Recency of access
Comparison Table
| Feature | LFU | LRU |
|---|---|---|
| Basis | Frequency | Recent usage |
| Keeps | Frequently used pages | Recently used pages |
| Historical bias | High | Lower |
| Adaptability | Slower | Faster |
Example Difference
Suppose:
Page used frequently long ago
Not used recently
LFU:
Keeps page
LRU:
Removes page
LFU and Locality of Reference
LFU relies on:
Locality of reference
Especially:
Frequency locality
Programs often repeatedly access:
Same pages
Examples:
Loops
Frequently used functions
Shared libraries
Complexity of LFU
Naive LFU implementation:
Expensive
Requires:
Frequent counter updates
Victim searches
Optimized Implementations
Use:
Hash tables
Frequency lists
Min-heaps
LFU in Modern Systems
Pure LFU rarely used directly in operating systems.
Reason:
Complexity
Aging problems
However LFU-inspired ideas used in:
Database caches
Web caches
CDN systems
Memory management policies
LFU in CPU Caches
Some caching systems approximate:
LFU behavior
to preserve frequently accessed data.
Page Faults and LFU
Goal of LFU:
Minimize page faults
by preserving:
Frequently used pages
Thrashing and LFU
If working set larger than RAM:
LFU alone cannot prevent thrashing
System may still:
Continuously swap pages
Real-World Example
Suppose web server repeatedly accesses:
Authentication module
Configuration files
Frequently requested pages
LFU keeps these frequently accessed pages in RAM while removing:
Rarely accessed content
Advantages Summary
Preserves frequently used pages
Effective for stable workloads
Exploits repeated-access behavior
Disadvantages Summary
Historical bias
Slow adaptation
Counter overhead
Aging issues