Swap Token - Advanced Operating Systems and Kernel Applications - page 93

time interval form stair climbing curves as
their executions proceed. Program vortex
belongs to this type.

3), three types together (group 4), multiple type
1's (group 5), multiple type 2's (group 6), and
multiple type 3's (group 7). To provide insights
into the LRU page replacement behaviors during
program interactions, five representative program
interaction groups are described in this chapter.
The performance results of many other program
interactions are consistent with the reported ones.
In order to clearly and concisely present effects of
the false LRU pages on the program executions,
two programs in each group are selected.
The five selected program interaction groups
includes gzip with vortex (belonging to group 1),
bit-r with gcc (belonging to group 2), vortex with
gcc (belonging to group 3), two vortex programs,
each with a different input (belonging to group 6),
and two LU programs (belonging to group 7).
In the experiments, the available user memory
space was adjusted by the monitor program accord-
ingly so that each program has considerable per-
formance degradation due to 20% to 50% memory
shortage. The shortage ratios are calculated based
on the peak memory demands during programs'
executions. In practice, the real memory shortage
ratios are smaller due to their dynamically chang-
ing memory demands, as shown in Figures 1 and
2. As the program execution reaches the shortage
range, these memory-constrained programs start
thrashing, but are not completely page-fault I/O
bound. It is the range where improvements on
page replacement algorithms can help the most.
The swap token mechanism aims at eliminating
thrashing in this situation and intends to leave
the true page-fault I/O bound situation to load
control.
Figure 3 presents the memory behaviors mea-
sured by MAD and RSS of programs gzip and
vortex . In the figures, both RSS curves fluctuate
during the concurrent execution, which demon-
strates the impact of the gap between memory
demands and the limited memory allocations for
each process. The gap persists for a long period of
time, even though the memory is enough to satisfy
the demand for one process at a time.

• Non-regularly changing memory allot-

ments : This type of programs has non-
regular memory demands in their life times
of executions. Their demands on memory
sizes are changed dynamically with high
variations. When the available space is suf-
ficient, there are multiple ups and downs
in the RSS curves in their executions.
Programs gcc and LU belong to this type.

memory performance due to
interactionS of different
typeS of programS

performance metrics

We use slowdown to measure the degradation
of a program performance due to its concurrent
execution, which is defined as the ratio between
the execution time of the program in a shared
environment and its execution time in a dedicated
environment without major page faults. Major
sources of the slowdown are the penalty of page
faults, shared CPU cycles, processor context
switch, and monitoring activity overheads.
Among them, we found that context switch and
monitoring activity overheads are trivial in our
measurements.

memory performance of
program interactions

Recall that we have classified three types of
memory usage patterns in programs, namely,
type 1: quickly acquiring memory allotments;
type 2: gradually acquiring memory allotments;
and type 3: non-regularly changing memory
allotments. There are seven typical groups of
execution interactions between these three types
of programs: type 1 and type 2 (group 1), type
1 and type 3 (group 2), type 2 and type 3 (group