LearnViz CompSci
Home / Learn / Computer Architecture & Logic / Cache Replacement Policies

Intermediate Topic 28 of 51 Computer Architecture & Logic

Cache Replacement Policies

Rules like LRU deciding which block to evict.

How it works

When a set is full and a new block must be loaded, the replacement policy picks a victim. Least recently used evicts the block untouched for the longest time, exploiting temporal locality; FIFO evicts the oldest; random picks any; pseudo-LRU approximates LRU cheaply with a few bits; and LFU evicts the least frequently used. Belady's optimal policy evicts the block used furthest in the future and serves as a benchmark.

Step-by-step walkthrough

  1. The cache holds A B C D and is full.
  2. Access A, it becomes most recently used.
  3. Access C, B and D are now the least recently used.
  4. A miss for E must evict a line.
  5. LRU evicts the oldest-used line B, FIFO evicts the oldest-loaded and random picks any.

Where it is used

CPU caches, operating-system page replacement, database buffer pools, CDN and web caches all choose a policy. Real hardware often uses tree-based pseudo-LRU.

Common pitfall

True LRU is expensive to implement in hardware for high associativity. Sequential scans larger than the cache flush useful data under LRU. FIFO can show Belady's anomaly, where more capacity gives more misses. Match the policy to the workload and measure hit rates.

Where it fits in the course

Cache Replacement Policies is topic 28 of 51 in Computer Architecture & Logic, rated Intermediate. It follows Cache Mapping. The next topic is Virtual Memory in Hardware.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the Computer Architecture & Logic quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Cache Replacement Policies?
Rules like LRU deciding which block to evict. It belongs to Computer Architecture & Logic and is an intermediate-level topic.
Where do people use Cache Replacement Policies?
CPU caches, operating-system page replacement, database buffer pools, CDN and web caches all choose a policy.
What is the most common mistake with Cache Replacement Policies?
True LRU is expensive to implement in hardware for high associativity.
What should I learn before this topic?
Start with Cache Mapping, the topic just before it in Computer Architecture & Logic.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Computer Architecture & Logic quiz.
Is Cache Replacement Policies hard to learn?
It is an Intermediate topic. Be comfortable with the Beginner topics in this area first, then read the common pitfall carefully, since it is where most mistakes happen.
How long does it take to learn Cache Replacement Policies?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Cache Replacement Policies?
Cache Mapping, Virtual Memory in Hardware, Cache Memory are closely connected. The full list is in the related topics section of this page.
What should I study after Cache Replacement Policies?
Continue with Virtual Memory in Hardware, the next topic in Computer Architecture & Logic.

Related topics