US5537635A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for assignment of reclaim vectors in a partitioned cache with a virtual minimum partition size
Assignee: International Business Machines Corp
•
Filing: 1994-04-04
•
Granted: 1996-07-16
•
Expires: 2014-04-04
Abstract
Abstract A method for avoiding a cache-full condition in an LRU organized, data set partitioned, page oriented cache of a defined capacity intercoupling a processor to an external storage subsystem is provided. The processor is capable of storing pages of a data set into a plurality of cache partitions. The method comprises the steps of periodically determining the target size of each partition for optimal partitioning, and assigning a reclaim vector to each partition specifying the number of frames to be stolen from each of the other partitions necessary to achieve the corresponding target size. If the target size of a particular partition is less than the partition's virtual minimum size, the method adjusts that partition's reclaim vector to enable the partition to steal sufficient frames from other partitions to achieve the virtual minimum size. In response to a cache miss, frames are stolen from other partitions, as directed by the reclaim vector of the partition storing the data set to which the missing page reference is a member, by removing the lowest page in LRU order and adding the resulting frame to the storing partition and modifying the storing partition's reclaim vector.
Inventors
- 👤 Daniel G. Douglas
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 11:37
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/12; G06F12/121; G06F12/128; G06F12/0802; G06F12/0866; G06F2212/00; G06F2212/31; G06F2212/311
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
193 words
A method for avoiding a cache full condition in a dataset partitioned, page oriented cache of a defined capacity having dynamic resource allocation and intercoupling a processor to an external storage subsystem, said processor including means for storing pages of a dataset into a plurality of cache partitions, comprising the steps of: (a) periodically determining the target size of each partition for optimal partitioning; (b) assigning a reclaim vector to each partition specifying the number of frames to be stolen from each of the other partitions necessary to achieve a corresponding target size; (c) if the target size of a particular partition is less than the partition's virtual minimum size, adjusting that partition's reclaim vector to enable the partition to steal sufficient frames from other partitions to achieve the virtual minimum size; and (d) responsive to one or more page cache miss references, stealing one or more frames from other partitions, as directed by the reclaim vector of the partition storing the dataset to which the missed page reference is a member, and adding the resulting frame to the storing partition, and modifying the storing partition's reclaim vector to reflect the pages stolen.
Claim 2
Dependent Claim
50 words
A method according to claim 1, wherein, if the target size is also less than the current size, the step of adjusting comprises adjusting the reclaim vector to enable the partition to steal sufficient frames from other partitions to progress from the target size to the partition's virtual minimum size.
Claim 3
Dependent Claim
26 words
A method according to claim 2, wherein the reclaim vector is modified to steal frames from partitions whose current size is at least the virtual minimum.
Claim 4
Dependent Claim
46 words
A method according to claim 3, wherein, if unable to obtain enough frames from partitions whose current size is at least the virtual minimum size but less than the target size, frames are stolen from any partition whose size is at least the virtual minimum size.
Claim 5
Dependent Claim
50 words
A method according to claim 1, wherein, if the target size is also greater than the current size, the step of adjusting comprises adjusting the reclaim vector to enable the partition to steal sufficient frames from other partitions to progress from the current size to the partition's virtual minimum size.
Claim 6
Dependent Claim
33 words
A method according to claim 5, wherein the reclaim vector is adjusted to steal frames from partitions whose current size is at least the virtual minimum size but less than the target size.
Claim 7
Dependent Claim
46 words
A method according to claim 6, wherein, if unable to obtain enough frames from partitions whose current size is at least the virtual minimum size but less than the target size, frames are stolen from any partition whose size is at least the virtual minimum size.
Claim 8
Dependent Claim
15 words
A method according to claim 1, wherein each partition has the same virtual minimum size.
Claim 9
Dependent Claim
40 words
A method according to claim 1, wherein, in the step of adjusting, each reclaim vector is adjusted such that each partition can steal sufficient frames to achieve that partition's minimum size from only those partitions which stole frames from it.
Claim 10
Dependent Claim
21 words
A method according to claim 1, wherein the step of stealing is performed by removing the lowest page in LRU order.
Claim 11
Independent Claim
133 words
A method for dynamically reallocating resources among partitions in a dataset partitioned, page oriented cache of a defined capacity intercoupling a processor to an external storage subsystem, said processor including means for storing pages of a dataset into a plurality of cache partitions, comprising the steps of: (a) comparing a target size with a virtual minimum size for each partition; (b) if the target size is less than the virtual minimum size for a partition, assign a reclaim vector to such partition which directs that frames be stolen in an amount equivalent to the greater of the difference between the minimum size and the target size or the difference between the minimum size and the current size; and (c) stealing frames in accordance with the assigned reclaim vectors in response to predetermined events.
Claim 12
Dependent Claim
15 words
A method according to claim 11, wherein a predetermined event is a cache miss reference.
Claim 13
Dependent Claim
58 words
A method according to claim 11, further comprising the step of, if the target size is greater than the virtual minimum size for a partition, assigning a reclaim vector to such partition which directs that frames be stolen in an amount equivalent to the greater of the difference between the target size and the current size, and zero.
Claim 14
Dependent Claim
237 words
A data processing system for avoiding a cache full condition in a dataset partitioned, page oriented cache of a defined capacity having dynamic resource allocation and intercoupling a processor to an external storage subsystem, said processor, comprising the steps of: a direct access storage device; a processor includes means for storing pages of a dataset into a plurality of cache partitions in said partitioned cache; a dataset partitioned, page oriented cache of a defined capacity and having a plurality of partitions, capable of dynamic resource allocation, and intercoupling the direct access storage device and the processor; and a controller for: periodically determines the target size of each partition for optimal partitioning; assigning a reclaim vector to each partition specifying the number of frames to be stolen from each of the other partitions necessary to achieve a corresponding target size; if the target size of a particular partition is less than the partition's virtual minimum size, adjusting that partition's reclaim vector to enable the partition to steal sufficient frames from other partitions to achieve the virtual minimum size; and responsive to one or more page cache miss references, stealing one or more frames from other partitions, as directed by the reclaim vector of the partition storing the dataset to which the missed page reference is a member, and adding the resulting frame to the storing partition, and modifying the storing partition's reclaim vector to reflect the pages stolen.
Claim 15
Dependent Claim
12 words
A system according to claim 14, wherein the controller is the processor.
References Cited (Backward Citations)
US4463424A
Cited
US4489378A
Cited
US4603382A
Cited
US4754394A
Cited
US4980822A
Cited
US4926323A
Cited
US5394531A
Cited
US5138705A
Cited
US5285527A
Cited
US5457793A
Cited
US5434992A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-16 | 2000-01-15 | 2000-07-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-16 | 2004-01-15 | 2004-07-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-16 | 2008-01-15 | 2008-07-16 | $7700.00 | Window Closed / Lapsed |