1. Introduction
LRU provides good performance because it replaces the least recently used page. However, implementing exact LRU requires maintaining detailed usage history, which is expensive in terms of hardware and software overhead.
Modern operating systems therefore use approximations of LRU.
One of the most widely used approximations is the Clock Algorithm, also known as the Second Chance Algorithm.
The Clock Algorithm provides performance close to LRU while requiring much less overhead.
2. What is the Clock Algorithm?
The Clock Algorithm is a page replacement algorithm that uses:
A circular list of pages
A reference bit (R bit)
A rotating pointer called the clock hand
to approximate LRU page replacement.
Key Idea
Recently Used
↓
Give Second Chance
Not Recently Used
↓
Replace
3. Core Concept
Each page is associated with a Reference Bit (R).
Meaning of R Bit
R = 1
Page Used Recently
R = 0
Page Not Used Recently
Whenever a page is accessed:
Reference Bit = 1
4. Why It Is Called Clock Algorithm
Pages are arranged logically in a circle.
A pointer continuously moves around the circle like the hand of a clock.
Page 1
Page 4 Page 2
Page 3
The pointer rotates:
Page 1 → Page 2 → Page 3 → Page 4
↓
Back to Page 1
5. Data Structure
The algorithm maintains:
Circular queue of pages
One reference bit per page
One clock pointer
Structure
Frame 1 (R)
Frame 2 (R)
Frame 3 (R)
Frame 4 (R)
↑
Clock Hand
6. Working Principle
When a page fault occurs:
The clock hand examines pages one by one.
7. Replacement Rules
Case 1: Reference Bit = 0
R = 0
↓
Replace Page
The page has not been used recently.
Therefore:
Victim Selected
8. Case 2: Reference Bit = 1
R = 1
↓
Give Second Chance
The algorithm:
Set R = 0
↓
Move Clock Hand Forward
The page is spared for now.
9. Complete Algorithm
Page Fault Occurs
↓
Check Page At Clock Hand
If R = 0:
Replace Page
If R = 1:
Set R = 0
Move Forward
Repeat Until R = 0 Found
10. Step-by-Step Example
Given
Frames = 3
Reference String:
1 2 3 2 4 1 5
11. Initial Loading
Reference 1
[1] [ ] [ ]
R = 1
Reference 2
[1] [2] [ ]
R = 1 1
Reference 3
[1] [2] [3]
R = 1 1 1
Memory becomes full.
12. Access Page 2
Reference:
2
Page already exists.
Set:
R(2) = 1
No page fault.
13. Reference 4
Memory:
[1] [2] [3]
R = 1 1 1
Clock hand starts scanning.
Check Page 1
R = 1
↓
Set R = 0
Check Page 2
R = 1
↓
Set R = 0
Check Page 3
R = 1
↓
Set R = 0
Pointer returns to Page 1.
Now:
R = 0
Replace Page 1 with Page 4.
Memory:
[4] [2] [3]
14. Why It Is Called Second Chance
Consider:
Page A
R = 1
Instead of immediate replacement:
Give One More Chance
↓
Reset Bit
↓
Continue
Only pages that survive an entire rotation without being referenced are removed.
15. Relationship with LRU
LRU asks:
Which Page Was Used Least Recently?
Clock asks:
Has This Page Been Used Recently?
Thus:
Clock
≈
Approximate LRU
16. Why Clock Approximates LRU
Pages used recently:
R = 1
↓
Protected
Pages unused for a long time:
R = 0
↓
Replaced
This behavior is similar to LRU.
17. Characteristics of Clock Algorithm
Uses reference bit
Circular structure
Approximates LRU
Low overhead
Practical implementation
18. Advantages
18.1 Low Overhead
Only one bit per page.
Reference Bit
=
1 Bit
18.2 Efficient
No timestamps or stacks required.
18.3 Practical
Used in real operating systems.
18.4 Near-LRU Performance
Provides good page fault rates.
19. Disadvantages
19.1 Not Exact LRU
Tracks only:
Recently Used?
Yes / No
Not exact usage order.
19.2 Multiple Scans Possible
Pointer may need several rotations.
Many Pages
R = 1
↓
Several Scans Required
19.3 Slightly Worse Than LRU
Approximation introduces some inaccuracies.
20. Clock vs FIFO
| Feature | FIFO | Clock |
|---|---|---|
| Uses Reference Bit | No | Yes |
| Locality Awareness | No | Yes |
| Performance | Moderate | Better |
| Complexity | Very Low | Low |
21. Clock vs LRU
| Feature | Clock | LRU |
|---|---|---|
| Accuracy | Approximate | Exact |
| Overhead | Low | High |
| Hardware Requirement | Minimal | Higher |
| Performance | Good | Better |
22. Enhanced Second Chance (Advanced)
Some systems use:
Reference Bit (R)
+
Modified Bit (M)
to make even better replacement decisions.
This is called:
Enhanced Clock Algorithm
23. Real-World Analogy
Imagine people sitting in a circle.
When selecting someone to leave:
Recently Spoke?
Yes
↓
Give Another Chance
Silent For Long Time?
Yes
↓
Remove
This is exactly how the Clock Algorithm works.
Most Important Point
The Clock Algorithm is a practical approximation of LRU that uses a reference bit and a circular pointer to give recently used pages a second chance before replacement, achieving good performance with low overhead.