hide
Free keywords:
-
Abstract:
A generalized paging problem is considered. Each request is
expressed as a set of $u$ pages. In order to satisfy the
request, at least one of these pages must be in the cache.
Therefore, on a page fault, the algorithm must load into the cache
at least one page out of the $u$ pages given in the request.
The problem arises in systems in which requests can be serviced by
various utilities (e.g., a request for a data that lies in various
web-pages) and a single utility can service many requests (e.g., a
web-page containing various data). The server has the freedom to
select the utility that will service the next request and hopefully
additional requests in the future.
The case $u=1$ is simply the classical paging problem, which is
known to be polynomially solvable. We show that for any $u>1$ the
offline problem is NP-hard and hard to approximate if the cache
size $k$ is part of the input, but solvable in polynomial time for
constant values of $k$. We consider mainly online algorithms, and
design competitive algorithms for arbitrary values of $k,u$. We
study in more detail the cases where $u$ and $k$ are small.
%We further study two modifications of the problem.
We also give an algorithm which uses resource
augmentation and which is asymptotically optimal for $u=2$.
