Process Characteristics
CIS343
Locality
Our ability to design
operating systems to be maximally efficient depends on many factors. Among the most important is our
understanding of the concept of locality. To make the best use of multiple levels of memory, such as cache
to make a program run faster, or, such as paging to make fuller use of RAM, we
would like to have some way of predicting which chunk of memory will be
required by the program in the near future.
Fortunately for us, many programs exhibit a high degree of locality in
their memory reference patterns.
Mastery of this concept gives us much advantage in the design of both
the hardware of a computer and the structures and algorithms of an operating
system.
The concept of locality is
usually divided into two categories, spatial locality and temporal
locality. We look at each in turn.
Spatial Locality:
If a program accesses a
particular memory location, often it will soon access a nearby memory
location. This is known as spatial
locality. Sequential execution of
code, systematic movement through an array, the tendency to access components
of a structure at about the same time, and the tendency to cluster access to
variables which are declared together are among the phenomena which tend to
produce spatial locality in a program.
(Strictly speaking, locality is a property of a process, not a
program. But it is the design of the
program which determines whether the process will exhibit a high or low degree
of locality).
As discussed in class, we can
make the concepts of spatial locality more precise with the following formula:
a :: deg-SpacLoc(k,s) = #(spac-loc-mem-refs) /
#(mem-refs),
where a memory reference, m, to location l which occurred at time t, qualifies as a
spac-loc-mem-ref if there is a memory reference, m’, to location l’ at time t’, such that either l’<= l+k or
l’>= l-k and t’<=
t+s, where k and s are small, pre-set units of space and time.
Temporal Locality:
If a program accesses a
particular memory location, often it will soon access the very same memory
location. This is known as temporal
locality. Iteration (which produces
repeated execution of a given segment of code), searching, sorting and other
repetitive operations on an array or a linked list, continual growth and
shrinking of a stack, and recursion are among the phenomena which tend to
produce temporal locality in a program.
As with spatial locality, we
can make the concept of temporal locality more precise with the following
formula:
b :: deg-TempLoc(s) = #(temp-loc-mem-refs) /
#(mem-refs),
where a memory reference, m, to location l which occurred at time t, qualifies as a
temp-loc-mem-ref if there is a memory reference, m’, to the same location l at
time t’, such that t’<= t+s,
where s is a small, pre-set unit of time.
Points to Ponder:
1. Let m be a
spac-loc-mem-ref. Is it always also
a temp-loc-mem-ref? Is it ever also
a temp-loc-mem-ref?
2. Let m be a
temp-loc-mem-ref. Is it always also
a spac-loc-mem-ref? Is it ever also
a spac-loc-mem-ref?
3. With respect to usefulness for predicting paging
activity, is there a difference between temporal and spatial locality? I.e., is one more useful than the
other? If so, which one?
Working Set
A generalization of the
concept of locality, applied specifically to paging, is the concept of working
set, introduced and popularized by Denning.
“The working set with parameter D for a
process at virtual time t, W(t,D), is the set of pages of that
process that have been referenced in the last D virtual time
units.” {Stallings, p. 366} D is usually referred to as the window size.
If the working set of a
process is in RAM, then no page faults occur.
Therefore, to the extent that we can identify the working set of a
process at various points in its execution, to that extent we can reduce page
faulting, achieving a greater degree of resource utilization. A more thorough discussion of this concept
is found on pages 366-368 of Stallings.
Boundedness
For processor scheduling,
which is the responsibility of the operating system, an important
characteristic of a process is what we will refer to as its boundedness. A process which makes frequent use of I/O is
said to be I/O-bound. A process which
spends the majority of its time computing, doing very little I/O in the process
is said to be compute-bound.
As with so many concepts in
operating systems theory, there is no precise definition of these terms. For the purposes of our study, we will adopt
the following as “working definitions” of I/O-bound and compute-bound phases
of operation of a process. The unit
of time we will use in these definitions will be instruction executions.
g :: A process is in an I/O-bound phase if it executes
an I/O operation
within 10 units of time, or less.
d :: A process is in a compute-bound phase if it
executes 100 or more
instructions without I/O operation.
e :: A process is in a neutral phase with respect to
boundedness if it is
in neither an I/O-bound nor a compute-bound phase.
Register/RAM Usage
If a process is able to do
all of its calculation using only the registers of the CPU, then it will not be
slowed down by the need to access RAM or by delays due to the disk I/O and the page
faults associated with paging.
Therefore, it is helpful for us to know to what extent a process has
been able to achieve this goal. For the
purposes of our study, we will adopt the following as “working definitions” of
register-intensive and RAM-intensive phases of operation of a process.
h :: A process is in a RAM-intensive phase if it reads/writes RAM
within 10 units of time, or less.
l :: A process is in a register-intensive phase if it
executes 100 or
more instructions without RAM access (other than to
fetch the
next instruction).
m :: A process is in a neutral phase with respect to
register/RAM
usage if it is in neither of these phases.