Foundations — Cache miss types (compulsory, capacity, conflict)

Before you can talk about why misses happen, you must be fluent in the vocabulary the parent note throws around: block, set, index, associativity, the mod symbol $\mathrm{mod}$, LRU, and the little $M$ letters with subscripts. This page builds every one of those from nothing, in an order where each rests on the previous.

---

1. Memory as a giant shelf of numbered boxes

Why the topic needs it: every access in the parent note (0, 4, 0, 4…) is an address. Without the idea of numbered boxes, none of the sequences mean anything.

---

2. The block — the chunk that actually moves

You never fetch a single byte from the big shelf into the cache. That would be wasteful. Instead memory is sliced into fixed-size blocks (also called lines).

Why the topic needs it: the parent writes sequences like 0, 4, 2 — those are block numbers $B$, not byte addresses. When we say "first ever touch of block 4," the block is the thing being touched. (Bringing in neighbours in one block is exactly what Spatial and Temporal Locality exploits, and how big a block should be is Cache Block Size Trade-offs.)

---

3. The cache — a small shelf with numbered slots

Hit vs miss, restated with our new words:

Why the topic needs it: "miss types" only make sense once you know a miss = "not in a slot." Eviction is the event that causes a future miss, which is the beating heart of capacity and conflict misses.

---

4. Where is a block allowed to sit? — the index and $\mathrm{mod}$

Here is the mechanical rule that makes conflict misses possible. In the simplest cache, each block has exactly one legal home slot, decided by arithmetic.

Worked feel for it — with $S=4$:

Block $B$	$B\mathrm{mod}4$	Home set
0	0	0
4	0	0 ← collides with block 0!
1	1	1
6	2	2

That collision of block 0 and block 4 is exactly the parent's Worked Example 1.

---

5. Associativity — how many homes a block may have

Why the topic needs it: the entire definition of a conflict miss is "a miss that a fully-associative cache of the same size would have avoided." You cannot state that without knowing what "fully-associative" means. Deeper mechanics live in Cache Associativity & Set Mapping.

---

6. LRU — who gets evicted when a set is full

When a set has $n$ slots and all are full but a new block needs in, someone must leave. Which one? A replacement policy decides.

Why the topic needs it: the parent's capacity example writes states like [1,2] and [2,0] — that ordering is LRU bookkeeping. To classify a capacity miss you must simulate the fully-associative cache with a replacement policy, and LRU is the standard one. Full detail: LRU and Replacement Policies.

---

7. The $M$ symbols — counting misses by cause

Finally the notation in the parent's formulas.

---

Prerequisite map

---

Equipment checklist

• I can turn a byte address into a block number $B$ ::: $B=\lfloor \text{address}/\text{block size}\rfloor$ — divide and round down.
• I can compute an index with mod ::: $\text{index}=B\mathrm{mod}S$; e.g. $6\mathrm{mod}4=2$ (remainder).
• I know why two blocks collide in direct-mapped ::: they share the same $B\mathrm{mod}S$, so they want the same single home slot.
• I can state the three associativity levels ::: direct-mapped = 1 slot/set, $n$-way = $n$ slots/set, fully-associative = 1 set holding everything.
• I know what LRU evicts ::: the block unused for the longest time (the LRU end of the ordering).
• I can name the cure for each C ::: compulsory→prefetch/bigger block, capacity→bigger cache, conflict→more associativity.
• I know the decomposition formula ::: $M_{\text{total}}=M_{\text{compulsory}}+M_{\text{capacity}}+M_{\text{conflict}}$.