Reward based cache management

Abstract

A method and apparatus for buffering is provided. 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 fall 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. 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 accumulated for the buffer and, once accumulated, the buffer's profit value earns the buffer's place in the list. Specifically, after new data is added to a buffer, it is placed at the insertion point for the list. When the buffer is next accessed, it is placed at the top of list. As other buffers are added to the top of the list above the buffer, the buffer is pushed down the list. As the buffer is pushed down, its access history is updated, but its order within the list is left unchanged. When the buffer reaches a certain position within the list, the buffer's profit value dictates the buffer's place in the list.