Caching Files with a Program-based Last n Successors Model

Abstract

Recent increases in CPU performance have outpaced increases in hard drive performance. As a result, disk operations have become more expensive in terms of CPU cycles spent waiting for disk operations to complete. File prediction can mitigate this problem by prefetching files into cache before they are accessed. However, incorrect prediction is to a certain degree both unavoidable and costly. We present the Program-based Last N Successors (PLNS) file prediction model that identifies relationships between files through the names of the programs accessing them. Our simulation results show that PLNS makes at least 21.11% fewer incorrect predictions and roughly the same number of correct predictions as the last-successor model. We also examine the cache hit ratio of applying PLNS to the Least Recently Used (LRU) caching algorithm and show that a cache using PLNS and LRU together can perform as well as a cache up to 40 times larger using LRU alone.