Beyond Physical Memory: Policies
In a virtual memory manager, life is easy when you have a lot of free
memory. A page fault occurs, you find a free page on the free-page list,
and assign it to the faulting page. Hey, Operating System, congratula-
tions! You did it again.
Unfortunately, things get a little more interesting when little memory
is free. In such a case, this memorypressure forces the OS to start paging
out pages to make room for actively-used pages. Deciding which page
(or pages) to evict is encapsulated within the replacement policy of the
OS; historically, it was one of the most important decisions the early vir-
tual memory systems made, as older systems had little physical memory.
Minimally, it is an interesting set of policies worth knowing a little more
about. And thus our problem:
THE CRUX: HOW TO DECIDE WHICH PAGE TO EVICT
How can the OS decide which page (or pages) to evict from memory?
Thisdecisionismadebythereplacementpolicyofthesystem,whichusu-
ally follows some general principles (discussed below) but also includes
certain tweaks to avoid corner-case behaviors.
22.1 Cache Management
Before diving into policies, we first describe the problem we are trying
to solve in more detail. Given that main memory holds some subset of
all the pages in the system, it can rightly be viewed as a cache for virtual
memory pages in the system. Thus, our goal in picking a replacement
policy for this cache is to minimize the number of cache misses, i.e., to
minimize the number of times that we have to fetch a page from disk.
Alternately, one can view our goal as maximizing the number of cache
hits, i.e., the number of times a page that is accessed is found in memory.
Knowing the number of cache hits and misses let us calculate the av-
erage memory access time (AMAT) for a program (a metric computer
architects compute for hardware caches [HP06]). Specifically, given these
values, we can compute the AMAT of a program as follows:
AMAT = TM + (PMiss ·TD) (22.1)
1
2 BEYOND PHYSICAL MEMORY: POLICIES
where TM represents the cost of accessing memory, TD the cost of ac-
cessing disk, and PMiss the probability of not finding the data in the
cache (a miss); PMiss varies from 0.0 to 1.0, and sometimes we refer to
a percent miss rate instead of a probability (e.g., a 10% miss rate means
PMiss = 0.10). Note you always pay the cost of accessing the data in
memory; when you miss, however, you must additionally pay the cost of
fetching the data from disk.
For example, let us imagine a machine with a (tiny) address space:
4KB, with 256-byte pages. Thus, a virtual address has two components: a
4-bitVPN(themost-significantbits)andan8-bitoffset(theleast-significant
bits). Thus, a process in this example can access 24 or 16 total virtual
pages. In this example, the process generates the following memory ref-
erences (i.e., virtual addresses): 0x000, 0x100, 0x200, 0x300, 0x400, 0x500,
0x600, 0x700, 0x800, 0x900. These virtual addresses refer to the first byte
of each of the first ten pages of the address space (the page number being
the first hex digit of each virtual address).
Let us further assume that every page except virtual page 3 is already
in memory. Thus, our sequence of memory references will encounter the
following behavior. hit, hit, hit, miss, hit, hit, hit, hit, hit, hit. We can
computethehitrate(thepercentofreferencesfoundinmemory): 90%, as
9 out of 10 references are in memory. The miss rate is thus 10% (PMiss =
0.1). In general, PHit +PMiss = 1.0; hit rate plus miss rate sum to 100%.
To calculate AMAT, we need to know the cost of accessing memory
and the cost of accessing disk. Assuming the cost of accessing memory
(TM) is around 100 nanoseconds, and the cost of accessing disk (TD) is
about 10 milliseconds, we have the following AMAT: 100ns+0.1·10ms,
which is 100ns + 1ms, or 1.0001 ms, or about 1 millisecond. If our hit
rate had instead been 99.9% (Pmiss = 0.001), the result is quite different:
AMAT is 10.1 microseconds, or roughly 100 times faster. As the hit rate
approaches 100%, AMAT approaches 100 nanoseconds.
Unfortunately, as you can see in this example, the cost of disk access
is so high in modern systems that even a tiny miss rate will quickly dom-
inate the overall AMAT of running programs. Clearly, we need to avoid
as many misses as possible or run slowly, at the rate of the disk. One way
to help with this is to carefully develop a smart policy, as we now do.
22.2 The Optimal Replacement Policy
To better understand how a particular replacement policy works, it
would be nice to compare it to the best possible replacement policy. As it
turns out, such an optimal policy was developed by Belady many years
ago [B66] (he originally called it MIN). The optimal replacement policy
leads to the fewest number of misses overall. Belady showed that a sim-
ple (but, unfortunately, difficult to implement!) approach that replaces
the page that will be accessed furthest in the future is the optimal policy,
resulting in the fewest-possible cache misses.
OPERATING
SYSTEMS
[VERSION 0.92] WWW.OSTEP.ORG
BEYOND PHYSICAL MEMORY: POLICIES 3
TIP: COMPARING AGAINST OPTIMAL IS USEFUL
Although optimal is not very practical as a real policy, it is incredibly
useful as a comparison point in simulation or other studies. Saying that
your fancy new algorithm has a 80% hit rate isn’t meaningful in isolation;
sayingthatoptimalachievesan82%hitrate(andthusyournewapproach
is quite close to optimal) makes the result more meaningful and gives it
context. Thus, in any study you perform, knowing what the optimal is
lets you perform. a better comparison, showing how much improvement
is still possible, and also when you can stop making your policy better,
because it is close enough to the ideal [AD03].
Hopefully, the intuition behind the optimal policy makes sense. Think
about it like this: if you have to throw out some page, why not throw
out the one that is needed the furthest from now? By doing so, you are
essentially saying that all the other pages in the cache are more important
than the one furthest out. The reason this is true is simple: you will refer
to the other pages before you refer to the one furthest out.
Let’s trace through a simple example to understand the decisions the
optimal policy makes. Assume a program accesses the following stream
of virtual pages: 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1. Figure 22.1 shows the behavior
of optimal, assuming a cache that fits three pages.
In the figure, you can see the following actions. Not surprisingly, the
first three accesses are misses, as the cache begins in an empty state; such
amississometimesreferredtoasacold-startmiss(orcompulsorymiss).
Then we refer again to pages 0 and 1, which both hit in the cache. Finally,
we reach another miss (to page 3), but this time the cache is full; a re-
placement must take place! Which begs the question: which page should
we replace? With the optimal policy, we examine the future for each page
currentlyinthecache(0,1,and2),andseethat0isaccessedalmostimme-
diately, 1 is accessed a little later, and 2 is accessed furthest in the future.
Thus the optimal policy has an easy choice: evict page 2, resulting in
pages 0, 1, and 3 in the cache. The next three references are hits, but then
Resulting
Access Hit/Miss? Evict Cache State
0 Miss 0
1 Miss 0, 1
2 Miss 0, 1, 2
0 Hit 0, 1, 2
1 Hit 0, 1, 2
3 Miss 2 0, 1, 3
0 Hit 0, 1, 3
3 Hit 0, 1, 3
1 Hit 0, 1, 3
2 Miss 3 0, 1, 2
1 Hit 0, 1, 2
Figure 22.1: Tracing The Optimal Policy
c© 2014, ARPACI-DUSSEAU
THREE
EASY
PIECES
4 BEYOND PHYSICAL MEMORY: POLICIES
ASIDE: TYPES OF CACHE MISSES
In the computer architecture world, architects sometimes find it useful
to characterize misses by type, into one of three categories: compulsory,
capacity, and conflict misses, sometimes called the Three C’s [H87]. A
compulsory miss (or cold-start miss [EF78]) occurs because the cache is
empty to begin with and this is the first reference to the item; in con-
trast, a capacity miss occurs because the cache ran out of space and had
to evict an item to bring a new item into the cache. The third type of
miss (a conflict miss) arises in hardware because of limits on where an
item can be placed in a hardware cache, due to something known as set-
associativity; it does not arise in the OS page cache because such caches
are always fully-associative, i.e., there are no restrictions on where in
memory a page can be placed. See H&P for details [HP06].
we get to page 2, which we evicted long ago, and suffer another miss.
Here the optimal policy again examines the future for each page in the
cache (0, 1, and 3), and sees that as long as it doesn’t evict page 1 (which
is about to be accessed), we’ll be OK. The example shows page 3 getting
evicted, although 0 would have been a fine choice too. Finally, we hit on
page 1 and the trace completes.
Wecanalsocalculatethehitrateforthecache: with6hitsand5misses,
the hit rate is HitsHits+Misses which is 66+5 or 54.5%. You can also compute
the hit rate modulo compulsory misses (i.e., ignore the first miss to a given
page), resulting in a 85.7% hit rate.
Unfortunately, as we saw before in the development of scheduling
policies, the future is not generally known; you can’t build the optimal
policy for a general-purpose operating system1. Thus, in developing a
real, deployable policy, we will focus on approaches that find some other
way to decide which page to evict. The optimal policy will thus serve
only as a comparison point, to know how close we are to “perfect”.
22.3 A Simple Policy: FIFO
Many early systems avoided the complexity of trying to approach
optimal and employed very simple replacement policies. For example,
some systems used FIFO (first-in, first-out) replacement, where pages
were simply placed in a queue when they enter the system; when a re-
placement occurs, the page on the tail of the queue (the “first-in” page) is
evicted. FIFO has one great strength: it is quite simple to implement.
Let’sexaminehowFIFOdoesonourexamplereferencestream(Figure
22.2, page 5). We again begin our trace with three compulsory misses to
pages 0, 1, and 2, and then hit on both 0 and 1. Next, page 3 is referenced,
causing a miss; the replacement decision is easy with FIFO: pick the page
1If you can, let us know! We can become rich together. Or, like the scientists who “discov-
ered” cold fusion, widely scorned and mocked [FP89].
OPERATING
SYSTEMS
[VERSION 0.92] WWW.OSTEP.ORG
BEYOND PHYSICAL MEMORY: POLICIES 5
Resulting
Access Hit/Miss? Evict Cache State
0 Miss First-in→ 0
1 Miss First-in→ 0, 1
2 Miss First-in→ 0, 1, 2
0 Hit First-in→ 0, 1, 2
1 Hit First-in→ 0, 1, 2
3 Miss 0 First-in→ 1, 2, 3
0 Miss 1 First-in→ 2, 3, 0
3 Hit First-in→ 2, 3, 0
1 Miss 2 First-in→ 3, 0, 1
2 Miss 3 First-in→ 0, 1, 2
1 Hit First-in→ 0, 1, 2
Figure 22.2: Tracing The FIFO Policy
that was the “first one” in (the cache state in the figure is kept in FIFO
order, with the first-in page on the left), which is page 0. Unfortunately,
our next access is to page 0, causing another miss and replacement (of
page 1). We then hit on page 3, but miss on 1 and 2, and finally hit on 3.
Comparing FIFO to optimal, FIFO does notably worse: a 36.4% hit
rate (or 57.1% excluding compulsory misses). FIFO simply can’t deter-
mine the importance of blocks: even though page 0 had been accessed
a number of times, FIFO still kicks it out, simply because it was the first
one brought into memory.
ASIDE: BELADY’S ANOMALY
Belady (of the optimal policy) and colleagues found an interesting refer-
ence stream that behaved a little unexpectedly [BNS69]. The memory-
reference stream: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. The replacement policy
they were studying was FIFO. The interesting part: how the cache hit
rate changed when moving from a cache size of 3 to 4 pages.
In general, you would expect the cache hit rate to increase (get better)
when the cache gets larger. But in this case, with FIFO, it gets worse! Cal-
culatethehitsandmissesyourselfandsee. Thisoddbehaviorisgenerally
referred to as Belady’s Anomaly (to the chagrin of his co-authors).
Some other policies, such as LRU, don’t suffer from this problem. Can
you guess why? As it turns out, LRU has what is known as a stack prop-
erty [M+70]. For algorithms with this property, a cache of size N + 1
naturally includes the contents of a cache of size N. Thus, when increas-
ing the cache size, hit rate will either stay the same or improve. FIFO and
Random (among others) clearly do not obey the stack property, and thus
are susceptible to anomalous behavior.
c© 2014, ARPACI-DUSSEAU
THREE
EASY
PIECES
6 BEYOND PHYSICAL MEMORY: POLICIES
Resulting
Access Hit/Miss? Evict Cache State
0 Miss 0
1 Miss 0, 1
2 Miss 0, 1, 2
0 Hit 0, 1, 2
1 Hit 0, 1, 2
3 Miss 0 1, 2, 3
0 Miss 1 2, 3, 0
3 Hit 2, 3, 0
1 Miss 3 2, 0, 1
2 Hit 2, 0, 1
1 Hit 2, 0, 1
Figure 22.3: Tracing The Random Policy
22.4 Another Simple Policy: Random
Another similar replacement policy is Random, which simply picks a
random page to replace under memory pressure. Random has properties
similar to FIFO; it is simple to implement, but it doesn’t really try to be
toointelligentinpickingwhichblockstoevict. Let’slookathowRandom
does on our famous example reference stream (see Figure 22.3).
Of course, how Random does depends entirely upon how lucky (or
unlucky)Randomgetsinitschoices. Intheexampleabove,Randomdoes
a little better than FIFO, and a little worse than optimal. In fact, we can
run the Random experiment thousands of times and determine how it
does in general. Figure 22.4 shows how many hits Random achieves over
10,000 trials, each with a different random seed. As you can see, some-
times(justover40%ofthetime),Randomisasgoodasoptimal,achieving
6 hits on the example trace; sometimes it does much worse, achieving 2
hits or fewer. How Random does depends on the luck of the draw.
0 1 2 3 4 5 6 7
0
10
20
30
40
50
Number of Hits
Frequency
Figure 22.4: Random Performance Over 10,000 Trials
OPERATING
SYSTEMS
[VERSION 0.92] WWW.OSTEP.ORG
BEYOND PHYSICAL MEMORY: POLICIES 7
Resulting
Access Hit/Miss? Evict Cache State
0 Miss LRU→ 0
1 Miss LRU→ 0, 1
2 Miss LRU→ 0, 1, 2
0 Hit LRU→ 1, 2, 0
1 Hit LRU→ 2, 0, 1
3 Miss 2 LRU→ 0, 1, 3
0 Hit LRU→ 1, 3, 0
3 Hit LRU→ 1, 0, 3
1 Hit LRU→ 0, 3, 1
2 Miss 0 LRU→ 3, 1, 2
1 Hit LRU→ 3, 2, 1
Figure 22.5: Tracing The LRU Policy
22.5 Using History: LRU
Unfortunately, any policy as simple as FIFO or Random is likely to
have a common problem: it might kick out an important page, one that
is about to be referenced again. FIFO kicks out the page that was first
brought in; if this happens to be a page with important code or data
structures upon it, it gets thrown out anyhow, even though it will soon be
paged back in. Thus, FIFO, Random, and similar policies are not likely to
approach optimal; something smarter is needed.
As we did with scheduling policy, to improve our guess at the future,
we once again lean on the past and use history as our guide. For example,
if a program has accessed a page in the near past, it is likely to access it
again in the near future.
One type of historical information a page-replacement policy could
use is frequency; if a page has been accessed many times, perhaps it
should not be replaced as it clearly has some value. A more commonly-
used property of a page is its recency of access; the more recently a page
has been accessed, perhaps the more likely it will be accessed again.
This family of policies is based on what people refer to as the prin-
ciple of locality [D70], which basically is just an observation about pro-
grams and their behavior. What this principle says, quite simply, is that
programs tend to access certain code sequences (e.g., in a loop) and data
structures(e.g.,anarrayaccessedbytheloop)quitefrequently;weshould
thus try to use history to figure out which pages are important, and keep
those pages in memory when it comes to eviction time.
And thus, a family of simple historically-based algorithms are born.
The Least-Frequently-Used (LFU) policy replaces the least-frequently-
usedpagewhenanevictionmusttakeplace. Similarly,theLeast-Recently-
Used (LRU) policy replaces the least-recently-used page. These algo-
rithmsareeasytoremember: onceyouknowthename,youknowexactly
what it does, which is an excellent property for a name.
To better understand LRU, let’s examine how LRU does on our exam-