Patent ID: 8180969

Claim:
A cache comprising: storage circuitry for storing information in each of a plurality of cache lines; addressing circuitry having an input for receiving memory addresses and comparing received memory addresses with multiple ways of stored addresses to determine a hit condition representing a match of a stored address and a received address; a pseudo least recently used (PLRU) tree circuit for storing one or more states of a PLRU tree, the PLRU tree having a plurality of levels beginning with a root and which indicates one of a plurality of ways in the cache, each level having one or more nodes, multiple nodes within a same level being child nodes to a parent node of an immediately higher level, wherein, when there is at least one unlocked way of the cache, none of the one or more states of the PLRU tree indicate a locked way; and PLRU update circuitry coupled to the addressing circuitry and the PLRU tree circuit, the PLRU update circuitry receiving lock information to lock one or more lines of the cache and preventing a PLRU tree state from selecting a locked line, wherein the lock information comprises a way lock bit for each cache line of the cache which indicates whether a corresponding way of the cache is locked or not and a node lock bit corresponding to each node of the PLRU tree which indicates whether a corresponding node of the PLRU tree is locked or not; wherein, for each allocation of a new cache line when there is at least one unlocked way of the cache, a state of the PLRU tree stored by the PLRU tree circuit indicates a selected replacement way, wherein the selected replacement way indicated by the state of the PLRU tree is directly used as the selected replacement way for the new cache line without further processing of the selected replacement way.