Cache miss classification and metadata accounting
Goals, prerequisites and conventions
Classify compulsory/capacity/conflict misses with an explicit reference cache; calculate physical cache storage including tags, valid, dirty and stated replacement bits. Prerequisites: the live cache-foundations lesson and lesson 07 replacement/write policies. We do not reteach mapping or conflate OS page faults with hardware cache misses.
For traces, use serial reads of named blocks, initially empty caches, allocation on each miss, no prefetch/invalidation, and the same block size. Our 3C classification uses a fully associative LRU reference cache with the same number of lines as the actual cache. Track the reference on every request, even when the actual cache hits. Classify only misses of the actual cache.
1. An operational three-step rule
For each actual miss:
- If the block has never appeared earlier in the trace, call it compulsory.
- Otherwise, if the fully associative reference also misses now, call it capacity under this reference convention.
- Otherwise, the reference hits but the actual cache misses: call it conflict.
This clean comparison requires stated replacement and starting-state rules. It is not valid to call every repeated miss a conflict, nor to classify a miss from the current actual state alone. In generalized systems, coherence, invalidation, prefetch, replacement-policy differences and non-LRU behavior may require richer categories. We use the named textbook 3C reference convention, not a claim that every real miss has a uniquely obvious physical cause.
2. Worked trace containing all three categories
Actual cache: two-line direct-mapped, block b maps to line b mod 2. Reference: two-line fully associative LRU. Read blocks 0,2,0,1,2.
- Request 0: actual miss; first-ever 0→compulsory. Reference becomes [0].
- Request 2: actual miss, replaces 0 in line 0; first-ever 2→compulsory. Reference oldest→newest is [0,2].
- Request 0: actual miss, replaces 2; block seen before. Reference hits and becomes [2,0]→conflict.
- Request 1: actual miss in line 1; first-ever 1→compulsory. Reference evicts 2 and becomes [0,1].
- Request 2: actual miss in line 0; block seen before. Reference also misses, evicts 0, becomes [1,2]→capacity under the stated convention.
Actual results are five misses: three compulsory, one conflict, one capacity. The reference has four misses. Here actual misses minus reference misses equals the one conflict miss because the actual cache never hits while the reference misses. Do not generalize that subtraction without checking the full paired trace.
3. Why paired per-request classification is safer than subtraction
Compare the same two-line direct-mapped actual cache and LRU reference on 0,1,3,0. Actual outcomes M,M,M,H: block 0 remains in line 0 while 1 and 3 contend for line 1. Reference outcomes M,M,M,M: after 0,1,3, its LRU policy has evicted 0. On the final request the actual cache hits while the reference misses. There are three actual compulsory misses and zero other actual misses; actual miss count minus reference count is −1 and cannot be a conflict count. The fully associative LRU cache has placement flexibility but its replacement choices need not dominate a direct-mapped cache on every trace. This is why our definition classifies actual misses using simultaneous reference state instead of blindly subtracting totals.
4. Data capacity versus physical bits
Let data capacity C bytes, block size B bytes, associativity E, address width A bits. Assume C/B and (C/B)/E are integers, and block size B and set count S are powers of two. Under byte addressing and ordinary low-bit indexing, lines L=C/B; sets S=L/E; offset bits b=log2 B; index bits s=log2 S; tag bits t=A−s−b. These formulas summarize prerequisites for storage accounting, not a new mapping lesson.
If every line stores one valid bit and one dirty bit, line metadata is t+2 bits. Total physical information storage is 8C+L(t+2)+replacement bits, plus any separately specified ECC/parity/other bits. Dirty bits belong only when the design says they exist. Direct mapping needs no victim-selection bits. Do not count a next-level memory address in full for each line: offset/index are implicit in placement and byte position.
Worked example: 32-bit byte addresses, 4 KiB data cache, 32-byte blocks, two-way associativity, write-back, one valid and one dirty bit/line. L=4096/32=128; S=64; b=5,s=6,t=21. Tag+valid+dirty storage=128×23=2944 bits. True two-way LRU uses one bit per set, hence 64 bits. Data bits=32768. Total=32768+2944+64=35776 bits=4472 bytes. The advertised data capacity stays 4096 bytes; metadata increases implementation storage, not available user data.
5. Replacement-state counts require a representation
Two-way true LRU needs one bit per set to identify the less-recently-used way once both are valid. For E ways, a full recency order has E! possibilities; information-theoretic minimum is ceil(log2(E!)) bits, but practical logic can store it differently. For four ways, 4!=24 orders imply at least five bits for a fully represented order. Tree pseudo-LRU commonly uses E−1 bits for power-of-two E, but it approximates LRU and is not an exact recency ordering. Therefore a four-way pseudo-LRU cache's three bits are not evidence that true four-way LRU needs only three. In total-storage problems, use the replacement representation stated; if unspecified, identify the ambiguity rather than quietly picking one.
Common mistakes
Track seen-before and both caches separately. First-ever reads are compulsory even when they also displace useful data. Only actual misses receive a miss class. Metadata and data use different units. One bit per set is not one bit per line. State exact versus approximate replacement before counting its bits.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Two-line direct-mapped actual and two-line fully associative LRU reference are initially empty. Reads 0,2,0. The third actual miss is:
A. Compulsory B. Capacity under the stated reference C. Conflict under the stated reference D. Not a miss
Answer: C
A: Block 0 has been seen already.
B: The fully associative reference still holds 0.
C: Actual evicted 0 due to its shared line with 2; reference hits.
D: The direct-mapped line currently holds 2.
P02. For the same caches, reads 0,2,0,1,2 produce how many actual compulsory/conflict/capacity misses, respectively?
A. 3,1,1 B. 3,2,0 C. 2,1,2 D. 5,0,0
Answer: A
A: First 0,2,1 are compulsory; third request conflict; fifth capacity.
B: The final 2 also misses in the reference, so it is not conflict under this convention.
C: Three distinct first-ever blocks appear.
D: Repeated references are not compulsory.
P03. Why can total actual misses minus total fully associative LRU misses fail as a conflict count?
A. The actual cache may hit when the reference misses B. LRU has no state C. Compulsory misses occur only in direct mapping D. Tags cannot be compared
Answer: A
A: Different replacement histories can create actual hits/reference misses, so paired classification is needed.
B: LRU maintains access-recency state.
C: Both initially empty caches miss on a first-ever block.
D: Tags and block identity can be tracked in both caches.
P04. A 32-bit byte address, 2 KiB data cache, 16-byte blocks and two ways give tag width:
A. 20 bits B. 21 bits C. 22 bits D. 25 bits
Answer: C
A: This overcounts the index/offset bits.
B: Seven index bits would describe 128 sets, but there are 64.
C: 128 lines/2=64 sets: index6, offset4, tag32−6−4=22.
D: This leaves insufficient bits for set index and offset.
P05. 128 cache lines each have 21 tag bits, one valid and one dirty bit. Total line metadata, excluding replacement?
A. 2688 bits B. 2816 bits C. 2944 bits D. 3072 bits
Answer: C
A: This counts only tag bits.
B: This counts only one of valid/dirty.
C: 128×(21+1+1)=2944 bits.
D: This assumes an extra unstated bit per line.
P06. What is the information-theoretic minimum number of bits for all full recency orders of four distinct valid ways?
A. 3 B. 4 C. 5 D. 6
Answer: C
A: Three bits encode only eight states; tree pseudo-LRU is approximate.
B: Four bits encode sixteen states, fewer than 24 orders.
C: 4!=24; ceil(log2 24)=5.
D: Six can encode them but is not the minimum.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire COA syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in