Check out the new USENIX Web site.

Home About USENIX Events Membership Publications Students
ALS 2001 Paper    [ALS 2001 Technical Program]

next up previous
Next: Introduction

Pp. 143-151 of the Proceedings

Adaptive Page Replacement to Protect Thrashing in Linux 1

Song Jiang and Xiaodong Zhang
Department of Computer Science
College of William and Mary
Williamsburg, VA 23187-8795


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.

next up previous
Next: Introduction
This paper was originally published in the Proceedings of the 5th Annual Linux Showcase & Conference, November 5–10, 2001, Oakland, CA, USA
Last changed: 22 Aug. 2003 ch
Technical Program
ALS 2001 Home