Method for dynamically allocating LRU/MRU managed memory among concurrent sequential processes

• US 4,463,424 A
• Filed: 10/21/1983
• Issued: 07/31/1984
• Est. Priority Date: 02/19/1981
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mattson, Richard L., Rodriguez-Rosell, Juan A.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US06/544,331
• Time in Patent Office: 284 Days
• Field of Search: 364/200 MS File, 364/300
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list

Abstract

Short traces of consecutive CPU references to storage are accumulated and processed to ascertain hit ratio as a function of cache size. From this determination, an allocation of cache can be made. Because this determination requires minimal processing time, LRU-referenceable memory space among concurrently executing sequential processes is used dynamically by a CPU cache manager.

Claims

1. A CPU-implementable method for dynamically adjusting the portions of LRU-referenceable memory space shared among concurrently executing sequential processes in which a supervisory process is invoked to manage the memory referencing, wherein the steps include:

(a) determining an optimal space allocation among the processes by

(1) accumulating a trace of consecutive references to items stored in the LRU memory space;

(2) partitioning the space over a range of predetermined sizes;

(3) ascertaining the hit/miss ratios from the accumulated trace as a function of LRU memory space partition sizes; and

(4) responsive to each trace reference, LRU ordering the items in the partitioned space and adjusting for overflow among the partitions; and

(b) reallocating the partitions among the concurrent processes according to and in overlapped relation with the determination step by the supervisory process.

2. A machine-implemented method for dynamically selecting pageable groups of data and associated cache sizes with respect to one or more caches of a CPU-accessible demand paging hierarchical storage system, said system having an LRU/MRU page replacement policy, including the erasure of cache stored items, the cache being shared among concurrently executing sequential processes in which a supervisory process is invoked to manage the memory references, the method steps include:

(a) determining the optimal space allocation among the processes by

(1) accumulating a trace of consecutive references to items stored in the cache,

(2) processing the traces to obtain hit/miss ratios as a function of q pageable groups and p cache sizes, said processing step including the step of partitioning an LRU page stack into p+1 equivalence classes, all pages in any given partition having the same stack distance,

(3) arranging the groups of pageable data responsive to each reference by ordering the items in the cache and adjusting for overflow so as to maintain the highest hit ratio as a function of cache size; and

(b) reallocating the cache among the concurrent processes according to and in overlapped relation with the determination step by the supervisory process.

3. A machine-implemented method according to claim 2, wherein the determination step requires no more than (2p+1) items requiring movement, alteration, or scanning per referenced item and no more than (p+1)^q computations within each predetermined time period.

4. A machine-implemented method according to claim 3, wherein:

(a) the step of partitioning an LRU stack into equivalence classes is a function of the consecutive addition of the maximum predetermined group sizes; and

(b) a reference to an item for a given cache size is registered as a miss if the group number of an item i in an LRU stack is less than the group (position) number and is registered as a hit for all cache capacities equal to or greater than the group number.