Cache memory management system and method

• US 6,807,607 B1
• Filed: 05/30/2000
• Issued: 10/19/2004
• Est. Priority Date: 08/17/1999
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lamparter, Bernd
• Primary Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/580,856
• Time in Patent Office: 1,603 Days
• Field of Search: 711/133, 711/134, 711/135, 711/136
• US Class Current: 711/133
• CPC Class Codes: G06F 12/121 using replacement algorithms

Abstract

Decisions to remove objects from a cache memory are made on an object-by-object basis. When a cache replacement decision is called for, a single object is selected from the cache. A weight value is assigned to the selected object in accordance with a predetermined methodology. The assigned object weight is compared to a current threshold weight. If the assigned object weight is the lesser of the two weights, the selected object is marked for removal from the cache and the threshold weight is reduced. If the assigned object weight is the greater of the two, the threshold weight is raised. In a preferred embodiment, the threshold weight is lowered more quickly than it is raised. The technique can be used in standalone workstations and in proxy servers, among other environments.

Claims

1. A cache memory management method comprising the steps of:

selecting a single object from the cache;

assigning an object weight to the selected object;

comparing the assigned object weight to an existing threshold weight;

if the assigned object weight is lower than the existing threshold weight, marking the selected object for removal from the cache and lowering the value of the threshold weight; and

if the assigned weight is greater than the existing threshold weight, raising the value of the threshold weight;

wherein the threshold weight is raised by increments different than the increments by which it is lowered.

2. A cache memory management method as set forth in claim 1 wherein the single object is selected at random from the set of objects stored in the cache.

3. A cache memory management method as set forth in claim 1 wherein the single object is selected using a defined selection schedule.

4. A cache memory management method as set forth in claim 1 wherein the incremental change in the threshold weight when the threshold is being lowered is at least five times as great as the incremental change in the threshold weight when the threshold is being raised.

6. A cache memory management system as set forth in claim 1 wherein the management logic lowers the threshold weight in increments greater than the increments used in raising the threshold weight.

5. A cache memory management system comprising:

object selection logic for selecting a candidate object from cache memory;

object weighting logic for assigning an object weight to the selected object;

comparison logic for comparing the assigned object weight to a current threshold weight; and

management logic for;

if the assigned object weight is lower than the current threshold weight, marking the selected object for removal from the cache and lowering the threshold weight, and

if the assigned object weight is greater than the current threshold weight, raising the threshold weight;

wherein the management logic lowers the threshold weight at a different rate than it raises the threshold weight.

7. A program product comprising a computer useable medium having a computer readable program embodied in said medium wherein the computer readable program when executed by a computer causes the computer to:

select a single object from a cache memory;

assign a weight to the selected object;

compare the assigned weight to an existing threshold weight;

if the assigned weight is lower than the existing threshold weight, mark the selected object for removal from the cache and lower the value of the threshold weight; and

if the assigned weight is greater than the existing threshold weight raise the value of the threshold weight;

wherein the threshold weight is raised by increments different than the increments by which it is lowered.

8. A program product as set forth in claim 7 wherein the single object is selected from cache memory at random.

9. A program product as set forth in claim 7 wherein the single object is selected from cache memory in accordance with a defined selection schedule.