Patent ID: 7984243

Claim:
A cache memory which holds, for each cache entry, order data indicating an access order, and which replaces a cache entry that is oldest in the access order, the cache entry holding unit data for caching, comprising: a modifier that modifies the order data regardless of an actual access order; and a selector that selects, based on the modified order data, a cache entry to be replaced, wherein said modifier attaches, to the modified order data, an oldest-order flag which indicates, when enabled, that the access order is the oldest regardless of the actual access order and which indicates that the cache entry to be replaced is written to no further, wherein the cache entry to be replaced has, as the order data, a 1-bit order flag that indicates whether the cache entry to be replaced has been accessed since each cache entry had been reset, each cache entry being reset when a 1-bit order flag is enabled for each cache entry, wherein said selector selects the cache entry to be replaced when a cache miss occurs and a cache entry having the oldest-order flag enabled is present, and wherein said selector selects the cache entry to be replaced in accordance with the order data when the 1-bit order flag indicates that the cache entry to be replaced has been accessed since each cache entry had been reset and when the cache entry having the oldest-order flag unenabled is present.