Lru Approximations - Learning Module

Loading content...

0/240

Enhanced Second-Chance Algorithm

Not All Pages Are Created Equal

The basic Clock algorithm treats all pages with R=0 as equally suitable victims. But there's a critical distinction the basic algorithm ignores: has the page been modified since it was loaded?

Evicting a clean page (one that hasn't been modified) is cheap—we simply discard it. If needed again, we reload it from disk. But evicting a dirty page (one that has been modified) is expensive—we must first write the modified contents back to disk before we can reuse the frame. This write operation can take 5-10 milliseconds, an eternity in CPU time.

The Enhanced Second-Chance Algorithm (also called Enhanced Clock or NRU-based Clock) addresses this by considering both the reference bit (R) and the dirty/modify bit (M) when selecting victims. By preferring clean, unreferenced pages over dirty ones, we minimize expensive disk writes.

What You Will Learn

By the end of this page, you will understand: the cost difference between evicting clean vs. dirty pages, the four-class page categorization based on (R,M) bits, the enhanced algorithm that preferentially evicts cheaper victims, implementation details with multiple sweep passes, and why this refinement significantly improves I/O efficiency in real systems.

The Cost of Dirty Page Eviction

Before diving into the algorithm, let's quantify exactly why dirty page eviction is so much more expensive than clean page eviction.

Clean page eviction:

Mark page table entry as not present
Invalidate TLB entry
Mark frame as available
Total time: ~1-10 microseconds (memory operations only)

Dirty page eviction:

Mark page table entry as not present
Invalidate TLB entry
Write 4KB (or larger) page contents to disk
Wait for disk acknowledgment
Mark frame as available
Total time: ~5-15 milliseconds (disk I/O dominated)

The ratio: Dirty page eviction is approximately 1,000 to 10,000 times slower than clean page eviction!

Eviction Costs by Storage Type
Storage Type	Write Time (4KB)	Clean Eviction	Dirty Eviction	Ratio
HDD (7200 RPM)	5-10 ms	~10 µs	5-10 ms	500-1000x
SATA SSD	50-100 µs	~10 µs	50-100 µs	5-10x
NVMe SSD	10-20 µs	~5 µs	10-20 µs	2-4x
Intel Optane	5-10 µs	~5 µs	5-10 µs	~2x

The implication:

Even though SSDs dramatically reduce the dirty/clean eviction cost ratio, the difference is still significant. And on systems with traditional hard drives (still common in servers due to cost and capacity), the difference is enormous.

Example impact:

Consider a system under memory pressure that must evict 1,000 pages:

Scenario	Clean Pages	Dirty Pages	Total Time (HDD)
All clean	1,000	0	10 ms
50% dirty	500	500	5,000 ms (5 sec!)
All dirty	0	1,000	10,000 ms (10 sec!)

By preferring clean pages as victims, we can reduce eviction time by orders of magnitude.

Disk I/O Blocking

In many systems, dirty page write-back can block the page fault handler, freezing the faulting process (and potentially others waiting for memory). Minimizing dirty page evictions during fault handling directly improves system responsiveness and latency.

The Four-Class Page Categorization

The Enhanced Second-Chance algorithm categorizes pages into four classes based on the combination of two bits:

R (Reference bit): Has the page been accessed recently? (Set by hardware, cleared by OS)
M (Modify/Dirty bit): Has the page been written to since loading? (Set by hardware, never cleared until page is written back)

The four classes (in order of eviction preference):

Page Classes in Enhanced Second-Chance
Class	(R, M)	Interpretation	Eviction Cost	Priority
0	(0, 0)	Not referenced, not modified	Lowest (free)	Best victim
1	(0, 1)	Not referenced, modified	Medium (write needed)	Second choice
2	(1, 0)	Referenced, not modified	Low (free, but recent)	Third choice
3	(1, 1)	Referenced, modified	Highest (recent + write)	Last resort

Understanding the ordering:

Class 0 (0,0): The ideal victim. The page hasn't been used recently (R=0) and is clean (M=0). We can simply discard it—no disk I/O required. If needed later, we reload from the original source.

Class 1 (0,1): Not recently used, but dirty. We'll need to write it back before eviction. However, since it's not being actively used, evicting it probably won't cause an immediate re-fault.

Class 2 (1,0): Recently used but clean. The page is "hot" (recently accessed), so evicting it may cause a fault soon. However, if we must evict it, at least no write is needed.

Class 3 (1,1): The worst victim. Recently used (likely to be needed again soon) AND dirty (requires expensive write-back). Evicting this page incurs maximum cost.

Key insight: We prioritize avoiding disk writes over keeping recently-used pages. A clean page that was just accessed is a better victim than a dirty page that hasn't been touched in a while—because avoiding the write saves more time than avoiding the potential re-fault.

Converting Mermaid diagram...

NRU Connection

This four-class categorization is identical to the Not Recently Used (NRU) algorithm's classification. Enhanced Second-Chance can be viewed as combining NRU's classification with Clock's efficient circular scanning. We'll cover NRU in detail later in this module.

The Enhanced Second-Chance Algorithm

The Enhanced Second-Chance algorithm modifies the basic Clock algorithm to prefer lower-class victims. There are two main implementation approaches:

Approach 1: Multiple Pass Sweeps

Make up to four passes through the circular buffer, with each pass looking for a specific class:

Pass 1: Scan for (0,0) pages without changing any bits
Pass 2: Scan for (0,1) pages without changing any bits
Pass 3: Scan for (0,0) pages, clearing R bits as we go (gives referenced pages a chance)
Pass 4: Scan for (0,1) pages (must find one—all R bits now clear)

Algorithm pseudocode:

enhanced_second_chance.pseudo

Pseudo

function enhanced_second_chance_find_victim():
    // Pass 1: Look for (0,0) - not referenced, clean
    // Best possible victim - no disk I/O needed
    for i = 0 to NUM_FRAMES-1:
        frame_index = (clock_hand + i) % NUM_FRAMES
        page = frames[frame_index]
        
        if page.R == 0 and page.M == 0:
            clock_hand = (frame_index + 1) % NUM_FRAMES
            return frame_index  // Perfect victim found!
    
    // Pass 2: Look for (0,1) - not referenced, dirty
    // Need to write back, but page is cold
    for i = 0 to NUM_FRAMES-1:
        frame_index = (clock_hand + i) % NUM_FRAMES
        page = frames[frame_index]
        
        if page.R == 0 and page.M == 1:
            clock_hand = (frame_index + 1) % NUM_FRAMES
            return frame_index  // Acceptable victim
    
    // Pass 3: Look for (0,0) while CLEARING R bits
    // This pass gives referenced pages a "second chance"
    for i = 0 to NUM_FRAMES-1:
        frame_index = (clock_hand + i) % NUM_FRAMES
        page = frames[frame_index]
        
        // Clear R bit for next pass
        clear_reference_bit(page)
        
        if page.R == 0 and page.M == 0:  // Check AFTER clearing
            clock_hand = (frame_index + 1) % NUM_FRAMES
            return frame_index
    
    // Pass 4: Look for (0,1) - must find one now
    // All R bits have been cleared in pass 3
    for i = 0 to NUM_FRAMES-1:
        frame_index = (clock_hand + i) % NUM_FRAMES
        page = frames[frame_index]
        
        if page.R == 0 and page.M == 1:
            clock_hand = (frame_index + 1) % NUM_FRAMES
            return frame_index
    
    // Should never reach here - pass 4 guarantees finding victim
    panic("Enhanced second-chance failed to find victim")

Approach 2: Single Pass with Class Tracking

An alternative approach makes a single pass, tracking the best victim seen so far and updating if we find a better class:

Start at clock hand position
For each page, compute its class (0-3)
If class is better than best seen, update the best candidate
If we find class 0, evict immediately (can't do better)
If we complete a full sweep without class 0, evict the best found
Clear R bits during the pass to prepare for next eviction

This approach has the same worst-case complexity but potentially finds victims faster by stopping early on class 0 finds.

Implementation Choice

The multi-pass approach is more common in practice because it's conceptually simpler and has predictable memory access patterns (important for CPU cache efficiency). The single-pass approach may seem more efficient but requires more complex bookkeeping.

Detailed Implementation

Here's a complete C implementation of the Enhanced Second-Chance algorithm with full commentary:

enhanced_clock.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
/*
 * Enhanced Second-Chance (Enhanced Clock) Algorithm
 * Considers both R (reference) and M (modify/dirty) bits
 */
 
#include <stdint.h>
#include <stdbool.h>
 
#define NUM_FRAMES 256
#define PAGE_SIZE 4096
 
// PTE bit masks (x86-64)
#define PRESENT_BIT     0x001
#define WRITABLE_BIT    0x002
#define ACCESSED_BIT    0x020  // R - Reference bit
#define DIRTY_BIT       0x040  // M - Modify bit
 
typedef struct {
    uint32_t process_id;
    uint32_t virtual_page;
    uint64_t *pte_ptr;
    bool occupied;
} frame_entry_t;
 
typedef struct {
    frame_entry_t frames[NUM_FRAMES];
    uint32_t clock_hand;
    uint32_t occupied_count;
} enhanced_clock_t;
 
enhanced_clock_t eclock;
 
/*
 * Get page class based on R and M bits
 * Returns: 0, 1, 2, or 3
 */
static inline int get_page_class(frame_entry_t *frame) {
    uint64_t pte = *frame->pte_ptr;
    int r = (pte & ACCESSED_BIT) ? 1 : 0;
    int m = (pte & DIRTY_BIT) ? 1 : 0;
    
    // Class = 2*R + M
    // (0,0)->0, (0,1)->1, (1,0)->2, (1,1)->3
    return (r << 1) | m;
}
 
/*
 * Clear reference bit for a frame
 */
static void clear_reference_bit(frame_entry_t *frame) {
    uint64_t old_pte = *frame->pte_ptr;
    uint64_t new_pte = old_pte & ~ACCESSED_BIT;
    
    // Atomic update to handle concurrent access
    __atomic_compare_exchange_n(
        frame->pte_ptr, &old_pte, new_pte,
        false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST
    );
    
    // Invalidate TLB to ensure future accesses re-read PTE
    invalidate_tlb_entry(frame->process_id, frame->virtual_page);
}
 
/*
 * Write dirty page to backing store
 */
static void write_page_to_backing_store(frame_entry_t *frame) {
    void *page_data = frame_to_virtual_addr(frame);
    disk_write(
        frame->process_id,
        frame->virtual_page,
        page_data,
        PAGE_SIZE
    );
    
    // Clear dirty bit after successful write
    *frame->pte_ptr &= ~DIRTY_BIT;
}
 
/*
 * Enhanced Second-Chance: Find victim using 4-pass algorithm
 * Returns frame index of selected victim
 */
uint32_t enhanced_clock_find_victim(void) {
    uint32_t start = eclock.clock_hand;
    uint32_t i;
    
    // ============================================
    // PASS 1: Look for class (0,0) - clean, not referenced
    // ============================================
    for (i = 0; i < NUM_FRAMES; i++) {
        uint32_t idx = (start + i) % NUM_FRAMES;
        frame_entry_t *frame = &eclock.frames[idx];
        
        if (!frame->occupied) continue;
        
        int cls = get_page_class(frame);
        if (cls == 0) {  // (0,0) - Perfect victim!
            eclock.clock_hand = (idx + 1) % NUM_FRAMES;
            return idx;
        }
    }
    
    // ============================================
    // PASS 2: Look for class (0,1) - dirty, not referenced
    // ============================================
    for (i = 0; i < NUM_FRAMES; i++) {
        uint32_t idx = (start + i) % NUM_FRAMES;
        frame_entry_t *frame = &eclock.frames[idx];
        
        if (!frame->occupied) continue;
        
        int cls = get_page_class(frame);
        if (cls == 1) {  // (0,1) - Needs write, but cold
            eclock.clock_hand = (idx + 1) % NUM_FRAMES;
            return idx;
        }
    }
    
    // ============================================
    // PASS 3: Look for class (0,0) while clearing R bits
    // This converts class 2 -> class 0, class 3 -> class 1
    // ============================================
    for (i = 0; i < NUM_FRAMES; i++) {
        uint32_t idx = (start + i) % NUM_FRAMES;
        frame_entry_t *frame = &eclock.frames[idx];
        
        if (!frame->occupied) continue;
        
        // Clear reference bit FIRST
        clear_reference_bit(frame);
        
        // Re-check class (R now 0)
        int cls = get_page_class(frame);
        if (cls == 0) {  // Was (1,0), now (0,0)
            eclock.clock_hand = (idx + 1) % NUM_FRAMES;
            return idx;
        }
    }
    
    // ============================================
    // PASS 4: Look for class (0,1)
    // Must find one - all pages now have R=0
    // ============================================
    for (i = 0; i < NUM_FRAMES; i++) {
        uint32_t idx = (start + i) % NUM_FRAMES;
        frame_entry_t *frame = &eclock.frames[idx];
        
        if (!frame->occupied) continue;
        
        int cls = get_page_class(frame);
        if (cls == 1) {  // Was (1,1), now (0,1)
            eclock.clock_hand = (idx + 1) % NUM_FRAMES;
            return idx;
        }
    }
    
    // Should never reach here
    panic("Enhanced clock: no victim found after 4 passes");
    return 0;
}
 
/*
 * Handle page fault with enhanced second-chance
 */
void enhanced_clock_page_fault(uint32_t pid, uint32_t vpage) {
    // First check for free frames
    for (uint32_t i = 0; i < NUM_FRAMES; i++) {
        if (!eclock.frames[i].occupied) {
            load_page_into_frame(pid, vpage, i);
            return;
        }
    }
    
    // No free frames - find victim
    uint32_t victim = enhanced_clock_find_victim();
    frame_entry_t *frame = &eclock.frames[victim];
    
    // Check if victim is dirty - must write back
    if (*frame->pte_ptr & DIRTY_BIT) {
        write_page_to_backing_store(frame);
    }
    
    // Evict victim
    evict_page(frame);
    
    // Load new page
    load_page_into_frame(pid, vpage, victim);
}

Implementation details:

Class calculation: We compute class as 2*R + M, giving values 0-3 in the correct priority order
Atomic operations: Reference bit updates use atomic compare-exchange for thread safety on multi-core systems
TLB invalidation: After clearing reference bits, we invalidate TLB entries to ensure subsequent accesses reset the bit properly
Pass structure: Each pass is a complete sweep of the circular buffer; the clock hand only advances when we select a victim
Dirty page handling: Dirty pages are written to backing store before eviction; the write happens synchronously in this simple implementation (production systems often batch writes)

Worked Example: Enhanced Clock in Action

Let's trace through the Enhanced Second-Chance algorithm with a concrete scenario.

Setup:

4 physical frames (0-3)
Clock hand at position 0
Current state after some execution:

Initial State
Frame	Page	R	M	Class
0	A	1	1	3 (worst)
1	B	1	0	2
2	C	0	1	1
3	D	1	0	2

Scenario: Page E needs to be loaded. All frames are occupied.

Pass 1: Search for class (0,0)

Frame 0 (Page A): Class 3 ≠ 0, skip
Frame 1 (Page B): Class 2 ≠ 0, skip
Frame 2 (Page C): Class 1 ≠ 0, skip
Frame 3 (Page D): Class 2 ≠ 0, skip

Pass 1 complete: No class 0 found.

Pass 2: Search for class (0,1)

Frame 0 (Page A): Class 3 ≠ 1, skip
Frame 1 (Page B): Class 2 ≠ 1, skip
Frame 2 (Page C): Class 1 = 1, FOUND VICTIM!

Result: Frame 2 selected. Page C must be written back (M=1) before eviction.

Clock hand advances to Frame 3.

State After Eviction
Frame	Page	R	M	Class	Notes
0	A	1	1	3	Unchanged
1	B	1	0	2	Unchanged
2	E	0	0	0	Newly loaded
3	D	1	0	2	Unchanged

Now suppose page F needs to be loaded...

Current state: Clock hand at Frame 3

Pass 1: Search for class (0,0)

Frame 3 (Page D): Class 2 ≠ 0, skip
Frame 0 (Page A): Class 3 ≠ 0, skip
Frame 1 (Page B): Class 2 ≠ 0, skip
Frame 2 (Page E): Class 0 = 0, FOUND VICTIM!

Result: Frame 2 selected (Page E). No write-back needed (M=0)!

Observation: Page E was just loaded and immediately evicted. This can happen when the working set is larger than available memory—the algorithm is doing its job by selecting the cheapest victim, but performance will suffer. This is a symptom of thrashing, not a flaw in the algorithm.

Recently Loaded Pages

Newly loaded pages start with R=0 (the hardware will set it on first access after loading). If a page fault occurs before the new page is accessed, it becomes a class 0 victim. Some implementations protect newly loaded pages by setting R=1 initially or using additional "young" page tracking.

Complexity Analysis

Enhanced Second-Chance has different complexity characteristics than basic Clock due to its multi-pass nature.

Time Complexity:

Time Complexity Analysis
Case	Basic Clock	Enhanced Clock	Notes
Best case	O(1)	O(1)	First page checked is ideal victim
Worst case	O(2n)	O(4n)	Must complete all 4 passes
Average case	O(1) amortized	O(n/4) to O(n)	Depends on class distribution

Worst case breakdown:

Pass 1: Scan n pages looking for class 0 (none found)
Pass 2: Scan n pages looking for class 1 (none found)
Pass 3: Scan n pages, clearing R bits, looking for class 0 (none found)
Pass 4: Scan n pages looking for class 1 (must find one)

Total: 4n page inspections in worst case

When does worst case occur?

When all pages have (R=1, M=1)—all are referenced AND dirty. This is actually rare in practice because:

Not all pages are written to (code pages, read-only data)
Periodic reference bit clearing eventually creates class 2 pages
Background dirty page writeback creates clean pages

Amortization doesn't work as well:

Unlike basic Clock, Enhanced Clock's complexity doesn't amortize as cleanly. Each victim selection may require multiple passes regardless of previous selections. However, the benefit (fewer disk writes) typically outweighs the slightly higher scanning cost.

Space Complexity

•Same as basic Clock: O(n) for frame table, O(1) for clock hand
•No additional per-page storage: Uses existing R and M bits from PTE
•Potential in-memory dirty page tracking: Some implementations maintain lists of dirty pages for background writeback (additional O(n))

I/O vs CPU Tradeoff

Enhanced Second-Chance trades CPU time (more scanning) for I/O time (fewer disk writes). Since disk I/O is orders of magnitude slower than memory scanning, this is almost always a winning trade. Even 4x more scanning to avoid one disk write saves time.

Comparison with Basic Clock

Let's systematically compare Enhanced Second-Chance with the basic Clock algorithm:

Basic Clock vs Enhanced Clock
Aspect	Basic Clock	Enhanced Clock
Bits used	R only	R and M
Page classes	2 (R=0, R=1)	4 ((0,0), (0,1), (1,0), (1,1))
Victim preference	Any R=0 page	Clean pages preferred
CPU cost	Lower (1-2 passes)	Higher (1-4 passes)
I/O cost	Higher (more dirty evictions)	Lower (prefers clean pages)
Overall performance	Good	Better on most workloads
Implementation	Simpler	Slightly more complex

When to Use Enhanced Clock

•HDD-based systems (high write cost)
•Write-heavy workloads
•Mixed read/write workloads
•Virtual machines (dirty tracking matters)
•Database systems (dirty page management)

When Basic Clock May Suffice

•NVMe SSD (low write cost)
•Read-only or mostly-read workloads
•Systems with aggressive background writeback
•When simplicity is paramount
•Real-time systems (predictable scan time)

Performance impact example:

Consider evicting 1000 pages with 30% dirty rate:

Algorithm	Dirty Evictions	Clean Evictions	Est. I/O Time (HDD)
Basic Clock (random)	~300	~700	3000 ms
Enhanced Clock (optimized)	~50	~950	500 ms

By preferring clean pages, Enhanced Clock reduces disk I/O by 83% in this scenario. The extra CPU time for multi-pass scanning (perhaps 1-2 ms) is negligible compared to the 2,500 ms saved.

Production Optimizations

Real operating systems implement several optimizations on top of the basic Enhanced Second-Chance algorithm:

1. Background Dirty Page Writeback

Instead of writing dirty pages synchronously during eviction, modern systems proactively write dirty pages in the background:

Kernel thread (pdflush on Linux, similar on other OSes) periodically scans for dirty pages
Dirty pages older than a threshold (e.g., 30 seconds) are written back
After writeback, pages become class 0 or 2 (M cleared)
Eviction rarely needs to wait for writes

2. Free Page Reserve

Maintain a pool of free frames at all times:

When free count drops below low watermark, start evicting pages
Continue until free count reaches high watermark
Page faults then usually find free frames immediately
Eviction work is spread over time rather than spiking during allocation

background_writeback.pseudo

Pseudo

// Background dirty page writeback (simplified)
 
constants:
    DIRTY_THRESH_SECONDS = 30
    LOW_WATERMARK = 64        // Start reclaiming when free < 64
    HIGH_WATERMARK = 256      // Stop reclaiming when free >= 256
    BATCH_SIZE = 32           // Pages to write per batch
 
// Background writeback thread (runs periodically)
function background_writeback():
    dirty_list = collect_old_dirty_pages(DIRTY_THRESH_SECONDS)
    
    for batch in split_into_batches(dirty_list, BATCH_SIZE):
        // Sort by disk location for sequential writes
        sort_by_disk_location(batch)
        
        // Write batch (may be async to disk controller)
        for page in batch:
            write_page_to_disk(page)
            clear_dirty_bit(page)
        
        // Yield to other threads periodically
        yield()
 
// Free page reclaimer (triggered by low memory)
function reclaim_free_pages():
    while count_free_frames() < HIGH_WATERMARK:
        // Use enhanced clock to find victim
        victim = enhanced_clock_find_victim()
        
        if is_dirty(victim):
            queue_for_writeback(victim)  // Async
            continue  // Try next victim
        
        // Evict clean victim immediately
        evict_page(victim)
        add_to_free_list(victim.frame)

3. Separate Active/Inactive Lists

Linux uses a two-list variant:

Active list: Recently accessed pages (protected from eviction)
Inactive list: Candidates for eviction
Pages move between lists based on access patterns
Clock-like scanning occurs primarily on inactive list

4. Memory Pressure Levels

Adapt algorithm based on memory pressure:

Pressure Level	Behavior
Low	Standard 4-pass Enhanced Clock
Medium	Reduce to 2 passes (accept dirty evictions faster)
High	Immediate eviction (any class acceptable)
Critical	OOM killer activation

Real-World Complexity

Production memory managers are significantly more complex than textbook algorithms. They integrate with: NUMA awareness, memory cgroups, huge page management, swap systems, and file system caches. The Enhanced Second-Chance concept remains central, but it's one component in a larger system.

Summary: Enhanced Second-Chance Algorithm

The Enhanced Second-Chance algorithm represents a thoughtful refinement that significantly improves I/O efficiency with minimal additional complexity.

Key Takeaways

•Dirty page eviction is expensive — orders of magnitude slower than clean page eviction due to required disk writes
•Four-class categorization — pages are ranked by (R,M) from best victim (0,0) to worst (1,1)
•Multi-pass algorithm — up to 4 sweeps through the circular buffer, searching for progressively worse victim classes
•I/O optimization priority — clean pages are preferred even if they were more recently used, because avoiding disk writes saves more time
•Trade CPU for I/O — additional scanning cost is negligible compared to disk I/O savings
•Production enhancements — background writeback, free page reserves, and active/inactive lists further optimize real implementations

What's next:

Enhanced Second-Chance uses the (R,M) bit combination to prioritize victims. The Not Recently Used (NRU) algorithm takes a similar approach but with a different implementation strategy—selecting victims randomly from the lowest non-empty class rather than using circular scanning. The next page explores NRU in detail.

Page Complete

You now understand the Enhanced Second-Chance algorithm—how it extends basic Clock by considering the dirty bit, why this reduces I/O costs, and how production systems build upon this foundation.

Enhanced Second-Chance Algorithm

Not All Pages Are Created Equal

The basic Clock algorithm treats all pages with R=0 as equally suitable victims. But there's a critical distinction the basic algorithm ignores: has the page been modified since it was loaded?

What You Will Learn

The Cost of Dirty Page Eviction

Before diving into the algorithm, let's quantify exactly why dirty page eviction is so much more expensive than clean page eviction.

Clean page eviction:

Mark page table entry as not present
Invalidate TLB entry
Mark frame as available
Total time: ~1-10 microseconds (memory operations only)

Dirty page eviction:

Mark page table entry as not present
Invalidate TLB entry
Write 4KB (or larger) page contents to disk
Wait for disk acknowledgment
Mark frame as available
Total time: ~5-15 milliseconds (disk I/O dominated)

The ratio: Dirty page eviction is approximately 1,000 to 10,000 times slower than clean page eviction!

Eviction Costs by Storage Type
Storage Type	Write Time (4KB)	Clean Eviction	Dirty Eviction	Ratio
HDD (7200 RPM)	5-10 ms	~10 µs	5-10 ms	500-1000x
SATA SSD	50-100 µs	~10 µs	50-100 µs	5-10x
NVMe SSD	10-20 µs	~5 µs	10-20 µs	2-4x
Intel Optane	5-10 µs	~5 µs	5-10 µs	~2x

The implication:

Example impact:

Consider a system under memory pressure that must evict 1,000 pages:

Scenario	Clean Pages	Dirty Pages	Total Time (HDD)
All clean	1,000	0	10 ms
50% dirty	500	500	5,000 ms (5 sec!)
All dirty	0	1,000	10,000 ms (10 sec!)

By preferring clean pages as victims, we can reduce eviction time by orders of magnitude.

Disk I/O Blocking

The Four-Class Page Categorization

The Enhanced Second-Chance algorithm categorizes pages into four classes based on the combination of two bits:

R (Reference bit): Has the page been accessed recently? (Set by hardware, cleared by OS)
M (Modify/Dirty bit): Has the page been written to since loading? (Set by hardware, never cleared until page is written back)

The four classes (in order of eviction preference):

Page Classes in Enhanced Second-Chance
Class	(R, M)	Interpretation	Eviction Cost	Priority
0	(0, 0)	Not referenced, not modified	Lowest (free)	Best victim
1	(0, 1)	Not referenced, modified	Medium (write needed)	Second choice
2	(1, 0)	Referenced, not modified	Low (free, but recent)	Third choice
3	(1, 1)	Referenced, modified	Highest (recent + write)	Last resort

Understanding the ordering:

Class 0 (0,0): The ideal victim. The page hasn't been used recently (R=0) and is clean (M=0). We can simply discard it—no disk I/O required. If needed later, we reload from the original source.

Class 1 (0,1): Not recently used, but dirty. We'll need to write it back before eviction. However, since it's not being actively used, evicting it probably won't cause an immediate re-fault.

Class 2 (1,0): Recently used but clean. The page is "hot" (recently accessed), so evicting it may cause a fault soon. However, if we must evict it, at least no write is needed.

Class 3 (1,1): The worst victim. Recently used (likely to be needed again soon) AND dirty (requires expensive write-back). Evicting this page incurs maximum cost.

Converting Mermaid diagram...

NRU Connection

The Enhanced Second-Chance Algorithm

The Enhanced Second-Chance algorithm modifies the basic Clock algorithm to prefer lower-class victims. There are two main implementation approaches:

Approach 1: Multiple Pass Sweeps

Make up to four passes through the circular buffer, with each pass looking for a specific class:

Pass 1: Scan for (0,0) pages without changing any bits
Pass 2: Scan for (0,1) pages without changing any bits
Pass 3: Scan for (0,0) pages, clearing R bits as we go (gives referenced pages a chance)
Pass 4: Scan for (0,1) pages (must find one—all R bits now clear)

Algorithm pseudocode:

enhanced_second_chance.pseudo

Pseudo

function enhanced_second_chance_find_victim():
    // Pass 1: Look for (0,0) - not referenced, clean
    // Best possible victim - no disk I/O needed
    for i = 0 to NUM_FRAMES-1:
        frame_index = (clock_hand + i) % NUM_FRAMES
        page = frames[frame_index]
        
        if page.R == 0 and page.M == 0:
            clock_hand = (frame_index + 1) % NUM_FRAMES
            return frame_index  // Perfect victim found!
    
    // Pass 2: Look for (0,1) - not referenced, dirty
    // Need to write back, but page is cold
    for i = 0 to NUM_FRAMES-1:
        frame_index = (clock_hand + i) % NUM_FRAMES
        page = frames[frame_index]
        
        if page.R == 0 and page.M == 1:
            clock_hand = (frame_index + 1) % NUM_FRAMES
            return frame_index  // Acceptable victim
    
    // Pass 3: Look for (0,0) while CLEARING R bits
    // This pass gives referenced pages a "second chance"
    for i = 0 to NUM_FRAMES-1:
        frame_index = (clock_hand + i) % NUM_FRAMES
        page = frames[frame_index]
        
        // Clear R bit for next pass
        clear_reference_bit(page)
        
        if page.R == 0 and page.M == 0:  // Check AFTER clearing
            clock_hand = (frame_index + 1) % NUM_FRAMES
            return frame_index
    
    // Pass 4: Look for (0,1) - must find one now
    // All R bits have been cleared in pass 3
    for i = 0 to NUM_FRAMES-1:
        frame_index = (clock_hand + i) % NUM_FRAMES
        page = frames[frame_index]
        
        if page.R == 0 and page.M == 1:
            clock_hand = (frame_index + 1) % NUM_FRAMES
            return frame_index
    
    // Should never reach here - pass 4 guarantees finding victim
    panic("Enhanced second-chance failed to find victim")

Approach 2: Single Pass with Class Tracking

An alternative approach makes a single pass, tracking the best victim seen so far and updating if we find a better class:

Start at clock hand position
For each page, compute its class (0-3)
If class is better than best seen, update the best candidate
If we find class 0, evict immediately (can't do better)
If we complete a full sweep without class 0, evict the best found
Clear R bits during the pass to prepare for next eviction

This approach has the same worst-case complexity but potentially finds victims faster by stopping early on class 0 finds.

Implementation Choice

Detailed Implementation

Here's a complete C implementation of the Enhanced Second-Chance algorithm with full commentary:

enhanced_clock.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
/*
 * Enhanced Second-Chance (Enhanced Clock) Algorithm
 * Considers both R (reference) and M (modify/dirty) bits
 */
 
#include <stdint.h>
#include <stdbool.h>
 
#define NUM_FRAMES 256
#define PAGE_SIZE 4096
 
// PTE bit masks (x86-64)
#define PRESENT_BIT     0x001
#define WRITABLE_BIT    0x002
#define ACCESSED_BIT    0x020  // R - Reference bit
#define DIRTY_BIT       0x040  // M - Modify bit
 
typedef struct {
    uint32_t process_id;
    uint32_t virtual_page;
    uint64_t *pte_ptr;
    bool occupied;
} frame_entry_t;
 
typedef struct {
    frame_entry_t frames[NUM_FRAMES];
    uint32_t clock_hand;
    uint32_t occupied_count;
} enhanced_clock_t;
 
enhanced_clock_t eclock;
 
/*
 * Get page class based on R and M bits
 * Returns: 0, 1, 2, or 3
 */
static inline int get_page_class(frame_entry_t *frame) {
    uint64_t pte = *frame->pte_ptr;
    int r = (pte & ACCESSED_BIT) ? 1 : 0;
    int m = (pte & DIRTY_BIT) ? 1 : 0;
    
    // Class = 2*R + M
    // (0,0)->0, (0,1)->1, (1,0)->2, (1,1)->3
    return (r << 1) | m;
}
 
/*
 * Clear reference bit for a frame
 */
static void clear_reference_bit(frame_entry_t *frame) {
    uint64_t old_pte = *frame->pte_ptr;
    uint64_t new_pte = old_pte & ~ACCESSED_BIT;
    
    // Atomic update to handle concurrent access
    __atomic_compare_exchange_n(
        frame->pte_ptr, &old_pte, new_pte,
        false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST
    );
    
    // Invalidate TLB to ensure future accesses re-read PTE
    invalidate_tlb_entry(frame->process_id, frame->virtual_page);
}
 
/*
 * Write dirty page to backing store
 */
static void write_page_to_backing_store(frame_entry_t *frame) {
    void *page_data = frame_to_virtual_addr(frame);
    disk_write(
        frame->process_id,
        frame->virtual_page,
        page_data,
        PAGE_SIZE
    );
    
    // Clear dirty bit after successful write
    *frame->pte_ptr &= ~DIRTY_BIT;
}
 
/*
 * Enhanced Second-Chance: Find victim using 4-pass algorithm
 * Returns frame index of selected victim
 */
uint32_t enhanced_clock_find_victim(void) {
    uint32_t start = eclock.clock_hand;
    uint32_t i;
    
    // ============================================
    // PASS 1: Look for class (0,0) - clean, not referenced
    // ============================================
    for (i = 0; i < NUM_FRAMES; i++) {
        uint32_t idx = (start + i) % NUM_FRAMES;
        frame_entry_t *frame = &eclock.frames[idx];
        
        if (!frame->occupied) continue;
        
        int cls = get_page_class(frame);
        if (cls == 0) {  // (0,0) - Perfect victim!
            eclock.clock_hand = (idx + 1) % NUM_FRAMES;
            return idx;
        }
    }
    
    // ============================================
    // PASS 2: Look for class (0,1) - dirty, not referenced
    // ============================================
    for (i = 0; i < NUM_FRAMES; i++) {
        uint32_t idx = (start + i) % NUM_FRAMES;
        frame_entry_t *frame = &eclock.frames[idx];
        
        if (!frame->occupied) continue;
        
        int cls = get_page_class(frame);
        if (cls == 1) {  // (0,1) - Needs write, but cold
            eclock.clock_hand = (idx + 1) % NUM_FRAMES;
            return idx;
        }
    }
    
    // ============================================
    // PASS 3: Look for class (0,0) while clearing R bits
    // This converts class 2 -> class 0, class 3 -> class 1
    // ============================================
    for (i = 0; i < NUM_FRAMES; i++) {
        uint32_t idx = (start + i) % NUM_FRAMES;
        frame_entry_t *frame = &eclock.frames[idx];
        
        if (!frame->occupied) continue;
        
        // Clear reference bit FIRST
        clear_reference_bit(frame);
        
        // Re-check class (R now 0)
        int cls = get_page_class(frame);
        if (cls == 0) {  // Was (1,0), now (0,0)
            eclock.clock_hand = (idx + 1) % NUM_FRAMES;
            return idx;
        }
    }
    
    // ============================================
    // PASS 4: Look for class (0,1)
    // Must find one - all pages now have R=0
    // ============================================
    for (i = 0; i < NUM_FRAMES; i++) {
        uint32_t idx = (start + i) % NUM_FRAMES;
        frame_entry_t *frame = &eclock.frames[idx];
        
        if (!frame->occupied) continue;
        
        int cls = get_page_class(frame);
        if (cls == 1) {  // Was (1,1), now (0,1)
            eclock.clock_hand = (idx + 1) % NUM_FRAMES;
            return idx;
        }
    }
    
    // Should never reach here
    panic("Enhanced clock: no victim found after 4 passes");
    return 0;
}
 
/*
 * Handle page fault with enhanced second-chance
 */
void enhanced_clock_page_fault(uint32_t pid, uint32_t vpage) {
    // First check for free frames
    for (uint32_t i = 0; i < NUM_FRAMES; i++) {
        if (!eclock.frames[i].occupied) {
            load_page_into_frame(pid, vpage, i);
            return;
        }
    }
    
    // No free frames - find victim
    uint32_t victim = enhanced_clock_find_victim();
    frame_entry_t *frame = &eclock.frames[victim];
    
    // Check if victim is dirty - must write back
    if (*frame->pte_ptr & DIRTY_BIT) {
        write_page_to_backing_store(frame);
    }
    
    // Evict victim
    evict_page(frame);
    
    // Load new page
    load_page_into_frame(pid, vpage, victim);
}

Implementation details:

Class calculation: We compute class as 2*R + M, giving values 0-3 in the correct priority order
Atomic operations: Reference bit updates use atomic compare-exchange for thread safety on multi-core systems
TLB invalidation: After clearing reference bits, we invalidate TLB entries to ensure subsequent accesses reset the bit properly
Pass structure: Each pass is a complete sweep of the circular buffer; the clock hand only advances when we select a victim
Dirty page handling: Dirty pages are written to backing store before eviction; the write happens synchronously in this simple implementation (production systems often batch writes)

Worked Example: Enhanced Clock in Action

Let's trace through the Enhanced Second-Chance algorithm with a concrete scenario.

Setup:

4 physical frames (0-3)
Clock hand at position 0
Current state after some execution:

Initial State
Frame	Page	R	M	Class
0	A	1	1	3 (worst)
1	B	1	0	2
2	C	0	1	1
3	D	1	0	2

Scenario: Page E needs to be loaded. All frames are occupied.

Pass 1: Search for class (0,0)

Frame 0 (Page A): Class 3 ≠ 0, skip
Frame 1 (Page B): Class 2 ≠ 0, skip
Frame 2 (Page C): Class 1 ≠ 0, skip
Frame 3 (Page D): Class 2 ≠ 0, skip

Pass 1 complete: No class 0 found.

Pass 2: Search for class (0,1)

Frame 0 (Page A): Class 3 ≠ 1, skip
Frame 1 (Page B): Class 2 ≠ 1, skip
Frame 2 (Page C): Class 1 = 1, FOUND VICTIM!

Result: Frame 2 selected. Page C must be written back (M=1) before eviction.

Clock hand advances to Frame 3.

State After Eviction
Frame	Page	R	M	Class	Notes
0	A	1	1	3	Unchanged
1	B	1	0	2	Unchanged
2	E	0	0	0	Newly loaded
3	D	1	0	2	Unchanged

Now suppose page F needs to be loaded...

Current state: Clock hand at Frame 3

Pass 1: Search for class (0,0)

Frame 3 (Page D): Class 2 ≠ 0, skip
Frame 0 (Page A): Class 3 ≠ 0, skip
Frame 1 (Page B): Class 2 ≠ 0, skip
Frame 2 (Page E): Class 0 = 0, FOUND VICTIM!

Result: Frame 2 selected (Page E). No write-back needed (M=0)!

Recently Loaded Pages

Complexity Analysis

Enhanced Second-Chance has different complexity characteristics than basic Clock due to its multi-pass nature.

Time Complexity:

Time Complexity Analysis
Case	Basic Clock	Enhanced Clock	Notes
Best case	O(1)	O(1)	First page checked is ideal victim
Worst case	O(2n)	O(4n)	Must complete all 4 passes
Average case	O(1) amortized	O(n/4) to O(n)	Depends on class distribution

Worst case breakdown:

Pass 1: Scan n pages looking for class 0 (none found)
Pass 2: Scan n pages looking for class 1 (none found)
Pass 3: Scan n pages, clearing R bits, looking for class 0 (none found)
Pass 4: Scan n pages looking for class 1 (must find one)

Total: 4n page inspections in worst case

When does worst case occur?

When all pages have (R=1, M=1)—all are referenced AND dirty. This is actually rare in practice because:

Not all pages are written to (code pages, read-only data)
Periodic reference bit clearing eventually creates class 2 pages
Background dirty page writeback creates clean pages

Amortization doesn't work as well:

Space Complexity

•Same as basic Clock: O(n) for frame table, O(1) for clock hand
•No additional per-page storage: Uses existing R and M bits from PTE
•Potential in-memory dirty page tracking: Some implementations maintain lists of dirty pages for background writeback (additional O(n))

I/O vs CPU Tradeoff

Comparison with Basic Clock

Let's systematically compare Enhanced Second-Chance with the basic Clock algorithm:

Basic Clock vs Enhanced Clock
Aspect	Basic Clock	Enhanced Clock
Bits used	R only	R and M
Page classes	2 (R=0, R=1)	4 ((0,0), (0,1), (1,0), (1,1))
Victim preference	Any R=0 page	Clean pages preferred
CPU cost	Lower (1-2 passes)	Higher (1-4 passes)
I/O cost	Higher (more dirty evictions)	Lower (prefers clean pages)
Overall performance	Good	Better on most workloads
Implementation	Simpler	Slightly more complex

When to Use Enhanced Clock

•HDD-based systems (high write cost)
•Write-heavy workloads
•Mixed read/write workloads
•Virtual machines (dirty tracking matters)
•Database systems (dirty page management)

When Basic Clock May Suffice

•NVMe SSD (low write cost)
•Read-only or mostly-read workloads
•Systems with aggressive background writeback
•When simplicity is paramount
•Real-time systems (predictable scan time)

Performance impact example:

Consider evicting 1000 pages with 30% dirty rate:

Algorithm	Dirty Evictions	Clean Evictions	Est. I/O Time (HDD)
Basic Clock (random)	~300	~700	3000 ms
Enhanced Clock (optimized)	~50	~950	500 ms

By preferring clean pages, Enhanced Clock reduces disk I/O by 83% in this scenario. The extra CPU time for multi-pass scanning (perhaps 1-2 ms) is negligible compared to the 2,500 ms saved.

Production Optimizations

Real operating systems implement several optimizations on top of the basic Enhanced Second-Chance algorithm:

1. Background Dirty Page Writeback

Instead of writing dirty pages synchronously during eviction, modern systems proactively write dirty pages in the background:

Kernel thread (pdflush on Linux, similar on other OSes) periodically scans for dirty pages
Dirty pages older than a threshold (e.g., 30 seconds) are written back
After writeback, pages become class 0 or 2 (M cleared)
Eviction rarely needs to wait for writes

2. Free Page Reserve

Maintain a pool of free frames at all times:

When free count drops below low watermark, start evicting pages
Continue until free count reaches high watermark
Page faults then usually find free frames immediately
Eviction work is spread over time rather than spiking during allocation

background_writeback.pseudo

Pseudo

// Background dirty page writeback (simplified)
 
constants:
    DIRTY_THRESH_SECONDS = 30
    LOW_WATERMARK = 64        // Start reclaiming when free < 64
    HIGH_WATERMARK = 256      // Stop reclaiming when free >= 256
    BATCH_SIZE = 32           // Pages to write per batch
 
// Background writeback thread (runs periodically)
function background_writeback():
    dirty_list = collect_old_dirty_pages(DIRTY_THRESH_SECONDS)
    
    for batch in split_into_batches(dirty_list, BATCH_SIZE):
        // Sort by disk location for sequential writes
        sort_by_disk_location(batch)
        
        // Write batch (may be async to disk controller)
        for page in batch:
            write_page_to_disk(page)
            clear_dirty_bit(page)
        
        // Yield to other threads periodically
        yield()
 
// Free page reclaimer (triggered by low memory)
function reclaim_free_pages():
    while count_free_frames() < HIGH_WATERMARK:
        // Use enhanced clock to find victim
        victim = enhanced_clock_find_victim()
        
        if is_dirty(victim):
            queue_for_writeback(victim)  // Async
            continue  // Try next victim
        
        // Evict clean victim immediately
        evict_page(victim)
        add_to_free_list(victim.frame)

3. Separate Active/Inactive Lists

Linux uses a two-list variant:

Active list: Recently accessed pages (protected from eviction)
Inactive list: Candidates for eviction
Pages move between lists based on access patterns
Clock-like scanning occurs primarily on inactive list

4. Memory Pressure Levels

Adapt algorithm based on memory pressure:

Pressure Level	Behavior
Low	Standard 4-pass Enhanced Clock
Medium	Reduce to 2 passes (accept dirty evictions faster)
High	Immediate eviction (any class acceptable)
Critical	OOM killer activation

Real-World Complexity

Summary: Enhanced Second-Chance Algorithm

The Enhanced Second-Chance algorithm represents a thoughtful refinement that significantly improves I/O efficiency with minimal additional complexity.

Key Takeaways

•Dirty page eviction is expensive — orders of magnitude slower than clean page eviction due to required disk writes
•Four-class categorization — pages are ranked by (R,M) from best victim (0,0) to worst (1,1)
•Multi-pass algorithm — up to 4 sweeps through the circular buffer, searching for progressively worse victim classes
•I/O optimization priority — clean pages are preferred even if they were more recently used, because avoiding disk writes saves more time
•Trade CPU for I/O — additional scanning cost is negligible compared to disk I/O savings
•Production enhancements — background writeback, free page reserves, and active/inactive lists further optimize real implementations

What's next:

Page Complete

You now understand the Enhanced Second-Chance algorithm—how it extends basic Clock by considering the dirty bit, why this reduces I/O costs, and how production systems build upon this foundation.