Implementation and Performance Evaluation of an Efficient Caching Algorithm for Two-Level Disk Cache Hierarchies

The speed gap between the processor and disks is becoming a serious problem in computer systems today. To rectify this problem, various caching techniques have been traditionally used. For example, the UNIX operating system has a built-in cache called the buffer cache to keep recently used disk blocks in main memory. Another example is the so-called disk cache in I/O processors and intelligent disk controllers. These two types of cache form a two-level disk cache hierarchy where the buffer cache is the primary cache and the disk cache the secondary cache. In such a two-level cache hierarchy, unless special care is taken, it is likely that the disk blocks kept in one cache are also kept in the other cache resulting in reduced total caching capacity. In this paper, we describe the design and implementation of a unified cache management algorithm called the push-pull algorithm that tries to avoid such double caching. In the proposed algorithm, a new disk block is stored in only one cache ..