A method and means are provided for increasing both the MMBR (minimum misses before replaceable) and MHBR (minimum hits before replaceable) parameters for a virtual 3-way cache, consisting of three unlocked sets, from one to two. Thus, a minimum of two accesses to the sets B, C and D would be required, before a previously accessed set becomes the LRU. In one embodiment, a method is provided for selecting a data set for replacement in a locking cache that includes at least four data sets. Initially, a 4-way binary tree LRU associated with at least some of the sets of the locking cache is specified or configured, wherein the binary tree has a top level LRU bit, a first branch having one locked set and one unlocked set, and a second branch having two unlocked sets. The first and second branches are each provided with an LRU bit. The LRU bit of the first branch is set to a logic 1, when the unlocked set of the first branch is the MRU set of the three unlocked sets, to a logic 0, when such unlocked set is not the MRU or LRU set, and arbitrarily to either a logic 1 or 0, when such unlocked set is the LRU set.
