Importance

Loading Importance Indicators...

Abstract

A cache system controls the insertion and deletion of data items using a plurality of utilization lists. When a data item is stored within the data cache, a corresponding data pointer, or other indicator, is stored within the utilization list in a manner indicative of the sequence in which data items were stored in the data cache. When a data item is subsequently retrieved from the data cache, the corresponding data pointer may be altered or moved to indicate that the data item has recently been retrieved. The data pointers corresponding to data items that have never been retrieved will indicate the sequence with which the data items were stored in the cache such that data items may be identified as least recently used (LRU) data items. The data pointers corresponding to data items that have been retrieved provide an indication of the sequence with which the data items have been retrieved such that the most recently retrieved data item is considered the most recently used (MRU) data item. The system controls the deletion of data items from the cache by deleting the LRU data items. A large number of utilization lists may operate independently to accommodate a large number of users. An entry pointer selects one of the utilization lists to store the data pointer corresponding to a data item stored within the cache. A deletion pointer selects one of the utilization lists. The system deletes the LRU data item based on the utilization list currently selected by the deletion pointer.

Loading the Abstract Image...

First Claim