Cache Replacement Policies and Cache Miss Types: FIFO, LRU and 3C Worked Examples
See exactly when FIFO, LRU and Optimal evict different blocks, then classify compulsory, conflict and capacity misses with two small cache traces.
KnowledgeGate Team
Exam prep & CS education

Three ideas often get mixed together in cache questions. Mapping decides which set a memory block may enter, replacement decides which resident line leaves when that set is full, and miss type explains why the requested block was absent. In the wider memory hierarchy, mapping, replacement, and miss classification must be kept distinct.
Cache mapping comes before replacement
A memory block is the transfer unit, and a cache line is one slot that holds a block. A set groups candidate lines; associativity is its line count.
Mapping fixes the candidates before policy. A direct-mapped cache has one candidate, so it has no victim choice. A 2-way set-associative cache chooses within the indexed pair. A fully associative cache may choose any line.
Use a 4-line, 2-way cache with 2 sets of 2 lines and set index = block number mod 2. Blocks 0, 2 and 4 map to set 0; blocks 1, 3 and 5 map to set 1. Cache mapping and hit ratio therefore come before victim selection.
Consult the policy only on a miss when every line in the selected set is valid. Fill an empty line without eviction.

FIFO, LRU, Random and Optimal
Each replacement policy answers the same victim question with different information:
FIFO evicts the line loaded earliest. A hit does not change the insertion queue.
LRU evicts the line whose most recent access is oldest. Every hit refreshes recency.
Random selects an eligible resident line without using age or recency information.
Optimal evicts the block whose next use lies farthest in the future.
FIFO tracks insertion order; exact LRU tracks access order. Random needs no meaningful recency state. Optimal is an offline bound because future references are unknown. Larger caches may approximate LRU. For a deterministic comparison, FIFO and LRU apply their exact rules, while Optimal supplies the offline lower bound; Random has no single predictable trace.
Worked example with a three-line cache
A fully associative 3-line cache starts empty and reads A, B, C, A, D, A, B, C. Ignore write policy. FIFO states run oldest to newest, and LRU states run LRU to MRU; Optimal has no age order.
Step | Block | FIFO result and contents | LRU result and contents | Optimal result and contents |
|---|---|---|---|---|
1 | A | M: | M: | M: |
2 | B | M: | M: | M: |
3 | C | M: | M: | M: |
4 | A | H: | H: | H: |
5 | D | M: evict A, | M: evict B, | M: evict C, |
6 | A | M: evict B, | H: | H: |
7 | B | M: evict C, | M: evict C, | H: |
8 | C | M: evict D, | M: evict D, | M: evict D, |
FIFO gets 1 hit and 7 misses, so 1/8 = 12.5%. The step-4 hit does not move A, so D evicts it at step 5.
LRU gets 2 hits and 6 misses, so 2/8 = 25%. The step-4 hit makes A MRU, so D evicts B. A hits again at step 6.
Optimal sees A, B and C next at steps 6, 7 and 8, so it evicts C. It gets 3 hits and 5 misses, or 3/8 = 37.5%. At the final step, all residents have no future use; the table chooses D from that tie.
On this sequence, Optimal records the most hits and FIFO the fewest. One sequence cannot establish that LRU always beats FIFO.

Compulsory, conflict and capacity misses
Classify a miss with the 3C test in a fixed order:
A block's first reference is compulsory, even when its load triggers an eviction.
Otherwise, compare with a fully associative cache of the same total capacity and replacement rule.
If only restricted set mapping causes the miss, it is a conflict miss. If the equal-capacity fully associative cache also misses, it is a capacity miss.
For a conflict example, trace 0, 2, 4, 0 in the 4-line, 2-way LRU cache. All blocks map to set 0. The first three misses are compulsory; their LRU-to-MRU states are [0], [0, 2] and [2, 4]. The final 0 misses, evicts 2 and leaves [4, 0]. A fully associative 4-line cache could hold 0, 2 and 4, so it would hit. This miss is conflict, although set 1 is empty.
For capacity, use a fully associative 2-line LRU cache with 0, 1, 2, 0. The first three compulsory misses produce [0], [0, 1] and [1, 2]. The final 0 misses because three blocks competed for two lines. With no set restriction, it is a capacity miss.
Coherence or invalidation misses require an extended 4C classification for multicore systems; classic single-core systems use the 3C classification.
A reliable method for reference-string questions
Use the same procedure on every access:
Convert the address to a block number if necessary.
Compute the set index.
Check the valid bit and tag for a hit.
On a miss with a full set, apply only the named replacement policy.
Update FIFO insertion order or LRU access order after the access.
Write the state convention above the first row. For classification, test first-seen status, then run the same-capacity fully associative comparison. Maintain an independent cache state for each policy.
Audit the arithmetic: hits + misses = 8 for every policy. FIFO gives 1/8, LRU 2/8, and Optimal 3/8. For latency, continue with cache write policies and AMAT numericals.
Traps that change the answer
Treating a FIFO hit as a new insertion changes the victim. A must stay oldest after step 4, so FIFO evicts A at step 5.
Failing to refresh LRU on that same hit incorrectly evicts A instead of B.
Applying replacement across the whole cache is wrong in a set-associative problem. Only the indexed set participates.
Calling every repeated-block miss a capacity miss ignores the fully associative test. The final 0 in
0, 2, 4, 0is conflict.Presenting Optimal as an implementable online policy, or claiming one trace proves LRU always wins, goes beyond what the example establishes.
Short version and the next practice step
Mapping narrows the eligible lines, the policy chooses a victim on a full-set miss, and the 3C test explains the miss. Retrace A, B, C, A, D, A, B, C without looking at the table. Then change the cache from 3 lines to 2 and compare all three totals.
After retracing both examples, move to timed cache-replacement questions. For structured GATE study, use GATE Guidance by Sanchit Sir. For broader core-CS learning, use Zero to Hero, Complete CS Course, or browse the CS Fundamentals courses by topic.
Keep learning
Cache Replacement Policies and Miss Types MCQs: 12 Solved Questions
Solve 9 MCQs and 3 MSQs on compulsory, conflict and capacity misses, cache miss rate, mapping, set-wise LRU traces, and Optimal replacement.
Page Replacement Algorithms for GATE: FIFO, LRU and Optimal with Belady's Anomaly Explained
One shared reference string traced fault by fault through FIFO, LRU and Optimal page replacement with 3 frames, then re-run under FIFO with 4 frames to demonstrate Belady's anomaly. Includes the counting rules GATE expects, why LRU beating FIFO is a tendency and not a theorem, and the stack-algorithm property that makes LRU and Optimal immune to the anomaly.
Page Replacement Algorithms MCQs: 12 solved questions (FIFO, LRU, Optimal)
Page replacement MCQs for GATE, UGC NET and DSSSB: FIFO and Belady's anomaly, LRU, Optimal, and page-fault counting numericals, each solved and explained.
FIFO Page Replacement Explained: Step-by-Step Fault Counting and Belady's Anomaly
Learn a reliable FIFO queue method, trace every hit and fault across a complete example, and see why adding a frame can sometimes increase the fault count.





