Application-Controlled Paging for a Shared Cache.
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 $H_k \sim \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 $2H_{P-1}+2 \sim 2 \ln P$. 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 min{HP-1,Hk}, 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.
Introduction
Caching is a useful technique for obtaining high performance in these days where the
latency of disk access is relatively high. Today's computers typically have several
application processes running concurrently on them, by means of time sharing and
multiple processors. Some processes have special knowledge of their future access
patterns. Cao et al [CFL94a, CFL94b] exploit this special knowledge to develop
effective file caching strategies.
An application providing specific information about its future needs is equivalent
to the application having its own caching strategy for managing its own pages in cache.
We consider the multi-application caching problem, formally defined in Section 3, in
which P concurrently executing application processes share a common cache of size k.
In Section 4 we propose an online application-controlled caching scheme in which
decisions need to be taken at two levels: when a page needs to be evicted from cache,
the global strategy chooses a victim process, but the process itself decides which of
its pages will be evicted from cache.
Each application process may use any available information about its future page
requests when deciding which of its pages to evict. However, we assume no global
information about the interleaving of the individual page request sequences; all our
bounds are with respect to a worst-case interleaving of the individual request sequences

Competitive ratios smaller than the H k lower bound for classical caching [FKL
are possible for multi-application caching, because each application may employ future
information about its individual page request sequence. 1 The application-controlled
algorithm proposed by Cao, Felten, and Li [CFL94a] achieves a competitive ratio
of which we prove in the Appendix. We show in Sections 5-7 that our
new online application-controlled caching algorithm improves the competitive ratio
to which is optimal up to a factor of 2 in the realistic scenario
when k. (If we use the algorithm of [FKL + 91] for the case P - k, the resulting
bound is optimal up to a factor of 2 for all P .) Our results are significant since P is
often much smaller than k, perhaps by several orders of magnitude.
In the scenario where application processes occasionally make bad page replacement
decisions (or "mistakes"), we show in Section 8 that our online algorithm incurs
very few page faults globally as a function of the number of mistakes. Our algorithm
is also fair, in the sense that the mistakes made by one processor in its page
replacement decisions do not worsen the page fault rate of other processors.
Classical Caching and Competitive Analysis
The well-known classical caching (or paging) problem deals with a two-level memory
hierarchy consisting of a fast cache of size k and slow memory of arbitrary size. A
Here Hn represents the nth harmonic number
sequence of requests to pages is to be satisfied in their order of occurrence. In order
to satisfy a page request, the page must be in fast memory. When a requested page
is not in fast memory, a page fault occurs, and some page must be evicted from fast
memory to slow memory in order to make room for the new page to be put into fast
memory. The caching (or paging) problem is to decide which page must be evicted
from the cache. The cost to be minimized is the number of page faults incurred over
the course of servicing the page requests.
Belady [Bel66] gives a simple optimum offline algorithm for the caching problem;
the page chosen for eviction is the one in cache whose next request is furthest in
the future. In order to quantify the performance of an online algorithm, Sleator
and Tarjan [ST85] introduce the notion of competitiveness, which in the context of
caching can be defined as follows: For a caching algorithm A, let FA (oe) be the number
of page faults generated by A while processing page request sequence oe. If A is a
randomized algorithm, we let FA (oe) be the expected number of page faults generated
by A on processing oe, where the expectation is with respect to the random choices
made by the algorithm. An online algorithm A is called c-competitive if for every
page request sequence oe, we have FA (oe) - c \Delta FOPT (oe) fixed
constant. The constant c is called the competitive ratio of A. Under this measure, an
online algorithm's performance needs to be relatively good on worst-case page request
sequences in order for the algorithm to be considered good.
Sleator and Tarjan [ST85] show a lower bound of k on the competitive ratio of
deterministic caching algorithm. Fiat et al [FKL prove a lower bound of H k if
randomized algorithms are allowed. They also give a simple and elegant randomized
algorithm for the problem that achieves a competitive ratio of 2H k . Sleator
and McGeoch [MS91] give a rather involved randomized algorithm that attains the
theoretically optimal competitive ratio of H k .
3 Multi-application Caching Problem
In this paper we take up the theoretical issue of how best to use application pro-
cesses' knowledge about their individual future page requests so as to optimize caching
performance. For analysis purposes we use an online framework similar to that of
As mentioned before, the caching algorithms in [FKL
use absolutely no information about future page requests. Intuitively, knowledge
about future page requests can be exploited to decide which page to evict from the
cache at the time of a page fault. In practice an application often has advance knowledge
of its individual future page requests. Cao, Felten and Li [CFL94a, CFL94b]
introduced strategies that try to combine the advance knowledge of the processors in
order to make intelligent page replacement decisions.
In the multi-application caching problem we consider a cache capable of
storing k pages that is shared by P different application processes, which
we denote Each page in cache and memory belongs to
ONLINE ALGORITHM FOR MULTI-APPLICATION CACHING 3
exactly one process. The individual request sequences of the processes
may be interleaved in an arbitrary (worst-case) manner.
Worst-case measure is often criticized when used for evaluating caching algorithms
for individual application request sequences [BIRS91, KPR92], but we feel that the
worst-case measure is appropriate for considering a global paging strategy for a cache
shared by concurrent application processes that have knowledge of their individual
page request sequences. The locality of reference within each application's individual
request sequence is accounted for in our model by each application process's knowledge
of its own future requests. The worst-case nature of our model is that it assumes
nothing about the order and durations of time for which application processes are
active. In this model our worst-case measure of competitive performance amounts to
considering a worst-case interleaving of individual sequences.
The approach of Cao et al [CFL94a] is to have the kernel deterministically choose
the process owning the least recently used page at the time of a page fault and ask that
process to evict a page of its choice (which may be different from the least recently
used page). In Appendix A we show under the assumption that processes always
make good page replacement decisions that Cao et al's algorithm has a competitive
2. The algorithm we present in the next section and
analyze thereafter improves the competitive ratio to 2H P
Online Algorithm for Multi-application Caching
Our algorithm is an online application-controlled caching strategy for an operating
system kernel to manage a shared cache in an efficient and fair manner. We show in the
subsequent sections that the competitive ratio of our algorithm is 2H
and that it is optimal to within a factor of about 2 among all online algorithms. (If
we can use the algorithm of [FKL
On a page fault, we first choose a victim process and then ask it to evict a
suitable page. Our algorithm can detect mistakes made by application processes,
which enables us to reprimand such application processes by having them pay for
their mistakes. In our scheme, we mark pages as well as processes in a systematic
way while processing the requests that constitute a phase.
1 The global sequence of page requests is partitioned into a consecutive
sequence of phases; each phase is a sequence of page requests. At the beginning of
each phase, all pages and processes are unmarked. A page gets marked during a phase
when it is requested. A process is marked when all of its pages in cache are marked.
A new phase begins when a page is requested that is not in cache and all the pages
in cache are marked. A page accessed during a phase is called clean with respect to
that phase if it was not in the online algorithm's cache at the beginning of a phase.
A request to a clean page is called a clean page request. Each phase always begins
with a clean page request.
ONLINE ALGORITHM FOR MULTI-APPLICATION CACHING 4
Our marking scheme is similar to the one in [FKL + 91] for the classical caching
problem. However, unlike the algorithm in [FKL + 91], the algorithm we develop is a
non-marking algorithm, in the sense that our algorithm may evict marked pages. In
addition, our notion of phase in Definintion 1 is different from the notion of phase
in [FKL + 91], which can be looked upon as a special case of our more general notion.
We put the differences into perspective in Section 4.1.
Our algorithm works as follows when a page p belonging to process P r is requested:
1. If p is in cache:
(a) If p is not marked, we mark it.
(b) If process P r has no unmarked pages in cache, we mark P r .
2. If p is not in cache:
(a) If process P r is unmarked and page p is not a clean page with respect
to the ongoing phase (i.e, P r has made a mistake earlier in the phase by
evicting p) then:
i. We ask process P r to make a page replacement decision and evict one
of its pages from cache in order to bring page p into cache. We mark
page p and also mark process P r if it now has no unmarked pages in
cache.
(b) Else (process P r is marked or page p is a clean page, or both):
i. If all pages in cache are marked, we remove marks from all pages
and processes, and we start a new phase, beginning with the current
request for p.
ii. Let S denote the set of unmarked processes having pages in the cache.
We randomly choose a process P e from S, each process being chosen
with a uniform probability 1=jSj.
iii. We ask process P e to make a page replacement decision and evict one
of its pages from cache in order to bring page p into cache. We mark
page p and also mark process P e if it now has no unmarked page in
cache.
Note that in Steps 2(a)i and 2(b)iii our algorithm seeks paging decisions from
application processes that are unmarked. Consider an unmarked process P i that has
been asked to evict a page in a phase, and consider P i 's pages in cache at that time.
Let u i denote the farthest unmarked page of process P i ; that is, u i is the unmarked
page of process P i whose next request occurs furthest in the future among all of P i 's
unmarked cached pages. Note that process P i may have marked pages in cache whose
next requests occur after the request for u i .
2 The good set of an unmarked process P i at the current point in the
phase is the set consisting of its farthest unmarked page u i in cache and every marked
page of P i in cache whose next request occurs after the next request for page u i . A
page replacement decision made by an unmarked process P i in either Step 2(a)i or
Step 2(b)iii that evicts a page from its good set is regarded as a good decision with
respect to the ongoing phase. Any page from the good set of P i is a good page for
eviction purposes at the time of the decision. Any decision made by an unmarked
process P i that is not a good decision is regarded as a mistake by process P i .
If a process P i makes a mistake by evicting a certain page from cache, we can
detect the mistake made by P i if and when the same page is requested again by P i in
the same phase while P i is still unmarked.
In Sections 6 and 7 we specifically assume that application processes are always
able to make good decisions about page replacement. In Section 8 we consider fairness
properties of our algorithm in the more realistic scenario where processes can make
mistakes.
4.1 Relation to Previous Work on Classical Caching
Our marking scheme approach is inspired by a similar approach for the classical
caching problem in [FKL + 91]. However, the phases defined by our algorithm are
significantly different in nature from those in [FKL + 91]. Our phase ends when there
are k distinct marked pages in cache; more than k distinct pages may be requested in
the phase. The phases depend on the random choices made by the algorithm and are
probabilistic in nature. On the other hand, a phase defined in [FKL
exactly k distinct pages have been accessed, so that given the input request sequence,
the phases can be determined independently of the caching algorithm being used.
The definition in [FKL + 91] is suited to facilitate the analysis of online caching
algorithms that never evict marked pages, called marking algorithms. In the case
of marking algorithms, since marked pages are never evicted, as soon as k distinct
pages are requested, there are k distinct marked pages in cache. This means that the
phases determined by our definition for the special case of marking algorithms are
exactly the same as the phases determined by the definition in [FKL + 91]. Note that
our algorithm is in general not a marking algorithm since it may evict marked pages.
While marking algorithms always evict unmarked pages, our algorithm always calls
on unmarked processes to evict pages; the actual pages evicted may be marked.
5 Lower Bounds for OPT and Competitive Ratio
In this section we prove that the competitive ratio of any online caching algorithm
can be no better than minfH g. Let us denote by OPT the optimal offline
algorithm for caching that works as follows: When a page fault occurs, OPT evicts
the page whose next request is furthest in the future request sequence among all pages
in cache.
As in [FKL + 91], we will compare the number of page faults generated by our
online algorithm during a phase with the number of page faults generated by OPT
during that phase. We express the number of page fronts as a function of the number
of clean page requests during the phase. Here we state and prove a lower bound on
the (amortized) number of page faults generated by OPT in a single phase. The
proof is a simple generalization of an analogous proof in [FKL + 91], which deals only
with the deterministic phases of marking algorithms.
Lemma 1 Consider any phase oe i of our online algorithm in which ' i clean pages are
requested. Then OPT incurs an amortized cost of at least ' i =2 on the requests made
in that phase. 2
be the number of clean pages in OPT 's cache at the beginning of phase
is the number of pages requested in oe i that are in OPT 's cache but not
in our algorithm's cache at the beginning of oe i . Let d i+1 represent the same quantity
for the next phase oe i+1 . Let d dm of the d i+1 clean pages in
OPT 's cache at the beginning of oe i+1 are marked during oe i and d u of them are not
marked during oe i . Note that d
Of the ' i clean pages requested during oe i , only d i are in OPT 's cache, so OPT
generates at least ' during oe i . On the other hand, while processing
the requests in oe i , OPT cannot use d u of the cache locations, since at the beginning
of oe i+1 there are d u pages in OPT 's cache that are not marked during oe i . (These d u
pages would have to be in OPT 's cache before oe i even began.) There are k marked
pages in our algorithm's cache at the end of oe i , and there are dm other pages marked
during oe i that are out of our algorithm's cache. So the number of distinct pages
requested during oe i is at least dm k. Hence, OPT serves at least dm
corresponding to oe i without using d u of the cache locations. This means that OPT
generates at least (k during oe i . Therefore, the number
of faults OPT generates on oe i is at least
Let us consider the first j phases. In the jth phase of the sequence, OPT has
at least ' faults. In the first phase, OPT generates k faults and
k. Thus the sum of OPT 's faults over all phases is at least
where we use the fact that d 2 - Thus by definition, the amortized number of
faults OPT generates over any phase oe i is at least ' i =2.
By "amortized" in Lemma 1 we mean for each j - 1 that the number of page faults made by
OPT while serving the first j phases is at least
is the number of clean page
requests in the ith phase.
Next we will construct a lower bound for the competitive ratio of any randomized
online algorithm even when application processes have perfect knowledge of their
individual request sequences. The proof is a straightforward adaptation of the proof
of the H k lower bound for classical caching [FKL + 91]. However, in the situation at
hand, the adversary has more restrictions on the request sequence that he can use to
prove the lower bound, thereby resulting in a lowering of the lower bound.
Theorem 1 The competitive ratio of any randomized algorithm for the multi-application
caching problem is at least minfH P even if application processes
have perfect knowledge of their individual request sequences.
lower bound on the classical caching problem from [FKL
is directly applicable by considering the case where each process accesses only one
page each. This gives a lower bound of H k on competitive ratio.
In the case when P - k, we construct a multi-application caching problem based
on the nemesis sequence used in [FKL + 91] for classical caching. In [FKL + 91] a lower
bound of H k 0
is proved for the special case of a cache of size k 0 and a total of k
pages, which we denote c 1 , c 2 , . ,c k 0 +1 . All but one of the pages can fit in cache
at the same time. Our corresponding multi-application caching problem consists
of so that there is one process
corresponding to each page of the classical caching lower bound instance for a k 0 -
sized cache . Process
. The total number
pages among all the processes is k is the cache size; that is, all but one
of the pages among all the processes can fit in memory simultaneously.
In the instance of the multi-application caching problem we construct, the request
sequence for each process P i consists of repetitions of the double round-robin sequence
(1)
of length 2r i . We refer to the double round-robin sequence (1) as a touch of process P i .
When the adversary generates requests corresponding to a touch of process P i , we
say that it "touches process P i ."
Given an arbitrary adversarial sequence for the classical caching problem described
above, we construct an adversarial sequence for the multi-application caching problem
by replacing each request for page c i in the former problem by a touch of process
in the latter problem. We can transform an algorithm for this instance of
multi-application caching into one for the classical caching problem by the following
correspondence: If the multi-application algorithm evicts a page from process P j
while servicing the touch of process P i , the classical caching algorithm evicts page c j
in order to service the request to page c i . In Lemma 2 below, we show that there
is an optimum online algorithm for the above instance of multi-application caching
that never evicts a page belonging to process P i while servicing a fault on a request
for a page from process P i . Thus the transformation is valid, in that page c i is always
resident in cache after the page request to c i is serviced. This reduction immediately
implies that the competitive ratio for this instance of multi-application caching must
be at least H k 0
Lemma 2 For the above instance of multi-application caching, any online algorithm
A can be converted into an online algorithm A 0 that is at least as good in
an amortized sense and that has the property that all the pages for process P i are in
cache immediately after a touch of P i is processed.
Intuitively, the double round-robin sequences force an optimal online algorithm
to service the touch of a process by evicting a page belonging to another pro-
cess. We construct online algorithm A 0 from A in an online manner. Suppose that
both A and A 0 fault during a touch of process P i . If algorithm A evicts a page of P j ,
for some j 6= i, then A 0 does the same. If algorithm A evicts a page of P i during the
first round-robin while servicing a touch of P i , then there will be a page fault during
the second round-robin. If A then evicts a page of another process during the second
round-robin, then A 0 evicts that page during the first round-robin and incurs no fault
during the second round-robin. The first page fault of A was wasted; the other page
could have been evicted instead during the first round-robin. If instead A evicts another
page of P i during the second round-robin, then A 0 evicts an arbitrary page of
another process during the first round-robin, and A 0 incurs no page fault during the
second round-robin. Thus, if A evicts a page of P i , it incurs at least one more page
fault than does A 0 .
If A faults during a touch of P i , but A 0 doesn't, there is no paging decision for A 0
to make. If A does not fault during a touch of P i , but A 0 does fault, then A 0 evicts
the page that is not in A's cache. The page fault for A 0 is charged to the extra page
fault that A incurred earlier when A 0 evicted one of P i 's pages.
Thus the number of page faults that A 0 incurs is no more than the number of page
faults that A incurs. By construction, all pages of process P i are in algorithm A 0 's
cache immediately after a touch of process P i .
The double round-robin sequences in the above reduction can be replaced by single
round-robin sequences by redoing the explicit lower bound argument of [FKL
6 Holes
In this section, we introduce the notion of holes, which plays a key role in the analysis
of our online caching algorithm. In Section 6.2, we mention some crucial properties of
holes of our algorithm under the assumption that applications always make good page
replacement decisions. These properties are also useful in bounding the page faults
that can occur in a phase when applications make mistakes in their page replacement
decisions.
Definition 3 The eviction of a cached page at the time of a page fault on a clean
page request is said to create a hole at the evicted page. Intuitively, a hole is the lack
of space for some page, so that that page's place in cache contains a hole and not the
page. If page p 1 is evicted for servicing the clean page request, page p 1 is said to be
associated with the hole. If page p 1 is subsequently requested and another page p 2
is evicted to service the request, the hole is said to move to p 2 , and now p 2 is said
to be associated with the hole. And so on, until the end of the phase. We say that
hole h moves to process P i to mean that the hole h moves to some page p belonging
to process P i .
6.1 General observations about holes
All requests to clean pages during a phase are page faults and create holes. The
number of holes created during a particular phase equals the number of clean pages
requested during that phase. Apart from clean page requests, requests to holes also
cause page faults to occur. By a request to a hole we mean a request for the page
associated with that hole. As we proceed down the request sequence during a phase,
the page associated with a particular hole varies with time. Consider a hole h that
is created at a page p 1 that is evicted to serve a request for clean page p c . When a
request is made for page p 1 , some page p 2 is evicted, and h moves to p 2 . Similarly
when page p 2 is requested, h moves to some p 3 , and so on. Let
the temporal sequence of pages all associated with hole h in a particular phase such
that page p 1 is evicted when clean page p c is requested, page
evicted when p i\Gamma1 is requested and the request for p m falls in the next phase. Then
the number of faults incurred in the particular phase being considered due to requests
to h is m \Gamma 1.
6.2 Useful properties of holes
In this section we make the following observations about holes under the assumption
that application processes make only good decisions.
Lemma 3 Let u i be the farthest unmarked page in cache of process P i at some point
in a phase. Then process P i is a marked process by the time the request for page u i
is served.
This follows from the definition of farthest unmarked page and the nature of
the marking scheme employed in our algorithm.
Lemma 4 Suppose that there is a request for page p i , which is associated with hole h.
Suppose that process P i owns page p i . Then process P i is already marked at the time
of the present request for page p i .
associated with hole h because process P i evicted page p i when
asked to make a page replacement decision, in order to serve either a clean request or
a page fault at the previous page associated with h. In either case, page p i was a good
page at the time process P i made the particular paging decision. Since process P i was
unmarked at the time the decision was made, p i was either the farthest unmarked
page of process P i then or some marked page of process P i whose next request is after
the request for P i 's farthest unmarked page. By Lemma 3, process P i is a marked
process at the time of the request for page p i .
Lemma 5 Suppose that page p i is associated with hole h. Let P i denote the process
owning page p i . Suppose page p i is requested at some time during the phase. Then
hole h does not move to process P i subsequently during the current phase.
Proof : The hole h belongs to process P i . By Lemma 4 when a request is made to h,
marked and will remain marked until the end of the phase. Since only
unmarked processes are chosen to to evict pages, a request for h thereafter cannot
result in eviction of any page belonging to P i , so a hole can never move to a process
more than once.
Let there be R unmarked processes at the time of a request to a hole h. For
any unmarked process denote the farthest unmarked page of
process P j at the time of the request to hole h. Without loss of generality, let us
relabel the processes so that
is the temporal order of the first subsequent appearance of the pages u j in the global
page request sequence.
Lemma 6 In the situation described in (2) above, suppose during the page request
for hole h that the hole moves to a good page p i of unmarked process P i to serve the
current request for h. Then h can never move to any of the processes
during the current phase.
Proof : The first subsequent request for the good page p i that P i evicts, by definition,
must be the same as or must be after the first subsequent request for the farthest unmarked
page u i . So process P i will be marked by the next time hole h is requested, by
Lemma 4. On the other hand, the first subsequent requests of the respective farthest
unmarked pages u 1 , . , u appear before that of page u i . Thus, by Lemma 3, the
are already marked before the next time hole h (page
gets requested and will remain marked for the remainder of the phase. Hence, by the
fact that only unmarked processes get chosen, hole h can never move to any of the
7 Competitive Analysis of our Online Algorithm
Our main result is Theorem 2, which states that our online algorithm for the multi-application
caching problem is roughly 2 ln P-competitive, assuming application processes
always make good decisions (e.g., if each process knows its own future page
requests). By the lower bound of Theorem 1, it follows that our algorithm is optimal
in terms of competitive ratio up to a factor of 2.
COMPETITIVE ANALYSIS OF OUR ONLINE ALGORITHM 11
Theorem 2 The competitive ratio of our online algorithm in Section 4 for the multi-application
caching problem, assuming that good evictions are always made, is at most
2. Our competitive ratio is within a factor of about 2 of the best possible
competitive ratio for this problem.
The rest of this section is devoted to proving Theorem 2. To count the number of
faults generated by our algorithm in a phase, we make use of the properties of holes
from the previous section. If ' requests are made to clean pages during a phase, there
are ' holes that move about during the phase. We can count the number of faults
generated by our algorithm during the phase as
where N i is the number of times hole h i is requested during the phase. Assuming
good decisions are always made, we will now prove for each phase and for any hole h i
that the expected value of N i is bounded by H P \Gamma1 .
Consider the first request to a hole h during the phase. Let R h be the number of
unmarked processes at that point of time. Let CR h
be the random variable associated
with the number of page faults due to requests to hole h during the phase.
Lemma 7 The expected number E(CR h
of page faults due to requests to hole h is at
most HR h
We prove this by induction over R h . We have E(C
Suppose for . Using the same terminology and
notation as in Lemma 6, let the farthest unmarked pages of the R h unmarked processes
at the time of the request for h appear in the temporal order
in the global request sequence. We renumber the R h unmarked processes for convenience
so that page u i is the farthest unmarked page of unmarked process P i .
When the hole h is requested, our algorithm randomly chooses one of the R h
unmarked processes, say, process P i , and asks process P i to evict a suitable page.
Under our assumption, the hole h moves to some good page p i of process P i . From
Lemmas 5 and 6, if our algorithm chooses unmarked process P i so that its good
page p i is evicted, then at most R h \Gamma i processes remain unmarked the next time h is
requested. Since each of the R h unmarked processes is chosen with a probability of
1=R h , we have
E(CR h
R h
E(CR h \Gammai )
R h
APPLICATION-CONTROLLED CACHING WITH FAIRNESS 12
The last equality follows easily by induction and algebraic manipulations.
Now let us complete the proof of Theorem 2. By Lemma 4 the maximum possible
number of unmarked processes at the time a hole h is first requested is
implies that the average number of times any hole can be requested during a phase
is bounded by H P \Gamma1 . By (3), the total number of page faults during the phase is
at most '(1 We have already shown in Lemma 1 that the OPT algorithm
incurs an amortized cost of at least '=2 for the requests made in the phase. Therefore,
the competitive ratio of our algorithm is bounded by '(1 +H P 2.
Applying the lower bound of Theorem 1 completes the proof.
Application-Controlled Caching with Fairness
In this section we analyze our algorithm's performance in the realistic scenario where
application processes can make mistakes, as defined in Definition 2. We bound the
number of page faults it incurs in a phase in terms of page faults caused by mistakes
made by application processes during that phase. The main idea here is that if an
application process P i commits a mistake by evicting a certain page p and then during
the same phase requests page p while process P i is still unmarked, our algorithm makes
process pay for the mistake in Step 2(a)i.
On the other hand, if page p's eviction from process P i was a mistake, but process
marked when page p is later requested in the same phase, say, at time t,
then process P i 's mistake is ``not worth detecting'' for the following reason: Since
evicting page p was a mistake, it must mean that at the time t 1 of p's eviction, there
existed a set U of one or more unmarked pages of process P i in cache whose subsequent
requests appear after the next request for page p. Process P i is marked at the
time of the next request for p, implying that all pages in U were evicted by P i at
some times t 2 , t 3 , . t jU j+1 after the mistake of evicting p. If instead at time t 1 , t 2 ,
. t jU j+1 process P i makes the specific good paging decisions of evicting the farthest
unmarked pages, the same set fpg [ U of pages will be out cache at time t. In our
notion of fairness we choose to ignore all such mistakes and consider them "not worth
detecting."
Definition 4 During an ongoing phase, any page fault corresponding to a request
for a page p of an unmarked process P i is called an unfair fault if the request for
page p is not a clean page request. All faults during the phase that are not unfair are
called faults.
The unfair faults are precisely those page faults which are caused by mistakes
considered "worth detecting." We state the following two lemmas that follow trivially
from the definitions of mistakes, good decisions, unfair faults, and fair faults.
APPLICATION-CONTROLLED CACHING WITH FAIRNESS 13
Lemma 8 During a phase, all page requests that get processed in Step 2(a)i of our
algorithm are precisely the unfair faults of that phase. That is, unfair faults correspond
to mistakes that get caught in Step 2(a)i of our algorithm.
Lemma 9 All fair faults are precisely those requests that get processed in Step 2(b)iii.
We now consider the behavior of holes in the current mistake-prone scenario.
The number of holes in a phase equals the number of clean pages requested
in the phase.
Lemma 11 Consider a hole h associated with a page p of a process P i . If a request
for h is an unfair fault, process P i is still unmarked and the hole h moves to some
other page belonging to process P i . If a request for hole h is a fair fault, then process P i
is already marked and the hole h can never move to process P i subsequently during
the phase.
If the request for hole h is an unfair fault, then by definition process P i is
unmarked and by Lemma 8, h moves to some other page p 0 of process P i . If the
request for h is a fair fault, then by definition and the fact that the request for h is
not a clean page request, process P i is marked. Since our algorithm never chooses a
marked process for eviction, it follows that h can never visit process P i subsequently
during the phase.
During a phase, a hole h is created in some process, say P 1 , by some clean page
request. It then moves around zero or more times within process P 1 on account of
mistakes, until a request for hole h is a fair fault, upon which it moves to some
other process P 2 , never to come back to process P 1 during the phase. It behaves
similarly in process P 2 , and so on up to the end of the phase. Let T h denote the total
number of faults attributed to requests to hole h during a phase, of which F h faults
are fair faults and U h faults are unfair faults. We have
By Lemma 11 and the same proof techniques as those in the proofs of Lemma 7
and Theorem 2, we can prove the following key lemma:
Lemma 12 The expected number E(F h ) of page requests to hole h during a phase
that result in fair faults is at most H P \Gamma1 .
By Lemma 10, our algorithm incurs at most '+
page faults in a phase with
clean page requests. The expected value of this quantity is at most '(H P
, by Lemma 12.
The expression
is the number of unfair faults, that is, the number of
mistakes considered "worth detecting." Our algorithm is very efficient in that the
number of unfair faults is an additive term. For any phase OE with ' clean requests,
we denote
as M OE .
9 CONCLUSIONS 14
Theorem 3 The number of faults in a phase OE with ' clean page requests and M OE
unfair faults is bounded by '(1 . At the time of each of the M OE unfair
faults, the application process that makes the mistake that causes the fault must evict
a page from its own cache. No application process is ever asked to evict a page to
service an unfair fault caused by some other application process.
9 Conclusions
Cache management strategies are of prime importance for high performance comput-
ing. We consider the case where there are P independent processes running on the
same computer system and sharing a common cache of size k. Applications often have
advance knowledge of their page request sequences. In this paper we have address the
issue of exploiting this advance knowledge to devise intelligent strategies to manage
the shared cache, in a theoretical setting. We have presented a simple and elegant
application-controlled caching algorithm for the multi-application caching problem
that achieves a competitive ratio of 2H 2. Our result is a significant improvement
over the competitive ratios of 2P multi-application caching
and \Theta(H k ) for classical caching, since the cache size k is often orders of magnitude
greater than P . We have proven that no online algorithm for this problem can have a
competitive ratio smaller than minfH even if application processes have perfect
knowledge of individual request sequences. We conjecture that an upper bound
of H P \Gamma1 can be proven, up to second order terms, perhaps using techniques from
[MS91], although the resulting algorithm is not likely to be practical.
Using our notion of mistakes we are able to consider a more realistic setting when
application processes make bad paging decisions and show that our algorithm is a fair
and efficient algorithm in such a situation. No application needs to pay for some other
application process's mistake, and we can bound the global caching performance of our
algorithm in terms of the number of mistakes. Our notions of good page replacement
decisions, mistakes, and fairness in this context are new.
One related area of possible future work is to consider alternative models to our
model of worst-case interleaving. Another interesting area would be consider caching
in a situation where some applications have good knowledge of future page requests
while other applications have no knowledge of future requests. We could also consider
pages shared among application processes.



--R

A study of replacement algorithms for virtual storage com- puters
Competitive pag- A THE CAO

Implementation and performance of application-contolled file caching
On competitive algorithms for paging problems.
Markov paging.
A strongly competitive randomized paging algorithm.
Amortized efficiency of list update and paging rules.
--TR

--CTR
Guy E. Blelloch , Phillip B. Gibbons, Effectively sharing a cache among threads, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
application-controlled;competitive;online;caching;randomized