Worked examples — Cache miss types (compulsory, capacity, conflict)

This page is the drill floor for the 3 C's. The parent note built the definitions; here we hunt down every kind of situation a miss-classification problem can throw at you and solve each one fully.

Before touching a single example, we agree on the one machine we run in our head, because classifying a miss means simulating idealized caches.

Two idealized caches above evict blocks, and which block they evict changes the counts. So before any example we must pin down the eviction rule they use.

A quick reminder of the one arithmetic rule that makes conflicts happen, since every direct-mapped example below uses it. First we name the two quantities it needs, and the two arithmetic operators they lean on.

---

The scenario matrix

Every miss-classification problem you will ever meet is one (or a blend) of these cells. Each later example is tagged with the cell it covers.

Cell	What makes it special	Covered by
A. Pure compulsory	Every access is a brand-new block; cache size irrelevant	Ex 1
B. Pure conflict	Only 2–3 blocks used, but mapping forces a fight	Ex 2
C. Pure capacity	Working set > cache, no mapping to blame (fully-assoc)	Ex 3
D. The trap: "looks conflict, is capacity"	Non-cold miss that a fully-assoc would also miss	Ex 4
E. Associativity turns conflict → hit	Same trace, raise ways, watch conflicts vanish	Ex 5
F. Degenerate input	Empty trace / single block / all-hits after warm-up	Ex 6
G. Block-size / spatial-locality effect	Bigger block changes compulsory and capacity counts	Ex 7
H. Real-world word problem	Row-major vs column-major array walk (2D loop)	Ex 8
I. Exam twist: full 3-way decomposition	One trace, report all three C's by subtraction	Ex 9

---

Example 1 — Cell A: pure compulsory

Steps.

1. Compute each index $=B\mathrm{mod}4$: $0\to 0,1\to 1,2\to 2,3\to 3$. Why this step? We need to know if any two blocks share a home. All four indices differ ⇒ nobody collides.
2. Walk the trace. Each block is touched for the first time, so each is a miss with an empty home slot. Why this step? A first-ever reference is compulsory by definition — no cache, however clever, holds data it has never seen.

Access	Index	Home before	Result
0	0	empty	Compulsory
1	1	empty	Compulsory
2	2	empty	Compulsory
3	3	empty	Compulsory

Answer: 4 compulsory, 0 capacity, 0 conflict.

---

Example 2 — Cell B: pure conflict

Steps.

1. Indices: $0\mathrm{mod}4=0$ and $8\mathrm{mod}4=0$. Both blocks want set 0. Why this step? This is the mechanical origin of conflict — same remainder ⇒ same single home.
2. Simulate the real cache — since set 0 holds only one line, each newcomer evicts the other.

Access	Result	Reason
0	Compulsory	first touch
8	Compulsory	first touch, evicts 0
0	Conflict	seen before ⇒ not cold
8	Conflict	thrash
0	Conflict	thrash
8	Conflict	thrash

3. Prove it's conflict (not capacity): run a fully-associative 4-line cache on the same trace. It holds $\{0,8\}$ comfortably (2 blocks $\le$ 4 slots), so every repeat is a hit — 0 non-compulsory misses. Why this step? Conflict $=M_{\text{real}}-M_{\text{full}}$. Here $M_{\text{real}}=6$, $M_{\text{full}}=2$, so conflict $=4$. ✅

Answer: 2 compulsory, 0 capacity, 4 conflict.

---

Example 3 — Cell C: pure capacity

Steps.

1. Track the cache as an LRU list [LRU … MRU] (rule defined at the top of the page). Why this step? With no index restriction, the only reason to evict is "out of room", and LRU decides who leaves — the leftmost (least-recently-used) block.

Access	Cache after	Result	Reason
0	[0]	Compulsory	first touch
1	[0,1]	Compulsory	first touch
2	[1,2]	Compulsory	first touch, evicts 0 (LRU)
0	[2,0]	Capacity	0 seen before, but only 2 slots for 3-block working set
1	[0,1]	Capacity	evicts 2
2	[1,2]	Capacity	evicts 0

2. Why not conflict? A fully-associative cache has no mapping, so $M_{\text{real}}=M_{\text{full}}$ always ⇒ conflict $=0$ by definition. Why this step? It nails the rule: fully-associative caches cannot have conflict misses.

Answer: 3 compulsory, 3 capacity, 0 conflict.

---

Example 4 — Cell D: the trap ("looks conflict, is capacity")

Steps.

1. Indices: $0\to 0,1\to 1,2\to 0,3\to 1$. So set 0 is fought over by $\{0,2\}$ and set 1 by $\{1,3\}$. Why this step? Identify who shares a home before simulating.
2. Simulate the real direct-mapped cache (each set holds exactly one line):

Access	Index	State (set0 / set1) before	Result
0	0	– / –	Compulsory (fill set0 with 0)
1	1	0 / –	Compulsory (fill set1 with 1)
2	0	0 / 1	Compulsory (evicts 0)
0	0	2 / 1	miss — type? (evicts 2)
3	1	0 / 1	Compulsory (evicts 1)
0	0	0 / 3	Hit

Why this step? Count the real misses: accesses #1,#2,#3,#4,#5 all miss ⇒ $M_{\text{real}}=5$; access #6 hits. Access #4 is the mystery one.

3. To type access #4, simulate a fully-associative 2-line LRU on the whole trace 0,1,2,0,3,0, showing every step so $M_{\text{full}}$ is not a black box:

Access	Cache after [LRU … MRU]	Result	Reason
#1 0	[0]	miss	first touch
#2 1	[0,1]	miss	first touch
#3 2	[1,2]	miss	full, evict 0 (LRU)
#4 0	[2,0]	miss	0 was evicted at #3 ⇒ not resident
#5 3	[0,3]	miss	full, evict 2 (LRU)
#6 0	[3,0]	hit	0 still resident (touched at #4)

Why this step? The fully-assoc cache also misses at access #4, and its total is $M_{\text{full}}=5$ (misses at #1–#5, hit at #6). By the rule "conflict only if a same-size fully-assoc would have hit", access #4 cannot be conflict — it is capacity.

4. Classify all six accesses:

Access	Real result	Type
#1 0	miss	Compulsory
#2 1	miss	Compulsory
#3 2	miss	Compulsory
#4 0	miss	Capacity (fully-assoc also missed)
#5 3	miss	Compulsory
#6 0	hit	—

Answer: 4 compulsory, 1 capacity, 0 conflict, 1 hit (5 real misses total).

---

Example 5 — Cell E: associativity turns conflict into hits

Steps.

1. Indices: $0\mathrm{mod}2=0$, $8\mathrm{mod}2=0$. Both go to set 0, but set 0 now has 2 ways (2 lines). Why this step? Conflict happens when a set overflows. A 2-way set holds both rivals.
2. Simulate (each set is its own tiny LRU list):

Access	Set 0 ways [LRU … MRU]	Result
0	[0]	Compulsory
8	[0,8]	Compulsory
0	[8,0]	Hit
8	[0,8]	Hit
0	[8,0]	Hit
8	[0,8]	Hit

Answer: 2 compulsory, 0 capacity, 0 conflict, 4 hits. The 4 conflict misses from Example 2 vanished with more associativity and the same total size.

---

Example 6 — Cell F: degenerate inputs

Steps.

1. (a) Empty trace. No accesses ⇒ $0$ misses of every type. Why: miss counts are over the trace; an empty trace has nothing to miss on.
2. (b) 7,7,7,7. First 7 is compulsory; it stays resident (nobody evicts it), so the rest hit. Why: temporal locality in the extreme — the same block, never displaced. ⇒ 1 compulsory, 3 hits.
3. (c) 1,2,1,2, indices $1\mathrm{mod}4=1$, $2\mathrm{mod}4=2$ (different homes). Why: distinct homes ⇒ no collision; both resident after first touch. ⇒ 2 compulsory, 2 hits, 0 conflict, 0 capacity.

Answer: (a) all zero; (b) 1 compulsory; (c) 2 compulsory. No capacity/conflict anywhere.

---

Example 7 — Cell G: block size changes the counts

Steps.

1. Block number $=\lfloor \text{address}/\text{block size}\rfloor$ (floor = round down, defined at the top). Why: the block number is what maps and what "already fetched" is measured in.
2. 4 B blocks: addresses 0,4,8,12 → block numbers $\lfloor 0/4\rfloor ,\lfloor 4/4\rfloor ,\lfloor 8/4\rfloor ,\lfloor 12/4\rfloor =0,1,2,3$ — four distinct blocks ⇒ 4 compulsory. Why: each address is its own block, none share a fetch.
3. 16 B blocks: $\lfloor 0/16\rfloor =\lfloor 4/16\rfloor =\lfloor 8/16\rfloor =\lfloor 12/16\rfloor =0$ — all in block 0 ⇒ only the first access misses ⇒ 1 compulsory, 3 hits. Why: one fetch pulls in bytes 0–15, so 4,8,12 arrive "for free" — spatial locality captured by the larger block.

Answer: 4 B block → 4 compulsory; 16 B block → 1 compulsory.

---

Example 8 — Cell H: real-world word problem (2D array walk)

Steps.

1. Each row is one 16 B block ⇒ block number = row number $\in \{0,1,2,3\}$. Index $=\text{row}\mathrm{mod}2$: rows 0,2 → set 0; rows 1,3 → set 1. Why: map the data structure to blocks before counting.
2. Row-major reads all 4 elements of row 0 (one block: 1 miss + 3 hits), then row 1, etc. Why: consecutive elements share a block ⇒ spatial locality is captured. Block visit order: 0,0,0,0, 1,1,1,1, 2,2,2,2, 3,3,3,3. Each new block is touched once then reused immediately while still resident ⇒ 4 misses (all compulsory), 12 hits.
3. Column-major reads (0,0),(1,0),(2,0),(3,0) — rows 0,1,2,3 → blocks 0,1,2,3 — then column 1 revisits rows 0,1,2,3, and so on. Why: poor locality — a block is fetched, evicted before its reuse, and refetched. Block visit order: 0,1,2,3, 0,1,2,3, 0,1,2,3, 0,1,2,3.
4. Count column-major on the direct-mapped 2-set cache. Set 0 alternates between blocks 0 and 2; set 1 alternates between blocks 1 and 3. Simulate set 0's visits (0,2,0,2,0,2,0,2): the first 0 and first 2 are compulsory, every later visit finds the other block resident ⇒ miss. Same for set 1 (1,3,1,3,…). Why: with only one line per set and two blocks fighting for it, every access after the two first-touches thrashes. Result: all 16 accesses miss — the two first-touches per set (4 total) are compulsory, the remaining 12 are conflict.

Answer: Row-major = 4 misses (4 compulsory, 0 conflict). Column-major = 16 misses (4 compulsory + 12 conflict). Same data, 4× more misses purely from the wrong walk order.

---

Example 9 — Cell I: full 3-way decomposition by subtraction

Steps.

1. Indices: $0,2,4\mathrm{mod}2=0,0,0$ — all three share set 0 (one line). Why: set up who collides.
2. $M_{\text{real}}$ (direct-mapped, set 0 holds 1 block): 0 miss, 2 miss(evict 0), 4 miss(evict 2), 0 miss, 2 miss, 4 miss ⇒ 6 misses. Why: the real machine's total.
3. $M_{\text{full}}$ (fully-assoc, 2 lines, LRU) on same trace, every step shown:

Access	Cache after [LRU … MRU]	Result
0	[0]	miss
2	[0,2]	miss
4	[2,4]	miss, evict 0 (LRU)
0	[4,0]	miss, evict 2
2	[0,2]	miss, evict 4
4	[2,4]	miss, evict 0

⇒ 6 misses. Why: the finite-but-unrestricted machine. Working set = 3 > 2 slots, so it thrashes too. 4. $M_{\infty }$ = distinct blocks = $|\{0,2,4\}|=3$. Why: compulsory count. 5. Decompose: $M_{\text{compulsory}}=3,M_{\text{capacity}}=M_{\text{full}}-M_{\infty }=6-3=3,M_{\text{conflict}}=M_{\text{real}}-M_{\text{full}}=6-6=0.$ Why: each subtraction strips out exactly one cause.

Answer: 3 compulsory, 3 capacity, 0 conflict (total 6). The blocks share a set, but even a fully-associative cache couldn't hold all 3 in 2 lines — so the blame is capacity, not conflict, despite the shared index. Adding associativity here would not help; only a bigger cache would.

---

The decision flow (memorize this, not the tables)

Recall One-line self-test (cover the answers)

Same-index blocks always cause conflict misses? ::: No — if the working set exceeds the cache they are capacity misses (Ex 9). Column-major vs row-major matrix walk — which misses more? ::: Column-major, because it defeats spatial locality (Ex 8). Fully-associative cache, how many conflict misses? ::: Zero, by definition (Ex 3). Bigger block always cuts total misses? ::: No — cuts compulsory but can raise capacity/conflict (Ex 7). How do you prove a miss is conflict not capacity? ::: Simulate a same-size fully-associative cache; conflict only if it would have hit (Ex 4).

These examples plug straight into Average Memory Access Time (AMAT): multiply each miss count by its penalty to see which C dominates your runtime.