The Findings
A system thrashing is often a result of a sudden spike in memory requests during page demanding from a small number of running programs, which is difficult for OS to handle this situation.

The Swap-Token Solution
Swap-token is a lightweight and dynamic thrashing protection mechanism for OS. The basic idea is to set a token in the system, which is randomly or targetly given to a process that has page faults when thrashing happens. The process that has the token is given a privilege to allocate more physical memory pages to build its working set, which is expected to quickly finish its execution and to release its physical memory space allocation to other processes. A time stamp is used to handover the token one by one.

The Usage of the Swap-Token in OS
The first version of swap-token implemented in Linux applies the random approach. The second version is called preempt swap-token, where a priority counter is set for each process to track the number of swap-out pages. The token is always given to the process with a high priority, which has a high number of swap-out pages. The length of the time stamp is not a constant but is determined by the priority: the higher the number of swap-out pages of a process, the longer the time stamp for it will be.

• ``Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems", Performance Evaluation, Vol. 60, Issue 1-4, 2005, pp. 5-29.
  • The token algorithm in this paper has been adopted in Linux Kernel version 2.6, called "swap token"
  • A formal presentation of "swap token" archieved in Linux Memory Management documentation.
  • The "swap token" source code in Linux kernels by Rik van Riel is archived in Cross-Referening Linux Library.
  • A "preemtive swap token" patch is available in Linux kernel 2.6.
  • The token algorithm (swap token) is presented in a section in the widely used Linux Kernel book Understanding the Linux Kernel (3rd edition) by D. P. Bovet and M. Casati.
  • A detailed description of the token algorithm (swap token) in Linux is presented in a section in Book Professional Linux Kernel Architecture by Wolfgan Mauerer.
  • The token algorithm (swap token) is referred as an example in the section of Linux and Academia in Book Professional Linux Kernel Architecture by Wolfgan Mauerer.
  • The concept of ``false LRU pages" causing system thrashing is quoted in the Linux Memory Management Wiki.