查看文章

The optimal offline cache replacement algorithm is a MIN algorithm that chooses which data item to remove when a new data item is brought from lower level of cache or main memory. The optimal offline algorithm evicts a cache item whose next request is the furthest away. For a particular program, the performance behavior of the cache memory is determined by memory and block sizes and by the nature of the replacement algorithm. Replacement algorithms, however, deserve analysis because they are based on a variety of assumptions and design considerations. This paper presents a simpler proof based on the greedy algorithm. The paper demonstrates that every ideal solution can be repeatedly transformed into the solution provided by the greedy algorithm without increasing the miss of the optimal solution, hence demonstrating that the greedy solution is providing optimality. This paper also presents a new …