System and method for determining what position in cache memory to store data elements

Abstract

A cache management system and method monitors and controls the contents of cache memory. A time indication provider provides a time indication signal to a cache indexer, for maintaining a cache index which are stored in cache as well as an indication that a data element must be written to a longer term data storage device. A cache manager is responsible for placing data elements into and removing data elements from the cache memory. The cache manager is responsive to at least one data element stored in cache which must be written to a longer term data storage device, and to the associated time indication, for determining the amount of time that the data element has been stored in cache as well as the average period of time that elapses between a data element being inserted in cache and being removed from cache. Based on a comparison of the average period of time that elapses between a data element being entered into and removed from cache and the amount of time that the data element which is written to a longer term data storage device has been stored in cache, the cache manager determines whether to place the data element in the top of the cache, to allow the data element to remain in cache a longer period of time, or at the bottom of the cache which will cause the date element to be removed from cache more quickly.

What is claimed is: 
     
       1. In a cache for a computer system for storing data elements in a first cache section and a second cache section, the data elements in the second section including least recently used and last recently used data elements, a computer implemented method of controlling the contents of the second cache section comprising the steps of: (A) determining the amount of time a first data element was resident in the first cache section;   (B) determining the average elapsed period of time at least a second data element is resident in the second cache section;   (C) comparing the amount of time determined in step (A) with the period of time determined in step (B); and,   (D) if the amount of time determined in step (A) is greater that the period of time determined in step (B), placing the first data element from the first cache section into the second cache section as a least recently used data element.   
     
     
       2. The method of claim 1, further comprising the step of: (E) if the amount of time determined in step (A) is less than the period of time determined in step (B), placing the first data element from the first cache section into the second cache section as a last recently used element.   
     
     
       3. The method of claim 2, further comprising the stepwise movement of the data element placed in the second cache section as a last recently used element to the least recently used element before the data element is discarded in accordance with a least recently use (LRU) routine. 
     
     
       4. The method of claim 2, further including the step of overwriting the least recently used data element when the first data element is placed in the second cache section as the last recently used data element. 
     
     
       5. The method of claim 2 wherein step (B) further comprises the step of determining, for a plurality of data elements, an average period of time that elapses between a data element being inserted in said second cache memory section as a last recently used data element and said data element being removed from said second cache memory section as the least recently used data element. 
     
     
       6. The method of claim 1, further including the step of discarding the data element which meets the requirement of step (D) from the second cache section in accordance with a least recently used (LRU) routine. 
     
     
       7. The method of claim 1, wherein the first cache section contains data elements awaiting writing to a data storage device and the second cache section contains data elements which have been written to the data storage device. 
     
     
       8. The method of claim 1, wherein the average elapsed period of substep (B) includes determining the elapsed time from the time a data element is inserted in the second cache section as a last recently used data element and the data element is removed from the second cache section as the least recently used data element. 
     
     
       9. The method of claim 1 further comprising the step of determining the number of times each a data element in the first cache section has been read, and wherein, if the number of times the data element has been read exceeds one, the data element is placed in the second cache section as a last recently used element without a comparison of the average amount of time that elapses with the period of time the data element was stored in the first data cache. 
     
     
       10. In a cache for a computer system, the cache storing data elements in a first cache section and a second cache section, the data elements in the second section including least recently used and last recently used data elements, apparatus for controlling the contents of the second cache section comprising: (A) means for determining the amount of time a first data element was resident in the first cache section;   (B) means for determining the average elapsed period of time at least a second data element is resident in the second cache section;   (C) means for comparing the amount of time determined in step (A) with the period of time determined in step (B); and,   (D) if the amount of time determined in step (A) is greater that the period of time determined in step (B), means for placing the first data element from the first cache section into the second cache section as a least recently used data element;   
     
     
       11. The cache of claim 10, further comprising: (E) if the amount of time determined by the means for determining in (A) is less than the period of time determined by the means for determining in (B), means for placing the first data element from the first cache section into the second cache section as a last recently used element.   
     
     
       12. The cache of claim 11, frther comprising means for providing the stepwise movement of the data element placed in the second cache section as a last recently used element to the least recently used element before the data element is discarded in accordance with a least recently use (LRU) routine. 
     
     
       13. The cache of claim 11, further including means for overwriting the least recently used data element when the first data element is placed in the second cache section as the last recently used data element. 
     
     
       14. The cache of claim 11 further comprising means for determining, for a plurality of data elements, an average period of time that elapses between a data element being inserted in said second cache memory section as a last recently used data element and said data element being removed from said second cache memory section as the least recently used data element. 
     
     
       15. The cache of claim 10, further including means for discarding the data element which meets the requirement of D) from the second cache section in accordance with a least recently used (LRU) routine. 
     
     
       16. The cache of claim 10, wherein the first cache section contains data elements awaiting writing to a data storage device and the second cache section contains data elements which have been written to the data storage device. 
     
     
       17. The cache of claim 10, wherein the means for determining the average elapsed period of (B) includes means for determining the elapsed time from the time a data element is inserted in the second cache section as a last recently used data element and the data element is removed from the second cache section as the least recently used data element. 
     
     
       18. The cache of claims further comprising means for determining the number of times each a data element in the first cache section has been read, and wherein, if the number of times the data element has been read exceeds one, the data element is placed in the second cache section as a last recently used element without a comparison of the average amount of time that elapses with the period of time the data element was stored in the first data cache.