Hardware Reference
In-Depth Information
The question of whether demand paging should be used or not is relevant only
when a program first starts up. Once it has been running for a while, the needed
pages will already have been collected in main memory. If, however, the computer
is timeshared and processes are swapped out after running 100 msec or there-
abouts, each program will be restarted many times during the course of its run.
Because the memory map is unique to each program, and is changed when pro-
grams are switched, for example, in a timesharing system, the question repeatedly
becomes a critical one.
The alternative approach is based on the observation that most programs do not
reference their address space uniformly but that references tend to cluster on a
small number of pages. This concept is called the
locality principle
. A memory
reference may fetch an instruction, it may fetch data, or it may store data. At any
instant in time,
t
, there exists a set consisting of all the pages used by the
k
most
recent memory references. Denning (1968) has called this the
working set
.
Because the working set normally varies slowly with time, it is possible to
make a reasonable guess as to which pages will be needed when the program is
restarted, on the basis of its working set when it was last stopped. These pages
could then be loaded in advance before starting the program up (assuming they fit).
Ideally, the set of pages that a program is actively and heavily using, called the
working set
, can be kept in memory to reduce page faults. However, programmers
rarely know which pages are in the working set, so the operating system must dis-
cover this set dynamically. When a program references a page that is not in main
memory, the needed page must be fetched from the disk. To make room for it,
however, some other page will generally have to be sent back to the disk. Thus an
algorithm that decides which page to remove is needed.
Choosing a page to remove at random is probably not a good idea. If the page
containing the faulting instruction should happen to be the one picked, another
page fault will occur as soon as an attempt is made to fetch the next instruction.
Most operating systems try to predict which of the pages in memory is the least
useful in the sense that its absence would have the smallest adverse effect on the
running program. One way of doing so is to make a prediction when the next ref-
erence to each page will occur and remove the page whose predicted next reference
lies furthest in the future. In other words, rather than evict a page that will be
needed shortly, try to select one that will not be needed for a long time.
One popular algorithm evicts the page least recently used because the a priori
probability of its not being in the current working set is high. It is called the
LRU
(
Least Recently Used
) algorithm. Although it usually performs well, there are
pathological situations, such as the one described below, where it fails miserably.
Imagine a program that is executing a large loop that extends over nine virtual
pages on a machine with room for only eight pages in physical memory. After the
