System and method for determining when and what position in cache memory to store data elements utilizing least and last accessed data replacement method

• US 5,513,336 A
• Filed: 12/12/1994
• Issued: 04/30/1996
• 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): Kim, Matthew M.
• Application Number:
  US08/354,479
• Time in Patent Office: 505 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/403, 395/440, 395/460, 395/461, 395/463
• 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. Cache memory is organized into at least a first section for storing data waiting to be written to a longer term data storage device, and a second section for storing data elements which have been written to the longer term data storage device. A time indication provider provides a time indication signal to a cache indexer, for maintaining a cache index representing data elements 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 determimes 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 a data element spends in cache, and the amount of time a data element spends in cache, and the amount of time that the element 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 data element to be removed from cache more quickly.

Claims

1. A cache management system including a cache manager, for monitoring and controlling contents of a cache memory coupled to at least one longer term data storage device, said cache management system comprising:

said cache memory including a first cache memory section, for storing data elements awaiting writing to said at least one longer term data storage device, and a second cache memory section for storing data elements which have been written to said at least one longer term data storage device, said data elements stored in said second cache memory section including a last recently used data element and a least recently used data element, said last recently used data element moveable, over time, in said second cache memory section to become said least recently used data element;

a time indicator, for providing a time indication signal;

a cache indexer, responsive to said time indication signal, for maintaining a cache index of data elements which are stored in at least said first and second cache memory sections, said cache index of data elements including a time indication associated with each data element indexed in said cache index by said cache indexer; and

a cache manager for placing data elements into and removing data elements from said first and second cache memory sections, said cache manager responsive to at least one data element stored in said first cache memory section and written to said at least one longer term data storage device, and responsive to said time indication associated with each data element stored in said cache and indexed in said cache index by said cache indexer, for determining an average period of time that elapses between at least one data element being inserted into said second cache memory section as a last recently used data element, and said at least one data element inserted into said second cache memory section as a last recently used data element being removed from said second cache memory section as said least recently used data element, and for determining a period of time that said at least one data element was stored in said first cache memory section, for comparing said average period of time that elapses with said period of time said at least one data element was stored in said second cache memory section, for placing said at least one data element into said second cache memory section as a last recently used data element if said period of time is less than said average period of time that elapses, and for placing said at least one data element into said second cache memory section as a least recently used data element if said period of time is greater than said average period of time that elapses.

2. The cache management system of claim 1, wherein said at least one longer term data storage device includes at least one disk drive.

3. The cache management system of claim 2, wherein said data elements include disk drive tracks.

4. The cache management system of claim 1, wherein said cache manager determines, 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 said least recently used data element.

5. The cache management system of claim 1, wherein said system includes a plurality of coupled longer term data storage devices;

and

wherein said cache indexer maintains only one cache index.

6. The cache management system of claim 1, wherein said cache manager determines if said average period of time is greater than or less than two times said average period of time that elapses.

7. The cache management system of claim 1, wherein said cache index includes a data element access counter, for providing an indication of a number of times each data element stored in said first cache memory section has been read;

and

wherein if said cache manager determines a number of times a data element has been read while stored in said first cache memory section and, if said number of times said data element has been read is greater than one, said cache manager places said at least one data element into said second cache memory section as a said last recently used data element without comparison of said average period of time that elapses with said period of time said data element was stored in said first cache memory section.

8. The cache management system of claim 1, wherein said cache indexer maintains a cache index indicating data elements which are retrieved from said at least one longer term data storage device and stored in said cache memory.

9. The cache management system of claim 8, wherein said time indication associated with each element indexed in said cache index includes a time of retrieval of an associated data element from said at least one longer term data storage device.

10. The cache management system of claim 1 further including:

a sequential data access indicator, responsive to said cache index, for detecting at least first and second sequential data elements stored in said cache memory, and responsive to said detection of a plurality of sequential data elements stored in said cache memory, to a user selectable sequential data access indicator threshold value, and to a comparison of said time indications associated with at least said first and second sequential data elements, for providing an indication that at least one process executing on at least one host coupled to said at least one longer term data storage device is effecting a sequential data access.

11. The cache management system of claim 10, further including:

a data retrieval requestor, responsive to said indication that at least one process executing on at least one host coupled to said at least one longer term data storage device is effecting a sequential data access, and responsive to a user selectable value of a predetermined number of data elements to be prefetched, for requesting retrieval from said at least one longer term data storage device of up to a number of data elements equal to the value of said user selectable predetermined number of data elements to be prefetched; and

a cache data replacer, responsive to a user selectable value of a predetermined maximum number of sequential data elements to be stored in said second section of cache memory for use by said at least one process effecting a sequential data access, and to said data retrieval requestor requesting retrieval of a data element, for requesting replacement of at least one least recently used sequential data element stored in said second section of said cache memory.

12. The cache management system of claim 10, wherein said sequential data access indicator provides an indication of the termination of a sequential data access in effect by said at least one process upon detection of non-sequential data elements requested by said at least one process and stored in said cache memory.

13. The cache management system of claim 12, wherein said one cache index is organized on a longer term data storage device by longer term data storage device basis.

14. The cache management system of claim 11, wherein said selectable sequential data access indicator threshold value and the value of said selectable predetermined number of data elements to be prefetched are user selectable for each longer term data storage device coupled to the cache management system.

15. The cache management system of claim 1, wherein said cache indexer maintains a cache index for each longer term data storage device coupled to said cache management system.

16. The cache management system of claim 1, wherein each of said data elements retrieved from said at least one longer term data storage device include an individual data record.

17. The cache management system of claim 1, wherein each of said data elements retrieved from said at least one longer term data storage device include all data records stored in one data storage unit of said data storage device;

and

wherein said cache indexer maintains a current index of a plurality of data storage units stored in said cache memory.

18. The cache management system of claim 17, wherein said at least one longer term data storage device includes at least one disk drive.

19. The cache management system of claim 18, wherein said data storage unit of said data storage device includes a disk drive track.

20. The cache management system of claim 18, wherein said data storage unit of said data storage device includes a disk drive cylinder.

21. The cache management system of claim 1, wherein said at least one data storage device includes at least one optical disk.

22. The cache management system of claim 1, wherein said cache memory includes a high-speed semiconductor memory.

23. The cache management system of claim 1, wherein said cache management system further includes at least one data storage device controller including said cache manager.

24. The cache management system of claim 1, wherein said cache management system further includes at least one host adapter including said cache manager.

25. The cache management system of claim 11, wherein said cache management system includes one system wide cache memory;

and

wherein said cache management system establishes and maintains at least one micro-second cache memory section having a predetermined number of memory locations for use by said at least one process effecting a sequential data access, and said predetermined number of memory locations corresponding to said user selectable value of a predetermined maximum number of sequential data elements to be stored in said cache memory.

26. The cache management system of claim 25, wherein said data retrieval requestor requests storage of said prefetched data elements in said at least one micro second-cache-memory section;

and

wherein said cache data replacer requests replacement of the least recently used sequential data element stored in said at least one micro second-cache-memory section.

27. The cache management system of claim 25, wherein said cache management system includes a plurality of processes effecting a sequential data access;

and

wherein said cache management system establishes and maintains one micro second-cache-memory section for each of said plurality of processes effecting a sequential data access.

28. The cache management system of claim 25, wherein said at least one micro second-cache-memory section is established and maintained for exclusive use by only said at least one process during the effecting of a sequential data access.

29. The cache management system of claim 28, wherein said cache management system returns the predetermined number of memory locations of said at least one micro second-cache-memory section to, and for use by, said system wide cache memory upon an indication of the termination of a sequential data access in effect by said at least one process, said indication of the termination of a sequential data access provided by said sequential data access indicator upon detection of non-sequential data elements requested by said at least one process.

30. The cache management system of claim 1, wherein said time indication includes a real time indication.

31. The system of claim 1, wherein said time indication includes a relative time indication.

32. A cache management system including a cache manager, for monitoring and controlling contents of a cache memory coupled to at least one longer term data storage device, said cache management system comprising:

said cache memory including a first cache memory section, for storing data elements awaiting writing to said at least one longer term data storage device, and a second cache memory section for storing data elements which have been written to said at least one longer term data storage device, said data elements stored in said second cache memory section including a last recently used data element and a least recently used data element, said last recently used data element moveable, over time, in said second cache memory section to become said least recently used data element;

a time indicator, for providing a time indication signal;

a cache indexer, responsive to said time indication signal, for maintaining a cache index of data elements which are stored in at least said first and second cache memory sections, said cache index of data elements including a time indication associated with each data element indexed in said cache index by said cache indexer, said cache index including a data element access counter providing an indication of a number of times said data element has been read while stored in said first cache memory section;

a sequential data access indicator, responsive to said cache index, for detecting a plurality of sequential data elements stored in said cache memory, and responsive to said detection of a plurality of sequential data elements stored in cache memory, to a user selectable sequential data access indicator threshold value, and to a comparison of said time indications associated with at least first and second sequential data elements of said plurality of detected sequential data elements, for providing an indication that at least one process executing on said at least one host is effecting a sequential data access; and

said cache manager for placing data elements into and removing data elements from said first and second cache memory sections, said cache manager responsive to at least one data element stored in said first cache memory section and written to said at least one longer term data storage device, and responsive to said indication of said number of times said data element has been read while stored in said first memory section included in said cache index, for determining a number of times the data element has been accessed while stored in said first cache memory section, and if said number of times said data element has been accessed is greater than one, for placing said at least one data element into said second cache memory section as a least recently used element.

33. A cache management method, for monitoring and controlling contents of a cache memory coupled to at least one host and to at least one data storage device, said cache management method comprising:

providing said cache memory including a first cache memory section, for storing data elements awaiting writing to said at least one longer term data storage device, and a second cache memory section for storing data elements which have been written to said at least one longer term data storage device, said data elements stored in said second cache memory section including a last recently used data element and a least recently used data element, said last recently used data element moveable, over time, in said second cache memory section to become said least recently used data element;

providing a time indicator, for providing a time indication signal;

providing a cache indexer, responsive to said time indication signal, for maintaining a cache index of data elements which are stored in at least said first and second cache memory sections, said cache index of data elements including a time indication associated with each data element indexed in said cache index by said cache indexer;

providing a cache manager, responsive to said time indication associated with each data element stored in said cache and indexed in said cache index by said cache indexer, said cache manager determining an average period of time that elapses between at least one data element being inserted into said second cache memory section as a last recently used data element, and said at least one data element inserted into said second cache memory section as a last recently used data element being removed from said second cache memory section as said least recently used data element;

determining a period of time that said at least one data element was stored in said first cache memory section;

comparing said average period of time that elapses with said period of time said at least one data element was stored in said first cache memory section;

placing said at least one data element into said second cache memory section as a last recently used data element if said period of time is less than said average period of time that elapses; and

placing said at least one data element into said second cache memory section as a least recently used data element if said period of time is greater than said average period of time that elapses.