Adaptive Page Replacement to Protect Thrashing in Linux

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.