tailieunhanh - THE FRACTAL STRUCTURE OF DATA REFERENCE- P17

THE FRACTAL STRUCTURE OF DATA REFERENCE- P17:For purposes of understanding its performance, a computer system is traditionally viewed as a processor coupled to one or more disk storage devices, and driven by externally generated requests (typically called transactions). Over the past several decades, very powerful techniques have become available to the performance analyst attempting to understand, at a high level, the operational behavior of such systems. | Memory Management in an LRU Cache 67 2. GENERALIZED LRU Within our adopted analysis framework we have seen that the lru algorithm is optimal in the case that 01 02 . 0 . We now show that it is also possible to extend the lru algorithm so as to achieve optimality under the full range of conditions permitted by the multiple-workload hierarchical reuse model. As before our starting point is the marginal benefit of cache memory. Our objective is to arrange matters so that the marginal benefit as stated by is the same for all workloads i. To accomplish this we now observe that the quantity is the same for all i if and only if Ti is proportional to 0i DJzi. To accomplish an optimal arrangement of cache memory we may therefore proceed by adjusting the single reference residency times of the individual workloads so as to achieve the proportionality relationship just stated. It should be recalled that the value of 0i for a given workload can be estimated from measurements of Ti and Ti this relationship is stated by . By associating cached data with timestamps showing the time ofthe most recent reference it is not difficult in turn to measure the quantities Ti and Ti. To measure Ti for example one approach is to occasionally place dummy entries entries with no associated data into the lru list alongside the entries being staged for workload i. When a dummy entry reaches the bottom ofthe lru list the time since it was initially placed into the list provides a direct measurement ofthe single-reference residency time. Similarly the discussion of simulation techniques previously presented in Chapter 4 includes a method for using cache entry timestamps to measure the quantities Ti. To establish the desired proportionality relationship our first step is to associate each cached item of data with a timestamp showing the time of last reference and to use these timestamps as a basis for measuring the quantities Ti Ti and 0i. Optionally we may also choose to assign .