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

that a local policy is not an effective solution for
virtual memory management.

detected. The 4.4 BSD operating system [McKu-
sick et al. 1996], AIX system in the IBM RS/6000
[IBM 1996], HP-UX 10.0 in HP 9000 [HP 1995]
are the examples to adopt this method. In addition,
HP-UX system provides a ``serialize()” command
to run the processes once at a time after thrashing
is detected.

the working Set model

Denning [Denning 1968-1] proposes the work-
ing set model to measure the current memory
demand of a running program in the system. A
working set of a program is a set of its recently
accessed pages. Specifically, at virtual time t ,
the program's working set W t , is the subset of all
pages of the program which has been accessed in
the previous θ virtual time units (the working set
window). The task's virtual time is a measure of
the duration the program has control of the pro-
cessor and is executing instructions. A working
set replacement algorithm is used to ensure no
pages in the working set of a running program will
be replaced [Denning 1970]. Since the I/O time
caused by page faults is excluded in the working
set model, the working set replacement algorithm
can theoretically eliminate the thrashing caused
by chaotic memory competition. However, the
implementation of this model is very expensive
because a working set monitoring is required for
each individual process based on its virtual time
[Morris 1972].
The affordable LRU approximations of work-
ing set algorithm, such as two-handed clock, FIFO
with second chance, have to replace virtual time
with real time in determining the working sets.
This approximation leaves a loophole for the false
LRU pages.

advantages of a lightweight
thrashing prevention mechanism

The most destructive aspect of thrashing is that,
although thrashing may have been triggered by
a brief, random peak in workloads (e.g. all of the
users of a system happen to press the Enter keys at
the same second), the system might keep thrashing
for an indefinitely long time. This could likely
happen in a networked system, where multiple
users coincidentally run memory-intensive pro-
grams simultaneously without coordination on the
usage of the memory. Because thrashing is often
a result of a sudden spike of memory demand in
the workload, a lightweight, dynamic protection
mechanism that brings only momentary change
to the system behaviors for eliminating thrashing
is more desirable than a brute-force action, such
as process suspension or even a process removal.
This is because suspension-based load control
strategy has several limitations. First, a suspension/
reactivation scheme is based on the detection of
thrashing. Before certain conditions are detected
and the suspension/reactivation actions are taken,
the system has been thrashing and its memory has
been under-utilized for a period of time. Second,
in a multiprogramming environment, a short mo-
ment of lack or availability of free memory, or
increase or decrease of page fault rates, may not
necessarily indicate that thrashing is immediately
coming or leaving. Thus, it is hard to determine the
timing of suspension/reactivation of processes in
the load control strategy, especially for programs
of very dynamically changing memory demands.
A wrong decision can significantly degrade the

load controls

A commonly used method to protect systems
from thrashing is load control, which adjusts the
memory demands from multiple processes by
changing the multiprogramming level (MPL), or
the number of active processes in the system. It
suspends/reactivates, even swaps out/in processes
to control memory demands after the thrashing is