A first request to evict a first cache line that is stored in a cache memory may be received. The first cache line may be evicted based on a replacement policy. A second request to evict a second cache line from the cache memory may be received. Following the receipt of the second request, it is determined whether a condition associated with the replacement policy has been satisfied. If the condition associated with replacement policy has been satisfied, then the second cache line may be evicted based on a random replacement policy.