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

Chapter 5
Swap Token:
Rethink the Application of the
LRU Principle on Paging to
Remove System Thrashing
Song Jiang
Wayne State University, USA
abStract
Most computer systems use the global page replacement policy based on the LRU principle to reduce
page faults. The LRU principle for the global page replacement dictates that a Least Recently Used (LRU)
page, or the least active page in a general sense, should be selected for replacement in the entire user
memory space. However, in a multiprogramming environment under high memory load, an indiscriminate
use of the principle can lead to system thrashing, in which all processes spend most of their time waiting
for the disk service instead of making progress. In this chapter, we will rethink the application of the
LRU principle on global paging to identify one of root causes for thrashing, and describe a mechanism,
named as swap token, to solve the issue. The mechnism is simple in its design and implementation but
highly effective in alleviating or removing thrashing. A key feature of the swap token mechanism is that
it can distinguish the conditions for an LRU page, or a page that has not been used for relatively long
period of time, to be generated and accordingly categorize LRU pages into two types: true and false
LRU pages. The mechanism identifies false LRU pages to avoid use of the LRU principle on these pages,
in order to remove thrashing. A prototype implementation of the swap token mechanism in the Linux
kernel as well as some experiment measurements are presented. The experiment results show that the
mechanism can consistently reduce the program execution slowdown in a multiprogramming environment
including SPEC2000 programs and other memory-intensive applications by up to 67%. The slowdown
reductions mainly come from reductions of up to 95% of total page faults during program interactions.
This chapter also shows that the mechanism introduces little overhead to program executions, and its
implementations on Linux (and Unix) systems are straightforward.