When a cache miss occurs, the cache controller must select a victim cache line to evict and make space for new data from main memory. This process is known as cache line eviction.
The method used to select which line to evict is called the cache replacement policy.
Types of Replacement Policies:
- Round-Robin (Cyclic Replacement):
- Replaces the next line in a fixed circular order.
- Uses a victim counter that increments sequentially.
- When max is reached, counter resets to base value.
- Predictable behavior (good for real-time/embedded systems).
- Not adaptive — may lead to suboptimal performance.
- Pseudorandom Replacement:
- Selects victim randomly using a non-sequential increment.
- Victim counter increments by a random value each time.
- Adds unpredictability — helps avoid performance bottlenecks in certain patterns.
- Less deterministic; harder to analyze in timing-critical systems.
Allocation Policy on a Cache Miss
When a cache miss occurs, the system needs to decide when to allocate a cache line. This is controlled by the cache allocation policy.
1. Read-Allocate Policy:
- Cache line is allocated only during read misses.
- If the victim cache line is dirty, it is written back to main memory first.
- Writes do not allocate cache lines (unless data already present).
- Used by: ARM7, ARM9, ARM10
2. Read-Write Allocate Policy:
- Cache line is allocated on both read and write misses.
- On write:
- If the cache line is dirty ➝ write back to memory, then fill.
- If cache line is invalid ➝ fill directly.
- Used by: Intel XScale, some advanced ARM cores