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

from the swap file. This arrangement makes sure
that the token only goes to the process in need of
memory. The token is only taken by a process
when page faults occur due to memory shortage.
In other words, a process will not compete for the
token until the memory space is insufficient for
it. The system functions exactly as the original
Linux system when memory space is sufficient
for processes. In the implementation, a new status,
called swapping_status , is introduced for each
process to indicate whether the process is in the
stage of swapping in/out pages.
As we have explained, false LRU pages are
generated for a process in its page swapping
period. The process does not access its allocated
memory because it does not have a chance to do
so due to swapping.
Therefore, these pages should be prevented
from swapping out. With the swap token mecha-
nism, a process holding the token can prevent
its false LRU pages from being replaced. In the
process of searching for and marking LRU pages
(by turning off their reference bits) for page re-
placement, kernel function __get_free_pages()
skips the process that holds the token and is in the
swapping status. In this way the memory pages
of the process with the token are protected when
and only when it has unsolved page faults, and
false LRU pages are eliminated from it.
The LRU pages of a process identified during a
normal computing phase are the true LRU pages,
which are the replacement candidates targeted
by the swap token mechanism. To this end, the
privilege for the process holding the token is
removed as soon as the process resolves its page
faults by turning off its swapping status, which
allows __get_free_pages() to include the process
in its search for LRU pages for replacement. In
our implementation, there is an exception handler.
When the privileged process cannot find LRU
pages from other processes for replacement, the
system will have to select LRU pages for the
process from its own resident space.
The swap token mechanism is highly light-

weight. Its only additional operations are to set
the token/swapping status, and to decide whether
the process holding the token should be skipped or
not when the system is searching for LRU pages
for replacement. Thus, the implementation incurs
very little overhead.

fairness issue in memory usage

If a process has fully established its working
set, and it is able to regularly access it, there is a
good chance for the process to keep its allocated
memory space even with the competition from
other processes through their page faults, because
it would generate few false LRU pages when the
process establishes its working set and has a small
number of page faults. Therefore, this process
can be expected to efficiently finish its execu-
tion and then release its space to other processes,
which allows multiple processes to finish their
executions one by one with a high CPU utiliza-
tion even with a considerable memory shortage.
Most operating systems make efforts to keep
the system away from thrashing and stay in this
situation until load controls have to be applied.
As a lightweight, proactive thrashing protection
mechanism, swap token allows a process to keep
the token for the rest of its lifetime once it receives
it. When a program exits its execution, the token
will be returned for public use.
The fairness issue of memory usage among
processes in thrashing is usually addressed in the
load control policies, rather than explicitly consid-
ered in the global page replacement policies. For
example, the 4.4 BSD operating system initially
suspends a process after thrashing. If the thrash-
ing continues, additional processes are suspended
until enough memory space becomes available. In
order to address the issue of fairness, even if there
is not enough memory, the suspended processes
are allowed to reactivate its execution after about
20 seconds. If the thrashing condition returns,
other processes will be selected for suspension to
free memory space. As a mechanism to overcome