EP0391871A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for managing a prioritized cache
Assignee: International Business Machines Corp
•
Filing: 1990-04-02
•
Granted: —
•
Expires: 2010-04-02
Abstract
Abstract There is disclosed a method for managing an LRU (least recently used) cache in a staged storage system storing data sets on a prioritized basis. The method uses the signed difference between an assigned and actual hit ratio to dynamically allocate cache size to a class of data and its correlation with the priority of that class. Advantageously, the hit ratio performance of a class of data cannot be degraded beyond a predetermined level by a class of data having lower priority (assigned importance).
Inventors
- 👤 Kevin Frank Smith
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-26 18:47
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/126; G06F12/0802; G06F12/0866; G06F12/0888; G06F12/122
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
106 words
A method for managing an LRU cache whose data contents are defined over a priority range 1...N, said cache being located in a predetermined echelon of a CPU-coupled, staged storage system, data in said cache being referenced with read and write operations in a cycle, comprising the the steps of: (a) assigning prioritization, target hit ratio, and cache size to each of N cache partitions; (b) measuring the actual hit ratios for each partition; (c) relative magnitude comparing the actual and target ratios for each partition; and (d) readjusting cache space on an LRU basis as a function of the sign of the relative magnitude comparison.
Claim 2
Independent Claim
106 words
A method for managing an LRU cache whose data contents are defined over a priority range 1...N, said cache being located in a predetermined echelon of a CPU-coupled, staged storage system, data in said cache being referenced with read and write operations in a cycle, comprising the the steps of: (a) assigning prioritization, target hit ratio, and cache size to each of N cache partitions; (b) measuring the actual hit ratios for each partition; (c) relative magnitude comparing the actual and target ratios for each partition; and (d) readjusting cache space on an LRU basis as a function of the sign of the relative magnitude comparison.
Claim 3
Dependent Claim
20 words
The method according to claim 1, wherein said measuring step for the actual hit ratio utilizes a weighted running average.
Claim 4
Dependent Claim
56 words
The method according to claim 1, wherein if the sum of the signed relative magnitude comparison is less than zero, distributing cache size in proportion to the number of cache read operations per partition; and further wherein if the sum is greater than zero, distributing cache size to bias in favor of the higher priority partitions.
Claim 5
Independent Claim
173 words
A method for managing an LRU cache whose data contents are defined over a priority range from priority 1...N, said cache being located in a predetermined echelon of a host-coupled, staged storage system, data in said cache being referenced by read and write operations in a cycle, comprising the steps of: (a) initially partitioning the cache and assigning a target hit ratio arbitrarily to each partition; (b) during subsequent reference cycles, periodically monitoring the actual hit ratio associated with each partition and altering the size of each partition of said cache as a function of the signed difference between the actual and target hit ratios such that a positive difference causes a reduction in partition size, while a negative difference causes an increase in partition size; (c) ascertaining the priority class of data referenced by the host to the staged storage system; and (d) causing a reference to be made to the partition 1...N correlated with the ascertained priority class 1...N, otherwise causing a reference to be made to the staged storage system.
Claim 6
Independent Claim
173 words
A method for managing an LRU cache whose data contents are defined over a priority range from priority 1...N, said cache being located in a predetermined echelon of a host-coupled, staged storage system, data in said cache being referenced by read and write operations in a cycle, comprising the steps of: (a) initially partitioning the cache and assigning a target hit ratio arbitrarily to each partition; (b) during subsequent reference cycles, periodically monitoring the actual hit ratio associated with each partition and altering the size of each partition of said cache as a function of the signed difference between the actual and target hit ratios such that a positive difference causes a reduction in partition size, while a negative difference causes an increase in partition size; (c) ascertaining the priority class of data referenced by the host to the staged storage system; and (d) causing a reference to be made to the partition 1...N correlated with the ascertained priority class 1...N, otherwise causing a reference to be made to the staged storage system.
Claim 7
Dependent Claim
23 words
The method according to claim 4, wherein said cache is an n-way set associative cache, N being the number of cached priority classes.
Claim 8
Dependent Claim
21 words
The method according to claim 4, wherein estimated increases or reductions in cache size are a function of powers of two.
Claim 9
Dependent Claim
62 words
The method according to claim 4, wherein if the sum of the signed monitored differences between the actual and target hit ratios is less than zero, distributing cache size in proportion to the number of cache read operations per partition; and further wherein if the sum is grater than zero, distributing cache size to bias in favor of the higher priority partitions.
Claim 10
Dependent Claim
121 words
The method according to claim 4, wherein said method uses a cyclic, rule-based, control data sensitive inferencing system, said control data including cache parametric values of partition size, priority, target and actual hit ratios, said system including means for storing control data and rules, and means cooperating with the storage means for executing a control cycle, each rule having pattern indication and action specifying parts thereof, comprising the cyclic steps of: (a) identifying an executable subset of rules by matching the pattern parts of the rules to those elements of control data in the storage means modified or created during a preceding cycle; (b) selecting a rule from the identified rules; and (c) executing the action prescribed by the selected rule.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.