Dynamic storage allocation system for a prioritized cache

In a CPU-coupled, multi-echelon, staged data storage system, a computer-implemented method for managing a partitioned cache located at a predetermined echelon of said data storage system, said cache for storing data for immediate reference by CPU read and write operations, said method comprising the steps of:

• initially partitioning said cache into a plurality of cache partitions;
• for each cache partition:
• initially assigning a cache storage space allocation, and
• ascertaining a cache hit rate slope that corresponds to a ratio of a change in a reference hit rate to the corresponding change in said storage space allocation necessary to create said change in reference hit rate, said reference hit rate corresponding to the time rate at which references are made to data which is in said each cache partition;
• comparing the cache hit rate slope of a first cache partition with the cache hit rate slope of a second cache partition;
• if the cache hit rate slope of said first cache partition is less than the cache hit rate slope of said second cache, deleting cache storage space from said first cache partition and adding it to the cache storage space allocated to said second partition;
• otherwise,
• repeating the comparing and deleting steps.

A computer-implemented method for managing a LRU cache having data contents in a plurality of cache partitions defined over a priority class range of 1 . . . N, said cache being located in a predetermined echelon of a CPU-coupled, multi-echelon, staged storage system, data in said cache being referenced by read and write operations in a cycle, a cache partition metric termed "hit rate slope" being the ratio of a change in the time rate of said references to data located in the respective said cache partition to a corresponding change in the cache data storage space allocated to the respective said cache partition, said method comprising the steps of:

• assigning a priority value, a weighting factor, a first hit rate estimate and a first space allocation to each of N cache partitions;
• measuring the actual hit rate slope for each said cache partition;
• determining a weighted hit rate slope for each said cache partition, said weighted hit rate slope being equal to the product of the respective actual hit rate slope and the respective weighting factor;
• estimating the cache data storage space allocation change for each said cache partition required to equalize the weighted hit rate slope for all said cache partitions;
• and
• reallocating a fraction of the aggregate cache data storage space among said cache partitions for which said weighted hit rate slope is positive, in proportion to the corresponding said cache data storage space allocation changes, without substantially changing the existing cache data storage space allocation among said cache partitions for which said weighted hit rate slope is non-positive, said fraction being no more than unity.