US6141731A — Method and system for managing data in cache usin…

Claim 1

Independent Claim 151 words

A method for caching data, comprising the steps of: providing a first and second data structures indicating data entries in a cache, wherein each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure; receiving a new data entry; processing the first and second data structures to determine a LRU data entry in each data structure; selecting from the determined LRU data entries the LRU data entry that is the least recently used; demoting the selected LRU data entry from the cache and data structure including the selected data entry; adding the new data entry to the cache; and indicating the new data entry as located at the MRU entry of one of the first and second data structures.

Claim 2

Independent Claim 151 words

A method for caching data, comprising the steps of: providing a first and second data structures indicating data entries in a cache, wherein each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure; receiving a new data entry; processing the first and second data structures to determine a LRU data entry in each data structure; selecting from the determined LRU data entries the LRU data entry that is the least recently used; demoting the selected LRU data entry from the cache and data structure including the selected data entry; adding the new data entry to the cache; and indicating the new data entry as located at the MRU entry of one of the first and second data structures.

Claim 3

Dependent Claim 143 words

The method of claim 1, wherein the first data structure indicates data entries in the cache sequentially accessed and the second data structure indicates data entries in the cache non-sequentially accessed, wherein the step of selecting the LRU data entries comprises the steps of: determining whether adding the new data entry to cache would cause the number of sequentially accessed data entries to exceed a threshold, wherein the step of selecting from the determined LRU data entries the LRU data entry that is least recently used occurs after determining that adding the new data entry to cache would not cause the sequentially accessed data entries to exceed the threshold; and selecting the LRU data entry from the first data structure to demote after determining that adding the new data entry to cache would cause the sequentially accessed data entries to exceed the threshold.

Claim 4

Dependent Claim 93 words

The method of claim 2, further comprising the steps of: receiving a data access request for requested data in the cache; returning the requested data from the cache; determining whether the data access request is a sequential access; indicating that the requested data is located at the MRU entry of the first data structure after determining that the data access request is a sequential access; and indicating that the requested data is located at the MRU entry of the second data structure after determining that the data access request is a non-sequential access.

Claim 5

Dependent Claim 204 words

The method of claim 1, wherein the first data structure indicates data entries written to the cache as part of a first type of write operation and the second data structure indicates data entries written to the cache as part of a second type of write operation, wherein data written to the cache as part of the first type of write operation is also written to a first storage unit, and wherein the new data entry comprises data to write to a second storage unit, further comprising the steps of: determining whether the new data entry is of the first write operation type; selecting the LRU data entry from the first data structure to destage from the first storage unit to the second storage unit after determining that the new data entry is of the first write operation type; indicating the selected LRU data entry as removed from the first data structure; and adding the new data entry to the first storage unit, wherein the step of indicating the new data entry as located at the MRU entry of one of the first and second data structures comprises indicating the new data entry as located at the MRU entry of the first data structure.

Claim 6

Dependent Claim 138 words

The method of claim 4, further comprising the steps of: receiving modified data for a data entry that is already in cache; determining whether the received modified data is of the first type of write operation; updating the data entry in cache with the received modified data; updating the data entry in the first storage unit with the received modified data after determining that the received modified data is of the first type of write operation; indicating that the updated data entry is at the MRU entry of the first data structure after determining that the modified data is of the first type of write operation; and indicating that the updated data entry is at the MRU entry of the second data structure after determining that the data access request is of the second type of write operation.

Claim 7

Dependent Claim 112 words

The method of claim 4, further comprising the steps of: providing a third data structure indicating data entries in cache sequentially accessed and a fourth data structure indicating data entries in cache non-sequentially accessed, wherein the third and fourth data structures have an MRU entry and an LRU entry; determining whether the new data entry is sequentially accessed data; indicating that the new data entry is at the MRU entry of the third data structure after determining that the new data entry is sequentially accessed; and indicating that the new data entry is at the MRU entry of the fourth data structure after determining that the new data entry is non-sequentially accessed.

Claim 8

Dependent Claim 144 words

The method of claim 1, further comprising a third and fourth data structures, wherein the first data structure indicates modified data entries written in cache and a storage unit as part of a sequential write operation, wherein the second data structure indicates modified data entries written in cache and the storage unit as part of a non-sequential write operation, wherein the third data structure indicates modified data entries written in cache and not the storage unit as part of a sequential write operation, and wherein the fourth data structure indicates modified data entries written in cache and not in the storage unit as part of a non-sequential write operation, wherein the step of processing the first and second data structures further comprises processing the third and fourth data structures to determine an LRU data entry from the first, second, third, and fourth data structures.

Claim 9

Dependent Claim 57 words

The method of claim 7, further comprising the step of providing a modified data threshold indicating a maximum number of modified data entries to maintain in cache, wherein the step of processing the four data structures occurs after determining that the addition of modified data to the cache will cause the modified data threshold to be exceeded.

Claim 10

Dependent Claim 228 words

The method of claim 8, further comprising a fifth data structure indicating the number of entries in the cache sequentially accessed and a sixth data structure indicating the number of entries in cache non-sequentially accessed, further comprising the steps of: providing a sequentially accessed threshold indicating a maximum number of sequentially accessed data entries to maintain in cache; determining whether the addition of a data entry to the cache will cause the number of data entries in cache to exceed the modified and sequentially accessed thresholds, wherein the step of processing the first, second, third, and fourth data structures occurs after determining that the addition of modified data to the cache will exceed the modified data threshold and not exceed the sequentially accessed threshold; processing the fifth and sixth data structures to determine LRU data entries after determining that the modified threshold is not exceeded, wherein the steps of selecting and demoting comprises selecting and demoting the LRU data entry that is the least recently used entry from the fifth and sixth data structures; and processing the first and third data structures to determine LRU data entries after determining that the modified and sequentially accessed thresholds are both exceeded, wherein the steps of selecting and demoting comprises selecting and demoting the LRU data entry that is the least recently used entry from the first and third data structures.

Claim 11

Dependent Claim 75 words

The method of claim 1, wherein the time value cannot exceed a maximum time value, wherein after reaching the maximum time value the time value resets to zero, further comprising the step of determining whether the time value for at least one of the LRU data entries was reset to zero, wherein the step of selecting the LRU data entry comprises selecting the LRU data entry that has a time value that was previously reset.

Claim 12

Dependent Claim 197 words

The method of claim 10, wherein the time value comprises a sequence number that is incremented when data entries are indicated as added to the MRU entry of the data structures, wherein the maximum time value comprises a maximum sequence number, and wherein the LRU data entry in a data structure has the lowest sequence number in the data structure, wherein the step of determining whether the time value for an LRU data entry was reset to zero comprises the steps of: (i) determining a difference between the sequence numbers of the LRU data entries in the first and second data structures; and (ii) determining whether the difference between the sequence numbers is greater than half the maximum sequence number; and wherein the step of selecting the LRU data entry from the data structures comprises the steps of: (i) selecting the LRU data entry having a largest sequence number after determining that the difference between the LRU data entries is greater than half the maximum sequence number; and (ii) selecting the LRU data entry having a lowest sequence number after determining that the difference between the LRU data entries is less than half the maximum sequence number.

Claim 13

Dependent Claim 137 words

The method of claim 1, further comprising a third data structure indicating data entries in the first and second data structures, wherein each data entry indicated in the third data structure has a modified time value indicating when the data entry was first modified in cache, further comprising the steps of: executing a routine at predetermined intervals to destage data from cache to a storage unit; providing a base time value indicating a previous time value; determining, when executing the routine, data entries in the third data structure having a time value that is older than the base time value; destaging, for each determined data entry in the third data structure, the copy of the modified data maintained in cache to the storage unit; and indicating the destaged data entry as removed from the third linked list.

Claim 14

Independent Claim 185 words

A system for caching data, comprising: a processing unit; a cache including data entries; a memory area including first and second data structures accessible to the processing unit, wherein the data structures indicate data entries in the cache, wherein each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure; program logic executed by the processing unit, comprising: (i) means for processing the first and second data structures to determine a LRU data entry in each data structure; (ii) means for selecting from the determined LRU data entries the LRU data entry that is the least recently used; (iii) means for demoting the selected LRU data entry from the cache and data structure including the selected data entry; (iv) means for adding a new data entry to the cache; and (v) means for indicating the new data entry as located at the MRU entry of one of the first and second data structure.

Claim 15

Independent Claim 185 words

A system for caching data, comprising: a processing unit; a cache including data entries; a memory area including first and second data structures accessible to the processing unit, wherein the data structures indicate data entries in the cache, wherein each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure; program logic executed by the processing unit, comprising: (i) means for processing the first and second data structures to determine a LRU data entry in each data structure; (ii) means for selecting from the determined LRU data entries the LRU data entry that is the least recently used; (iii) means for demoting the selected LRU data entry from the cache and data structure including the selected data entry; (iv) means for adding a new data entry to the cache; and (v) means for indicating the new data entry as located at the MRU entry of one of the first and second data structure.

Claim 16

Dependent Claim 36 words

The system of claim 13, wherein the data structures are linked lists, wherein the MRU entry is at one end of the linked list and the LRU entry is at another end of the linked list.

Claim 17

Dependent Claim 35 words

The system of claim 13, wherein the cache and memory area are included in a first memory device, further comprising a second memory device, wherein the cache stores data accessed from the secondary memory device.

Claim 18

Dependent Claim 97 words

The system of claim 13, wherein the first data structure indicates data entries in the cache sequentially accessed and the second data structure indicates data entries in the cache non-sequentially accessed, wherein the program logic further comprises: means for determining whether adding the new data entry to cache would cause the number of sequentially accessed data entries to exceed a threshold; and means for selecting the LRU data entry from the first data structure to demote after determining that adding the new data entry to cache would cause the sequentially accessed data entries to exceed the threshold.

Claim 19

Dependent Claim 104 words

The system of claim 16, wherein the program logic further comprises: means for receiving a data access request for requested data in the cache; means for returning the requested data from the cache; means for determining whether the data access request is a sequential access; means for indicating that the requested data is located at the MRU entry of the first data structure after determining that the data access request is a sequential access; and means for indicating that the requested data is located at the MRU entry of the second data structure after determining that the data access request is a non-sequential access.

Claim 20

Dependent Claim 196 words

The system of claim 13, wherein the first data structure indicates data entries written to the cache as part of a first type of write operation and the second data structure indicates data entries written to the cache as part of a second type of write operation, further comprising: a first storage unit, wherein data written to the cache as part of the first type of write operation is also written to a first storage unit; a second storage unit; wherein the program logic further comprises: (i) means for determining whether the new data entry is part of the first write operation; (ii) means for selecting the LRU data entry from the first data structure to destage from the first storage unit to the second storage unit after determining that the new data entry is part of the first write operation; and (iii) means for adding the new data entry to the first storage unit, wherein the step of indicating the new data entry as located at the MRU entry of one of the first and second data structure comprises indicating the new data entry as located at the MRU entry of the first data structure.

Claim 21

Dependent Claim 151 words

The system of claim 18, wherein the program logic further comprises: means for processing modified data for a data entry that is already in cache; means for determining whether the modified data is one of the first type of write operation; means for updating the data entry in cache with the received modified data; means for updating the data entry in the first storage unit with the received modified data after determining that the received modified data is of the first type of write operation; means for indicating that the updated data entry is at the MRU entry of the first data structure after determining that the modified data is of the first type of write operation; and means for indicating that the updated data entry is at the MRU entry of the second data structure after determining that the data access request is of the second type of write operation.

Claim 22

Dependent Claim 152 words

The system of claim 13, wherein the memory area further comprises a third data structure indicating data entries in the first and second data structures, wherein each data entry in the third data structure has a modified time value indicating when the data entry was first modified in cache, wherein the program logic further comprises: means for executing a routine at predetermined intervals to destage data from cache to a storage unit; means for providing a base time value indicating a previous time value; means for determining, when executing the routine, data entries in the third data structure having a time value that is older than the base time value; and means for destaging, for each determined data entry in the third data structure, the copy of the modified data maintained in cache to the storage unit; and means for indicating the destaged data entry as removed from the third data structure.

Claim 23

Dependent Claim 185 words

An article of manufacture for use in programming a processing unit to manage cache, the article of manufacture comprising at least one computer readable storage device including at least one computer program embedded therein that causes the processing unit to perform the steps: providing a first and second data structures indicating data entries in a cache, wherein each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure; receiving a new data entry; processing the first and second data structures to determine a LRU data entry in each data structure; selecting from the determined LRU data entries the LRU data entry that is the least recently used; demoting the selected LRU data entry from the cache and data structure including the selected data entry; adding the new data entry to the cache; and indicating the new data entry as located at the MRU entry of one of the first and second data structures.

Claim 24

Dependent Claim 185 words

An article of manufacture for use in programming a processing unit to manage cache, the article of manufacture comprising at least one computer readable storage device including at least one computer program embedded therein that causes the processing unit to perform the steps: providing a first and second data structures indicating data entries in a cache, wherein each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure; receiving a new data entry; processing the first and second data structures to determine a LRU data entry in each data structure; selecting from the determined LRU data entries the LRU data entry that is the least recently used; demoting the selected LRU data entry from the cache and data structure including the selected data entry; adding the new data entry to the cache; and indicating the new data entry as located at the MRU entry of one of the first and second data structures.

Claim 25

Dependent Claim 149 words

The article of manufacture of claim 21, wherein the first data structure indicates data entries in cache sequentially accessed and the second data structure indicates data entries in cache non-sequentially accessed, wherein the step of selecting the LRU data entries comprises causing the processing unit to perform the steps of: determining whether adding the new data entry to cache would cause the number of sequentially accessed data entries to exceed a threshold, wherein the step of selecting from the determined LRU data entries the LRU data entry that is least recently used occurs after determining that adding the new data entry to cache would not cause the sequentially accessed data entries to exceed the threshold; and selecting the LRU data entry from the first data structure to demote after determining that adding the new data entry to cache would cause the sequentially accessed data entries to exceed the threshold.

Claim 26

Dependent Claim 95 words

The article of manufacture of claim 22, further comprising the steps of: receiving a data access request for requested data in the cache; returning the requested data from the cache; determining whether the data access request is a sequential access; indicating that the requested data is located at the MRU entry of the first data structure after determining that the data access request is a sequential access; and indicating that the requested data is located at the MRU entry of the second data structure after determining that the data access request is a non-sequential access.

Claim 27

Dependent Claim 205 words

The article of manufacture of claim 21, wherein the first data structure comprises data entries written to the cache as part of a first type of write operation and the second data structure comprises data entries written as part of a second type of write operation, wherein data written to the cache as part of the first type of write operation is also written to a first storage unit, and wherein the new data entry comprises data to write to a second storage unit, further comprising the steps of: determining whether the new data entry is of the first write operation type; selecting the LRU data entry from the first data structure to destage from the first storage unit to the second storage unit after determining that the new data entry is of the first type of write operation type; indicating the selected LRU data entry as removed from the first data structure; and adding the new data entry to the first storage unit, wherein the step of indicating the new data entry as located at the MRU entry of one of the first and second data structures comprises indicating the new data entry as located at the MRU entry of the first data structure.

Claim 28

Dependent Claim 139 words

The article of manufacture of claim 24, further comprising the steps of: receiving modified data for a data entry that is already in cache; determining whether the received modified data is of the first type of write operation; updating the data entry in cache with the received modified data; updating the data entry in the first storage unit with the received modified data after determining that the received modified data is of the first type of write operation; indicating that the updated data entry is at the MRU entry of the first data structure after determining that the modified data is of the first type of write operation; and indicating that the updated data entry is at the MRU entry of the second data structure after determining that the modified data is of the second type of write operation.

Claim 29

Dependent Claim 114 words

The article of manufacture of claim 25, further comprising the steps of: providing a third data structure indicating data entries in cache sequentially accessed and a fourth data structure of data entries in cache non-sequentially accessed, wherein the third and fourth data structures have an MRU entry and an LRU entry; determining whether the new data entry is sequentially accessed data; indicating that the new data entry is at the MRU entry of the third data structure after determining that the new data entry is sequentially accessed; and indicating that the new data entry is at the MRU entry of the fourth data structure after determining that the new data entry is non-sequentially accessed.

Claim 30

Dependent Claim 146 words

The article of manufacture of claim 21, further comprising a third and fourth data structures, wherein the first data structure indicates modified data entries written in cache and a storage unit as part of a sequential write operation, wherein the second data structure indicates modified data entries written in cache and the storage unit as part of a non-sequential write operation, wherein the third data structure indicates modified data entries written in cache and not the storage unit as part of a sequential write operation, and wherein the fourth data structure indicates modified data entries written in cache and not in the storage unit as part of a non-sequential write operation, wherein the step of processing the first and second data structures further comprises processing the third and fourth data structures to determine an LRU data entry from the first, second, third, and fourth data structures.

Claim 31

Dependent Claim 59 words

The article of manufacture of claim 27, further comprising the step of providing a modified data threshold indicating a maximum number of modified data entries to maintain in cache, wherein the step of processing the four data structures occurs after determining that the addition of modified data to the cache will cause the modified data threshold to be exceeded.

Claim 32

Dependent Claim 230 words

The article of manufacture of claim 28, further comprising a fifth data structure indicating the number of entries in the cache sequentially accessed and a sixth data structure indicating the number of entries in cache non-sequentially accessed, further comprising the steps of: providing a sequentially accessed threshold indicating a maximum number of sequentially accessed data entries to maintain in cache; determining whether the addition of a data entry to the cache will cause the number of data entries in cache to exceed the modified and sequentially accessed thresholds, wherein the step of processing the first, second, third, and fourth data structures occurs after determining that the addition of modified data to the cache will exceed the modified data threshold and not exceed the sequentially accessed threshold; processing the fifth and sixth data structures to determine LRU data entries after determining that the modified threshold is not exceeded, wherein the steps of selecting and demoting comprises selecting and demoting the LRU data entry that is the least recently used entry from the fifth and sixth data structures; and processing the first and third data structures to determine LRU data entries after determining that the modified and sequentially accessed thresholds are both exceeded, wherein the steps of selecting and demoting comprises selecting and demoting the LRU data entry that is the least recently used entry from the first and third data structures.

Claim 33

Dependent Claim 77 words

The article of manufacture of claim 21, wherein the time value cannot exceed a maximum time value, wherein after reaching the maximum time value the time value resets to zero, further comprising the step of determining whether the time value for at least one of the LRU data entries was reset to zero, wherein the step of selecting the LRU data entry comprises selecting the LRU data entry that has a time value that was previously reset.

Claim 34

Dependent Claim 199 words

The article of manufacture of claim 21, wherein the time value comprises a sequence number that is incremented when data entries are indicated as added to the MRU entry of the data structures, wherein the maximum time value comprises a maximum sequence number, and wherein the LRU data entry in a data structure has the lowest sequence number in the data structure, wherein the step of determining whether the time value for an LRU data entry was reset to zero comprises the steps of: (i) determining a difference between the sequence numbers of the LRU data entries in the first and second data structures; and (ii) determining whether the difference between the sequence numbers is greater than half the maximum sequence number; and wherein the step of selecting the LRU data entry from the data structures comprises the steps of: (i) selecting the LRU data entry having a largest sequence number after determining that the difference between the LRU data entries is greater than half the maximum sequence number; and (ii) selecting the LRU data entry having a lowest sequence number after determining that the difference between the LRU data entries is less than half the maximum sequence number.

Claim 35

Dependent Claim 138 words

The article of manufacture of claim 21, further comprising a third data structure indicating data entries in the first and second data structures, wherein each data entry in the third data structure has a modified time value indicating when the data entry was first modified in cache, further comprising the steps of: executing a routine at predetermined intervals to destage data from cache to a storage unit; providing a base time value indicating a previous time value; determining, when executing the routine, data entries in the third data structure having a time value that is older than the base time value; destaging, for each determined data entry in the third data structure, the copy of the modified data maintained in cache to the storage unit; and indicating the destaged data entry as removed from the third data structure.

Claim 36

Dependent Claim 168 words

A memory area accessible to a processing unit, wherein the memory unit stores: a plurality of data entries; a first and second data structures indicating the data entries, wherein each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure; and a new data entry added to the memory area, wherein the processing unit processes the first and second data structures to determine a LRU data entry in each data structure and selecting from the determined LRU data entries the LRU data entry that is the least recently used, wherein the processing unit demotes the selected LRU data entry from the cache and data structure including the selected data entry, and wherein the processing unit indicates that the new data entry as located at the MRU entry of one of the first and second data structures.

Claim 37

Dependent Claim 168 words

A memory area accessible to a processing unit, wherein the memory unit stores: a plurality of data entries; a first and second data structures indicating the data entries, wherein each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure; and a new data entry added to the memory area, wherein the processing unit processes the first and second data structures to determine a LRU data entry in each data structure and selecting from the determined LRU data entries the LRU data entry that is the least recently used, wherein the processing unit demotes the selected LRU data entry from the cache and data structure including the selected data entry, and wherein the processing unit indicates that the new data entry as located at the MRU entry of one of the first and second data structures.

Claim 38

Dependent Claim 45 words

The memory area of claim 33, wherein the first and second data structures are comprised of linked lists in cache, wherein the MRU entry is at one end of the linked list and the LRU entry is at the other end of the linked list.

Claim 39

Dependent Claim 95 words

The memory area of 33, wherein the first data structure indicates data entries in cache sequentially accessed and the second data structure indicates data entries in cache non-sequentially accessed, wherein the processing unit determines whether adding the new data entry to the memory area would cause the number of sequentially accessed data entries to exceed a threshold, and wherein the processing unit selects the LRU data entry from the first data structure to demote after determining that adding the new data entry to cache would cause the sequentially accessed data entries to exceed the threshold.

Claim 40

Dependent Claim 95 words

The memory area of 33, wherein the first data structure indicates data entries in cache sequentially accessed and the second data structure indicates data entries in cache non-sequentially accessed, wherein the processing unit determines whether adding the new data entry to the memory area would cause the number of sequentially accessed data entries to exceed a threshold, and wherein the processing unit selects the LRU data entry from the first data structure to demote after determining that adding the new data entry to cache would cause the sequentially accessed data entries to exceed the threshold.

Claim 41

Dependent Claim 85 words

The memory area of claim 35, wherein the processing unit indicates that a data entry to which a data access request was directed is located at the MRU entry of the first data structure after determining that the data access request is a sequential access, and wherein the processing unit indicates that the data entry to which the data access request was directed is located at the MRU entry of the second data structure after determining that the data access request is a non-sequential access.

Claim 42

Dependent Claim 168 words

The memory area of claim 33, wherein the first data structure indicates data entries written to the cache as part of a first type of write operation and the second data structure indicates data entries written to the cache as part of a second type of write operation, wherein the processing unit writes data written to the cache as part of the first type of write operation to a first storage unit, wherein the processing unit selects the LRU data entry from the first data structure to destage from the first storage unit to a second storage unit after determining that the new data entry is part of the first write operation, and wherein the processing unit adds the new data entry to the first storage unit, wherein the step of indicating the new data entry as located at the MRU entry of one of the first and second data structures comprises indicating the new data entry as located at the MRU entry of the first data structure.

Claim 43

Dependent Claim 146 words

The memory area of claim 33, further comprising a third and fourth data structures, wherein the first data structure indicates modified data entries written in cache and a storage unit as part of a sequential write operation, wherein the second data structure indicates modified data entries written in cache and the storage unit as part of a non-sequential write operation, wherein the third data structure indicates modified data entries written in cache and not the storage unit as part of a sequential write operation, and wherein the fourth data structure indicates modified data entries written in cache and not in the storage unit as part of a non-sequential write operation, wherein the step of processing the first and second data structure s further comprises processing the third and fourth data structures to determine an LRU data entry from the first, second, third, and fourth data structures.

Claim 44

Dependent Claim 108 words

The memory area method of claim 33, wherein the memory area further comprises a third data structure indicating data entries in cache sequentially accessed and a fourth data structure indicating data entries in cache non-sequentially accessed, wherein the third and fourth data structures have an MRU entry and an LRU entry, wherein the processing unit indicates that the new data entry is at the MRU entry of the third data structure after determining that the new data entry is sequentially accessed; and indicates that the new data entry is at the MRU entry of the fourth data structure after determining that the new data entry is non-sequentially accessed.

Claim 45

Dependent Claim 107 words

The memory area of claim 33, wherein the memory area further comprises: a third data structure indicating data entries in the first and second data structures, wherein each data entry in the third list has a modified time value indicating when the data entry was first modified in cache; and a base time value indicating a previous time value, wherein the processing determines data entries in the third data structure having a time value that is older than the base time value and, for each determined data entry in the third data structure, destages the copy of the modified data maintained in cache to the storage unit.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-10-31	2004-05-01	2004-10-31	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-10-31	2008-05-01	2008-10-31	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-10-31	2012-05-01	2012-10-31	$7700.00	Window Closed / Lapsed

Method and system for managing data in cache using multiple data structures

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag