Thrashing (computer science)
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
In
After initialization, most programs operate on a small number of code and data pages compared to the total memory the program requires. The pages most frequently accessed at any point are called the working set, which may change over time.
When the working set is not significantly greater than the system's total number of real storage page frames, virtual memory systems work most efficiently, and an insignificant amount of computing is spent resolving page faults. As the total of the working sets grows, resolving page faults remains manageable until the growth reaches a critical point at which the number of faults increases dramatically and the time spent resolving them overwhelms the time spent on the computing the program was written to do. This condition is referred to as thrashing. Thrashing may occur on a program that randomly accesses huge data structures, as its large working set causes continual page faults that drastically slow down the system. Satisfying page faults may require freeing pages that will soon have to be re-read from disk.
The term is also used for various similar phenomena, particularly movement between other levels of the memory hierarchy, wherein a process progresses slowly because significant time is being spent acquiring resources.
"Thrashing" is also used in contexts other than virtual memory systems—for example, to describe cache issues in computing or silly window syndrome in networking.
Overview
Programs are allocated a certain number of pages as needed by the
If processes are utilizing all main memory and need additional memory pages, a cascade of severe
Depending on the configuration and algorithms involved, the
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 scenario of this sort on the
A system thrashing is often a result of a sudden spike in page demand from a small number of running programs. Swap-token[3] 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. The second version is called preempt swap-token. 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.
Other uses
Thrashing is best known in the context of memory and storage, but analogous phenomena occur for other resources, including:
- Cache thrashing
Where main memory is accessed in a pattern that leads to multiple main memory locations competing for the same cache lines, resulting in excessive cache misses. This is most problematic for caches that have low associativity.
- TLB thrashing
Where the
- Heap thrashing
Frequent garbage collection, due to failure to allocate memory for an object, due to insufficient free memory or insufficient contiguous free memory due to memory fragmentation is referred to as heap thrashing.[4]
- Process thrashing
A similar phenomenon occurs for processes: when the
See also
- Page replacement algorithm – Algorithm for virtual memory implementation
- Congestion collapse– Reduced quality of service due to high network traffic
- Resource contention – In computing, a conflict over access to a shared resource
- Out of memory – State of computer operation where no additional memory can be allocated
- Software aging – Tendency of software to fail due to external changes or prolonged operation
References
- ^ Denning, Peter J. (1968). "Thrashing: Its causes and prevention" (PDF). Proceedings AFIPS, Fall Joint Computer Conference. 33: 915–922. Retrieved 2012-02-15.
- )
- .
- ^ Performance Optimization and Tuning Techniques for IBM Processors, including IBM POWER8, "heap+thrashing" p. 170
- ^ Ousterhout, J. K. (1982). "Scheduling Techniques for Concurrent Systems" (PDF). Proceedings of Third International Conference on Distributed Computing Systems. pp. 22–30.