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 respective one of a plurality of counters for each cache line stored in the multiple entries; in response to a memory access request that misses in the cache memory: the cache memory selecting a victim cache line stored in a particular entry of a particular congruence class for eviction from the cache memory by reference to at least a counter value of the victim cache line; the cache memory receiving, from a source device in the data processing system, a new cache line of data for insertion into the particular entry and an indication of a coherence state of that the new cache line had at the source device prior to receipt by the source device of the memory access request; and the cache memory installing the new cache line in the particular entry and setting an initial counter value of the counter for the new cache line based on the received indication of the coherence state at the source device and a device type of the source device.