Cache miss

A request whose required data are unavailable in the consulted memory cache. The model in spatial locality fetches the requested cache block and evicts a resident cache line only when capacity is full.

In the fixed memory access trace under memory cache, reads 1, 3, 5 and 8 first request cache blocks 0, 2, 1 and 3: four compulsory misses, also called cold misses. Reads 6, 7 and 11 revisit cache blocks that LRU replacement has evicted: three capacity misses. Read 5 is a compulsory miss even though it also causes an eviction; a full memory cache alone does not determine the classification. The fully associative cache permits every cache block in every cache slot, so this example has no conflict misses.

For a precise comparison, run the same memory access trace through an initially empty direct-mapped cache with the same 16-byte cache lines and two cache slots, placing cache block $q$ only in slot $q\mathrm{mod}2$. Read 3 brings in cache block 2 and displaces cache block 0, leaving the other cache slot unused. Read 4 consequently misses at address 0, whereas the fully associative cache still has cache block 0. That read is a conflict miss: increasing placement freedom at the same capacity removes it. The complete direct-mapped cache trace has eight cache misses: four compulsory misses, three capacity misses and one conflict miss.

The convention here classifies each cache miss by first asking whether its cache block has ever been requested. If so, compare with an initially empty fully associative cache of the same capacity and cache line size using LRU replacement on the same memory access trace: a miss there is a capacity miss, while a hit there identifies a conflict miss in the restricted design. This makes the comparison policy explicit; “capacity” is not a claim that no other replacement choice could save that individual read. The three categories describe this read-only demand model; external invalidations or fetching ahead of requests require additional reasoning. ^[ref]