Paging / Caching

Why Paging / Caching Matters

Modern computing architectures face a fundamental physical reality: memory that is extremely fast is prohibitively expensive and small, while memory that is large and cheap is orders of magnitude slower. CPU registers and L1 caches operate in under a nanosecond, main DRAM operates in tens to hundreds of nanoseconds, and secondary storage (SSDs or disk) or network storage operates in milliseconds—a delay factor of over 100,000x.

To bridge this massive performance gap, system designers use paging and caching. By maintaining a small, high-speed memory buffer of capacity $K$ (measured in fixed-size blocks called pages or cache frames), the system attempts to satisfy memory requests immediately from fast storage. When a requested page is already present in fast memory, a cache hit occurs, servicing the request with minimal latency. When the requested page is absent, a page fault (or cache miss) occurs: the system must fetch the missing page from slow secondary storage into fast memory. If the cache is already full ($K$ pages present), the system must execute a page replacement policy to select and evict a resident page to make room for the incoming one.

The curriculum scope covers the three fundamental page replacement policies:

FIFO (First-In, First-Out): Evicts the page that has resided in the cache the longest, regardless of how recently or frequently it was accessed.
LRU (Least Recently Used): Evicts the page that has not been accessed for the longest period of time, directly exploiting temporal locality.
Belady OPT (Optimal / MIN): Evicts the page that will not be accessed for the longest period of time in the future. OPT requires offline knowledge of future requests and serves as the theoretical gold standard against which all online policies are measured.

After completing this lesson, you will be able to formalize the online paging problem, trace page fault decisions step by step, design and implement $O(1)$ time-complexity caching data structures in Python, C++, and Java, and evaluate replacement policies based on competitive analysis and Belady's Anomaly.

The paging problem models a memory hierarchy with a fast cache of capacity $K$ and a large slow storage tier. When an incoming page request misses and the cache is full, a page replacement policy must evict a resident page to maintain performance; effective policies like LRU exploit temporal locality to minimize total page faults, while Belady's OPT provides the theoretical minimum fault count by evicting the page needed farthest in the future.

Core Concepts and Terminology

To analyze caching algorithms rigorously, we define the input sequence, operational bounds, and policy mechanics using precise terminology.

The online paging problem is defined over a universe of pages $U$ and a cache of fixed capacity $K \in \mathbb{N}^+$. The input is a sequence of page requests $S = (p_1, p_2, \dots, p_N)$ arriving one at a time over discrete time steps $t = 1, 2, \dots, N$, where $p_t \in U$. At each step $t$, the cache state is represented as a set $\text{Cache}_t \subset U$ with $|\text{Cache}_t| \le K$.

Hit Condition: If $p_t \in \text{Cache}_{t-1}$, then $\text{Cache}_t = \text{Cache}_{t-1}$ (a hit occurs; no page movement from slow storage).
Miss Condition: If $p_t \notin \text{Cache}_{t-1}$, a page fault occurs.
If $|\text{Cache}_{t-1}| \lt K$, the page is loaded into a free slot: $\text{Cache}_t = \text{Cache}_{t-1} \cup \{p_t\}$.
If $|\text{Cache}_{t-1}| = K$, an eviction candidate $e_t \in \text{Cache}_{t-1}$ is selected according to the policy, yielding $\text{Cache}_t = (\text{Cache}_{t-1} \setminus \{e_t\}) \cup \{p_t\}$.

The objective of any replacement policy is to minimize the total fault count $F(S) = \sum_{t=1}^N \mathbf{1}[p_t \notin \text{Cache}_{t-1}]$.

Key Term	Algorithmic Role	Concrete Example
Cache Capacity ($K$)	Defines maximum number of pages stored simultaneously in fast memory.	$K = 3$ physical memory frames reserved for virtual memory paging.
Page Fault (Miss)	Event triggered when requested page $p_t \notin \text{Cache}$. Requires loading $p_t$ from slow storage.	Requesting page `4` when cache holds `{1, 2, 3}` causes a fault.
Cache Hit	Event triggered when requested page $p_t \in \text{Cache}$. Data served instantly with zero eviction overhead.	Requesting page `1` when cache holds `{1, 2, 3}` results in a hit.
Eviction Victim	Resident page selected by replacement policy to be dropped when cache is full upon a miss.	LRU selects page `1` for eviction because it was accessed at step 1, whereas pages 2 and 3 were accessed at steps 2 and 3.
Temporal Locality	Property where recently accessed pages are highly likely to be accessed again soon.	A loop executing code instructions repeatedly accesses pages `{1, 2}` in quick succession.
Belady's Anomaly	Phenomenon where increasing capacity $K$ causes more total page faults under certain policies.	FIFO on sequence `3,2,1,0,3,2,4,3,2,1,0,4` produces 9 faults at $K=3$, but 10 faults at $K=4$.
Competitive Ratio	Ratio bounding online policy fault count relative to offline Belady OPT: $\frac{\text{Faults}_{\text{Online}}}{\text{Faults}_{\text{OPT}}} \le C$.	LRU is $K$-competitive: for any request sequence, LRU faults $\le K \times \text{OPT faults} + O(1)$.

How Paging / Caching Works, Step by Step

Every page request processed by a cache controller follows a strict state transition sequence. Below is the step-by-step operational flow for processing request $p_t$ at step $t$:

Receive Request: The processor issues a read/write command for page $p_t$.
Lookup Key in Index: Check if $p_t$ exists in the fast lookup structure (e.g., hash table or hardware TLB/content-addressable memory).
Branch on Hit vs. Miss: Case A: Cache Hit ($p_t \in \text{Cache}$) LRU: Remove $p_t$ from its current position in the recency list and append it to the tail (marking it Most Recently Used). FIFO / OPT: No modification to queue ordering or eviction priority is required. Return requested page data immediately.

Case B: Page Fault ($p_t \notin \text{Cache}$)
Increment total_faults counter by 1.
If $\text{size}(\text{Cache}) \lt K$ (Free slot available):
Insert $p_t$ into an unoccupied cache frame.
Add $p_t$ to index and update policy ordering structures.

If $\text{size}(\text{Cache}) = K$ (Cache full):
Select Eviction Victim $e$:
FIFO: Select page at the head of the arrival queue (oldest inserted page).
LRU: Select page at the head of the recency list (least recently used page).
OPT: Scan remaining requests $p_{t+1} \dots p_N$. For each resident page $p \in \text{Cache}$, find its next occurrence index. Select page $e$ whose next access is farthest in the future (or $\infty$ if never accessed again).

Evict $e$: Remove $e$ from cache frames and hash index.
Insert $p_t$: Place $p_t$ into freed frame, update hash index, and place at most recent position in policy structure.

Paging / Caching control flow

flowchart TD
A[Start: Request page p_t] --> B{Is p_t in Cache?}

```
B -- Yes: Cache Hit --> C{Policy Type?}
C -- LRU --> D[Move p_t to tail of LRU queue]
C -- FIFO / OPT --> E[Keep cache order unchanged]
D --> F[Return requested data]
E --> F

B -- No: Page Fault --> G[Increment Fault Count]
G --> H{Is Cache Size < K?}

H -- Yes: Space Available --> I[Insert p_t into free slot]
H -- No: Cache Full --> J{Select Eviction Policy}

J -- FIFO --> K[Pick page at head of FIFO queue]
J -- LRU --> L[Pick page at head of LRU queue]
J -- Belady OPT --> M[Pick page with farthest future access index]

K --> N[Evict candidate page from Cache]
L --> N
M --> N

N --> O[Insert p_t into freed slot]
I --> P[Update Hash Table and Queue Metadata]
O --> P
P --> F

```

Worked Example with a Full Trace

Let us execute a complete step-by-step trace comparing LRU, FIFO, and Belady OPT on a benchmark sequence.

Parameters:

Cache Capacity: $K = 3$
Reference String: [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] (Length $N = 12$)

Step-by-Step LRU Trace Matrix

Worked Example

Trace It by Hand

Test your understanding by tracing steps 7 through 10 of the sequence [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] on a cache of capacity $K = 3$:

At Step 6, the LRU cache holds [4, 1, 2] (where page 4 is LRU, page 2 is MRU).
Step 7 (Request page 5): Predict which page is evicted by LRU and what the cache state becomes.
Step 8 (Request page 1): Is this a hit or a miss? How does the recency queue change?
Step 10 (Request page 3): Compare LRU vs. Belady OPT. What does LRU evict vs. what Belady OPT evicts?

Answer Verification:

Step 7 (LRU): Page 5 is a miss. Page 4 is LRU (accessed at t=4). Evict page 4. Cache becomes [1, 2, 5].
Step 8 (LRU): Page 1 is present! It is a HIT. Cache reorders recency to [2, 5, 1].
Step 10: Cache holds [2, 5, 1] (reordered after hits at t=8, t=9). Request page 3 is a miss.
LRU evicts page 5 (accessed at t=7, whereas page 1 was t=8, page 2 was t=9). Cache becomes [1, 2, 3].
Belady OPT looks ahead at remaining requests [4, 5]. Next use of 5 is at t=12; pages 1 and 2 are never used again ($\infty$). OPT evicts page 1 or 2, preserving page 5 for step 12!

Implementation in Python, C++, and Java

The code below implements deterministic simulators for FIFO, LRU, and Belady OPT policies. Each implementation processes the benchmark sequence [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] on capacity $K = 3$ and prints step-by-step logs along with final fault counts.

## Complete, runnable Paging Simulator in Python (FIFO, LRU, Belady OPT)

def simulate_fifo(ref_str, capacity):
    cache = []
    faults = 0
    print("--- FIFO Policy ---")
    for i, page in enumerate(ref_str, 1):
        if page in cache:
            status = "Hit "
            evicted_msg = ""
        else:
            status = "Miss"
            faults += 1
            if len(cache) == capacity:
                evicted = cache.pop(0)
                evicted_msg = f" (Evicted {evicted})"
            else:
                evicted_msg = ""
            cache.append(page)
        cache_str = "[" + ", ".join(map(str, cache)) + "]"
        print(f"Step {i:2d}: Req {page:2d} -> {status} {cache_str}{evicted_msg}")
    print(f"FIFO Total Faults: {faults}\n")
    return faults


def simulate_lru(ref_str, capacity):
    cache = []  # index 0 is LRU, last index is MRU
    faults = 0
    print("--- LRU Policy ---")
    for i, page in enumerate(ref_str, 1):
        if page in cache:
            status = "Hit "
            cache.remove(page)
            cache.append(page)
            evicted_msg = ""
        else:
            status = "Miss"
            faults += 1
            if len(cache) == capacity:
                evicted = cache.pop(0)
                evicted_msg = f" (Evicted {evicted})"
            else:
                evicted_msg = ""
            cache.append(page)
        cache_str = "[" + ", ".join(map(str, cache)) + "]"
        print(f"Step {i:2d}: Req {page:2d} -> {status} {cache_str}{evicted_msg}")
    print(f"LRU Total Faults: {faults}\n")
    return faults


def simulate_opt(ref_str, capacity):
    cache = []
    faults = 0
    print("--- Belady OPT Policy ---")
    for i, page in enumerate(ref_str):
        step = i + 1
        if page in cache:
            status = "Hit "
            evicted_msg = ""
        else:
            status = "Miss"
            faults += 1
            if len(cache) == capacity:
                farthest_idx = -1
                evict_page = None
                for p in cache:
                    try:
                        next_use = ref_str.index(p, i + 1)
                    except ValueError:
                        next_use = float('inf')
                    if next_use > farthest_idx:
                        farthest_idx = next_use
                        evict_page = p
                cache.remove(evict_page)
                cache.append(page)
                evicted_msg = f" (Evicted {evict_page})"
            else:
                cache.append(page)
                evicted_msg = ""
        cache_str = "[" + ", ".join(map(str, cache)) + "]"
        print(f"Step {step:2d}: Req {page:2d} -> {status} {cache_str}{evicted_msg}")
    print(f"Belady OPT Total Faults: {faults}\n")
    return faults


if __name__ == "__main__":
    ref_string = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
    cap = 3
    print("Paging Simulation (Capacity = 3)")
    print(f"Reference String: {ref_string}\n")
    simulate_fifo(ref_string, cap)
    simulate_lru(ref_string, cap)
    simulate_opt(ref_string, cap)

// Complete, runnable Paging Simulator in C++ (FIFO, LRU, Belady OPT)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

string format_cache(const vector<int>& cache) {
    string s = "[";
    for (size_t i = 0; i < cache.size(); ++i) {
        s += to_string(cache[i]);
        if (i + 1 < cache.size()) s += ", ";
    }
    s += "]";
    return s;
}

void simulate_fifo(const vector<int>& ref, int capacity) {
    vector<int> cache;
    int faults = 0;
    cout << "--- FIFO Policy ---\n";
    for (size_t i = 0; i < ref.size(); ++i) {
        int page = ref[i];
        auto it = find(cache.begin(), cache.end(), page);
        string status, evicted_msg = "";
        if (it != cache.end()) {
            status = "Hit ";
        } else {
            status = "Miss";
            faults++;
            if (cache.size() == (size_t)capacity) {
                int evicted = cache.front();
                cache.erase(cache.begin());
                evicted_msg = " (Evicted " + to_string(evicted) + ")";
            }
            cache.push_back(page);
        }
        cout << "Step " << setw(2) << (i + 1) << ": Req " << setw(2) << page
             << " -> " << status << " " << format_cache(cache) << evicted_msg << "\n";
    }
    cout << "FIFO Total Faults: " << faults << "\n\n";
}

void simulate_lru(const vector<int>& ref, int capacity) {
    vector<int> cache;
    int faults = 0;
    cout << "--- LRU Policy ---\n";
    for (size_t i = 0; i < ref.size(); ++i) {
        int page = ref[i];
        auto it = find(cache.begin(), cache.end(), page);
        string status, evicted_msg = "";
        if (it != cache.end()) {
            status = "Hit ";
            cache.erase(it);
            cache.push_back(page);
        } else {
            status = "Miss";
            faults++;
            if (cache.size() == (size_t)capacity) {
                int evicted = cache.front();
                cache.erase(cache.begin());
                evicted_msg = " (Evicted " + to_string(evicted) + ")";
            }
            cache.push_back(page);
        }
        cout << "Step " << setw(2) << (i + 1) << ": Req " << setw(2) << page
             << " -> " << status << " " << format_cache(cache) << evicted_msg << "\n";
    }
    cout << "LRU Total Faults: " << faults << "\n\n";
}

void simulate_opt(const vector<int>& ref, int capacity) {
    vector<int> cache;
    int faults = 0;
    cout << "--- Belady OPT Policy ---\n";
    for (size_t i = 0; i < ref.size(); ++i) {
        int page = ref[i];
        auto it = find(cache.begin(), cache.end(), page);
        string status, evicted_msg = "";
        if (it != cache.end()) {
            status = "Hit ";
        } else {
            status = "Miss";
            faults++;
            if (cache.size() == (size_t)capacity) {
                int farthest_idx = -1;
                int evict_page = -1;
                size_t evict_pos = 0;
                for (size_t c = 0; c < cache.size(); ++c) {
                    int p = cache[c];
                    int next_use = 999999;
                    for (size_t j = i + 1; j < ref.size(); ++j) {
                        if (ref[j] == p) {
                            next_use = (int)j;
                            break;
                        }
                    }
                    if (next_use > farthest_idx) {
                        farthest_idx = next_use;
                        evict_page = p;
                        evict_pos = c;
                    }
                }
                cache.erase(cache.begin() + evict_pos);
                cache.push_back(page);
                evicted_msg = " (Evicted " + to_string(evict_page) + ")";
            } else {
                cache.push_back(page);
            }
        }
        cout << "Step " << setw(2) << (i + 1) << ": Req " << setw(2) << page
             << " -> " << status << " " << format_cache(cache) << evicted_msg << "\n";
    }
    cout << "Belady OPT Total Faults: " << faults << "\n\n";
}

int main() {
    vector<int> ref = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
    int capacity = 3;
    cout << "Paging Simulation (Capacity = 3)\n";
    cout << "Reference String: [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]\n\n";
    simulate_fifo(ref, capacity);
    simulate_lru(ref, capacity);
    simulate_opt(ref, capacity);
    return 0;
}

// Complete, runnable Paging Simulator in Java (FIFO, LRU, Belady OPT)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    private static String formatCache(List<Integer> cache) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < cache.size(); i++) {
            sb.append(cache.get(i));
            if (i + 1 < cache.size()) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public static void simulateFIFO(int[] ref, int capacity) {
        List<Integer> cache = new ArrayList<>();
        int faults = 0;
        System.out.println("--- FIFO Policy ---");
        for (int i = 0; i < ref.length; i++) {
            int page = ref[i];
            String status;
            String evictedMsg = "";
            if (cache.contains(page)) {
                status = "Hit ";
            } else {
                status = "Miss";
                faults++;
                if (cache.size() == capacity) {
                    int evicted = cache.remove(0);
                    evictedMsg = " (Evicted " + evicted + ")";
                }
                cache.add(page);
            }
            System.out.printf("Step %2d: Req %2d -> %s %s%s\n", (i + 1), page, status, formatCache(cache), evictedMsg);
        }
        System.out.println("FIFO Total Faults: " + faults + "\n");
    }

    public static void simulateLRU(int[] ref, int capacity) {
        List<Integer> cache = new ArrayList<>();
        int faults = 0;
        System.out.println("--- LRU Policy ---");
        for (int i = 0; i < ref.length; i++) {
            int page = ref[i];
            String status;
            String evictedMsg = "";
            if (cache.contains(page)) {
                status = "Hit ";
                cache.remove(Integer.valueOf(page));
                cache.add(page);
            } else {
                status = "Miss";
                faults++;
                if (cache.size() == capacity) {
                    int evicted = cache.remove(0);
                    evictedMsg = " (Evicted " + evicted + ")";
                }
                cache.add(page);
            }
            System.out.printf("Step %2d: Req %2d -> %s %s%s\n", (i + 1), page, status, formatCache(cache), evictedMsg);
        }
        System.out.println("LRU Total Faults: " + faults + "\n");
    }

    public static void simulateOPT(int[] ref, int capacity) {
        List<Integer> cache = new ArrayList<>();
        int faults = 0;
        System.out.println("--- Belady OPT Policy ---");
        for (int i = 0; i < ref.length; i++) {
            int page = ref[i];
            String status;
            String evictedMsg = "";
            if (cache.contains(page)) {
                status = "Hit ";
            } else {
                status = "Miss";
                faults++;
                if (cache.size() == capacity) {
                    int farthestIdx = -1;
                    int evictPage = -1;
                    int evictPos = 0;
                    for (int c = 0; c < cache.size(); c++) {
                        int p = cache.get(c);
                        int nextUse = Integer.MAX_VALUE;
                        for (int j = i + 1; j < ref.length; j++) {
                            if (ref[j] == p) {
                                nextUse = j;
                                break;
                            }
                        }
                        if (nextUse > farthestIdx) {
                            farthestIdx = nextUse;
                            evictPage = p;
                            evictPos = c;
                        }
                    }
                    cache.remove(evictPos);
                    cache.add(page);
                    evictedMsg = " (Evicted " + evictPage + ")";
                } else {
                    cache.add(page);
                }
            }
            System.out.printf("Step %2d: Req %2d -> %s %s%s\n", (i + 1), page, status, formatCache(cache), evictedMsg);
        }
        System.out.println("Belady OPT Total Faults: " + faults + "\n");
    }

    public static void main(String[] args) {
        int[] ref = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
        int capacity = 3;
        System.out.println("Paging Simulation (Capacity = 3)");
        System.out.println("Reference String: " + Arrays.toString(ref) + "\n");
        simulateFIFO(ref, capacity);
        simulateLRU(ref, capacity);
        simulateOPT(ref, capacity);
    }
}

Complexity, Correctness, and Invariants

Analyzing replacement algorithms requires evaluating runtime efficiency per request, space overhead, and competitive fault bounds.

Algorithm	Lookup Time	Eviction / Update Time	Space Complexity	Practical Online Feasibility	Competitive Ratio / Optimality
FIFO	$O(1)$ (with Hash Set)	$O(1)$ (Queue pop)	$O(K)$	High (Simple Queue)	Unbounded ($> K$ worst case)
LRU (Optimal Impl)	$O(1)$ (Hash Map + DLL)	$O(1)$ (Node splice)	$O(K)$	High (Standard cache structure)	Strictly $K$-competitive
Belady OPT	$O(1)$	$O(K \cdot N)$ offline scan	$O(K + N)$	Impossible online (requires future)	$1.0$ (Theoretical Optimum)
Clock (Second Chance)	$O(1)$ amortized	$O(1)$ amortized (Pointer scan)	$O(K)$ (1 bit per frame)	Very High (Hardware OS default)	Approximates LRU
LFU (Least Frequently Used)	$O(1)$ (Min-Heap / Buckets)	$O(\log K)$ or $O(1)$	$O(K)$	Medium (Frequency accumulation)	Unbounded without decay

Correctness & Optimality Invariant: Belady's OPT algorithm is proven minimal by Mattson's Stack Property: for any sequence $S$, maintaining a page set $C_K(t)$ of size $K$ satisfying $C_K(t) \subset C_{K+1}(t)$ ensures monotonic fault counts. Belady's OPT preserves the invariant that at time $t$, evicting page $e = \arg\max_{p \in \text{Cache}} \{\text{next\_access}(p)\}$ yields the maximum possible intersection with future optimal configurations, establishing that no policy can achieve strictly fewer page faults on sequence $S$.

Variants, Pitfalls, and Optimizations

Belady's Anomaly

A counter-intuitive flaw in simple replacement algorithms like FIFO is Belady's Anomaly: increasing cache capacity $K$ can actually increase the total number of page faults for specific access patterns. Stack algorithms (such as LRU and OPT) are mathematically immune to Belady's Anomaly because their cache contents for size $K$ are strictly a subset of cache contents for size $K+1$.

Common Implementation Pitfalls:

Naive $O(K)$ Search in LRU: Implementing LRU using a plain list/array requires scanning $O(K)$ to locate requested pages on hits. Production LRU must combine a Hash Map (for $O(1)$ node lookup) with a Doubly Linked List (for $O(1)$ node removal and head insertion).
Scan Pollution / Sequential Flooding: Iterating sequentially through a large database table or dataset larger than $K$ flushes all frequently accessed ("hot") items from an LRU cache. Use 2Q or ARC to isolate streaming requests into a separate queue.
Thrashing: When the aggregate working set size of all active processes exceeds available physical cache capacity $K$, the system spends virtually 100% of its execution time servicing page faults rather than processing computation.

Practice Problems and Real-World Use

Caching algorithms form the bedrock of performance engineering across hardware, operating systems, databases, and distributed web services.

Real-World System / Practice Problem	Application & Mechanism	Tested Core Concept	Difficulty
OS Virtual Memory (Linux Paging)	Manages physical RAM page frames using Clock (Second Chance) algorithm with active/inactive page lists.	Hardware reference bits, page fault handling	Intermediate
Database Buffer Pool (PostgreSQL / InnoDB)	Caching disk blocks in memory using 2Q / LRU-K to prevent scan pollution during `SELECT *` queries.	Mid-point insertion, frequency tracking	Advanced
CPU L1/L2/L3 Caches	Hardware set-associative cache line replacement via Pseudo-LRU (Tree-PLRU) bit-tree logic.	Sub-nanosecond hardware constraints	Advanced
Web Caching & CDNs (Redis, Varnish, Nginx)	In-memory key-value eviction strategies (`allkeys-lru`, `volatile-lru`, `sampled-lru`).	Distributed caching, memory limits	Intermediate
LeetCode 146: LRU Cache	Design a data structure supporting `get(key)` and `put(key, value)` in $O(1)$ time complexity.	Hash Map + Doubly Linked List	Medium
LeetCode 460: LFU Cache	Design a data structure supporting `get` and `put` in $O(1)$ time by tracking access frequencies.	Hash Map + Frequency Buckets	Hard
Belady Anomaly Proof	Formally prove that stack algorithms (where $C_K \subseteq C_{K+1}$) can never exhibit Belady's Anomaly.	Set theory, cache inclusion invariants	Intermediate

Cookie Consent