METHOD OF EFFICIENTLY CHOOSING A CACHE ENTRY FOR CASTOUT

• US 20090177844A1
• Filed: 01/08/2008
• Published: 07/09/2009
• Est. Priority Date: 01/08/2008
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Naylor, Bruce Eric, Ormsby, David Edwin, Patterson, Betty Joan
• Application Number:
  US11/970,743
• Publication Number:
  US 20090177844A1
• Time in Patent Office: Days
• US Class Current: 711/136
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value

Abstract

The present invention relates generally to a method and system for efficiently identifying a cache entry for cast out in relation to scanning a predetermined sampling subset of pseudo-randomly sampled cached entries and determining a least recently used (LRU) entry from the scanned cached entries subset, thereby avoiding a comprehensive review of all of or groups of the cached entries in the cache at any instant. In one or more implementations, a subset of the data entries in a cache are randomly sampled, assessed by timestamp in a doubly-linked listing and a least recently used data entry to cast out is identified.

Claims

1. A method for identifying a data entry of a cache for cast out, comprising:

defining a sample of data entries of the cache as a linked-list chain of data entries, wherein the sample is comprised of “

n”

data entries and the chain is comprised of “

m”

data entries, where m is greater than or equal to n;

wherein the sample is comprised of a designated scan starting data entry and (n−

1) data entries subsequent to the starting data entry;

evaluating one or more data entries in the linked-list chain in relation to one or more predetermined characteristics;

identifying at least recently used data entry for cast out; and

identifying a new data entry for addition to the cache and adding the identified new data entry to the cache after assigning the new data entry a control block following cast out of the least recently used data entry;

wherein the linked-list chain comprising in use control blocks of data entries of the cache having timestamps, and evaluating one or more data entries further comprises comparing the predetermined characteristics being timestamps of each data entry in the sample and ranking each data entry in accordance with its respective timestamp;

further comprising and prior to the step of evaluating, dividing data entries of the cache into one or more logical subpools for consistency in size in relation to size of the data entries in the sample.

2. The method of claim 1 further comprising casting out the identified least recently used data entry.

3. The method of claim 2, further comprising identifying a new data entry for addition to the cache and adding the identified new data entry to the cache after assigning the new data entry a control block following cast out of the least recently used data entry.

4. The method of claim 1, wherein the sample is defined randomly or psudeo-randomly.

5. The method of claim 4, wherein the sample comprises a scan starting pointer and a predetermined number of subsequent data entries in relation to a sample size less one.

6. The method of claim 5, further comprising the step of resetting the pointer after identifying the least recently used data entry to a data entry pointer subsequent to the sample of the chain.

7. A data system having an instantiable computer program product for identifying a data entry of a cache coupled with one or more cache clients for cast out from one or more data entries in a cache containing from a data storage device of a data system having a centralized processing unit (CPU), comprising a computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions including:

a first executable portion having instructions being capable of;

defining a sample of data entries of the cache as a linked-list chain of data entries, wherein the linked-list chain is a doubly-link list chain comprising of in use control blocks of data entries of the cache having timestamps, and the step of evaluating one or more data entries further comprises comparing the predetermined characteristics being timestamps of each data entry in the sample and ranking each data entry in accordance with its respective timestamp, wherein the sample is comprised of “

n”

data entries and the chain is comprised of “

m”

data entries, where m is greater than or equal to n;

wherein the sample is comprised of a designated scan starting data entry and (n−

1) data entries subsequent to the starting data entry;

wherein the cache is operably coupled with one or more cache items.

evaluating one or more data entries in the linked-list chain in relation to one or more predetermined characteristics;

identifying a least recently used data entry for cast out; and

identifying a new data entry for addition to the cache and adding the identified new data entry to the cache after assigning the new data entry a control block following cast out of the least recently used data entry.

8. The system of claim 7, further comprising casting out the identified least recently used data entry.

9. The system of claim 7, wherein the sample is random or pseudo-random.

10. A computerized method for identifying a cache data entry for cast out from one or more data entries in a cache containing from a data storage device of a data system having a centralized processing unit (CPU), memory, an operating system, and a data management system, using one or more application programs having program instructions comprising the steps of:

defining a sample of data entries of a cache in relation to a sample size;

defining the sample as a linked-list chain of data entries;

assessing one or more characteristics of the data entries in the linked-list chain;

wherein the linked-list chain is a doubly-link list chain comprising in use control blocks of data entries of the cache having timestamps, and the step of assessing one or more data entries further comprises comparing the characteristics being timestamps of each data entry in the sample and ranking each data entry in accordance with its respective timestamp;

identifying a least recently used data entry for cast out;

casting out the identified least recently used data entry; and

identifying a new data entry for addition to the cache and adding the identified new data entry to the cache after assigning the new data entry a control block following cast out of the least recently used data entry.