Editing Thrashing (computer science) (section)

==Overview==
[[Virtual memory]] works by treating a portion of [[secondary storage]] such as a computer [[hard disk]] as an additional layer of the [[cache hierarchy]].  Virtual memory allows [[Process (computing)|processes]] to use more memory than is physically present in [[Random-access memory|main memory]]. Operating systems supporting virtual memory assign processes a [[virtual address space]] and each process refers to [[Address (computing)|addresses]] in its [[execution context]] by a so-called virtual address. To access [[Data (computing)|data]] such as [[Machine code|code]] or [[Variable (computer science)|variables]] at that address, the process must translate the address to a [[physical address]] in a process known as [[virtual address translation]]. In effect, physical main memory becomes a [[Cache (computing)|cache]] for virtual memory, which is in general stored on disk in [[Page (computer memory)|memory pages]].

Programs are allocated a certain number of pages as needed by the [[operating system]].  Active memory pages exist in both RAM and on disk. Inactive pages are [[Cache replacement policies|removed from the cache]] and [[Write-back|written to disk]] when the main memory becomes full.

If processes are utilizing all main memory and need additional memory pages, a cascade of severe [[cache miss]]es known as [[page fault]]s will occur, often leading to a noticeable [[Latency (engineering)|lag]] in the operating system [[responsiveness]]. This process together with the futile, repetitive page swapping that occurs is known as "thrashing". This frequently leads to high, runaway CPU utilization that can grind the system to a halt. In modern computers, thrashing may occur in the paging system (if there is not sufficient [[physical memory]] or the disk access time is overly long), or in the I/O communications subsystem (especially in [[Bus contention|conflicts over internal bus access]]), etc.

Depending on the configuration and algorithms involved, the [[throughput]] and [[Latency (engineering)|latency]] of a system may degrade by multiple [[Computer performance by orders of magnitude|orders of magnitude]]. Thrashing is when the CPU performs 'productive' work less and 'swapping' work more. The overall memory access time may increase since the higher level memory is only as fast as the next lower level in the memory hierarchy.<ref>{{Cite book|title=Computer architecture: a quantitative approach|last=L.|first=Hennessy, John|date=2012|publisher=Morgan Kaufmann|others=Patterson, David A., [[Asanović, Krste]].|isbn=9780123838728|edition= 5th|location=Waltham, MA|oclc=755102367}}</ref> The CPU is busy swapping pages so much that it cannot respond to users' programs and interrupts as much as required. Thrashing occurs when there are too many pages in memory, and each page refers to another page. Real memory reduces its capacity to contain all the pages, so it uses 'virtual memory'. When each page in execution demands that page that is not currently in real memory (RAM) it places some pages on virtual memory and adjusts the required page on RAM. If the CPU is too busy doing this task, thrashing occurs.

===Causes===
In [[virtual memory]] systems, thrashing may be caused by programs or workloads that present insufficient [[locality of reference]]: if the [[working set]] of a program or a workload cannot be effectively held within physical memory, then constant data swapping, ''i.e.,'' thrashing, may occur. The term was first used during the tape operating system days to describe the sound the tapes made when data was being rapidly written to and read.
A worst case might occur on [[VAX]] processors. A single <code>MOVL</code> crossing a page boundary could have a source operand using a displacement deferred addressing mode, where the longword containing the operand address crosses a page boundary, and a destination operand using a displacement deferred addressing mode, where the longword containing the operand address crosses a page boundary, and the source and destination could both cross page boundaries. This single instruction references ten pages; if not all are in RAM, each will cause a page fault. The total number of pages thus involved in this particular instruction is ten, and all ten pages must be simultaneously present in memory.  If any one of the ten pages cannot be [[Paging|swapped in]] (for example to make room for any of the other pages), the instruction will fault, and every attempt to restart it will fail until all ten pages can be swapped in.

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 conference |author= Song Jiang, and Xiaodong Zhang | title="Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems" |conference=Performance Evaluation| 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 release the memory pages to other processes. A timestamp is used to hand over the tokens one by one. The first version of swap-token is implemented in Linux[http://fxr.watson.org/fxr/source/mm/thrash.c?v=linux-2.6 .] The second version is called preempt swap-token[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=7602bdf2fd14a40dd9b104e516fdc05e1bd17952 .] 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.