A competitive online algorithm for the paging problem with "shelf" memory

Abstract

We consider an extension of the two-level paging problem. Besides a fast memory (the cache) and a slow memory, we postulate a third memory, called the \shelf", near the fast memory so that it is more cost-e cient to store or retrieve a page from the shelf than to retrieve a page from the slow memory. Unlike the standard two-level paging prob- lem, the extension is not a special case of the K-server problem as it is not embedded in a space with a symmetric metric. Our goal is to establish an upper bound on the competitive ratio of this \three-level" memory paging problem. We show that unless per page storage costs more than per page retrieval from the shelf, a simple extension of the well-known LRU algorithm has competitive ratio of 2k + l + 1, where k and l are, respectively, the capacities of the cache and the shelf. If, in addition, k l, then the same algorithm is k + l + 2-competitive