Sequential reference management for cache memories

Claim 1

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: storing data requested from said mass storage device in said most recently used area of said probationary memory region; discarding previously stored data from said least recently used area of said probationary memory region in response to said previous storing step when said probationary memory region is full; receiving a read request for data stored in said probationary memory region; sending said requested data to the requestor; adding said requested data to said most recently used area of said protected memory region; removing data from said least recently used area of said protected memory region if said protected memory region does not have room to receive said requested data then adding said requested data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary memory, region.

Claim 2

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: storing data requested from said mass storage device in said most recently used area of said probationary memory region; discarding previously stored data from said least recently used area of said probationary memory region in response to said previous storing step when said probationary memory region is full; receiving a read request for data stored in said probationary memory region; sending said requested data to the requestor; adding said requested data to said most recently used area of said protected memory region; removing data from said least recently used area of said protected memory region if said protected memory region does not have room to receive said requested data then adding said requested data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary memory, region.

Claim 4

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memo region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a first read request for data not located in said cache memory; retrieving said requested data from said mass storage device; sending said requested data to said requestor; adding said requested data to said most recently used area of said probationary memory region if said probationary memory region has room for said requested data; removing data from said least recently used area of said probationary memory region if said probationary memory region does not have room for said requested data and then adding said requested data to said most recently used area of said probationary memory region; receiving a second read request for data located in said probationary memory region; sending said second requested data to said requestor; adding said second requested data to said most recently used area of said protected memory region if said protected memory region has room for said second requested data; removing data from said least recently used area of said protected memory region if said protected memory region does not have room to receive said second requested data then adding said second requested data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary memory region.

Claim 5

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memo region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a first read request for data not located in said cache memory; retrieving said requested data from said mass storage device; sending said requested data to said requestor; adding said requested data to said most recently used area of said probationary memory region if said probationary memory region has room for said requested data; removing data from said least recently used area of said probationary memory region if said probationary memory region does not have room for said requested data and then adding said requested data to said most recently used area of said probationary memory region; receiving a second read request for data located in said probationary memory region; sending said second requested data to said requestor; adding said second requested data to said most recently used area of said protected memory region if said protected memory region has room for said second requested data; removing data from said least recently used area of said protected memory region if said protected memory region does not have room to receive said second requested data then adding said second requested data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary memory region.

Claim 8

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a write request for data stored in said probationary memory region; erasing said stored data from said probationary memory region; adding new data from said write request to said most recently used area of said protected memory region if said protected memory region has room to receive said new data; removing data from said least recently used area of said protected memory region if said protected memory region does not have room to receive said new data then adding said new data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary memory region.

Claim 9

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a write request for data stored in said probationary memory region; erasing said stored data from said probationary memory region; adding new data from said write request to said most recently used area of said protected memory region if said protected memory region has room to receive said new data; removing data from said least recently used area of said protected memory region if said protected memory region does not have room to receive said new data then adding said new data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary memory region.

Claim 11

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a write request for data not stored in said cache memory; writing new data from said write request to said mass storage device; adding said new data from said mass storage device to said most recently used area of said probationary memory region if said probationary memory region has room to receive said new data; and removing data from said least recently used area of said probationary memory region if said probationary memory region does not have room to receive said new data, then adding said new data to said most recently used area of said probationary memory region.

Claim 12

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a write request for data not stored in said cache memory; writing new data from said write request to said mass storage device; adding said new data from said mass storage device to said most recently used area of said probationary memory region if said probationary memory region has room to receive said new data; and removing data from said least recently used area of said probationary memory region if said probationary memory region does not have room to receive said new data, then adding said new data to said most recently used area of said probationary memory region.

Claim 13

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a write request for data not stored in said cache memory; adding new data from said write request to said most recently used area of said probationary memory region if said probationary memory region has room to receive said new data; removing data from said least recently used area of said probationary memory region if said probationary memory region does not have room to receive said new data, then adding said new data to said most recently used area of said probationary memory region; determining if said removed data from said least recently used area of said probationary memory region is needed to update said mass storage device; updating said mass storage device with said removed data if needed; and, discarding said removed data if said updating of said mass storage device is not needed.

Claim 14

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a write request for data not stored in said cache memory; adding new data from said write request to said most recently used area of said probationary memory region if said probationary memory region has room to receive said new data; removing data from said least recently used area of said probationary memory region if said probationary memory region does not have room to receive said new data, then adding said new data to said most recently used area of said probationary memory region; determining if said removed data from said least recently used area of said probationary memory region is needed to update said mass storage device; updating said mass storage device with said removed data if needed; and, discarding said removed data if said updating of said mass storage device is not needed.

Claim 15

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a read request for data stored in said probationary memory region; sending said requested data to said requestor; determining if said requested data qualifies for promotion to said protected memory region; adding said requested data to said most recently used area of said probationary memory region if said requested data does not qualify for promotion; adding said requested data to said most frequently used area of said protected memory region if said requested data qualifies for promotion and said protected memory region has room for said requested data; removing data from said least frequently used area of said protected memory region if said requested data qualifies for promotion and said protected memory region does not have room for said requested data, then adding said requested data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary memory region.

Claim 16

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a read request for data stored in said probationary memory region; sending said requested data to said requestor; determining if said requested data qualifies for promotion to said protected memory region; adding said requested data to said most recently used area of said probationary memory region if said requested data does not qualify for promotion; adding said requested data to said most frequently used area of said protected memory region if said requested data qualifies for promotion and said protected memory region has room for said requested data; removing data from said least frequently used area of said protected memory region if said requested data qualifies for promotion and said protected memory region does not have room for said requested data, then adding said requested data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary memory region.

Claim 18

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a write request for data stored in said probationary memory region; erasing said stored data from said probationary memory region; determining if new data from aid writ request qualifies for promotion to said protected memory region; adding said new data to said most recently used area of said probationary memory region if said new data does not qualify for promotion; adding said new data to said most frequently used area of said protected memory region if said new data qualifies for promotion; removing data from said least frequently used area of said protected memory region if said new data qualifies for promotion and said protected memory region does not have room for said new data, then adding said requested data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary area.

Claim 19

A method of improving effectiveness of a cache memory being used to store data requested from a mass storage device by a requestor, the cache memory having a probationary memory region and a protected memory region, both said probationary and protected memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: receiving a write request for data stored in said probationary memory region; erasing said stored data from said probationary memory region; determining if new data from aid writ request qualifies for promotion to said protected memory region; adding said new data to said most recently used area of said probationary memory region if said new data does not qualify for promotion; adding said new data to said most frequently used area of said protected memory region if said new data qualifies for promotion; removing data from said least frequently used area of said protected memory region if said new data qualifies for promotion and said protected memory region does not have room for said new data, then adding said requested data to said most recently used area of said protected memory region; and adding said removed data from said least recently used area of said protected memory region to said most recently used area of said probationary area.

Claim 20

A method of improving effectiveness of a cache memory being used to store requested data from a mass storage device by a requestor, said cache memory having a protected memory region, an intermediate memory region and a probationary memory region, each of the protected, intermediate and probationary memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: storing data requested from said mass storage device in said most recently used area of said probationary memory region; discarding previously stored data from said least recently used area of the said probationary memory region in response to said storing step when said probationary memory region is full; requesting data from said probationary memory region and storing said data in said most recently used area of said intermediate memory region; transferring previously stored data from said least recently used area of said intermediate memory region in response to said step of storing said data when the intermediate memory region is full and storing said previously stored data from said least recently used area of said intermediate memory region in said most recently used area of said probationary memory region; requesting data from said intermediate memory region and storing said requested data as requested at least twice in said most recently used area of said protected memory region; removing previously stored data from said least recently used area of said protected memory region in response to said step of storing data when the protected memory region is full and storing said previously stored data from the least recently used area of the protected memory region in the most recently used area of the intermediate memory region and transferring previously stored data from the least recently used area of the intermediate memory region in response to said step of storing the previously stored data from the protected memory region when the intermediate memory region is full and storing said previously stored data from said intermediate memory region in the most recently used area of the probationary memory region; and, selecting data as data requested from the protected memory region and storing said data in the most recently used area of the protected memory region.

Claim 21

A method of improving effectiveness of a cache memory being used to store requested data from a mass storage device by a requestor, said cache memory having a protected memory region, an intermediate memory region and a probationary memory region, each of the protected, intermediate and probationary memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: storing data requested from said mass storage device in said most recently used area of said probationary memory region; discarding previously stored data from said least recently used area of the said probationary memory region in response to said storing step when said probationary memory region is full; requesting data from said probationary memory region and storing said data in said most recently used area of said intermediate memory region; transferring previously stored data from said least recently used area of said intermediate memory region in response to said step of storing said data when the intermediate memory region is full and storing said previously stored data from said least recently used area of said intermediate memory region in said most recently used area of said probationary memory region; requesting data from said intermediate memory region and storing said requested data as requested at least twice in said most recently used area of said protected memory region; removing previously stored data from said least recently used area of said protected memory region in response to said step of storing data when the protected memory region is full and storing said previously stored data from the least recently used area of the protected memory region in the most recently used area of the intermediate memory region and transferring previously stored data from the least recently used area of the intermediate memory region in response to said step of storing the previously stored data from the protected memory region when the intermediate memory region is full and storing said previously stored data from said intermediate memory region in the most recently used area of the probationary memory region; and, selecting data as data requested from the protected memory region and storing said data in the most recently used area of the protected memory region.

Claim 22

A method of improving effectiveness of a cache memory being used to store selected data from a mass storage device, said cache memory having a low priority memory region, an intermediate priority memory region and a high priority memory region, each of the low, intermediate and high priority memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: storing data selected from the mass storage device in the most recently used area of the intermediate priority memory region; transferring previously stored data from the least recently used area of the intermediate priority memory region in response to said step of storing when the intermediate priority memory region is full and storing said previously stored data from the intermediate priority memory region in the most recently used area of the low priority memory region; discarding data from the least recently used area of the low priority memory location in response to said step of storing when the low priority memory region is full; selecting data from the low priority memory region and storing said data in the most recently used area of the intermediate memory region; transferring previously stored data from the least recently used area of the intermediate priority memory region in response to said step of storing data when the intermediate priority memory region is full and storing said previously stored data from the least recently used area of the intermediate priority memory region in the most recently used area of the low priority memory region; selecting data from the intermediate priority memory region and storing said data in the most recently used area of the high priority memory region; transferring previously stored data from the least recently used area of the high priority memory region in response to said step of storing data when the high priority memory region is full and storing said previously stored data from the least recently used area of the high priority memory region in the most recently used area of the intermediate priority memory region and transferring previously stored data from the least recently used area of the intermediate memory region in response to said step of storing the previously stored data from the high priority memory region when the intermediate priority memory region is full and storing said previously stored data from said intermediate priority memory region in the most frequently used area of the low priority memory region; and selecting data from the high priority memory region and storing said data in the most recently used area of the high priority memory region.

Claim 23

A method of improving effectiveness of a cache memory being used to store selected data from a mass storage device, said cache memory having a low priority memory region, an intermediate priority memory region and a high priority memory region, each of the low, intermediate and high priority memory regions respectively having a most recently used area and a least recently used area, comprising the steps of: storing data selected from the mass storage device in the most recently used area of the intermediate priority memory region; transferring previously stored data from the least recently used area of the intermediate priority memory region in response to said step of storing when the intermediate priority memory region is full and storing said previously stored data from the intermediate priority memory region in the most recently used area of the low priority memory region; discarding data from the least recently used area of the low priority memory location in response to said step of storing when the low priority memory region is full; selecting data from the low priority memory region and storing said data in the most recently used area of the intermediate memory region; transferring previously stored data from the least recently used area of the intermediate priority memory region in response to said step of storing data when the intermediate priority memory region is full and storing said previously stored data from the least recently used area of the intermediate priority memory region in the most recently used area of the low priority memory region; selecting data from the intermediate priority memory region and storing said data in the most recently used area of the high priority memory region; transferring previously stored data from the least recently used area of the high priority memory region in response to said step of storing data when the high priority memory region is full and storing said previously stored data from the least recently used area of the high priority memory region in the most recently used area of the intermediate priority memory region and transferring previously stored data from the least recently used area of the intermediate memory region in response to said step of storing the previously stored data from the high priority memory region when the intermediate priority memory region is full and storing said previously stored data from said intermediate priority memory region in the most frequently used area of the low priority memory region; and selecting data from the high priority memory region and storing said data in the most recently used area of the high priority memory region.