Course contentsShow
← Computer Science
Lesson 1123 of 2,87226. Memory Hierarchy and CachingFree lesson

Cache Replacement Policies Overview

How caches decide which block to evict when full: LRU, FIFO, and random replacement strategies.

Cache Replacement Policies Overview

What you'll learn: How caches decide which block to evict when the cache is full and a new block needs to be loaded.

When a cache miss occurs and the cache is already full, the system must choose which existing cache block to replace with the new data. This decision can significantly impact your cache hit rate and overall performance.

Why Replacement Matters

Think of your cache like a small parking lot near a busy store. When the lot is full and a new customer arrives, you need to decide which currently parked car should leave. A smart policy keeps the cars most likely to be used again soon.

Common Replacement Strategies

LRU (Least Recently Used)

Evicts the block that hasn't been accessed for the longest time. The logic: if you haven't used something recently, you probably won't need it soon. This is effective because of temporal locality—recently accessed data is likely to be accessed again.

FIFO (First-In, First-Out)

Evicts the oldest block in the cache, regardless of how recently it was used. Simple to implement (just track insertion order), but doesn't consider actual usage patterns.

Random

Picks a block to evict at random. Surprisingly effective in some cases and requires minimal hardware—no tracking of usage history needed.

Trade-offs

LRU typically achieves the best hit rates but requires extra hardware to track access order for every block. FIFO is simpler but can evict frequently-used blocks just because they're old. Random is the simplest but unpredictable, though it avoids worst-case scenarios that can trap other policies.

Key Takeaway: Cache replacement policies balance performance (hit rate) against hardware complexity, with LRU favoring performance, Random favoring simplicity, and FIFO somewhere in between.