Operating SystemsI/O Software

Caching

LevelAdvanced

Duration90 mins

TopicI/O Software

3 / 5

Cache Policies

The Art of Deciding What to Forget

A cache's effectiveness hinges on one critical decision: when space runs out, what should be evicted? The wrong choice means evicting data that will be needed again soon, causing an expensive cache miss. The right choice means evicting data unlikely to be accessed, maximizing the cache's benefit.

This decision is made by the cache replacement policy—an algorithm that uses available information (access history, frequency, recency) to predict which cached data is least likely to be useful in the future. The quality of this prediction directly determines cache hit rate, which in turn determines system performance.

What You Will Learn

By the end of this page, you will understand the major cache replacement policies (LRU, LFU, ARC, and variants), their theoretical foundations, practical trade-offs, and how modern operating systems combine multiple strategies to achieve excellent performance across diverse workloads.

Replacement Policy Fundamentals

The Optimal Policy (Bélády's Algorithm)

The theoretically optimal policy is simple: evict the page that will be accessed furthest in the future. This minimizes misses by keeping data that will be needed soonest.

Unfortunately, this requires knowledge of future accesses—impossible in practice. But it provides an upper bound for comparison: no realizable policy can do better.

Realizable Policies

Practical policies must predict future access using only past behavior. They rely on locality:

Temporal locality: Recently accessed data is likely to be accessed again soon
Frequency locality: Frequently accessed data is likely to be accessed again

Different policies weight these factors differently, making each better suited to certain workload patterns.

Cache Policy Characteristics
Policy	Principle	Tracks	Weakness
FIFO	First In, First Out	Insertion order	Ignores access patterns entirely
LRU	Least Recently Used	Recency	Scan-resistant workloads defeat it
LFU	Least Frequently Used	Frequency	Cannot adapt to changing patterns
ARC	Adaptive Replacement	Both + history	More complex implementation
CLOCK	LRU approximation	Reference bit	Less accurate than true LRU

Least Recently Used (LRU)

LRU is the most widely used cache replacement policy. It evicts the page that hasn't been accessed for the longest time, based on the assumption that recent access predicts future access.

LRU Implementation

True LRU requires tracking access order precisely. The classic implementation uses a doubly-linked list:

lru_implementation.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
/*
 * LRU Cache Implementation
 * Uses doubly-linked list for O(1) operations
 */
struct lru_node {
    void *key;
    void *value;
    struct lru_node *prev;
    struct lru_node *next;
};
 
struct lru_cache {
    struct lru_node *head;      /* Most recently used */
    struct lru_node *tail;      /* Least recently used (evict) */
    struct hash_table *lookup;  /* O(1) key lookup */
    size_t capacity;
    size_t size;
};
 
/* Move node to head (most recently used) */
void lru_touch(struct lru_cache *cache, struct lru_node *node) {
    if (node == cache->head)
        return;  /* Already MRU */
    
    /* Remove from current position */
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    if (node == cache->tail) cache->tail = node->prev;
    
    /* Insert at head */
    node->next = cache->head;
    node->prev = NULL;
    if (cache->head) cache->head->prev = node;
    cache->head = node;
}
 
/* Evict least recently used (tail) */
void *lru_evict(struct lru_cache *cache) {
    struct lru_node *victim = cache->tail;
    if (!victim) return NULL;
    
    cache->tail = victim->prev;
    if (cache->tail) cache->tail->next = NULL;
    else cache->head = NULL;
    
    hash_remove(cache->lookup, victim->key);
    cache->size--;
    
    void *evicted = victim->value;
    free(victim);
    return evicted;
}

LRU Strengths and Weaknesses

Strengths:

Excellent for workloads with strong temporal locality
Simple conceptual model
Naturally adapts to working set changes

Weaknesses:

Scan vulnerability: A single sequential scan through data larger than the cache evicts everything useful, leaving the cache filled with scan data that won't be accessed again
No frequency awareness: A page accessed once recently beats a page accessed 1000 times slightly less recently
Implementation overhead: True LRU requires updating data structures on every access

The Scan Problem

Consider a database backup scanning all tables while the database handles normal queries. The backup's sequential access pattern could evict frequently-used indexes and hot rows, devastating performance for normal operations. This real-world scenario motivates more sophisticated policies.

Least Frequently Used (LFU)

LFU evicts the page with the lowest access count, keeping frequently-accessed (popular) data cached regardless of recency.

LFU Implementation

lfu_implementation.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
/*
 * LFU Cache with O(1) operations
 * Uses frequency buckets linked together
 */
struct lfu_node {
    void *key;
    void *value;
    size_t frequency;
    struct list_head freq_list;  /* Position in frequency bucket */
};
 
struct freq_bucket {
    size_t freq;
    struct list_head nodes;      /* Nodes with this frequency */
    struct list_head bucket_list; /* All buckets, ordered by freq */
};
 
struct lfu_cache {
    struct hash_table *lookup;
    struct list_head freq_buckets; /* Ascending frequency order */
    size_t min_freq;
    size_t capacity, size;
};
 
void lfu_access(struct lfu_cache *cache, struct lfu_node *node) {
    /* Remove from current frequency bucket */
    struct freq_bucket *old_bucket = get_bucket(cache, node->frequency);
    list_del(&node->freq_list);
    
    /* If bucket empty and was minimum, update min_freq */
    if (list_empty(&old_bucket->nodes) && 
        node->frequency == cache->min_freq)
        cache->min_freq++;
    
    /* Increment frequency and add to new bucket */
    node->frequency++;
    struct freq_bucket *new_bucket = get_or_create_bucket(
        cache, node->frequency);
    list_add_tail(&node->freq_list, &new_bucket->nodes);
}
 
struct lfu_node *lfu_evict(struct lfu_cache *cache) {
    /* Get minimum frequency bucket */
    struct freq_bucket *min_bucket = get_bucket(cache, cache->min_freq);
    
    /* Evict least recently used within that frequency (LRU tiebreaker) */
    struct lfu_node *victim = list_first_entry(
        &min_bucket->nodes, struct lfu_node, freq_list);
    
    list_del(&victim->freq_list);
    hash_remove(cache->lookup, victim->key);
    cache->size--;
    
    return victim;
}

LFU Strengths and Weaknesses

Strengths:

Resists scan pollution—sequential scans accumulate low frequency
Keeps genuinely hot data in cache
Excellent for stable, skewed access distributions

Weaknesses:

Cache pollution: Once-hot data that's no longer accessed fills the cache with high-frequency zombies
Slow warmup: New data starts with frequency 1, vulnerable to eviction before it can prove its value
No recency: Can't distinguish between 1000 accesses yesterday vs. 1000 accesses last month

The CLOCK Algorithm

CLOCK (also called Second-Chance) is a practical approximation of LRU that dramatically reduces overhead. Instead of maintaining a fully-ordered list, it uses a single reference bit per page.

CLOCK Operation

Pages are arranged in a circular buffer with a 'clock hand' pointer. Each page has a reference bit set to 1 when accessed. When eviction is needed:

clock_algorithm.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
/*
 * CLOCK page replacement algorithm
 * Used by Linux for page cache management
 */
struct page {
    unsigned int referenced : 1;  /* Set on access */
    unsigned int dirty : 1;
    void *data;
};
 
struct clock_cache {
    struct page *pages;
    size_t capacity;
    size_t hand;  /* Current position */
};
 
struct page *clock_evict(struct clock_cache *cache) {
    while (1) {
        struct page *p = &cache->pages[cache->hand];
        
        if (p->referenced) {
            /* Give second chance - clear and move on */
            p->referenced = 0;
            cache->hand = (cache->hand + 1) % cache->capacity;
        } else {
            /* Found victim - not recently referenced */
            cache->hand = (cache->hand + 1) % cache->capacity;
            return p;
        }
    }
}
 
/* Hardware/kernel sets this on access */
void clock_access(struct page *p) {
    p->referenced = 1;
}

Why CLOCK Works

CLOCK approximates LRU behavior:

Recently-accessed pages have reference bit set, get second chances
Long-untouched pages have reference bit clear (cleared by previous passes), get evicted
The clock hand's sweep period determines 'recency' granularity

Advantages over LRU:

O(1) access without data structure updates
Reference bit can be set by hardware (page table accessed bit)
Scales to millions of pages efficiently

Enhanced CLOCK Variants

CLOCK-Pro: Tracks both recent and frequent access patterns CAR: Combines CLOCK with adaptive behavior like ARC 2Q: Uses two queues to distinguish one-time from repeated access

Adaptive Replacement Cache (ARC)

ARC represents a breakthrough in cache replacement by adaptively balancing between recency (LRU) and frequency (LFU) based on observed workload behavior. It dynamically learns whether the current access pattern benefits more from recency or frequency information.

ARC Structure

ARC maintains four lists:

T1: Recent pages accessed only once (recency-focused) T2: Pages accessed at least twice (frequency-focused) B1: Ghost entries for recently evicted T1 pages B2: Ghost entries for recently evicted T2 pages

The cache holds pages in T1 ∪ T2, limited to cache size. B1 and B2 are metadata-only (no data cached), tracking what was recently evicted.

arc_algorithm.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
/*
 * Simplified ARC implementation
 * Demonstrates the adaptive balancing mechanism
 */
struct arc_cache {
    struct list_head T1, T2;    /* Cached pages */
    struct list_head B1, B2;    /* Ghost lists */
    size_t c;                   /* Cache capacity */
    size_t p;                   /* Target size for T1 (adaptive) */
    
    size_t t1_size, t2_size;
    size_t b1_size, b2_size;
};
 
void arc_request(struct arc_cache *arc, void *page) {
    /* Case 1: Hit in T1 - move to T2 (now frequent) */
    if (in_list(page, &arc->T1)) {
        move_to_mru(&arc->T2, page);
        arc->t1_size--; arc->t2_size++;
        return;
    }
    
    /* Case 2: Hit in T2 - move to MRU of T2 */
    if (in_list(page, &arc->T2)) {
        move_to_mru(&arc->T2, page);
        return;
    }
    
    /* Case 3: Hit in B1 ghost - recency was useful */
    if (in_list(page, &arc->B1)) {
        /* Adapt: increase target size for T1 */
        arc->p = min(arc->c, arc->p + max(1, arc->b2_size/arc->b1_size));
        
        replace(arc, 0);  /* Make room */
        remove_from(&arc->B1, page); arc->b1_size--;
        add_to_mru(&arc->T2, page); arc->t2_size++;  /* Now in cache */
        return;
    }
    
    /* Case 4: Hit in B2 ghost - frequency was useful */
    if (in_list(page, &arc->B2)) {
        /* Adapt: decrease target size for T1 */
        arc->p = max(0, arc->p - max(1, arc->b1_size/arc->b2_size));
        
        replace(arc, 1);  /* Make room */
        remove_from(&arc->B2, page); arc->b2_size--;
        add_to_mru(&arc->T2, page); arc->t2_size++;
        return;
    }
    
    /* Case 5: Complete miss - not in cache or ghosts */
    /* Manage ghost list sizes */
    if (arc->t1_size + arc->b1_size == arc->c) {
        if (arc->t1_size < arc->c) {
            evict_lru(&arc->B1); arc->b1_size--;
            replace(arc, 0);
        } else {
            evict_lru(&arc->T1); arc->t1_size--;
        }
    }
    add_to_mru(&arc->T1, page); arc->t1_size++;
}
 
/* Replace a page - favor T1 or T2 based on p */
void replace(struct arc_cache *arc, int in_b2) {
    if (arc->t1_size > 0 && 
        (arc->t1_size > arc->p || (in_b2 && arc->t1_size == arc->p))) {
        /* Evict from T1, add ghost to B1 */
        void *victim = evict_lru(&arc->T1); arc->t1_size--;
        add_to_mru(&arc->B1, victim); arc->b1_size++;
    } else {
        /* Evict from T2, add ghost to B2 */
        void *victim = evict_lru(&arc->T2); arc->t2_size--;
        add_to_mru(&arc->B2, victim); arc->b2_size++;
    }
}

ARC's Adaptive Mechanism

The key insight is the ghost lists (B1, B2). When a request hits in B1 (we previously evicted it from T1-recency), it means LRU would have kept it—recency was valuable. So we increase p, growing T1's share. Conversely, B2 hits indicate frequency was valuable, so we decrease p.

This self-tuning means ARC automatically adapts to:

Recency-dominated workloads (more T1)
Frequency-dominated workloads (more T2)
Mixed workloads (balanced T1/T2)
Changing workload patterns (adapts continuously)

ARC in Practice

ZFS uses ARC as its primary caching algorithm, achieving excellent performance across diverse workloads. IBM holds patents on ARC, which limited its adoption in some open-source projects, though patent-safe variants like CAR exist.

Linux Page Cache Policies

Linux uses a sophisticated multi-generation LRU (MGLRU) system that addresses classical LRU weaknesses while maintaining practical efficiency for millions of pages.

Two-List Approach (Traditional)

Traditionally, Linux maintained two lists:

Active List: Pages accessed recently (likely to be accessed again) Inactive List: Pages not accessed recently (candidates for eviction)

Pages start on the inactive list. If accessed while inactive, they're promoted to the active list. Active pages gradually demote to inactive if not re-accessed.

linux_page_reclaim.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
/*
 * Simplified Linux page aging and reclaim
 */
 
/* Page flags for reclaim decisions */
#define PG_referenced   1    /* Recently accessed */
#define PG_active       2    /* On active list */
 
/*
 * Determine if page should be promoted
 * Called when page is accessed
 */
void mark_page_accessed(struct page *page) {
    if (!PageReferenced(page)) {
        SetPageReferenced(page);
    } else if (!PageActive(page)) {
        /* Second access while inactive - promote */
        activate_page(page);
        ClearPageReferenced(page);
    }
}
 
/*
 * Page reclaim: scan inactive list
 */
unsigned shrink_inactive_list(struct lruvec *lruvec,
                               unsigned nr_to_scan) {
    LIST_HEAD(pages_to_free);
    unsigned nr_reclaimed = 0;
    
    while (nr_to_scan-- && !list_empty(&lruvec->inactive)) {
        struct page *page = lru_to_page(&lruvec->inactive);
        
        if (PageReferenced(page)) {
            /* Referenced - give another chance */
            ClearPageReferenced(page);
            list_move(&page->lru, &lruvec->inactive);
            continue;
        }
        
        if (PageDirty(page)) {
            /* Must write back first */
            pageout(page);
            continue;
        }
        
        /* Unreferenced, clean - can reclaim */
        list_move(&page->lru, &pages_to_free);
        nr_reclaimed++;
    }
    
    free_pages_list(&pages_to_free);
    return nr_reclaimed;
}

Multi-Gen LRU (MGLRU)

Modern Linux (5.18+) features MGLRU, which uses multiple generations instead of two lists:

Pages progress through generations as they age
Younger generations have higher eviction priority
Hardware page-table access bits efficiently track real access
Scan cost is O(hot pages) not O(total pages)

This dramatically improves behavior under memory pressure, especially for workloads with large working sets.

Choosing the Right Policy

Different workloads favor different policies. Understanding your access patterns helps choose appropriately:

Policy Selection Guide
Workload Pattern	Best Policy	Reasoning
Working set fits in cache	Any	All policies work well
Strong temporal locality	LRU/CLOCK	Recency is the dominant predictor
Zipf-distributed access	LFU or ARC	Hot items stay hot
Sequential scans mixed with random access	ARC or 2Q	Resists scan pollution
Changing access patterns	ARC	Adapts automatically
Memory constrained system	CLOCK/MGLRU	Low overhead matters

When in Doubt

ARC and its variants (CAR, CLOCK-Pro) provide robust performance across diverse workloads without tuning. If you're building a new caching layer and don't have strong evidence for a specific policy, start with something adaptive.

Summary: Cache Policies

Key Takeaways

•Replacement policies predict future access from past behavior — The optimal policy (evict furthest-future access) is unrealizable; practical policies use recency and frequency.
•LRU is simple but vulnerable — Excellent for temporal locality but sequential scans can flush the entire cache.
•LFU resists scans but has adaptation problems — Keeps hot data but can't handle changing access patterns.
•CLOCK approximates LRU efficiently — Single reference bit enables O(1) access tracking at scale.
•ARC adaptively balances recency and frequency — Self-tunes based on workload, handles diverse patterns well.
•Linux uses multi-generation LRU — Balances theory with practical efficiency for large page caches.

What's Next: The next page examines cache coherence—how systems maintain consistency when multiple caches hold copies of the same data.

Page Complete

You now understand the major cache replacement policies, their trade-offs, and when to apply each. This knowledge enables you to reason about cache behavior, tune systems for specific workloads, and make informed architectural decisions.

3 / 5

Loading learning content...

Operating SystemsI/O Software

Caching

LevelAdvanced

Duration90 mins

TopicI/O Software

3 / 5

Cache Policies

The Art of Deciding What to Forget

What You Will Learn

Replacement Policy Fundamentals

The Optimal Policy (Bélády's Algorithm)

The theoretically optimal policy is simple: evict the page that will be accessed furthest in the future. This minimizes misses by keeping data that will be needed soonest.

Unfortunately, this requires knowledge of future accesses—impossible in practice. But it provides an upper bound for comparison: no realizable policy can do better.

Realizable Policies

Practical policies must predict future access using only past behavior. They rely on locality:

Temporal locality: Recently accessed data is likely to be accessed again soon
Frequency locality: Frequently accessed data is likely to be accessed again

Different policies weight these factors differently, making each better suited to certain workload patterns.

Cache Policy Characteristics
Policy	Principle	Tracks	Weakness
FIFO	First In, First Out	Insertion order	Ignores access patterns entirely
LRU	Least Recently Used	Recency	Scan-resistant workloads defeat it
LFU	Least Frequently Used	Frequency	Cannot adapt to changing patterns
ARC	Adaptive Replacement	Both + history	More complex implementation
CLOCK	LRU approximation	Reference bit	Less accurate than true LRU

Least Recently Used (LRU)

LRU is the most widely used cache replacement policy. It evicts the page that hasn't been accessed for the longest time, based on the assumption that recent access predicts future access.

LRU Implementation

True LRU requires tracking access order precisely. The classic implementation uses a doubly-linked list:

lru_implementation.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
/*
 * LRU Cache Implementation
 * Uses doubly-linked list for O(1) operations
 */
struct lru_node {
    void *key;
    void *value;
    struct lru_node *prev;
    struct lru_node *next;
};
 
struct lru_cache {
    struct lru_node *head;      /* Most recently used */
    struct lru_node *tail;      /* Least recently used (evict) */
    struct hash_table *lookup;  /* O(1) key lookup */
    size_t capacity;
    size_t size;
};
 
/* Move node to head (most recently used) */
void lru_touch(struct lru_cache *cache, struct lru_node *node) {
    if (node == cache->head)
        return;  /* Already MRU */
    
    /* Remove from current position */
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    if (node == cache->tail) cache->tail = node->prev;
    
    /* Insert at head */
    node->next = cache->head;
    node->prev = NULL;
    if (cache->head) cache->head->prev = node;
    cache->head = node;
}
 
/* Evict least recently used (tail) */
void *lru_evict(struct lru_cache *cache) {
    struct lru_node *victim = cache->tail;
    if (!victim) return NULL;
    
    cache->tail = victim->prev;
    if (cache->tail) cache->tail->next = NULL;
    else cache->head = NULL;
    
    hash_remove(cache->lookup, victim->key);
    cache->size--;
    
    void *evicted = victim->value;
    free(victim);
    return evicted;
}

LRU Strengths and Weaknesses

Strengths:

Excellent for workloads with strong temporal locality
Simple conceptual model
Naturally adapts to working set changes

Weaknesses:

Scan vulnerability: A single sequential scan through data larger than the cache evicts everything useful, leaving the cache filled with scan data that won't be accessed again
No frequency awareness: A page accessed once recently beats a page accessed 1000 times slightly less recently
Implementation overhead: True LRU requires updating data structures on every access

The Scan Problem

Least Frequently Used (LFU)

LFU evicts the page with the lowest access count, keeping frequently-accessed (popular) data cached regardless of recency.

LFU Implementation

lfu_implementation.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
/*
 * LFU Cache with O(1) operations
 * Uses frequency buckets linked together
 */
struct lfu_node {
    void *key;
    void *value;
    size_t frequency;
    struct list_head freq_list;  /* Position in frequency bucket */
};
 
struct freq_bucket {
    size_t freq;
    struct list_head nodes;      /* Nodes with this frequency */
    struct list_head bucket_list; /* All buckets, ordered by freq */
};
 
struct lfu_cache {
    struct hash_table *lookup;
    struct list_head freq_buckets; /* Ascending frequency order */
    size_t min_freq;
    size_t capacity, size;
};
 
void lfu_access(struct lfu_cache *cache, struct lfu_node *node) {
    /* Remove from current frequency bucket */
    struct freq_bucket *old_bucket = get_bucket(cache, node->frequency);
    list_del(&node->freq_list);
    
    /* If bucket empty and was minimum, update min_freq */
    if (list_empty(&old_bucket->nodes) && 
        node->frequency == cache->min_freq)
        cache->min_freq++;
    
    /* Increment frequency and add to new bucket */
    node->frequency++;
    struct freq_bucket *new_bucket = get_or_create_bucket(
        cache, node->frequency);
    list_add_tail(&node->freq_list, &new_bucket->nodes);
}
 
struct lfu_node *lfu_evict(struct lfu_cache *cache) {
    /* Get minimum frequency bucket */
    struct freq_bucket *min_bucket = get_bucket(cache, cache->min_freq);
    
    /* Evict least recently used within that frequency (LRU tiebreaker) */
    struct lfu_node *victim = list_first_entry(
        &min_bucket->nodes, struct lfu_node, freq_list);
    
    list_del(&victim->freq_list);
    hash_remove(cache->lookup, victim->key);
    cache->size--;
    
    return victim;
}

LFU Strengths and Weaknesses

Strengths:

Resists scan pollution—sequential scans accumulate low frequency
Keeps genuinely hot data in cache
Excellent for stable, skewed access distributions

Weaknesses:

Cache pollution: Once-hot data that's no longer accessed fills the cache with high-frequency zombies
Slow warmup: New data starts with frequency 1, vulnerable to eviction before it can prove its value
No recency: Can't distinguish between 1000 accesses yesterday vs. 1000 accesses last month

The CLOCK Algorithm

CLOCK (also called Second-Chance) is a practical approximation of LRU that dramatically reduces overhead. Instead of maintaining a fully-ordered list, it uses a single reference bit per page.

CLOCK Operation

Pages are arranged in a circular buffer with a 'clock hand' pointer. Each page has a reference bit set to 1 when accessed. When eviction is needed:

clock_algorithm.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
/*
 * CLOCK page replacement algorithm
 * Used by Linux for page cache management
 */
struct page {
    unsigned int referenced : 1;  /* Set on access */
    unsigned int dirty : 1;
    void *data;
};
 
struct clock_cache {
    struct page *pages;
    size_t capacity;
    size_t hand;  /* Current position */
};
 
struct page *clock_evict(struct clock_cache *cache) {
    while (1) {
        struct page *p = &cache->pages[cache->hand];
        
        if (p->referenced) {
            /* Give second chance - clear and move on */
            p->referenced = 0;
            cache->hand = (cache->hand + 1) % cache->capacity;
        } else {
            /* Found victim - not recently referenced */
            cache->hand = (cache->hand + 1) % cache->capacity;
            return p;
        }
    }
}
 
/* Hardware/kernel sets this on access */
void clock_access(struct page *p) {
    p->referenced = 1;
}

Why CLOCK Works

CLOCK approximates LRU behavior:

Recently-accessed pages have reference bit set, get second chances
Long-untouched pages have reference bit clear (cleared by previous passes), get evicted
The clock hand's sweep period determines 'recency' granularity

Advantages over LRU:

O(1) access without data structure updates
Reference bit can be set by hardware (page table accessed bit)
Scales to millions of pages efficiently

Enhanced CLOCK Variants

CLOCK-Pro: Tracks both recent and frequent access patterns CAR: Combines CLOCK with adaptive behavior like ARC 2Q: Uses two queues to distinguish one-time from repeated access

Adaptive Replacement Cache (ARC)

ARC Structure

ARC maintains four lists:

The cache holds pages in T1 ∪ T2, limited to cache size. B1 and B2 are metadata-only (no data cached), tracking what was recently evicted.

arc_algorithm.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
/*
 * Simplified ARC implementation
 * Demonstrates the adaptive balancing mechanism
 */
struct arc_cache {
    struct list_head T1, T2;    /* Cached pages */
    struct list_head B1, B2;    /* Ghost lists */
    size_t c;                   /* Cache capacity */
    size_t p;                   /* Target size for T1 (adaptive) */
    
    size_t t1_size, t2_size;
    size_t b1_size, b2_size;
};
 
void arc_request(struct arc_cache *arc, void *page) {
    /* Case 1: Hit in T1 - move to T2 (now frequent) */
    if (in_list(page, &arc->T1)) {
        move_to_mru(&arc->T2, page);
        arc->t1_size--; arc->t2_size++;
        return;
    }
    
    /* Case 2: Hit in T2 - move to MRU of T2 */
    if (in_list(page, &arc->T2)) {
        move_to_mru(&arc->T2, page);
        return;
    }
    
    /* Case 3: Hit in B1 ghost - recency was useful */
    if (in_list(page, &arc->B1)) {
        /* Adapt: increase target size for T1 */
        arc->p = min(arc->c, arc->p + max(1, arc->b2_size/arc->b1_size));
        
        replace(arc, 0);  /* Make room */
        remove_from(&arc->B1, page); arc->b1_size--;
        add_to_mru(&arc->T2, page); arc->t2_size++;  /* Now in cache */
        return;
    }
    
    /* Case 4: Hit in B2 ghost - frequency was useful */
    if (in_list(page, &arc->B2)) {
        /* Adapt: decrease target size for T1 */
        arc->p = max(0, arc->p - max(1, arc->b1_size/arc->b2_size));
        
        replace(arc, 1);  /* Make room */
        remove_from(&arc->B2, page); arc->b2_size--;
        add_to_mru(&arc->T2, page); arc->t2_size++;
        return;
    }
    
    /* Case 5: Complete miss - not in cache or ghosts */
    /* Manage ghost list sizes */
    if (arc->t1_size + arc->b1_size == arc->c) {
        if (arc->t1_size < arc->c) {
            evict_lru(&arc->B1); arc->b1_size--;
            replace(arc, 0);
        } else {
            evict_lru(&arc->T1); arc->t1_size--;
        }
    }
    add_to_mru(&arc->T1, page); arc->t1_size++;
}
 
/* Replace a page - favor T1 or T2 based on p */
void replace(struct arc_cache *arc, int in_b2) {
    if (arc->t1_size > 0 && 
        (arc->t1_size > arc->p || (in_b2 && arc->t1_size == arc->p))) {
        /* Evict from T1, add ghost to B1 */
        void *victim = evict_lru(&arc->T1); arc->t1_size--;
        add_to_mru(&arc->B1, victim); arc->b1_size++;
    } else {
        /* Evict from T2, add ghost to B2 */
        void *victim = evict_lru(&arc->T2); arc->t2_size--;
        add_to_mru(&arc->B2, victim); arc->b2_size++;
    }
}

ARC's Adaptive Mechanism

This self-tuning means ARC automatically adapts to:

Recency-dominated workloads (more T1)
Frequency-dominated workloads (more T2)
Mixed workloads (balanced T1/T2)
Changing workload patterns (adapts continuously)

ARC in Practice

Linux Page Cache Policies

Linux uses a sophisticated multi-generation LRU (MGLRU) system that addresses classical LRU weaknesses while maintaining practical efficiency for millions of pages.

Two-List Approach (Traditional)

Traditionally, Linux maintained two lists:

Active List: Pages accessed recently (likely to be accessed again) Inactive List: Pages not accessed recently (candidates for eviction)

Pages start on the inactive list. If accessed while inactive, they're promoted to the active list. Active pages gradually demote to inactive if not re-accessed.

linux_page_reclaim.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
/*
 * Simplified Linux page aging and reclaim
 */
 
/* Page flags for reclaim decisions */
#define PG_referenced   1    /* Recently accessed */
#define PG_active       2    /* On active list */
 
/*
 * Determine if page should be promoted
 * Called when page is accessed
 */
void mark_page_accessed(struct page *page) {
    if (!PageReferenced(page)) {
        SetPageReferenced(page);
    } else if (!PageActive(page)) {
        /* Second access while inactive - promote */
        activate_page(page);
        ClearPageReferenced(page);
    }
}
 
/*
 * Page reclaim: scan inactive list
 */
unsigned shrink_inactive_list(struct lruvec *lruvec,
                               unsigned nr_to_scan) {
    LIST_HEAD(pages_to_free);
    unsigned nr_reclaimed = 0;
    
    while (nr_to_scan-- && !list_empty(&lruvec->inactive)) {
        struct page *page = lru_to_page(&lruvec->inactive);
        
        if (PageReferenced(page)) {
            /* Referenced - give another chance */
            ClearPageReferenced(page);
            list_move(&page->lru, &lruvec->inactive);
            continue;
        }
        
        if (PageDirty(page)) {
            /* Must write back first */
            pageout(page);
            continue;
        }
        
        /* Unreferenced, clean - can reclaim */
        list_move(&page->lru, &pages_to_free);
        nr_reclaimed++;
    }
    
    free_pages_list(&pages_to_free);
    return nr_reclaimed;
}

Multi-Gen LRU (MGLRU)

Modern Linux (5.18+) features MGLRU, which uses multiple generations instead of two lists:

Pages progress through generations as they age
Younger generations have higher eviction priority
Hardware page-table access bits efficiently track real access
Scan cost is O(hot pages) not O(total pages)

This dramatically improves behavior under memory pressure, especially for workloads with large working sets.

Choosing the Right Policy

Different workloads favor different policies. Understanding your access patterns helps choose appropriately:

Policy Selection Guide
Workload Pattern	Best Policy	Reasoning
Working set fits in cache	Any	All policies work well
Strong temporal locality	LRU/CLOCK	Recency is the dominant predictor
Zipf-distributed access	LFU or ARC	Hot items stay hot
Sequential scans mixed with random access	ARC or 2Q	Resists scan pollution
Changing access patterns	ARC	Adapts automatically
Memory constrained system	CLOCK/MGLRU	Low overhead matters

When in Doubt

Summary: Cache Policies

Key Takeaways

•Replacement policies predict future access from past behavior — The optimal policy (evict furthest-future access) is unrealizable; practical policies use recency and frequency.
•LRU is simple but vulnerable — Excellent for temporal locality but sequential scans can flush the entire cache.
•LFU resists scans but has adaptation problems — Keeps hot data but can't handle changing access patterns.
•CLOCK approximates LRU efficiently — Single reference bit enables O(1) access tracking at scale.
•ARC adaptively balances recency and frequency — Self-tunes based on workload, handles diverse patterns well.
•Linux uses multi-generation LRU — Balances theory with practical efficiency for large page caches.

What's Next: The next page examines cache coherence—how systems maintain consistency when multiple caches hold copies of the same data.

Page Complete

3 / 5