Conclusion

We have investigated the risk of system thrashing in page replacement implementations by examining the Linux kernel code of versions 2.0, 2.2, and 2.4, and running interacting memory-intensive programs in a Linux system. Our study indicates that this risk is hard to avoid in a non-adaptive replacement implementation due to the conflicting interests of requirements on CPU and memory utilizations. We have proposed and implemented a patch to enhance the existing replacement policy into an adaptive one in the Linux kernel to prevent the system from thrashing among interacting processes, and to improve the CPU utilization under heavy memory load. Conducting experiments and performance evaluation, we show that our method can effectively provide thrashing protection without negative effects to overall system performance for three reasons: (1) the privilege is granted only when a thrashing problem is detected; (2) although the protected process could lower the memory usage of the rest of the interacting processes for a short period of time, the system will soon become stable by the protection; and (3) Our patch is simple to implement with little overhead in the Linux kernels.

In our current experiment we always select the process which most possibly has the least memory shortage, because we intent to put least effort to fulfill our protection goal. However, this scheme may allow the same process to be protected more often than others. This may incur fairness concern. A simple solution is to let the protection privilege alternate among all the active processes. We would like include this in our future work.

Acknowledgments: We thank Phil Kearns for providing a kernel programming environment. We appreciate Bill Bynum for reading the paper and for his suggestions.