True least recently used replacement method and apparatus

Claim 1

A cache system for use in a computer system having a processor for providing memory access operations and having another means besides the processor for providing memory access operations, the cache system organized as an n way set associative cache, where n is greater than 2, the cache system monitoring memory access operations, the cache system comprising: memory means for storing information on way use history for only n-1 use ages for each set in the cache system as bits simultaneously accessed when a memory address is provided; means for determining the way use history of each set for the nth use age from said stored way use history information for each set; means for determining if processor provided or the another means provided memory access cycles are being monitored; means for shuffling way use history information for each memory access, said means for shuffling receiving previously stored way use history information from said memory means and said means for determining the way use history for the remaining use age, by setting a way containing the accessed location on processor cache hits or a way to be accessed on processor read cache misses to the most recently used way and rearranging the other stored way use history information in order of processor use age and by setting a way containing the accessed location on snoop write cache hits to the least recently used way and rearranging the other stored way use history information in order of processor use age; and means for updating said stored use history information in said memory means on processor cache hit, processor read cache miss and the another means write cache hit operations to reflect the shuffled way use history information developed by said shuffling means.