Reward based cache management

Details Reward based cache management Reward based cache management

1998-12-31

2002-04-23

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S134000, C711S136000, C711S159000

Reexamination Certificate

active

06378043

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to buffering data in a computer system.
BACKGROUND OF THE INVENTION
A computer system has limited memory for storing data processed by the computer system. At any given time, the amount of data to be processed may exceed the amount that may be stored in volatile memory. To address this problem, buffering systems are used. Generally, buffering systems use an area of volatile memory to store a portion of the data to be processed. This area of memory is referred to as a cache. Whenever a computer system needs a subset of data, it retrieves the needed subset from the cache. If the cache does not hold the data, then the computer system retrieves the data from the storage area holding the needed data (e.g. a non-volatile storage device, or another area of volatile memory), then may store the retrieved data in the cache. Over time, the cache becomes fill. When the cache is full, and a computer system needs data that is not in the cache, the computer system replaces a subset of data currently residing in the cache with the needed data. If the replaced data has been changed while it resided in the cache , it is typically written to another storage area (e.g. non-volatile storage device) before it is replaced.
The process of replacing a subset of data in a cache with another subset of data from another storage area, and then storing the replaced subset of data in area other than the cache, is referred to as swapping. Excessive swapping can be expensive, especially for caches used to buffer data between disk storage and volatile memory.
To reduce swapping, many buffering approaches have been developed. Typically, the goal of these buffering approaches is to retain in cache data that will reduce swapping, and to replace data whose absence will least increase swapping. The degree to which a set of data tends to reduce swapping if retained in memory is referred to as the profit of the set of data.
Each buffering approach uses some measure to gauge profit. Measures of profit are typically based on access characteristics that reflect the history of access to a set of data. These historical access characteristics are used to estimate the degree to which the data is likely to be accessed in the near future. Data that has access characteristics that indicates that it will be the least likely to be accessed (i.e. low profit) is replaced from the cache, data with access characteristics that indicate that it will be the most likely to be accessed (i.e. high profit) is retained.
Conventional buffering approaches include the least recently used (LRU) approach, the least frequently used (LFU) approach, and the first-in first-out (FIFO) approach. The LRU approach replaces the least recently used data in the cache with new data. Thus, under the LRU approach, the data with the highest profit is the most recently used data. The LRU approach is based on “locality of reference,” the tendency in computer programs to access within a period of time the same subsets of data. Thus, the data that was the most recently accessed is the data that will most likely be accessed in the near future.
The LFU approach replaces the least frequently used data. Thus, under the LFU approach, the data with the highest profit is the most frequently used data. The FIFO approach replaces the oldest data. Under the FIFO approach, the data with the highest profit is the newest data added to the cache.
A wide range of applications, especially in the operating system and database systems, use an ordered LRU list. A common LRU list implementation is an ordered linked list of buffers. The order of the list is important because it reflects the order in which the buffers are selected for replacement. The order is thus referred to as the replacement order. The replacement order reflects the profit of buffers relative to each other, as measured by recency of use. The buffer at the top of the list contains the most recently used data. The buffer at the bottom of the list contains the least recently used data. When a given buffer is accessed, the buffer is moved to the top of the list. When new data is brought into the cache, it replaces data in the buffer at the bottom of list (least recently used buffer). The buffer is then moved to the top of the list.
One disadvantage of the LRU approach is that a considerable amount of overhead is required to rearrange the list each time a buffer's data is accessed. Because of locality of reference, buffers at the top of list are the most likely to be accessed again in the near future. Consequently, many buffers at the top of the list do not progress very far toward the bottom before they are moved back to the top. Thus, much work is often wasted juggling buffers that remain near the top anyway.
Another disadvantage of the LRU approach is that it uses only one characteristic that indicates profit and ignores other highly relevant ones. As a result, a buffer which is in fact associated with the lowest profit among all buffers may be placed at top of the list. The replacement order thus inaccurately reflects the order of the true profit. For example, an LRU list contains buffers which are all being frequently accessed, except for a first buffer. When the first buffer is accessed, it is moved to the top of the list, above buffers which in fact have much higher profit.
A conventional buffering approach which does account for multiple characteristics that indicate profit is the buffering approach developed by Robinson and Murthy, herein referred to as the “Robinson approach”. The Robinson approach is an extension of the LRU approach. Like the LRU approach, in the Robinson approach buffers are maintained in an ordered link list, and the most recently used buffers are moved to the top of the list. However, when selecting a buffer for replacement, Robinson measures profit by accounting for, in addition to recency of use, frequency of access. Specifically, for each buffer a touch count is maintained. The touch count reflects the number of times a buffer has been accessed. When a buffer is selected for replacement, a subset of the buffers at the bottom of the list are examined. The buffer with the lowest touch count in the subset is selected for replacement.
One disadvantage of the Robinson approach is that the order of the list of buffers does not actually reflect a measure of profit that accounts for both recency of use and frequency of use. The reason for this lack of accounting is that the Robinson measure of profit is inconsistently calculated. Frequency of access is considered only when selecting a replacement. However, when a buffer is accessed, it is moved to the top of the list regardless of its touch count. Moreover, while the buffer list could be reordered using a consistent measure of profit, such a reordering is an expensive operation, and may negate any gain.
Based on the foregoing, it is clearly desirable to provide a method for measuring profit that accounts for multiple characteristics relevant to profit, and that efficiently selects data for replacement based on a consistently applied measure of profit.
SUMMARY OF THE INVENTION
A method and apparatus for buffering data is described. According to an aspect of the present invention, a set of buffers is maintained in an ordered list based on a profit value generated for each buffer. The profit value for a buffer reflects multiple access characteristics of the buffer. The list of buffers is partitioned into divisions referred to as buckets. Each bucket contains a set of buffers and is associated with a subrange of the full range of profit values that may be generated. The bucket that covers the very top of the list is associated with highest profit value subrange, the bucket that covers the bottom of the list is associated with the lowest profit value subrange.
According to another aspect of the present invention, when data is first placed in a buffer, the buffer's position within the buffer list is not immediately based on its profit value. Instead, an access history is first accumulate

Affiliated with

Also associated with

Rating

Reward based cache management does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reward based cache management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reward based cache management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2862328