Cache replacement and write policies
Cache replacement policies (LRU, FIFO, Random, LFU) decide which cache block to evict; write policies (write-through/write-back and write-allocate/no-write-allocate) decide when and where writes go — both affect performance measured by hit time, miss rate and miss penalty, and together determine ave
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Two or three sentences: where an engineer uses this.
Caches are used to reduce average memory access time between CPU and main memory. An engineer chooses a cache replacement policy and a write policy to trade off speed, complexity and memory traffic. Correct choices reduce program execution time and memory bandwidth use in embedded, desktop and server systems.
Key ideas
Explain from first principles, define terms, exact statements and derivations.
Cache: a small fast storage placed between CPU and main memory to hold copies of memory blocks likely to be used soon. Define a block (or line) as the unit transferred between cache and memory (common sizes: 16, 32, 64 bytes).
Hit: when the data the CPU requests is found in the cache. Miss: when it is not found and must be fetched from lower-level memory.
Hit time: time to access data from cache (includes tag check and possibly update). Measured in seconds (typically nanoseconds). Denote as Hit time.
Miss penalty: extra time required to fetch the missing block from lower level (memory or next cache), including transfer and fill. Denote as Miss penalty.
Miss rate: fraction of memory accesses that are misses. Miss rate + Hit rate = 1 where Hit rate is fraction of hits.
Types of cache misses (3C model): Compulsory (first reference to a block), Capacity (working set exceeds cache size even with optimal replacement), Conflict (mapping collisions in set-associative/direct-mapped caches).
Average Memory Access Time (AMAT). Exact statement used in exams: assuming that each miss adds its full miss penalty sequentially (no overlap), AMAT = Hit time + Miss rate × Miss penalty. Assumptions: single-level cache model for this formula; no overlap of miss service with next instruction unless explicitly modelled (e.g., with non-blocking caches). The formula is the base from which modifications for multi-level caches and write policies are derived.
Replacement policy: when a miss requires loading a block into a full set, the cache must evict one existing block. In a direct-mapped cache (1-way set associative), the single line of the set is always replaced (no policy choice). Policies (define each):
- LRU (Least Recently Used): evict the line that was used least recently. Exact behaviour: maintain usage order; on hit update its recency to most-recent.
- FIFO (First-In First-Out): evict the line that was brought into the set earliest; hits do not change order.
- Random: evict a randomly chosen line. Implementation is simple; average performance often close to LRU.
- LFU (Least Frequently Used): evict the line with smallest access count; must manage counters.
Theorem-style remark (exam style): LRU is a simple heuristic that approximates the optimal replacement (Belady's) under the assumption of temporal locality. No simple online algorithm always matches the offline optimal (Belady) which knows future accesses.
Belady's anomaly: For some access sequences and FIFO replacement, increasing cache size can increase miss rate. Statement: Belady's anomaly can occur for non-stack algorithms like FIFO; it cannot occur for stack algorithms (LRU is a stack algorithm). Explain: draw access sequence and two cache sizes to show misses increase. (For an exam draw the sequence and table of cache contents per access.)
Write policies (definitions):
- Write-through: every write to a cache line is also written immediately to lower-level memory. Simplicity: coherence easy; cost: higher memory traffic.
- Write-back (also called copy-back): writes update only cache; the block is marked dirty and written to memory only when evicted. Pros: lower memory traffic; cons: complexity and need to write dirty block on eviction.
- Write-allocate (also called fetch-on-write): on a write miss fetch the block into cache and then perform the write (commonly used with write-back caches).
- No-write-allocate (also called write-no-allocate): on a write miss do not bring the block into cache; write directly to memory (commonly used with write-through caches).
Explain interactions: Common pairs are write-back + write-allocate, and write-through + no-write-allocate, but combinations are allowed.
Exact handling on eviction: For write-back caches, evicting a line marked dirty requires a write-back to main memory, costing write-back penalty (equal to transferring a block to memory). This extra cost must be added to miss penalties when calculating AMAT if eviction can occur during a miss. In write-through caches, evictions are always clean (no write-back on eviction).
Diagram instruction (what to draw for exams): draw one cache set as a vertical box containing N lines (for N-way set associative). For each line draw fields: Valid bit, Dirty bit (if write-back), Tag bits, Data block. For LRU show a small counter or list of positions labelled MRU -> LRU.
Formulas
Each formula on its own line and explanation.
AMAT = Hit time + Miss rate × Miss penalty
- Hit time: time to service a cache hit (s). Miss rate: fraction (unitless). Miss penalty: extra time to service a miss (s). Applies to read-dominated models or when miss service is serialized.
Miss rate = Number of misses / Number of memory accesses
- Unitless fraction. Applies to measured or computed traces.
Hit rate = 1 - Miss rate
- Unitless.
Effective miss penalty (write-back) = Miss penalty + Probability(evicted block is dirty) × Write-back penalty
- All times in seconds. Use when block evictions can cause writes to memory.
AMAT (with write mix) = Hit time + Miss rate × Miss penalty + Write fraction × Extra write cost
- Write fraction = fraction of accesses that are writes; Extra write cost depends on write-through/no-write-allocate and whether a write buffer avoids stall. This is a modelling formula; specify exact extra write cost per policy in your answer. Common models: for write-through + no-write-allocate, write hits are posted to a write buffer (no stall unless the buffer is full), and write misses generate only a memory write (no block fetch). For write-back + write-allocate, write hits cost a cache hit, write misses fetch the block (read miss penalty) then update it, and evicting a dirty line adds a write-back. If a write buffer is used, Extra write cost is approximately P(buffer full) × buffer drain time.
Note: For multi-level caches, replace Miss penalty with AMAT of next level.
Worked examples
Two university-exam standard examples with steps and units.
Example 1 — AMAT calculation (read-dominated simple case) Given: Hit time = 1.0 ns, Miss rate = 8% (0.08), Miss penalty = 50.0 ns. Compute AMAT.
- Formula: AMAT = Hit time + Miss rate × Miss penalty.
- Substitute: AMAT = 1.0 ns + 0.08 × 50.0 ns.
- Compute: 0.08 × 50.0 ns = 4.0 ns.
- AMAT = 1.0 ns + 4.0 ns = 5.0 ns. Final answer: AMAT = 5.0 ns.
Example 2 — Replacement policy trace, 2-way set-associative cache Cache: 4 total lines, 2 sets (set 0 and set 1), 2 lines per set (2-way). Access sequence (by block number): 0, 1, 2, 3, 0, 1, 4, 0. Map function: set = block % 2. Start cache empty. Trace LRU (step-by-step):
- Access 0 (set0): miss — bring 0. Misses = 1.
- Access 1 (set1): miss — bring 1. Misses = 2.
- Access 2 (set0): miss — bring 2. Now set0 has [0 (LRU), 2 (MRU)]. Misses = 3.
- Access 3 (set1): miss — bring 3. Now set1 [1 (LRU), 3 (MRU)]. Misses = 4.
- Access 0 (set0): hit (present) — update recency: set0 becomes [2 (LRU), 0 (MRU)]. Misses = 4.
- Access 1 (set1): hit — update recency: set1 becomes [3 (LRU), 1 (MRU)]. Misses = 4.
- Access 4 (set0): miss — evict LRU of set0 (which is 2), bring 4. Misses = 5.
- Access 0 (set0): hit. Misses = 5. Result LRU: 5 misses.
Trace FIFO (step-by-step):
- Accesses 0,1,2,3: first four are misses, set0 gets [0,2], set1 gets [1,3]. Misses = 4.
- Access 0: hit (FIFO does not change order). Misses = 4.
- Access 1: hit. Misses = 4.
- Access 4 (set0): FIFO evicts oldest in set0 (0), so miss and bring 4. set0 becomes [2,4]. Misses = 5.
- Access 0 (set0): 0 is not present => miss. Evict 2 -> set0 [4,0]. Misses = 6. Result FIFO: 6 misses.
Conclusion: For this sequence LRU wins (5 vs 6 misses). This example also shows why FIFO can behave worse. Belady's anomaly refers to other sequences where FIFO can get more misses when cache size increases.
Common mistakes
- Applying AMAT formula without stating assumptions (e.g., whether miss service can overlap with CPU or whether a write buffer absorbs writes).
- Treating LRU as optimal for all sequences — it is a good heuristic but not always optimal; Belady's algorithm (optimal offline) needs future knowledge.
- For set-associative caches, students sometimes treat the whole cache as direct-mapped when doing replacement traces — remember replacement only happens within the accessed set.
For your exam
Kinds of questions and what full-marks answers include:
- Definitions: define cache, block, hit/miss, hit time, miss penalty, replacement policies, write policies. Give short pros/cons.
- Short notes: compare write-through vs write-back including when to use write-allocate / no-write-allocate.
- Derivations: derive AMAT = Hit time + Miss rate × Miss penalty and state assumptions. If multi-level cache, show iterative substitution AMAT_L1 = Hit1 + Miss1 × (Hit2 + Miss2 × MissPenalty2) (where Hit1/Hit2 are hit times and Miss1/Miss2 are miss rates).
- Numericals: compute AMAT given hit time, miss rate, miss penalty; trace replacement policies on given access sequences; include dirty-write-back costs when needed. Show stepwise trace with cache sets, which block evicted and counters updated.
- Diagrams: draw a cache set with Valid/Dirty/Tag/Data fields and show LRU state (e.g., use numbers 0..N-1 for recency). Label everything clearly.
A full-marks answer: writes definitions, states assumptions, shows formulas, does step-by-step arithmetic with units, and provides clear tracing tables for replacement problems.
Quick check
Three short questions:
- What is the main difference between write-through and write-back?
- Write the AMAT formula.
- For a 2-way set-associative cache, where does replacement occur: across whole cache or inside a set?
Answers: write-through updates memory on every write while write-back delays memory write until eviction; AMAT = Hit time + Miss rate × Miss penalty; replacement occurs inside the addressed set only.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?