S-Space College of Engineering/Engineering Practice School (공과대학/대학원) Dept. of Industrial Engineering (산업공학과) Journal Papers (저널논문_산업공학과)
A competitive online algorithm for the paging problem with "shelf" memory
- Hong, Sung-Pil
- Issue Date
- Springer Verlag
- Lecture Notes in Computer Science, Vol. 1627/1999 (1999) 400-408
- 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
- 0302-9743 (print)
- Files in This Item: There are no files associated with this item.