13.14

Standard buffer managers assume each block is of the same size and costs the same to read. Consider a buffer manager that, instead of LRU, uses the rate of reference to objects, that is, how often an object has been accessed in the last \(n\) seconds. Suppose we want to store in the buffer objects of varying sizes, and varying read costs (such as web pages, whose read cost depends on the site from which they are fetched). Suggest how a buffer manager may choose which block to evict from the buffer.

Our eviction strategy can use 3 pieces of information: 1. Size of a block 2. Read Cost of a block 3. Rate of Reference of a block

Let’s define the following 3 functions for a block \(b\).

  1. Let the Size of a given block \(b\) be denoted as: \(S(b)\).

  2. Let the Read Cost of a given block \(b\) be denoted as: \(RC(b)\).

  3. Let the Rate of Reference of a given block \(b\) be denoted as: \(RoR(b)\).

Define a new function called the Total Cost function for a given block \(b\) denoted as \(TC(b)\). Also when defining the function \(TC(b)\), define it in such a way that it is directly proportional to \(S(b), RC(b)\) and \(RoR(b)\).

Then when the buffer manager wants to evict a block, evict the block that has the smallest cost. Let \(b_x\) be a block in the buffer such that \(TC(b_x) \leq TC(b)\) for all \(b\) in the buffer. When the buffer manager wants to evict a block, simply evict \(b_x\).