Loading...
Application-Controlled Paging for a Shared Cache
Barve, Rakesh Grove, Edward F. Vitter, Jeffrey Scott
Barve, Rakesh
Grove, Edward F.
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
We propose a provably efficient application-controlled global strategy for organizing
a cache of size k shared among P application processes. Each application has access to information about its own future page requests, and by using that local information along with randomization in the context of a global caching algorithm, we are able to break through the conventional Hk ln k lower bound on the competitive ratio for the caching problem. If the P application processes always make good cache replacement decisions, our online application-controlled caching algorithm attains a competitive ratio of 2HP¡1 + 2 2 lnP. Typically, P is much smaller than k, perhaps by several orders of magnitude. Our competitive ratio improves upon the 2P + 2 competitive ratio achieved by the deterministic application-controlled strategy of Cao, Felten, and Li. We show that no online
application-controlled algorithm can have a competitive ratio better than minfHP¡1;Hkg, even if
each application process has perfect knowledge of its individual page request sequence. Our results
are with respect to a worst-case interleaving of the individual page request sequences of the P
application processes.
We introduce a notion of fairness in the more realistic situation when application processes do
not always make good cache replacement decisions. We show that our algorithm ensures that no application process needs to evict one of its cached pages to service some page fault caused by a mistake of some other application. Our algorithm not only is fair but remains efficient; the global paging performance can be bounded in terms of the number of mistakes that application processes make.
Description
AMS subject classi cations. 68N25, 68P01, 68P15, 68Q25, 68W20
PII. S0097539797324278
Date
2000
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Research Projects
Organizational Units
Journal Issue
Keywords
Caching, Application-controlled, Competitive, Online, Randomized
Citation
R. D. Barve, E. F. Grove, and J. S. Vitter. “Application-Controlled Paging for a Shared Cache,” SIAM Journal on Computing, 29(4), 2000, 1290–1303. An extended abstract appears in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’95), Milwaukee, WI, October 1995, 204–213. http://dx.doi.org/10.1137/S0097539797324278