Adaptive Page Replacement to Protect Thrashing in Linux

Song Jiang and Xiaodong Zhang

Proceedings of the 5th USENIX Annual Linux Showcase and Conference,
(ALS'01), Oakland, California, November 5-10, 2001.

Abstract

Analyzing the variations of page replacement implementations in recent 
Linux kernel versions of 2.0, 2.2, and 2.4, we compare their  
abilities to deal with system thrashing. We show that although the 
page implementation in Kernel 2.2 is relatively effective to protect    
thrashing among the three versions, none of them have adaptive ability, 
and thus the protection is limited. By running several groups of 
memory-intensive application programs on Kernel 2.2, we observe serious 
thrashing when memory shortage attains a certain level.

We propose and implement a thrashing protection patch in Linux kernels, 
which makes replacement policy responsively resolve excessive memory 
paging by temporarily helping one of the active processes quickly build
up its working set. Consequently, thrashing could be eliminated at the level 
of page replacement, so that load controls at a higher level, such as 
process suspensions/swapping can be avoided or delayed until 
it is truly necessary. Our experiments show that our patch can 
significantly reduce page faults and the execution time of each individual 
thrashing process for several groups of interacting programs. We also show that 
our method introduces little additional overhead to program executions, 
and its implementation in Linux (or Unix) system is straightforward. 

Back to the HPCS Main Page at the Ohio State University.