Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-06-09
2004-05-18
Bataille, Pierre Michel (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S145000, C711S159000, C711S207000
Reexamination Certificate
active
06738865
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method, system, and program for managing data in cache and selecting cache entries for demotion to make room for subsequently accessed data.
2. Description of the Related Art
In a memory cache, pages or tracks of data are copied from a storage device, such as a hard disk drive or other non-volatile storage device typically comprised of a magnetic medium, and placed into a volatile, electronic memory area referred to as cache. When tracks or data are accessed from the storage device they are loaded into cache and returned to the application requesting the data. Because the accessed data remains in cache, a subsequent request for the data can be returned from cache, which is substantially faster than retrieving the data from the storage device. Returning data from cache, referred to as a cache hit, improves performance and system throughput because a cache memory by definition provides faster access to data. A cache may also be used to provide faster access to a main volatile memory, such as a random access memory (RAM). For instance, many processors include an “on-board” cache that caches data from RAM for the processor to use and subsequently access from the faster cache memory. In both cases, disk caching and memory caching, the cache provides a high speed memory from which data may be returned faster than the storage device or main memory where the data is maintained.
After the cache utilization reaches a certain upper limit, the cache manager will demote data from cache to make room for subsequently accessed tracks. Areas of cache marked as demoted may then be overwritten by new data, thus making room for data more recently accessed from storage. In the prior art, a least recently used (LRU) algorithm is used as follows. When a track is added to a cache, a pointer to the track in cache is placed at a top of the LRU linked list. If a track already in cache is again accessed, then the pointer to that track in cache is placed at the top of the LRU list. When the cache manager determines that data must be demoted or removed from cache to make room for subsequent data accesses, the cache manager will demote tracks whose pointers are at the bottom of the list, representing those tracks that were accessed the longest time ago relative to other tracks in cache.
This prior art LRU approach works sufficiently well with sequentially accessed data, that is data that is accessed contiguously. However, such LRU algorithms are not optimal for randomly accessed data, that is tracks of storage accessed out of sequence. In such case, a demoted track in cache, even though it is the least recently accessed, may have been accessed more frequently than other tracks and is, thus, more likely to be subsequently accessed than those tracks in cache less frequently accessed. Thus, the LRU approach does not consider the frequency of access to cache entries when selecting entries for demotion.
Thus, there is a need in the art to improve cache hits, i.e., the read requests returned from cache to increase performance and data throughput.
SUMMARY OF THE PREFERRED EMBODIMENTS
To overcome the limitations in the prior art described above, preferred embodiments disclose a method, system, and program for caching data. Data from a device, such as a volatile memory device or non-volatile storage device, is maintained in entries in a cache. For each entry in cache, a variable indicates both a time when the cache entry was last accessed and a frequency of accesses to the cache entry.
In further embodiments, a determination is made when a number of entries in cache has reached a threshold. In response to reaching the threshold, a determination is made of a plurality of cache entries having a relatively low value for the variable with respect to the value of the variable for other cache entries. A relatively low variable value indicates that the cache entry is one of a least recently accessed entry and/or least frequently accessed entry. Those determined cache entries having the relatively low value for the variable are demoted from cache.
In still further embodiments, the variable for a cache entry is increased whenever the cache entry is accessed.
Preferred embodiments provide an algorithm and data structures for maintaining for each cache entry a ranking or variable indicating a time when the entry was last accessed and the number of accesses relative to other cache entries. This variable is used in determining which entries to demote from cache to make room for subsequently accessed data. Preferred embodiments would tend to demote among the entries that were least recently accessed those entries that are less frequently accessed. This methodology improves the cache hit ratio because an entry that is more frequently accessed relative to another entry is more likely to be accessed again in the future. Thus, the preferred methodology would select for demotion those entries less likely to be accessed in the future with respect to other entries. This is an improvement over prior art techniques that do not take into account the frequency of access when demoting cache entries.
REFERENCES:
patent: 5150472 (1992-09-01), Blank et al.
patent: 5432917 (1995-07-01), Parikh
patent: 5481691 (1996-01-01), Day, III et al.
patent: 5682500 (1997-10-01), Vishlitzky et al.
patent: 5751993 (1998-05-01), Ofek et al.
patent: 5761717 (1998-06-01), Vishlitzky et al.
patent: 5778442 (1998-07-01), Ezzat et al.
patent: 5924116 (1999-07-01), Aggarwal et al.
patent: 6012126 (2000-01-01), Aggarwal et al.
patent: 6266742 (2001-07-01), Challenger et al.
patent: 6378043 (2002-04-01), Girkar et al.
patent: 6470419 (2002-10-01), Take et al.
patent: 6487638 (2002-11-01), Dawkins et al.
patent: 604015 (1993-11-01), None
patent: 604015 (1993-11-01), None
patent: 60-214060 (1985-10-01), None
patent: 63-199344 (1988-12-01), None
patent: 04-051342 (1992-02-01), None
patent: 04-077844 (1992-03-01), None
patent: 04-314150 (1992-11-01), None
patent: 05-040698 (1993-02-01), None
patent: 06-083713 (1994-03-01), None
patent: 06-089221 (1994-03-01), None
patent: 7-506923 (1995-07-01), None
patent: 08-044625 (1996-02-01), None
patent: 08-069418 (1996-03-01), None
patent: 10-269028 (1998-10-01), None
patent: 11-065862 (1999-03-01), None
patent: 2000035934 (2000-02-01), None
patent: 2000-047942 (2000-02-01), None
patent: 2000-148515 (2000-05-01), None
patent: 2003044510 (2003-02-01), None
Application No. 2001-170848, “Notification of Reasons for Refusal”, Apr. 2003.*
Great Britain Search Report, date of search Feb. 14, 2002.
Burton David Alan
Webman Erez
Bataille Pierre Michel
International Business Machines - Corporation
Konrad Raynes & Victor LLP
Victor David W.
LandOfFree
Method, system, and program for demoting data from cache... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, and program for demoting data from cache..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and program for demoting data from cache... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3186645