1. In a data processing system having one or more processors and multiple levels of cache, including a lower level cache and a higher level cache, a method comprising: detecting a data request at the lower level cache; in response to a cache miss in the lower level cache, selecting a cache-line for eviction based upon (a) presence bits and (b) less recently used (LRU) bits, wherein said selecting further comprises: partitioning multiple “cache-ways” of a cache set into a less recently used (LRU) group and a more recently used (MRU) group using one or more of (a) pseudo-LRU bits; and (b) non-LRU based replacement policy parameters; in response to a cache miss in the lower level cache, initiating a process to determine which cache line is consequently selected for eviction in the lower level cache, based on values of one or more of: (a) a presence bit; (b) a LRU bit or a pseudo LRU bit; and (c) parameters from non-LRU based replacement policies, wherein the initiating comprises: (a) checking the value of the presence bits; (b) in response to the value of the presence bits being set to a first value, receiving an indication that a copy of the cache-line is not present in a corresponding higher level cache; and (c) in response to the value of the presence bits being set to a second value, receiving an indication that a copy of the cache-line is present in the corresponding higher level cache; identifying a least recently used cache-line in said lower level cache using said pseudo-LRU bits; in response to the least recently used cache-line not having a corresponding presence bit set to the second value or a group of cache-lines constituting the LRU group not having the corresponding presence bits set to the second value, executing one or more of: (a) a selection of the least recently used cache-line for eviction; (b) replacement of the least recently used cache-line with a new cache-line; and (c) a change to the LRU bits; and in response to the least recently used cache-line having a corresponding presence bit set to the second value and one or more elements of the LRU group not having the corresponding presence bit set to the second value, executing one or more of: (a) a random selection of a less recently used cache-line from the LRU group for eviction, wherein said less recently cache-line that is randomly selected is not the least recently used cache-line; (b) replacement of said less recently used cache-line with a new cache-line; and (c) a modification of the LRU bits; determining whether a copy of the cache-line selected for eviction is present in the higher level cache; and in response to the copy of the cache-line selected for eviction being present in the higher level cache, invalidating the copy of the cache-line selected for eviction; and updating pseudo-LRU bits.