Efficient Caching Algorithms for Two-Level Disk Cache Hierarchies

To overcome the speed gap between the processor and disk, caches of various forms have been traditionally used. One example is the buffer cache built into the UNIX operating system that keeps recently used disk blocks in main memory. Another example is the so-called disk cache in disk controllers. In most cases, the buffer cache is managed independently of the disk cache and vice versa. It is therefore very likely that the disk blocks kept in one cache are also found in the other cache resulting in reduction of total caching capacity. In this paper, we propose various caching algorithms that aim at minimizing such double caching in two-level disk cache hierarchies. We also evaluate the proposed algorithms by trace-driven simulation, demonstrating that they lead to 10-20% improvements in the average access time. Keywords : two-level disk cache hierarchies, double caching, trace-driven simulation, average disk block access time 1 Introduction The gap between processor and disk speed is ..