Cache Replacement

Why Cache Replacement Matters

A cache has room for three blocks. A fourth block is requested. All resident data may be correct, yet one block must leave before the new block can remain. Cache replacement chooses that victim, using past references as evidence about future reuse.

The choice matters in buffer pools, page caches, application caches, and memory-hierarchy models. Keeping a frequently reused block can avoid repeated transfers; preserving an old favorite after the workload changes can waste capacity. No history-based policy can see the future, and the policy with the lowest miss count on one trace need not win on another.

This lesson compares FIFO, LRU, LFU, and Clock/Second Chance on exactly the same sequence of read addresses. Each complete Python, C++, and Java program copies real block payloads, returns the requested values, records victim choices and metadata, and prints transfer counts. An ARC overview explains how ghost history can adapt a recency/frequency balance; ARC is not one of the four executable policies.

The earlier B/B+ tree and cache-layout lessons changed how a program arranges or visits data. Here the reference sequence stays fixed while replacement changes what survives between references. You will separate those effects, reproduce a complete trace, understand LFU's counting/tie conventions, and trace a Clock hand through a full second-chance sweep.

Correct values are necessary but insufficient for policy verification: a cache that accidentally behaves like FIFO can still return every read correctly. The lesson therefore checks each policy decision and state as well as the data.

Core Concepts and Terminology

The input consists of immutable backing words, a finite sequence of valid word addresses, a block length $B$ words, a capacity $Q$ block frames, and a policy name. The output is the value returned at every address plus a full state trace and aggregate hit/read/eviction counters. Each simulation starts cold and keeps its cache throughout the supplied sequence.

For a word address $a$, its block tag and in-block offset are $$ \operatorname{tag}(a)=\left\lfloor\frac aB\right\rfloor, \qquad \operatorname{offset}(a)=a\bmod B. $$ Backing block $t$ contains words at addresses $tB$ through $(t+1)B-1$, clipped to the input length. The last block is padded with zero words for transfer accounting; valid addresses never point to padding. Two addresses in the same block share one cached payload. A block tag identifies data; a frame number identifies a reusable cache slot.

Each logical word is eight bytes. One miss transfers $8B$ bytes, while resident payload capacity is $8BQ$ bytes. These are modeled widths, not Python integer-object sizes or native allocation costs. A missing block is read in full even if only one of its words is requested. A hit performs no backing transfer.

The model is fully associative: any block can occupy any frame. It is also read only, so every resident payload remains equal to its backing block. Evictions are clean, no dirty writebacks occur, and there is no final flush: $$ \text{transfers}=\text{block reads}=\text{misses},\qquad \text{references}=\text{hits}+\text{misses}. $$ A free-frame fill is a miss without eviction. A hit does not evict. With $Q=0$, the laboratory uses bypass mode: every reference reads its block into a temporary transfer buffer and retains nothing. There are no resident hits or evictions, and modulo-hand arithmetic is avoided.

Common metadata. A resident frame stores its tag, payload, insertion timestamp born, last-reference timestamp last, resident frequency freq, and reference bit ref. Timestamps are one-based positions in the trace. Insertion sets both timestamps to the current time, frequency to one, and reference bit to one. Every resident hit refreshes last, increments freq, and sets ref; a policy uses only the fields relevant to its own decision. FIFO does not use the refreshed last-reference field to select victims.

The four policy contracts are precise:

• FIFO, first in first out: evict the resident block with smallest insertion timestamp. Hits leave its insertion timestamp unchanged.
• LRU, least recently used: evict the resident block with smallest last-reference timestamp. Every hit refreshes that timestamp.
• LFU, least frequently used: evict the smallest resident frequency, breaking ties by least recent use, then frame index. Frequency counts references since the current insertion, starts at one, and is forgotten on eviction. This is a resident-count LFU variant, not a lifetime-count or aged LFU.
• Clock / Second Chance: maintain a circular hand and one reference bit per resident frame. On replacement, clear and pass set bits; choose the first zero bit, install the new block with bit one, and move the hand to the following frame. Hits set the bit but do not move the hand.

Free fills use the lowest empty frame index in all four implementations. Clock advances the hand after a fill; the other policies leave their unused hand at zero. These conventions make traces deterministic. The textbook Operating Systems: Three Easy Pieces, Chapter 22 provides background on replacement, optimal offline comparison, and Clock's use-bit approximation.

A replacement policy is not an admission rule, expiry rule, associativity rule, or write policy. The supplied positive-capacity cache admits every missed block and has no invalidation, expiration, pinning, or prefetch. Those choices are held fixed so the victim rule is the only policy difference.

How Cache Replacement Works, Step by Step

1. Validate the complete input before simulating. Check cache limits, policy name, backing length/values, trace length, and every address. Validation cannot partially change cache state because each call owns a fresh simulation.
2. Map the word to a block. Compute the tag and offset. Search the resident frames for that tag. The teaching implementation scans a small frame array; its lookup cost is not the constant-time lookup of a production hash-indexed cache.
3. If resident, return a hit. Read the selected word from the cached payload, update common hit metadata, and retain the same frame. No block is fetched. FIFO's born remains unchanged, and Clock's hand stays in place.
4. If absent, count one block read. Copy the corresponding backing block into a temporary payload, padding its tail if needed. Read the requested word from that payload. With zero capacity, return the value without retaining a frame.
5. Prefer a free slot. With positive capacity, choose the lowest empty frame index. Do not evict an occupied frame while a free slot exists. Clock advances its hand to the slot after this fill; no victim-scan inspections are counted for a free fill.
6. Otherwise select one victim. FIFO minimizes born; LRU minimizes last; LFU minimizes (freq,last,frame). Clock repeatedly examines the frame at its hand: if the bit is one, clear it and advance; if zero, select that frame. Count each Clock inspection, including the final zero-bit inspection.
7. Replace and record. Record the old tag as the victim, install the new payload and fresh metadata, and advance Clock's hand after installation. Save physical frame tags, frequencies, reference bits, hand, returned value, and hit/miss status. Aggregate reads, evictions, peak occupancy, and Clock scan inspections separately.

The first policy split in the sample. After block references $0,1,2,0,0$, all policies hold tags $[0,1,2]$. Arrival times are $[1,2,3]$, last-reference times are $[5,2,3]$, and resident frequencies are $[3,1,1]$. Request block three next. FIFO chooses block zero; LRU chooses block one; LFU chooses block one because counts one tie and block one is older by last use. Clock starts at frame zero with all bits one, clears all three, then revisits zero and chooses it. Thus Clock's first victim agrees with FIFO here, but its metadata and later victims differ.

The Clock diagram shows the complete four-inspection selection, including the wraparound. The four inspections are CPU/metadata work, not four block transfers. Only the requested block is fetched in this read-only model.

Why the sweep terminates. In the serial simulator, no hit occurs while a replacement loop is running. If every bit initially equals one, at most $Q$ inspections clear them and the next inspection sees a zero. If a zero already exists, it is reached earlier. A full-cache miss therefore needs at most $Q+1$ inspections with positive capacity.

flowchart TD
    A["Validate inputs; start empty cache"] --> B{"More addresses?"}
    B -->|No| C["Return values, states and counters"]
    B -->|Yes| D["Map address to block and search frames"]
    D --> E{"Block resident?"}
    E -->|Yes| F["Read cached word; update hit metadata"]
    F --> M["Record state and proceed"]
    E -->|No| G["Read one backing block into transfer buffer"]
    G --> H{"Capacity zero?"}
    H -->|Yes| M
    H -->|No| I{"Free frame exists?"}
    I -->|Yes| J["Choose lowest free frame"]
    I -->|No| K["Select FIFO, LRU, LFU or Clock victim; count eviction"]
    J --> L["Install fresh metadata; advance hand only for Clock"]
    K --> L
    L --> M
    M --> B

Worked Example with a Full Trace

Backing words are $[100,101,\ldots,109]$. Use $B=2$ words per block and $Q=3$ frames, so each miss reads sixteen logical bytes and resident capacity is forty-eight bytes. The word-address sequence is $$ [0,2,4,1,0,6,3,1,8,2,5,0], $$ which maps to blocks $$ [0,1,2,0,0,3,1,0,4,1,2,0]. $$ Every policy must return the same words: $$ [100,102,104,101,100,106,103,101,108,102,105,100]. $$ In particular, address one hits a payload originally loaded for address zero. This is block-level spatial reuse, not another reference to the identical word.

Every frame transition and victim. States below are physical frames zero, one, two; they are not FIFO queues or LRU-sorted lists. H means hit; M is a fill without a victim; MvX means a miss evicting block X. A dash denotes an empty frame. The diagram and table follow all twelve references, including the policy divergence after the first five.

LFU and Clock metadata at every step. LFU entries are tag:count in physical frame order. Clock bits also follow physical frame order; empty frames have bit zero. The hand is the next candidate frame. Scan count is the number of inspections for that reference only, and cumulative reads count actual block transfers.

At step six, LRU/LFU discard block one, while FIFO/Clock discard block zero. Step seven requests block one: FIFO/Clock hit, LRU/LFU miss. At step eight, Clock preserves newly referenced block one by clearing its bit and choosing zero-bit block two instead. This demonstrates that matching aggregate counts does not mean matching victim choices.

The decisive LRU/LFU difference arrives at step eleven. Both hold tags $[0,4,1]$. LRU sees last uses at steps eight, nine, ten and evicts block zero. LFU sees counts $[4,1,2]$ and evicts block four. Step twelve requests block zero: LRU misses and LFU hits. LFU has won this trace by preserving repeated use, not by knowing the future.

The totals are:

All twelve values are correct under every policy. FIFO and Clock tie at nine reads but have different victim sequences and final states. Clock's final tags are $[1,0,2]$, bits $[0,1,1]$, and hand two. The source never changes, and there are no pending writes at the end.

Implementation in Python, C++, and Java

Each panel is a complete standalone program running all four policies on the same sample. Run Python directly, compile C++ as C++17, or save the Java panel as Main.java and run Main. The output contains the common addresses/values, each policy's hit string and victim sequence, block-transfer totals, and final Clock state. ARC remains an explanatory overview rather than an unlabelled approximation in the code.

Input contract. Call simulate(memory,addresses,block_words,capacity,policy). The backing sequence contains at most $512$ integer words, each in $[-10^6,10^6]$. The trace contains at most $512$ word addresses, each in $[0,N)$ for backing length $N$. Require $1\le B\le64$ and $0\le Q\le32$. Policy names are exactly FIFO, LRU, LFU, or CLOCK. Both input sequences remain unchanged.

Validation order is cache parameters (PARAMETER), policy (POLICY), excessive backing length (SIZE), invalid backing value (VALUE), excessive trace length (TRACE), then invalid address (ADDRESS). The entire input is checked before any simulated access. Empty memory accepts an empty trace; any reference into empty memory fails as ADDRESS. An empty trace produces zero hits, reads, evictions, scans, and peak occupancy.

Python requires exact integers for numeric parameters, words, and addresses, rejecting booleans/floats as well as strings. A non-string or unsupported policy gives POLICY. C++ uses long long words, int addresses/parameters, and string policy. Java uses long words, int addresses/parameters, and String policy. Non-null flat containers are expected; unrelated objects or null containers are outside the contract. Numeric bounds keep tags, offsets, timestamps, and resident counts safely within the index types.

State contract. Every returned Step records the value, hit flag, requested block tag, victim tag, selected/accessed physical frame, post-access hand, physical tags, resident frequencies, reference bits, and per-access Clock inspections. A victim of $-1$ means no eviction, covering both hits and free fills. A frame of $-1$ means bypass at zero capacity. Empty frames have tag $-1$, count zero, and bit zero. The unused hand of FIFO/LRU/LFU remains zero; their reference bits/frequencies are diagnostic fields and do not change their defined victim rule.

Simple data structures are intentional. Membership and victim selection scan a bounded frame array; every step copies full metadata snapshots. This keeps all policies inspectable and equivalent across languages, but is not a claim of constant-time LRU or LFU implementation. A production implementation can use a hash index and policy-specific linked structures, as the complexity comparison explains.

The read-miss buffer is copied from backing storage before installation. It is temporary host storage outside resident cache capacity, including in bypass mode. Only installed frame payloads contribute to peak resident occupancy. On positive-capacity reload, frequency resets to one; keeping lifetime counts would silently implement a different LFU variant. Clock always sets a newly installed frame's bit to one and advances the hand, including during the initial free fills.

from dataclasses import dataclass


@dataclass
class Frame:
    tag: int
    values: list
    born: int
    last: int
    freq: int = 1
    ref: bool = True


@dataclass
class Step:
    value: int
    hit: bool
    block: int
    victim: int
    frame: int
    hand: int
    tags: list
    freqs: list
    refs: list
    scans: int


@dataclass
class Result:
    steps: list
    hits: int
    reads: int
    evictions: int
    peak_frames: int
    scans: int


def simulate(memory, addresses, block_words, capacity, policy):
    if (type(block_words) is not int or type(capacity) is not int
            or not 1 <= block_words <= 64 or not 0 <= capacity <= 32):
        raise ValueError("PARAMETER")
    if type(policy) is not str or policy not in ("FIFO", "LRU", "LFU", "CLOCK"):
        raise ValueError("POLICY")
    if len(memory) > 512:
        raise ValueError("SIZE")
    if any(type(v) is not int or not -1000000 <= v <= 1000000 for v in memory):
        raise ValueError("VALUE")
    if len(addresses) > 512:
        raise ValueError("TRACE")
    if any(type(a) is not int or not 0 <= a < len(memory) for a in addresses):
        raise ValueError("ADDRESS")
    frames = [None] * capacity
    hand = hits = reads = evictions = peak = total_scans = 0
    steps = []
    for time, address in enumerate(addresses, 1):
        tag, offset = divmod(address, block_words)
        slot = next((i for i, f in enumerate(frames) if f is not None and f.tag == tag), -1)
        hit = slot != -1
        victim, scans = -1, 0
        if hit:
            hits += 1
            f = frames[slot]
            f.last, f.freq, f.ref = time, f.freq + 1, True
            value = f.values[offset]
        else:
            reads += 1
            start = tag * block_words
            payload = memory[start:start + block_words]
            payload += [0] * (block_words - len(payload))
            value = payload[offset]
            if capacity:
                slot = next((i for i, f in enumerate(frames) if f is None), -1)
                if slot == -1:
                    evictions += 1
                    if policy == "CLOCK":
                        while True:
                            scans += 1
                            if not frames[hand].ref:
                                break
                            frames[hand].ref = False
                            hand = (hand + 1) % capacity
                        slot = hand
                    elif policy == "FIFO":
                        slot = min(range(capacity), key=lambda i: frames[i].born)
                    elif policy == "LRU":
                        slot = min(range(capacity), key=lambda i: frames[i].last)
                    else:
                        slot = min(range(capacity), key=lambda i: (frames[i].freq, frames[i].last, i))
                    victim = frames[slot].tag
                frames[slot] = Frame(tag, payload, time, time)
                if policy == "CLOCK":
                    hand = (slot + 1) % capacity
                peak = max(peak, sum(f is not None for f in frames))
        total_scans += scans
        steps.append(Step(value, hit, tag, victim, slot, hand,
                          [f.tag if f else -1 for f in frames],
                          [f.freq if f else 0 for f in frames],
                          [int(f.ref) if f else 0 for f in frames], scans))
    return Result(steps, hits, reads, evictions, peak, total_scans)


def compact(values):
    return '[' + ','.join(map(str, values)) + ']'


def main():
    memory = list(range(100, 110))
    addresses = [0, 2, 4, 1, 0, 6, 3, 1, 8, 2, 5, 0]
    print("words=10 block_words=2 frames=3 line_bytes=16 cache_bytes=48")
    print("addresses=" + compact(addresses))
    print("blocks=" + compact([a // 2 for a in addresses]))
    print("values=" + compact([memory[a] for a in addresses]))
    for policy in ("FIFO", "LRU", "LFU", "CLOCK"):
        r = simulate(memory, addresses, 2, 3, policy)
        assert [s.value for s in r.steps] == [memory[a] for a in addresses]
        events = ''.join('H' if s.hit else 'M' for s in r.steps)
        print(f"{policy} hits={r.hits} reads={r.reads} transfers={r.reads} "
              f"evictions={r.evictions} scans={r.scans} peak_frames={r.peak_frames} "
              f"events={events} victims={compact([s.victim for s in r.steps])}")
        if policy == "CLOCK":
            last = r.steps[-1]
            print(f"CLOCK final_tags={compact(last.tags)} final_refs={compact(last.refs)} hand={last.hand}")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cassert>
#include <iostream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using Word = long long;
struct Frame {
    int tag=-1;
    vector<Word> values;
    int born=0,last=0,freq=0;
    bool ref=false;
};
struct Step {
    Word value;
    bool hit;
    int block,victim,frame,hand;
    vector<int> tags,freqs,refs;
    int scans;
};
struct Result {
    vector<Step> steps;
    int hits=0,reads=0,evictions=0,peak_frames=0,scans=0;
};
Result simulate(const vector<Word>& memory,const vector<int>& addresses,
                int block_words,int capacity,const string& policy) {
    if(block_words<1 || block_words>64 || capacity<0 || capacity>32)
        throw invalid_argument("PARAMETER");
    if(policy!="FIFO" && policy!="LRU" && policy!="LFU" && policy!="CLOCK")
        throw invalid_argument("POLICY");
    if(memory.size()>512)throw invalid_argument("SIZE");
    for(Word v:memory)if(v < -1000000 || v > 1000000)throw invalid_argument("VALUE");
    if(addresses.size()>512)throw invalid_argument("TRACE");
    for(int a:addresses)if(a<0 || a>=static_cast<int>(memory.size()))throw invalid_argument("ADDRESS");
    vector<Frame> frames(capacity);
    Result result;
    int hand=0,time=0,used=0;
    for(int address:addresses) {
        ++time;
        int tag=address/block_words,offset=address%block_words,slot=-1;
        for(int i=0;i<capacity;++i)if(frames[i].tag==tag) { slot=i;break; }
        bool hit=slot!=-1;
        int victim=-1,scans=0;
        Word value;
        if(hit) {
            ++result.hits;
            Frame& f=frames[slot];f.last=time;++f.freq;f.ref=true;value=f.values[offset];
        } else {
            ++result.reads;
            int start=tag*block_words;
            vector<Word> payload(block_words,0);
            copy(memory.begin()+start,memory.begin()+min(start+block_words,static_cast<int>(memory.size())),payload.begin());
            value=payload[offset];
            if(capacity) {
                for(int i=0;i<capacity;++i)if(frames[i].tag==-1) { slot=i;break; }
                if(slot==-1) {
                    ++result.evictions;
                    if(policy=="CLOCK") {
                        while(true) {
                            ++scans;
                            if(!frames[hand].ref)break;
                            frames[hand].ref=false;hand=(hand+1)%capacity;
                        }
                        slot=hand;
                    } else {
                        slot=0;
                        for(int i=1;i<capacity;++i) {
                            bool better;
                            if(policy=="FIFO")better=frames[i].born<frames[slot].born;
                            else if(policy=="LRU")better=frames[i].last<frames[slot].last;
                            else better=tie(frames[i].freq,frames[i].last,i)<tie(frames[slot].freq,frames[slot].last,slot);
                            if(better)slot=i;
                        }
                    }
                    victim=frames[slot].tag;
                } else ++used;
                frames[slot]=Frame{tag,move(payload),time,time,1,true};
                if(policy=="CLOCK")hand=(slot+1)%capacity;
                result.peak_frames=max(result.peak_frames,used);
            }
        }
        vector<int> tags,freqs,refs;
        for(const Frame& f:frames) {
            tags.push_back(f.tag);freqs.push_back(f.freq);refs.push_back(f.ref?1:0);
        }
        result.scans+=scans;
        result.steps.push_back(Step{value,hit,tag,victim,slot,hand,move(tags),move(freqs),move(refs),scans});
    }
    return result;
}
template<class T>string compact(const vector<T>& values) {
    string s="[";
    for(size_t i=0;i<values.size();++i) { if(i)s+=',';s+=to_string(values[i]); }
    return s+"]";
}
int main() {
    vector<Word> memory;for(int i=100;i<110;++i)memory.push_back(i);
    vector<int> addresses{0,2,4,1,0,6,3,1,8,2,5,0},blocks;
    vector<Word> values;
    for(int a:addresses) { blocks.push_back(a/2);values.push_back(memory[a]); }
    cout<<"words=10 block_words=2 frames=3 line_bytes=16 cache_bytes=48\n"
        <<"addresses="<<compact(addresses)<<"\nblocks="<<compact(blocks)<<"\nvalues="<<compact(values)<<'\n';
    for(const string& policy:vector<string>{"FIFO","LRU","LFU","CLOCK"}) {
        Result r=simulate(memory,addresses,2,3,policy);
        string events;vector<int> victims;
        for(size_t i=0;i<r.steps.size();++i) {
            assert(r.steps[i].value==values[i]);events+=r.steps[i].hit?'H':'M';victims.push_back(r.steps[i].victim);
        }
        cout<<policy<<" hits="<<r.hits<<" reads="<<r.reads<<" transfers="<<r.reads
            <<" evictions="<<r.evictions<<" scans="<<r.scans<<" peak_frames="<<r.peak_frames
            <<" events="<<events<<" victims="<<compact(victims)<<'\n';
        if(policy=="CLOCK") {
            const Step& s=r.steps.back();
            cout<<"CLOCK final_tags="<<compact(s.tags)<<" final_refs="<<compact(s.refs)<<" hand="<<s.hand<<'\n';
        }
    }
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static final class Frame {
        final int tag,born;
        final long[] values;
        int last,freq=1;
        boolean ref=true;
        Frame(int tag,long[] values,int time) { this.tag=tag;this.values=values;born=time;last=time; }
    }
    static final class Step {
        final long value;
        final boolean hit;
        final int block,victim,frame,hand,scans;
        final int[] tags,freqs,refs;
        Step(long v,boolean h,int b,int victim,int frame,int hand,Frame[] frames,int scans) {
            value=v;hit=h;block=b;this.victim=victim;this.frame=frame;this.hand=hand;this.scans=scans;
            tags=new int[frames.length];freqs=new int[frames.length];refs=new int[frames.length];
            for(int i=0;i<frames.length;++i) {
                Frame f=frames[i];tags[i]=f==null?-1:f.tag;freqs[i]=f==null?0:f.freq;refs[i]=f!=null && f.ref?1:0;
            }
        }
    }
    static final class Result {
        final List<Step> steps=new ArrayList<>();
        int hits,reads,evictions,peakFrames,scans;
    }
    static Result simulate(long[] memory,int[] addresses,int blockWords,int capacity,String policy) {
        if(blockWords<1 || blockWords>64 || capacity<0 || capacity>32)throw new IllegalArgumentException("PARAMETER");
        if(!"FIFO".equals(policy) && !"LRU".equals(policy) && !"LFU".equals(policy) && !"CLOCK".equals(policy))
            throw new IllegalArgumentException("POLICY");
        if(memory.length>512)throw new IllegalArgumentException("SIZE");
        for(long v:memory)if(v < -1000000 || v > 1000000)throw new IllegalArgumentException("VALUE");
        if(addresses.length>512)throw new IllegalArgumentException("TRACE");
        for(int a:addresses)if(a<0 || a>=memory.length)throw new IllegalArgumentException("ADDRESS");
        Frame[] frames=new Frame[capacity];Result result=new Result();int hand=0,time=0,used=0;
        for(int address:addresses) {
            ++time;
            int tag=address/blockWords,offset=address%blockWords,slot=-1;
            for(int i=0;i<capacity;++i)if(frames[i]!=null && frames[i].tag==tag) { slot=i;break; }
            boolean hit=slot!=-1;int victim=-1,scans=0;long value;
            if(hit) {
                ++result.hits;Frame f=frames[slot];f.last=time;++f.freq;f.ref=true;value=f.values[offset];
            } else {
                ++result.reads;int start=tag*blockWords;
                long[] payload=Arrays.copyOfRange(memory,start,start+blockWords);value=payload[offset];
                if(capacity!=0) {
                    for(int i=0;i<capacity;++i)if(frames[i]==null) { slot=i;break; }
                    if(slot==-1) {
                        ++result.evictions;
                        if(policy.equals("CLOCK")) {
                            while(true) {
                                ++scans;if(!frames[hand].ref)break;
                                frames[hand].ref=false;hand=(hand+1)%capacity;
                            }
                            slot=hand;
                        } else {
                            slot=0;
                            for(int i=1;i<capacity;++i) {
                                Frame a=frames[i],b=frames[slot];boolean better;
                                if(policy.equals("FIFO"))better=a.born<b.born;
                                else if(policy.equals("LRU"))better=a.last<b.last;
                                else better=a.freq<b.freq || (a.freq==b.freq && (a.last<b.last || (a.last==b.last && i<slot)));
                                if(better)slot=i;
                            }
                        }
                        victim=frames[slot].tag;
                    } else ++used;
                    frames[slot]=new Frame(tag,payload,time);
                    if(policy.equals("CLOCK"))hand=(slot+1)%capacity;
                    result.peakFrames=Math.max(result.peakFrames,used);
                }
            }
            result.scans+=scans;result.steps.add(new Step(value,hit,tag,victim,slot,hand,frames,scans));
        }
        return result;
    }
    static String compact(int[] a) { return Arrays.toString(a).replace(" ",""); }
    static String compact(long[] a) { return Arrays.toString(a).replace(" ",""); }
    public static void main(String[] args) {
        long[] memory=new long[10];for(int i=0;i<10;++i)memory[i]=100+i;
        int[] addresses={0,2,4,1,0,6,3,1,8,2,5,0},blocks=new int[addresses.length];long[] values=new long[addresses.length];
        for(int i=0;i<addresses.length;++i) { blocks[i]=addresses[i]/2;values[i]=memory[addresses[i]]; }
        System.out.println("words=10 block_words=2 frames=3 line_bytes=16 cache_bytes=48");
        System.out.println("addresses="+compact(addresses));System.out.println("blocks="+compact(blocks));System.out.println("values="+compact(values));
        for(String policy:new String[]{"FIFO","LRU","LFU","CLOCK"}) {
            Result r=simulate(memory,addresses,2,3,policy);StringBuilder events=new StringBuilder();int[] victims=new int[r.steps.size()];
            for(int i=0;i<r.steps.size();++i) {
                Step s=r.steps.get(i);if(s.value!=values[i])throw new AssertionError("value");events.append(s.hit?'H':'M');victims[i]=s.victim;
            }
            System.out.println(policy+" hits="+r.hits+" reads="+r.reads+" transfers="+r.reads
                +" evictions="+r.evictions+" scans="+r.scans+" peak_frames="+r.peakFrames+" events="+events+" victims="+compact(victims));
            if(policy.equals("CLOCK")) {
                Step s=r.steps.get(r.steps.size()-1);
                System.out.println("CLOCK final_tags="+compact(s.tags)+" final_refs="+compact(s.refs)+" hand="+s.hand);
            }
        }
    }
}

Expected standard output, identical in all three languages:

• words=10 block_words=2 frames=3 line_bytes=16 cache_bytes=48
• addresses=[0,2,4,1,0,6,3,1,8,2,5,0]
• blocks=[0,1,2,0,0,3,1,0,4,1,2,0]
• values=[100,102,104,101,100,106,103,101,108,102,105,100]
• FIFO hits=3 reads=9 transfers=9 evictions=6 scans=0 peak_frames=3 events=MMMHHMHMMMMM victims=[-1,-1,-1,-1,-1,0,-1,1,2,3,0,4]
• LRU hits=4 reads=8 transfers=8 evictions=5 scans=0 peak_frames=3 events=MMMHHMMHMHMM victims=[-1,-1,-1,-1,-1,1,2,-1,3,-1,0,4]
• LFU hits=5 reads=7 transfers=7 evictions=4 scans=0 peak_frames=3 events=MMMHHMMHMHMH victims=[-1,-1,-1,-1,-1,1,2,-1,3,-1,4,-1]
• CLOCK hits=3 reads=9 transfers=9 evictions=6 scans=14 peak_frames=3 events=MMMHHMHMMMMM victims=[-1,-1,-1,-1,-1,0,-1,2,1,3,0,4]
• CLOCK final_tags=[1,0,2] final_refs=[0,1,1] hand=2

Complexity, Correctness, and Invariants

Traffic and occupancy. Let $T$ be the number of valid word references, $R$ block reads, $H$ hits, $E$ clean evictions, and $D$ distinct referenced blocks. Every reference is exactly one hit or miss: $$ H+R=T,\qquad 0\le R\le T. $$ For positive capacity in this cold, admit-every-miss, no-invalidation model, the final occupancy and eviction identity are $$ \text{resident blocks}=\min(Q,D),\qquad E=R-\min(Q,D). $$ The first $\min(Q,D)$ fills use free frames; later misses replace one resident. Thus a miss count is not an eviction count. Compulsory first references imply $R\ge D$. If $Q\ge D$, each referenced block remains resident after its first read, so all four policies have $R=D$. For $Q=0$, $R=T$, $H=E=0$, and occupancy is zero.

Transferred bytes are $8BR$. Partial final blocks still count as full transfers. For a nonempty trace, hit ratio is $H/T$ and miss ratio $R/T$; the empty-trace ratios are undefined rather than a division by zero. There is no useful policy ranking from hit ratio without specifying the workload, capacity, block size, and cold/warm boundary.

Best, average, and worst locality. A nonempty trace repeating one block needs one read when $Q\ge1$, regardless of reference count. A trace with no block reuse needs $T$ reads under every policy. Other traces can repeatedly evict useful blocks. No probability distribution is assumed, so there is no universal average-case miss ratio. Policy selection changes traffic while every correct implementation returns the same backing values.

Clock scan accounting. A full miss examines at most $Q+1$ frames. Across the whole serial trace, each scan either clears a one bit or chooses a zero-bit victim. Every cleared one must previously have been set by a reference or insertion, and at most one new one-bit credit is created per reference. There are at most $T$ clear operations and at most $T$ final victim inspections. Consequently $$ S_{\mathrm{Clock}}\le2T, $$ where $S_{\mathrm{Clock}}$ counts replacement-loop inspections only. Thus Clock's victim scanning has amortized $O(1)$ work per reference even though an individual full miss can take $\Theta(Q)$. Lookup, payload copying, and trace recording are separate costs. Hits and free fills contribute zero to the reported scan counter.

Actual laboratory runtime. For every recorded step, creating its tag/count/bit snapshots scans all $Q$ frames. Membership and linear minimum selection cost up to $O(Q)$, and copying a missed payload costs $\Theta(B)$. Input validation scans backing storage and addresses. With backing length $N$, aggregate work is $$ O\bigl(N+Q+T(Q+1)+BR\bigr). $$ For positive $Q$, the recorded hit path alone costs $\Theta(Q)$ because of snapshots; a miss costs $O(Q+B)$. These are best/worst CPU bounds for this instrumented design, not the metadata bounds of an optimized replacement data structure.

Resident payload uses at most $QB$ words plus $O(Q)$ frame metadata. A read miss temporarily uses another $B$-word transfer buffer; backing input occupies $N$ words. Saved snapshots use $O(T(Q+1))$ words including scalar event fields. Total host storage is therefore $O(N+(Q+1)B+Q+T(Q+1))$ under word accounting. Removing diagnostic history leaves cache/working storage $O(QB+Q+B)$ beyond backing memory. Actual language object overhead is excluded from logical byte counts.

Policy invariants. At all times, occupied tags are unique, their number is at most $Q$, and each payload equals the corresponding immutable backing block. A hit selects the unique matching tag. A miss fetches the correct block and either uses a free frame, replaces exactly one resident, or bypasses. Therefore the returned payload slot always equals memory[address].

FIFO's born remains the time of the current insertion, so minimizing it chooses the earliest resident arrival. LRU's last is refreshed on every reference, so its minimum chooses the least recent resident. LFU's freq equals the number of references during the current residence; lexicographic count/last/frame minimization implements the stated ties. Clock's hand remains a valid frame index for positive capacity; only a zero-bit frame is selected after finite clearing, and installation/hits restore the appropriate bit.

These invariants prove policy fidelity and value correctness, not optimal prediction. A policy can satisfy its rules perfectly and still make a poor choice for the next unseen request. Offline OPT/MIN evicts the block whose next reference is farthest in the known future and supplies a miss-count lower bound for the same cold trace/model; it is a comparison benchmark, not one of the implemented online policies.

Variants, Pitfalls, and Optimizations

Refresh the right metadata on hits. A hit is not a state-free event. LRU refreshes last use, LFU increments its resident count, and Clock sets its bit. FIFO preserves arrival time. The diagram shows a common bug: failing to refresh LRU recency makes the next victim follow FIFO-style arrival instead. Correct returned values alone cannot expose it.

Define LFU completely. Count lifetime, resident lifetime, a sliding window, or a decayed estimate: these are different policies. This code starts at one and forgets counts on eviction. Equal counts use LRU ties; choosing arbitrary dictionary iteration order makes examples unstable. Without aging, formerly hot blocks may keep large counts after a workload phase changes. Periodic decay or approximate counters can help, but introduce a different policy and additional implementation choices.

Clock is approximate recency. A bit records use since the last clearing opportunity, not an exact timestamp or complete access order. Multiple hits while a bit is already one do not give extra second chances. The hand moves on fills/replacements and clearing scans in this version, never on a hit. Setting new entries to zero or resetting the hand to frame zero on every miss changes the behavior.

More capacity is not a universal monotonicity rule. Test FIFO on block sequence $[1,2,3,4,1,2,5,1,2,3,4,5]$ starting cold: three frames incur nine misses, while four incur ten. This is Bélády's anomaly. Exact LRU is a stack policy: for the same trace, the smaller cache's resident set is contained in the larger cache's, so increasing capacity cannot increase LRU misses under the standard assumptions. Do not infer the same property for every replacement rule.

ARC overview. Megiddo and Modha's original ARC paper uses four disjoint LRU lists: $T_1$ holds recent resident entries, $T_2$ reused resident entries, and $B_1,B_2$ remember identifiers evicted from those sides. Ghost lists hold no payload: a ghost return is still a cache miss. Resident hits move to $T_2$'s MRU end. A new identifier enters $T_1$; a ghost return is fetched into $T_2$. A target $p\in[0,Q]$ guides which resident list supplies a victim. A $B_1$ return raises $p$, favoring recency; a $B_2$ return lowers it, favoring reuse. The original rule scales changes by relative ghost-list sizes. Resident payload stays within $Q$ entries and the complete directory within $2Q$ identifiers. This learns from eviction mistakes without LFU counters. Exact replacement/trimming cases matter; the paper's Figure 4 supplies the full algorithm. This is an overview, not an implementation or a claim that ARC wins every trace.

Changing payload or eligibility changes the problem. With stores, distinguish write-through, write-back, and write-allocate behavior. A dirty victim must be preserved before reuse, and final dirty residents may require flush; then total transfers include writes as well as reads. Pinned pages, in-flight requests, and mandatory retained entries restrict victim eligibility. A full cache with no eligible victim needs an explicit response rather than an unbounded Clock scan.

Block size and capacity must be compared fairly. Increasing $B$ at fixed frame count increases resident bytes as well as transfer size. Increasing $B$ at fixed byte capacity decreases frame count. Report the chosen comparison and count bytes as well as misses. This fully associative model has no set-conflict misses; real hardware restricts candidate ways and can use approximate policies for speed.

Admission, expiry, and replacement are separate. A one-time scan can pollute a cache that admits every missed block. Bypass/admission filters or segmented queues can reduce that damage. TTL expiry removes stale entries for a different reason than replacement; key/version coherence determines whether cached data is still valid. None of those semantics is simulated by changing the LRU victim alone.

Average latency is more than miss ratio. Under a simple serial two-level approximation, average access cost is hit cost plus miss probability times additional miss penalty. Real systems also pay metadata, synchronization, bandwidth, writeback, and queuing costs. A lower miss count can still accompany higher elapsed time if per-hit work or contention increases. The supplied frame-array simulator is for examining policy state, not benchmarking production cache throughput.

Use consistent experimental boundaries. A fresh run is cold; splitting a trace into separately simulated calls resets all state and resident LFU counts. Comparing a warm run with a cold one is not a policy comparison. Record the trace, block mapping, payload width, capacity, tie rules, admission/write model, and reset boundary so the result can be reproduced.

Practice Problems and Real-World Use

Use a direct backing lookup as the value oracle, but verify replacement independently too. A FIFO queue and an LRU recency list provide different representations from the implementation's timestamps. For LFU, maintain resident counts and choose the first minimum-count item in an independent recency list. For Clock, rotate a second-chance queue, clearing set bits until its front is eligible, rather than repeating the implementation's array-hand loop.

Check the full state after every reference: occupied tags unique, capacity respected, value unchanged, exact hit/miss and victim, LFU resident frequencies, Clock bits/hand, free-fill behavior, and read/eviction totals. Include repeated offsets within a block, partial final blocks, an empty trace, empty backing storage, zero capacity, one frame, and enough frames to retain every distinct referenced block.

All three implementations passed $8955$ shared test inputs per language: $8920$ valid workloads containing $142036$ references and $35$ rejected inputs. Tests include exhaustive block strings of lengths zero through five over three tags, all four policies and capacities zero through four, randomized traces, partial blocks, maximum backing/trace lengths, and parameter/value/address failures. Independent queue, recency-list, resident-count, and rotating-second-chance models match every returned value, hit, victim, physical frame, hand, frequency, reference bit, scan count, and aggregate counter. Additional checks cover $19$ Python exact-type rejections, $100$ payload-independence comparisons, the nine-versus-ten FIFO anomaly, and $75$ LRU capacity-monotonicity traces. C++ ran with address and undefined-behavior sanitizers. All standalone samples print byte-identical output.

For practice, design competing workloads rather than only increasing random-test volume. Combine a small hot set with a long scan, switch from one hot set to another, repeat a cycle just larger than capacity, and interleave rare expensive objects with common cheap ones. Equal block sizes and read costs are assumptions of this laboratory; object-size or fetch-cost weighting requires a different objective.

In application caches, cache-library APIs often expose eviction plus expiration/admission behavior. In database or operating-system settings, concurrency, dirty data, and eligibility add constraints to the same victim-selection question. Use the clear state-machine laboratory to understand those additions, then measure the actual system rather than extrapolating its runtime from this simulator.