Sequential reference management for cache memories

摘要

A cache memory is divided into at least two collections of data which effectively provide higher and lower priority regions for retaining data within the cache. The cache is arranged to divide its stored data into a high-priority (protected) collection of data and a low-priority (probationary) collection of data. Each collection of data is organized as a list, with a most recently used (MRU) end and a least recently used (LRU) end. Data accessed from either of the collections is added to the MRU end of the protected collection, having been removed from its previous place in either of the lists of collections. Data in any of the collections which is least recently used is removed from that collection as space is needed for other data. Newly acquired data, such as retrieved from or written to a mass storage device such as a disk drive is added to the MRU end of the probationary collection. Data which is removed from the protected collection is also added to the MRU end of the probationary collection. In this way, data retrieved from the probationary collection is promoted to the protected collection and if room is needed in the protected collection, then the least recently used data from the protected collection is removed and added (demoted) to the MRU section of the probationary collection to provide a "last chance" for data reuse.