一种松竞争性缓存快速存取算法

在文件缓存调度中，每个文件都有固定的大小和被存取的消耗，为了响应对文件操作的一系列请求，把缓存中所有文件的大小维持在一个特定的k值之内，从而最小化文件存取的总消耗。给出一个简单明确的快速存取算法，该算法总结了许多有名的内存分页策略和加权缓存策略，证明了对于大多数k的选择，存取消耗可以忽略不计或者是最佳值的恒定倍数(与k值无关)。从而证明了在线分页算法的竞争比可视为一个常数。

On-line algorithm of loose competitive caching

In response to a sequence of requests for files, where each file has a specified size and retrieval cost, the total size of each file in cache was maintained at some specified k so as to minimize the total retrieval cost. A simple deterministic on-line algorithm was proposed. In this algorithm, many well-known paging and weighted caching strategies were generalized, and the retrieval cost was either insignificant or at most a constant (independent of k) times the optimum value for most k. This helps explain...