Welcome to the InfoSci Platform
Swap Token: Rethink the Application of the LRU Principle on Paging to Remove System Thrashing

Swap Token: Rethink the Application of the LRU Principle on Paging to Remove System Thrashing

Song Jiang
Copyright: © 2010 |Pages: 21
ISBN13: 9781605668505|ISBN10: 1605668508|ISBN13 Softcover: 9781616923839|EISBN13: 9781605668512
DOI: 10.4018/978-1-60566-850-5.ch005
Cite Chapter Cite Chapter

MLA

Jiang, Song. "Swap Token: Rethink the Application of the LRU Principle on Paging to Remove System Thrashing." Advanced Operating Systems and Kernel Applications: Techniques and Technologies, edited by Yair Wiseman and Song Jiang, IGI Global, 2010, pp. 86-106. https://doi.org/10.4018/978-1-60566-850-5.ch005

APA

Jiang, S. (2010). Swap Token: Rethink the Application of the LRU Principle on Paging to Remove System Thrashing. In Y. Wiseman & S. Jiang (Eds.), Advanced Operating Systems and Kernel Applications: Techniques and Technologies (pp. 86-106). IGI Global. https://doi.org/10.4018/978-1-60566-850-5.ch005

Chicago

Jiang, Song. "Swap Token: Rethink the Application of the LRU Principle on Paging to Remove System Thrashing." In Advanced Operating Systems and Kernel Applications: Techniques and Technologies, edited by Yair Wiseman and Song Jiang, 86-106. Hershey, PA: IGI Global, 2010. https://doi.org/10.4018/978-1-60566-850-5.ch005

Export Reference

Mendeley
Favorite

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.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.