Editing Virtual memory (section)

===Thrashing===
When [[paging]] and [[Paging#Page stealing|page stealing]] are used, a problem called "[[thrashing (computer science)|thrashing]]"<ref name="Thrashing">{{cite web |title=Thrashing |url= https://public.support.unisys.com/aseries/docs/ClearPath-MCP-20.0/86000387-514/section-000023183.html |website=Unisys}}</ref> can occur, in which the computer spends an unsuitably large amount of time transferring pages to and from a backing store, hence slowing down useful work. A task's [[working set]] is the minimum set of pages that should be in memory in order for it to make useful progress. Thrashing occurs when there is insufficient memory available to store the working sets of all active programs. Adding real memory is the simplest response, but improving application design, scheduling, and memory usage can help. Another solution is to reduce the number of active tasks on the system. This reduces demand on real memory by swapping out the entire working set of one or more processes.

A system thrashing is often a result of a sudden spike in page demand from a small number of running programs. Swap-token<ref>{{Cite journal | author1=Song Jiang | author2=Xiaodong Zhang | title=Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems |journal=Performance Evaluation |issn=0166-5316 |volume=60 |issue=1–4 |year=2005 |pages = 5–29 |doi=10.1016/j.peva.2004.10.002}}</ref> is a lightweight and dynamic thrashing protection mechanism. The basic idea is to set a token in the system, which is randomly 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 the memory pages to other processes. A time stamp is used to handover the token one by one. The first version of swap-token was implemented in Linux 2.6.<ref name="swap-token-page">{{cite web|first=Xiaodong |last=Zhang<!--No authorship info on the page but it is under Zhang's personal site at OSU. Don't link [[Xiaodong Zhang]], that's someone else--> |publisher=Ohio State University |url=https://web.cse.ohio-state.edu/~zhang.574/swaptoken-PE-05.html|title=Swap Token effectively minimizes system thrasing effects and is adopted in OS kernels|url-status=dead|archive-url=https://web.archive.org/web/20231207203355/https://web.cse.ohio-state.edu/~zhang.574/swaptoken-PE-05.html|archive-date=2023-12-07}}</ref> The second version is called preempt swap-token and is also in Linux 2.6.<ref name="swap-token-page" /> In this updated swap-token implementation, 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.