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

experimental obSerVation of
program'S acceSS patternS

system performance because of high costs as-
sociated with these operations. Finally, when a
process is suspended, a large portion of its entire
working set can be replaced for other processes.
Re-establishing the working set after its reactiva-
tion, particularly for a large suspended program,
could involve significant overhead. For these
reasons, in the most of today's operating systems,
such as Solaris and Linux, only the approxima-
tion of global LRU replacement is implemented
without a built-in suspension/reactivation-based
load control mechanism.
It is noted that the ultimate solution to con-
stant and serious thrashing in a system due to
memory shortage is to increase physical memory
size, and a thrashing due to a significant memory
shortage can only be removed through swapping
out processes to reduce memory demands. The
swap token mechanism is intended to remove the
thrashing which can be considered as a temporary
and short-term pathological system condition
caused by limited memory shortage. Using the
swap token mechanism at the first place, it is
possible to eliminate system thrashing at its early
stage, minimizing the usage of load control. As a
proactive and lightweight mechanism, swap token
aims to achieve the same goal as load control
for thrashing protection, but without the limita-
tions of load control. Therefore, with the swap
token mechanism and load control guarding at
two different levels and two different stages, the
system performance will become more stable and
cost-effective.
In the remaining of the chapter, we will first
experimentally show the access behaviors of
some typical programs in Section 3. We then
show how system thrashing can be developed
when multiple of the programs run together in
Section 4. Section 5 describes the design of the
swap token mechanism, whose effectiveness is
experimentally evaluated in Section 6.

the benchmark programs

We have selected five memory-intensive appli-
cation programs, three of which are from SPEC
2000 ( gcc, gzip, and vortex ), and the other two are
programs for data reordering and matrix computa-
tion.All of these programs are both CPU-intensive
and memory-intensive, and are briefly described
as follows

• gcc : an optimized C programming lan-
guage compiler from SPEC 2000.
• gzip : a data compression utility from SPEC
2000.

• vorte: a data-oriented database program

from SPEC 2000.
bit-reversals ( • bit-r ): This program carries

out data reordering operations which are
required in many Fast Fourier Transform
(FFT) algorithms.
LU decomposition ( • LU ): This is a standard

matrix LU decomposition program for
solving linear systems.

experimental System Setup

The machine used in the experiments is a Pentium
II at 400 MHz with a physical memory space of
384 MBytes. The operating system is Redhat
Linux release 6.1 with the kernel 2.2.14. Program
memory space is allocated in units of 4KByte
pages. The disk is an IBM Hercules with capacity
of 8,450 MB.
When memory related activities in a program
execution occur, such as memory accesses and
page faults, the system kernel is heavily involved.
To gain insights into the memory system behav-
iors of application programs, program executions
are monitored at the kernel level by using some
lightweight instrumentation in the kernel. A user
monitor program is designed with two function-