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

Updated 17 Nov 20265 min read
Cache Replacement Policies and Cache Miss Types: FIFO, LRU and 3C Worked Examples

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.

A two-way set-associative cache maps blocks 0, 2, and 4 to Set 0 and blocks 1, 3, and 5 to Set 1 using block number mod 2.

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: A

M: A

M: A

2

B

M: A B

M: A B

M: A B

3

C

M: A B C

M: A B C

M: A B C

4

A

H: A B C

H: B C A

H: A B C

5

D

M: evict A, B C D

M: evict B, C A D

M: evict C, A B D

6

A

M: evict B, C D A

H: C D A

H: A B D

7

B

M: evict C, D A B

M: evict C, D A B

H: A B D

8

C

M: evict D, A B C

M: evict D, A B C

M: evict D, A B C

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.

Three cache-replacement lanes compare FIFO, LRU, and Optimal for sequence A, B, C, A, D, A, B, C, with totals of 1H/7M, 2H/6M, and 3H/5M.

Compulsory, conflict and capacity misses

Classify a miss with the 3C test in a fixed order:

  1. A block's first reference is compulsory, even when its load triggers an eviction.

  2. Otherwise, compare with a fully associative cache of the same total capacity and replacement rule.

  3. 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:

  1. Convert the address to a block number if necessary.

  2. Compute the set index.

  3. Check the valid bit and tag for a hit.

  4. On a miss with a full set, apply only the named replacement policy.

  5. 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, 0 is 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

Discussion