1. A method in a data processing system, the method comprising: in a set-associative cache memory having a plurality of congruence classes each including multiple entries for storing cache lines of data, maintaining a bank of counters including a respective one of a plurality of counters for each cache line stored in the plurality of congruence classes; prior to receiving a memory access request that specifies a target address that maps to a particular congruence class of the cache memory, the cache memory pre-selecting for eviction from the cache memory only one single first victim cache line out of all cache lines in the particular congruence class based on at least a counter value of the victim cache line, wherein the pre-selected first victim cache line is stored in a particular entry of the particular congruence class; in response to receiving the memory access request that specifies the target address that maps to the particular congruence class of the cache memory and that misses in the cache memory: the cache memory evicting the pre-selected first victim cache line from the particular entry and installing a new cache line in the particular entry; the cache memory pre-selecting, from among all the cache lines in the particular congruence class, only one single fixed second victim cache line to be evicted from the particular congruence class on a next miss to the particular congruence class regardless of any intervening accesses between the memory access request and the next miss, wherein the pre-selecting the second victim cache line includes pre-selecting the second victim cache line based on at least a counter value of the second victim cache line; adjusting counter values of counters of cache lines in the particular congruence class to make the cache lines more likely to be subsequently selected as a victim cache line; and adapting an amount counter values of counters are adjusted on a cache miss based on a dynamic distribution, at a given time, of the counter values across the bank of counters.