Method and apparatus for controlling the contents of a cache memory

• US 6,049,850 A
• Filed: 05/27/1997
• Issued: 04/11/2000
• Est. Priority Date: 06/04/1992
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Vishlitzky, Natan, Kopylovitz, Haim
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US08/863,262
• Time in Patent Office: 1,050 Days
• Field of Search: 711/113, 711/136, 711/159, 711/160, 711/129, 711/137
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/502 using adaptive policy
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: Y10S 427/104 Utilizing low energy electromagnetic radiation, e.g. microwave, radio wave, IR, UV, visible, actinic laser

Abstract

A cache management system and method monitors and controls the contents of cache memory coupled to at least one longer term data storage device. Cache memory is organized into at least first and second sections, the first section for storing data waiting to be written to a longer term data storage device and the second section for storing data elements which have been written to the longer term data storage device. The cache management system and method monitors data elements awaiting writing to the longer term data storage device. Once the elements have been actually written to the longer term data storage device, the cache management system and method utilizes an indication of the amount of time the data element was in cache as well as an indication of the number of times the data element was accessed, in order to determine how long to maintain the data record in the short term cache

Claims

1. In a cache for a computer system, the cache storing data elements in cache, the data elements including an indication of when each data element was placed into the cache, a computer implemented process for controlling the contents of the cache, comprising the steps of:

(A) determining those data elements that have not been written to at least one storage device;

(B) determining the time between when a first data element was placed into the cache and when a second data element was placed into the cache; and

if the amount of time determined in step (B) is less than a pre-established value, and after retrieving additional data elements from the at least one storage device and storing the retrieved data elements in the cache, replacing at least one data element in the cache.

2. The method of claim 1, further comprising the step of

if the amount of time determined in step (B) is greater than or equal to the pre-established value, keeping the at least one data element in the cache.

3. The method of claim 1, further comprising the step of:

replacing a last recently used data element in accordance with a least recently used (LRU) routine.

4. The method of claim 3, wherein the cache contains data elements that have been written to the at least one storage device.

5. The method of claim 4, further comprising the step of:

prior to step (A) establishing first and second cache sections, wherein the data elements that have not been written to the at least one storage device are stored in one cache section and the data elements that have been written to the at least one storage device are stored in the other cache section.

6. The method of claim 5, further comprising the step of:

determining that those data elements which have not been written to the at least one storage device are ready to be written to the at least one storage device.

7. The method of claim 6, further comprising the step of:

writing those data elements which have not been written to the at least one storage device to the at least one storage device.

8. The method of claim 7, further comprising the step of:

prior to writing the at least one data element to the at least one storage device, writing the at least one data element from the second cache section to the first cache section.

9. The method of claim 8, further comprising the steps of:

after the at least one data element has been written to the at least one storage device, determining the amount of time the at least one data element remains in the cache; and

if the amount of time is greater than a pre-established value, replacing the at least one data element in the cache.

10. The method of claim 8, further comprising the steps of:

after the at least one data element has been written to the at least one storage device, determining the amount of time the at least one data element remains in the cache;

if the amount of time is less than or equal to a pre-established value, retaining the at least one data element data element in the cache; and

if the amount of time is greater than the pre-established value, replacing the at least one data element in the cache.

11. The method of claim 1, further comprising the steps of:

determining that a sequential data access by at least one of a plurality of computer processes is in progress; and

indicating that the sequential data access by the at least one of a plurality of computer processes is in progress.

12. The method of claim 11, further comprising the step of:

placing a pre-determined number of data elements into the cache.

13. The method of claim 12, further comprising the step of:

determining if the at least one data element have been accessed by at least one of a plurality of computer processes.

14. The method of claim 13, further comprising the step of:

increasing the number of pre-determined elements to be placed into the cache if the at least one data element has been accessed by the at least one of the plurality of computer processes.

15. The method of claim 13, further comprising the step of:

decreasing the number of pre-determined elements to be placed into the cache if the at least one data element has not been accessed by the at least one of the plurality of computer processes.

16. In a cache for a computer system, the cache storing data elements, the data elements including an indication of when each data element was placed into the cache, an apparatus for controlling the contents of the cache comprising:

means for determining those data elements that have not been written to at least one storage device;

means for determining the time between when a first data element was placed into the cache and when a second data element was placed into the cache; and

means for replacing at least one data element in the cache if the amount of time between when the first data element was placed into the cache and when the second data element was placed into the cache is less than a pre-established value, and after retrieving additional data elements from the at least one storage device and storing the retrieved data elements in the cache.

17. The apparatus of claim 16, further comprising:

means for keeping the at least one data element in the cache if the amount of time determined by the means for determining the time is greater than or equal to the pre-established value.

18. The apparatus of claim 16, further comprising:

means for replacing a last recently used data element in accordance with a least recently used (LRU) routine.

19. The apparatus of claim 18, wherein the cache contains data elements that have been written to the at least one storage device.

20. The apparatus of claim 19, further comprising:

means for establishing first and second cache sections, wherein the data elements that have not been written to the at least one storage device are stored in one cache section and the data elements that have been written to the at least one storage device are stored in the other cache section.

21. The apparatus of claim 20, further comprising:

means for determining that those data elements which have not been written to the at least one storage device are ready to be written to the at least one storage device.

22. The apparatus of claim 21, further comprising:

means for writing those data elements which have not been written to the at least one storage device to the at least one storage device.

23. The apparatus of claim 22, further comprising:

means for writing the at least one data element from the second cache section to the first cache section prior to writing the at least one data element to the at least one storage device.

24. The apparatus of claim 22, further comprising:

means for determining the amount of time the at least one data element remains in the cache after the at least one data element has been written to the at least one storage device; and

means for replacing the at least one data element in the cache if the amount of time is greater than a pre-established value.

25. The apparatus of claim 22, further comprising:

means for determining the amount of time the at least one data element remains in the cache after the at least one data element has been written to the at least one storage device;

means for retaining the at least one data element in the cache if the amount of time is less than or equal to a pre-established value; and

means for replacing the at least one data element in the cache if the amount of time is greater than the pre-established value.

26. The apparatus of claim 16, further comprising:

means for determining that a sequential data access by at least one of a plurality of computer processes is in progress; and

means for indicating that the sequential data access by the at least one of a plurality of computer processes is in progress.

27. The apparatus of claim 26, further comprising:

means for determining if the at least one data element has been accessed by at least one of a plurality of computer processes.

28. The apparatus of claim 27, further comprising:

means for increasing the number of pre-determined elements to be placed into the cache if the at least one data element has been accessed by the at least one of the plurality of computer processes.

29. The apparatus of claim 27, further comprising:

means for decreasing the number of pre-determined elements to be placed into the cache if the at least one data element has not been accessed by the at least one of the plurality of computer processes.

30. The apparatus of claim 16, further comprising:

means for placing a pre-determined number of data elements into the cache.