US5787473A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cache management system using time stamping for replacement queue
Assignee: EMC Corp
•
Filing: 1996-09-20
•
Granted: 1998-07-28
•
Expires: 2016-09-20
Abstract
Abstract A shared system memory buffers data transfers between a plurality of host computers and a plurality of data storage devices. The system memory includes a cache memory and a number of queues and structures to facilitate performance. Management of a replacement queue within the system memory is based on the elapsed time and usage of the data element. If the elapsed time of a data element to be updated is less than a threshold, the data element will remain in the same location of the replacement queue; if the elapsed time is greater than the threshold, the data element is placed at the tail of the replacement queue. The threshold may be determined by dynamically monitoring the stress of the cache memory. The updating of the replacement queue is also affected by the number of times the data element has been accessed while in the replacement queue. The memory also includes a pending write data structure which is not part of the replacement queue.
Inventors
- 👤 Natan Vishlitzky
- 👤 Yuval Ofek
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 07:03
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/30; G06F11/34; G06F11/3409; G06F11/3419; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/122; G06F12/123; G06F2201/00; G06F2201/81; G06F2201/88; G06F2201/885; G06F2212/00; G06F2212/50; G06F2212/502
Claims Analysis
Total Claims: 83
Claim 1
Independent Claim
95 words
In a computer-implemented process for a cache memory which stores data elements in a replacement queue having a tail location and other data element storage locations, a method for replacing data elements in the replacement queue, comprising the steps of: time stamping each data element in the replacement queue at the time the data element is placed at the tail of the replacement queue; and, replacing or maintaining each data element based on the elapsed time such data element has been in the replacement queue as determined by the time stamping of such data element.
Claim 2
Dependent Claim
95 words
In a computer-implemented process for a cache memory which stores data elements in a replacement queue having a tail location and other data element storage locations, a method for replacing data elements in the replacement queue, comprising the steps of: time stamping each data element in the replacement queue at the time the data element is placed at the tail of the replacement queue; and, replacing or maintaining each data element based on the elapsed time such data element has been in the replacement queue as determined by the time stamping of such data element.
Claim 3
Dependent Claim
34 words
The method of claim 1, wherein the step of replacing or maintaining each data element is determined by the extent to which the elapsed time exceeds or is less than a predetermined time threshold.
Claim 4
Dependent Claim
29 words
The method of claim 2, wherein if the elapsed time is less than the predetermined threshold, the data element is maintained in its existing location in the replacement queue.
Claim 5
Dependent Claim
28 words
The method of claim 2, wherein if the elapsed time is greater than the predetermined threshold, the data element is placed at the tail of the replacement queue.
Claim 6
Dependent Claim
24 words
The method of claim 1, wherein the time stamp associated with each data element is stored in a memory associated with the cache memory.
Claim 7
Dependent Claim
28 words
The method of claim 5, wherein the time stamp indicates the time at which a non-write pending data element was promoted to the tail of the replacement queue.
Claim 8
Dependent Claim
17 words
The method of claim 6, wherein the tail of the replacement queue represents the most recently-used position.
Claim 9
Dependent Claim
28 words
The method of claim 4, and further including the step of changing the time stamp when the data element is placed at the tail of the replacement queue.
Claim 10
Dependent Claim
27 words
The method of claim 4, and wherein the time stamp is not changed when the elapsed time for a data element does not exceed the predetermined threshold.
Claim 11
Dependent Claim
32 words
The method of claim 2, wherein the predetermined threshold is a function of an average fall through time based on the elapsed time for prior data elements removed from the replacement queue.
Claim 12
Dependent Claim
52 words
The method of claim 10, further including the steps of: calculating the average fall through time, comparing the average fall through time to a fixed time period, and setting the predetermined threshold dependent upon whether the average fall through time is equal to or greater or less than the fixed time period.
Claim 13
Dependent Claim
49 words
The method of claim 11, wherein the predetermined threshold is set to one value if the average fall through time is greater than or equal to the fixed time period and set to a second value if the average fall through time is less than the fixed time period.
Claim 14
Dependent Claim
56 words
The method of claim 12, wherein the values set are a percentage of the average fall through value, and wherein the set value for an average fall through value less than the fixed time period is greater than the set value for an average fall through value greater than or equal to the fixed time period.
Claim 15
Dependent Claim
50 words
The method of claim 11 wherein the fixed time period is a function selected from one or more of the following functions: the size of the replacement cache, the type of data operations, including whether the operations are primarily reads of data elements, read-modify-writes of data elements or sequential operations.
Claim 16
Dependent Claim
35 words
The method of claim 11, and further including the steps of calculating the fall through time for a data element to be updated in the replacement queue, and dynamically recalculating the average fall through time.
Claim 17
Dependent Claim
39 words
The method of claim 15, and further including the step of resetting the predetermined threshold to the second value if the dynamic recalculation of the average fall through time is greater than or equal to the fixed time period.
Claim 18
Dependent Claim
69 words
The method of claim 11, wherein the step of calculating the average fall through time is performed by first determining the fall-through time of a data element being replaced in the replacement cache by the time stamp for that data element and second by using a predetermined routine to determine the average fall through time from the fall-through time of the data element being replaced in the replacement cache.
Claim 19
Dependent Claim
32 words
The method of claim 17, wherein the predetermined routine operates to calculate the average fall-through time as a function of the value of a counter exceeding a predetermined number of data elements.
Claim 20
Dependent Claim
40 words
The method of claim 4, further including the steps of: setting a usage count to a selected number when a data element is placed in the cache memory and incrementing the fixed number each time that data element is accessed.
Claim 21
Dependent Claim
28 words
The method of claim 19, wherein the placement of a data element in the replacement queue is dependent on the number of times data element has been accessed.
Claim 22
Dependent Claim
17 words
The method of claim 20, wherein the number of access times is compared to a threshold number.
Claim 23
Dependent Claim
30 words
The method of claim 21, further including the step of moving the data element to the tail of the replacement queue if the number of accesses exceeds the threshold number.
Claim 24
Dependent Claim
32 words
The method of claim 21, further comprising the step of moving the data element to the head of the replacement queue if the number of accesses is less than the threshold number.
Claim 25
Dependent Claim
43 words
The method of claim 8, and further including the steps of: resetting the usage count to another selected number if the usage count is greater than that of the threshold number; and placing the data element at the tail of the replacement queue.
Claim 26
Dependent Claim
66 words
In a computer-implemented process for a cache memory which stores data elements in cache memory slots in a replacement queue, a method for replacing data elements in the replacement queue, comprising the steps of: determining whether the number of accesses of a data element exceeds a predetermined number; and if the predetermined number is exceeded, moving the data element to the tail of the replacement queue.
Claim 27
Dependent Claim
66 words
In a computer-implemented process for a cache memory which stores data elements in cache memory slots in a replacement queue, a method for replacing data elements in the replacement queue, comprising the steps of: determining whether the number of accesses of a data element exceeds a predetermined number; and if the predetermined number is exceeded, moving the data element to the tail of the replacement queue.
Claim 28
Dependent Claim
46 words
The method of claim 25, further including the step of, if the number of accesses is less than the predetermined number, moving the data element to the front of the replacement queue, the front of the replacement queue indicating the data elements to be next replaced.
Claim 29
Dependent Claim
41 words
The method of claim 26, and further comprising the steps of: resetting a usage count to a fixed number if the usage count is greater than the predetermined number, and; placing the data element at the tail of the replacement queue.
Claim 30
Dependent Claim
96 words
In a cache memory for a computer system which stores data elements in a replacement queue having a tail location and other data element storage locations, a system for replacing data elements in the replacement queue, comprising: means for time stamping each data element in the replacement queue at the time the data element is placed at the tail of the replacement queue; and, means for replacing or maintaining each data element based on the elapsed time such data element has been in the replacement queue as determined by the time stamping of such data element.
Claim 31
Dependent Claim
96 words
In a cache memory for a computer system which stores data elements in a replacement queue having a tail location and other data element storage locations, a system for replacing data elements in the replacement queue, comprising: means for time stamping each data element in the replacement queue at the time the data element is placed at the tail of the replacement queue; and, means for replacing or maintaining each data element based on the elapsed time such data element has been in the replacement queue as determined by the time stamping of such data element.
Claim 32
Dependent Claim
37 words
The system of claim 28, wherein the means for the step of replacing or maintaining each data element is determined by the extent to which the elapsed time exceeds or is less than a predetermined time threshold.
Claim 33
Dependent Claim
29 words
The system of claim 29, wherein if the elapsed time is less than the predetermined threshold, the data element is maintained in its existing slot in the replacement queue.
Claim 34
Dependent Claim
28 words
The system of claim 29, wherein if the elapsed time is greater than the predetermined threshold, the data element is placed at the tail of the replacement queue.
Claim 35
Dependent Claim
26 words
The system of claim 28, wherein the means for time stamping associated with each data element is stored in a memory associated with the cache memory.
Claim 36
Dependent Claim
30 words
The system of claim 32, wherein the means for time stamping indicates the time at which a non-write pending data element was promoted to the tail of the replacement queue.
Claim 37
Dependent Claim
17 words
The system of claim 33, wherein the tail of the replacement queue represents the most recently-used position.
Claim 38
Dependent Claim
29 words
The system of claim 31, and further including means for changing the means for time stamping when the data element is placed at the tail of the replacement queue.
Claim 39
Dependent Claim
28 words
The system of claim 31, and wherein means for time stamping is not changed when the elapsed time for a data element does not exceed the predetermined threshold.
Claim 40
Dependent Claim
32 words
The system of claim 29, wherein the predetermined threshold is a function of an average fall through time based on the elapsed time for prior data elements removed for the replacement queue.
Claim 41
Dependent Claim
55 words
The system of claim 37, further comprising: means for calculating the average fall through time, means for comparing the average fall through time to a fixed time period, and means for setting the predetermined threshold dependent upon whether the average fall through time is equal to or greater or less than the fixed time period.
Claim 42
Dependent Claim
49 words
The system of claim 38, wherein the predetermined threshold is set to one value if the average fall through time is greater than or equal to the fixed time period and set to a second value if the average fall through time is less than the fixed time period.
Claim 43
Dependent Claim
56 words
The system of claim 39, wherein the values set are a percentage of the average fall through value, and wherein the set value for an average fall through value less than the fixed time period is greater than the set value for an average fall through value greater than or equal to the fixed time period.
Claim 44
Dependent Claim
50 words
The system of claim 37 wherein the fixed time period is a function selected from one or more of the following functions: the size of the replacement cache, the type of data operations, including whether the operations are primarily reads of data elements, read-modify-writes of data elements or sequential operations.
Claim 45
Dependent Claim
36 words
The system of claim 38, and further including means for calculating the fall through time for a data element to be updated in the replacement queue, and means for dynamically recalculating the average fall through time.
Claim 46
Dependent Claim
38 words
The system of claim 42, and further including means for resetting the predetermined threshold to the second value if the dynamic recalculation of the average fall through time is greater than or equal to the fixed time period.
Claim 47
Dependent Claim
74 words
The system of claim 38, wherein means for calculating the average fall through time is performed by a first means for determining the fall-through time of a data element being replaced in the replacement cache by the time stamp for that data element and a second means for using a predetermined routine to determine the average fall through time from the fall through time of the data element being replaced in the replacement cache.
Claim 48
Dependent Claim
33 words
The system of claim 44, wherein the predetermined routine includes means for calculating the average fall-through time as a function of the value of a counter exceeding a predetermined number of data elements.
Claim 49
Dependent Claim
41 words
The system of claim 31, further including: means for setting a usage count to a selected number when a data element is placed in the cache memory and means for incrementing the selected number each time that data element is accessed.
Claim 50
Dependent Claim
28 words
The system of claim 46, wherein the placement of a data element in the replacement queue is dependent on the number of times data element has been accessed.
Claim 51
Dependent Claim
17 words
The system of claim 47, wherein the number of access times is compared to a threshold number.
Claim 52
Dependent Claim
29 words
The system of claim 48, further including means for moving the data element to the tail of the replacement queue if the number of access exceeds the threshold number.
Claim 53
Dependent Claim
31 words
The system of claim 48, further comprising means for moving the data element to the head of the replacement queue if the number of accesses is less than the threshold number.
Claim 54
Dependent Claim
42 words
The system of claim 47, and further including: means for resetting the usage count to another selected number if the usage count is greater that the threshold number; and means for placing the data element at the tail of the replacement queue.
Claim 55
Dependent Claim
68 words
In a computer system cache memory which stores data elements in cache memory slots in a replacement queue having a tail, a system for replacing data elements in the replacement queue, comprising: means for determining whether the number of accesses of a data element exceeds a threshold number; and if the threshold number is exceeded, means for moving the data element to the tail of the replacement queue.
Claim 56
Dependent Claim
68 words
In a computer system cache memory which stores data elements in cache memory slots in a replacement queue having a tail, a system for replacing data elements in the replacement queue, comprising: means for determining whether the number of accesses of a data element exceeds a threshold number; and if the threshold number is exceeded, means for moving the data element to the tail of the replacement queue.
Claim 57
Dependent Claim
45 words
The system of claim 52, further including means for, if the number of accesses is less than the threshold number, moving the data element to the front of the replacement queue, the front of the replacement queue indicating the data elements to be next replaced.
Claim 58
Dependent Claim
42 words
The system of claim 53, and further comprising: means for resetting the usage count to a selected number if the usage count is greater than the threshold number, and, means for placing the data element at the tail of the replacement queue.
Claim 59
Dependent Claim
93 words
In a computer system cache memory which stores data elements in cache memory slots in a replacement queue having a tail, a system which replaces data elements in the replacement queue, comprising: a module which time stamps each data element in the replacement queue at the time the data element is placed at the tail of the replacement queue; and a module which replaces or maintains each data element based on the elapsed time such data element has been in the replacement queue as determined by the time stamping of the data element.
Claim 60
Dependent Claim
93 words
In a computer system cache memory which stores data elements in cache memory slots in a replacement queue having a tail, a system which replaces data elements in the replacement queue, comprising: a module which time stamps each data element in the replacement queue at the time the data element is placed at the tail of the replacement queue; and a module which replaces or maintains each data element based on the elapsed time such data element has been in the replacement queue as determined by the time stamping of the data element.
Claim 61
Dependent Claim
37 words
The system of claim 55, wherein the operation of the module to replace or maintain each data element is determined by the extent to which the elapsed time exceeds or is less than a predetermined time threshold.
Claim 62
Dependent Claim
29 words
The system of claim 56, wherein if the elapsed time is less than the predetermined threshold, the data element is maintained in its existing slot in the replacement queue.
Claim 63
Dependent Claim
28 words
The system of claim 56, wherein if the elapsed time is greater than the predetermined threshold, the data element is placed at the tail of the replacement queue.
Claim 64
Dependent Claim
71 words
In a computer-implemented process for a cache memory which stores data elements in cache memory slots in a replacement queue having a tail, a system which replaces data elements in the replacement queue, comprising: a module which determines whether the number of accesses of a data element exceeds a threshold number; and if the threshold number is exceeded, the module moves the data element to the tail of the replacement queue.
Claim 65
Dependent Claim
71 words
In a computer-implemented process for a cache memory which stores data elements in cache memory slots in a replacement queue having a tail, a system which replaces data elements in the replacement queue, comprising: a module which determines whether the number of accesses of a data element exceeds a threshold number; and if the threshold number is exceeded, the module moves the data element to the tail of the replacement queue.
Claim 66
Dependent Claim
44 words
The system of claim 59, wherein the module, if the number of accesses is less than the threshold number, moves the data element to the front of the replacement queue, the front of the replacement queue indicating the data elements to be next replaced.
Claim 67
Dependent Claim
38 words
The system of claim 60, wherein the module resets the usage count to a fixed number if the usage count is greater than the threshold number, and places the data element at the tail of the replacement queue.
Claim 68
Dependent Claim
106 words
A computer readable medium in the form of a cache memory which stores data elements in cache memory slots in a replacement queue, a system which replaces data elements in the replacement queue, comprising: a first module in the computer readable medium which time stamps each data element in the replacement queue at the time the data element is placed at the tail of the replacement queue; a second module in the computer readable medium which replaces or maintains each data element based on the elapsed time such data element has been in the replacement queue as determined by the time stamping of such data element.
Claim 69
Dependent Claim
106 words
A computer readable medium in the form of a cache memory which stores data elements in cache memory slots in a replacement queue, a system which replaces data elements in the replacement queue, comprising: a first module in the computer readable medium which time stamps each data element in the replacement queue at the time the data element is placed at the tail of the replacement queue; a second module in the computer readable medium which replaces or maintains each data element based on the elapsed time such data element has been in the replacement queue as determined by the time stamping of such data element.
Claim 70
Dependent Claim
33 words
The medium of claim 62, wherein whether each data element is replaced or maintained is determined by the extent to which the elapsed time exceeds or is less than a predetermined time threshold.
Claim 71
Dependent Claim
29 words
The medium of claim 63, wherein if the elapsed time is less than the predetermined threshold, the data element is maintained in its existing slot in the replacement queue.
Claim 72
Dependent Claim
28 words
The medium of claim 63, wherein if the elapsed time is greater than the predetermined threshold, the data element is placed at the tail of the replacement queue.
Claim 73
Dependent Claim
77 words
A computer readable medium in the form of a cache memory which stores data elements in cache memory slots in a replacement queue having a tail, a system which replaces data elements in the replacement queue, comprising: a module in the medium which determines whether the number of accesses of a data element exceeds a threshold number; and if the threshold number is exceed, the medium moves the data element to the tail of the replacement queue.
Claim 74
Dependent Claim
77 words
A computer readable medium in the form of a cache memory which stores data elements in cache memory slots in a replacement queue having a tail, a system which replaces data elements in the replacement queue, comprising: a module in the medium which determines whether the number of accesses of a data element exceeds a threshold number; and if the threshold number is exceed, the medium moves the data element to the tail of the replacement queue.
Claim 75
Dependent Claim
44 words
The medium of claim 66, further including, if the number of accesses is less than the threshold number, the data element is moved to the front of the replacement queue, the front of the replacement queue indicating the data elements to be next replaced.
Claim 76
Dependent Claim
125 words
A data storage system comprising: a plurality of host computers and a plurality of data storage devices; a system memory coupled to said host computers and to said storage devices for buffering data elements provided by said host computers, said system memory comprising: a cache memory for storing data elements to be transferred between the host computers and the data storage devices; a cache memory manager including a number of queues for managing the status of the data elements stored in the system memory; a cache index directory for storing at least pointers to the data element in said cache memory and for providing indications of the status of the data elements stored in cache memory; and said cache index directory including a usage indicator.
Claim 77
Dependent Claim
125 words
A data storage system comprising: a plurality of host computers and a plurality of data storage devices; a system memory coupled to said host computers and to said storage devices for buffering data elements provided by said host computers, said system memory comprising: a cache memory for storing data elements to be transferred between the host computers and the data storage devices; a cache memory manager including a number of queues for managing the status of the data elements stored in the system memory; a cache index directory for storing at least pointers to the data element in said cache memory and for providing indications of the status of the data elements stored in cache memory; and said cache index directory including a usage indicator.
Claim 78
Dependent Claim
126 words
A data storage system comprising: a plurality of host computers and a plurality of data storage devices; a system memory coupled to said host computers and to said storage devices for buffering data elements provided by said host computers, said system memory comprising: a cache memory for storing data elements to be transferred between the host computers and the data storage devices; a cache memory manager including a number of queues for managing the status of the data elements stored in the system memory; a cache index directory for storing at least pointers to the data element in said cache memory and for providing indications of the status of the data elements stored in cache memory; and said cache index directory including a time stamp indicator.
Claim 79
Dependent Claim
126 words
A data storage system comprising: a plurality of host computers and a plurality of data storage devices; a system memory coupled to said host computers and to said storage devices for buffering data elements provided by said host computers, said system memory comprising: a cache memory for storing data elements to be transferred between the host computers and the data storage devices; a cache memory manager including a number of queues for managing the status of the data elements stored in the system memory; a cache index directory for storing at least pointers to the data element in said cache memory and for providing indications of the status of the data elements stored in cache memory; and said cache index directory including a time stamp indicator.
Claim 80
Dependent Claim
35 words
The system as defined in claim 68, wherein the usage indicator in the cache index directory is updated each time a data element in the cache memory is accessed by one of the host computers.
Claim 81
Dependent Claim
33 words
The system as defined in claim 69, wherein the time stamp indicator is updated each time the data element is placed at the tail of a replacement queue in the cache memory manager.
Claim 82
Independent Claim
58 words
The system as defined in either of claims 68 or 69, wherein the cache memory manager includes a replacement queue for identifying a potential cache slot to store the next data element to be placed in the cache memory, and a pending write data structure for storing data elements associated with a write request from the host computers.
Claim 83
Dependent Claim
59 words
The system as defined in claim 72, wherein the cache memory manager further includes a stage request data structure for storing stage request messages issued between the host computers and the storage devices and a stage completion data structure for generating an interrupt signal to the host computers upon the completion of the command issued by the host computer.
References Cited (Backward Citations)
US5511188A
Cited
US5206939A
Cited
US5305389A
Cited
US5537568A
Cited
US5483468A
Cited
US5606688A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-27 | 2002-01-26 | 2002-07-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-27 | 2006-01-26 | 2006-07-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-27 | 2010-01-26 | 2010-07-28 | $7700.00 | Window Closed / Lapsed |