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

Claim 2

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.

Claim 3

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

Claim 4

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

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 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 an individual data record.

Claim 18

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.

Claim 19

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

Claim 20

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

Claim 21

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

Claim 22

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

Claim 23

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

Claim 24

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.

Claim 25

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

Claim 26

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.

Claim 27

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.

Claim 28

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.

Claim 29

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.

Claim 30

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.

Claim 31

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

Claim 32

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

Claim 33

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.

Claim 34

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.

Claim 35

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.

Claim 36

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.