A study of various caching strategies for data cache management.


Abstract: We review a frequency based replacement algorithm for managing caches used for disk blocks by a File System, DBMS or disk control unit, which we refer to as Data Caches. LRU replacement is generally used widely for such caches. We present a replacement algorithm based on the concept of maintaining reference counts in which locality has been "factored out". In this algorithm replacement choices are made using a combination of reference frequency and block age. Studies show that this algorithm can offer up to 34% performance improvement over LRU replacement, where the improvement is expressed as the fraction of the performance gain achieved between LRU replacement and the theoretically optimal policy in which the reference string must be known in advance. Furthermore, the implementation complexity and efficiency of this algorithm is comparable to one using LRU replacement algorithm.

Introduction: Processor speeds are increased dramatically over the past few years and are expected to continue to double every year, with main memory density doubling every two years. A typical data storage hierarchy consists of main memory, magnetic disks, an optical and tape drives. In any memory hierarchy, performance can be improved by caching
Data from a lower level of the hierarchy in a higher level. The goal in designing a cache management algorithm is to achieve a low cache miss rate as possible subject to constraints on the complexity of the algorithm. Caching can be used to increase system response time and improve data throughput of the system.
A. Definitions:
Cache can be defined as small high-speed memories placed between the processor and the main memory that increase the effective memory bandwidth. They are effective because they exploit the locality property of programs. Caches work on the premise that data in the cache will be reused often. To achieve this caches exploit the principles of spatial and temporal locality of reference. Spatial locality implies that if an object is referenced then near by objects will also soon be accessed. Temporal locality implies that a referenced object will tend to be referred again in the near future.
The goodness of a replacement algorithm lies in its ability to evict data that has no immediate need to reside in the cache and to retain data more likely to be accessed for as small a cache size as possible. Caches can be classified as Disk caches and CPU caches. The disk cache is a buffer in electronic storage of recently used portions of the disk space and as the potential to improve the system performance significantly. A CPU cache is present between CPU and main memory, the Disk cache is present between the main memory or CPU and hard disk. The design issues for Data caches are somewhat different than those of CPU caches. In

terms of differences in reference behavior, in general it seems that there is less locality in data caches as compared to CPU caches. If there were infact a small degree of dependence of each reference on previous references, then it is possible that an independent reference assumption could be used to accurately model reference behavior. In such a case the optimal cache management policy would be able to keep the blocks with the highest reference probability in the cache at all times. In practice of course there would be a problem in determining these probabilities. However, given a reference string, produced by a trace, the blocks can be sorted by reference frequency and this policy can be simulated. If the cache doesn't hold the information that is requested by the CPU, then a cache miss is said to have occurred. If the information requested be in the cache then it is said to be a Cache Hit. The time to access the information from the cache is called Hit time. If there is a cache miss then to get the information we need to access the next lower level memory on storage and this is known as miss penalty. The method by which a block in the cache is discarded to bring a new block upon request is called Block Replacement Algorithm. A good algorithm gets a higher hit rate with a lower cache size plus increasing the overall efficiency of the