thrash

In computer science, thrash (verb) is the term used to describe a degenerate situation on a computer where increasing resources are used to do a decreasing amount of work. In this situation the system is said to be thrashing. Usually it refers to two or more processes accessing a shared resource repeatedly such that serious system performance degradation occurs because the system is spending a disproportionate amount of time just accessing the shared resource. Resource access time may generally be considered as wasted, since it does not contribute to the advancement of any process.

Silly window syndrome is a type of communications system thrashing.

Overview

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 communications system (especially in conflicts over internal bus access), etc. Depending on the configuration and algorithms involved, the throughput and latency of a system may degrade by multiple orders of magnitude.

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 from them. Many older low-end computers have insufficient RAM (memory) for modern usage patterns and increasing the amount of memory can often cause the computer to run noticeably faster. This speed increase is due to removing the need for paging.

An example of this sort of situation occurred on the IBM System/370 series mainframe computer, in which a particular instruction could consist of an execute instruction, which crosses a page boundary, that the instruction points to a move instruction, that itself also crosses a page boundary, targeting a move of data from a source that crosses a page boundary, to a target of data that also crosses a page boundary. The total number of pages thus being used by this particular instruction is eight, and all eight pages must be present in memory at the same time. If the operating system allocates less than eight pages of actual memory in this example, when it attempts to swap out some part of the instruction or data to bring in the remainder, the instruction will again page fault, and it will thrash on every attempt to restart the failing instruction.

To resolve thrashing due to excessive paging, a user can do any of the following.

1. Increase the amount of RAM in the computer (generally the best long-term solution).
2. Decrease the number of programs being run on the computer.
3. Replace programs that are memory-heavy with equivalents that use less memory.

The term is also used when a small set of faster storage space, intended to be used to speed up access to a larger set of slower storage space, is accessed in a way that cancels out any benefits from the faster storage. An example of this is 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.

Causes and Symptoms of Thrashing

Thrashing results in several performance problems. Consider the following scenario, which is based on actual behavior of early paging systems.

The operating system monitors CPU utilization. If the CPU utilization is too low, the OS increases the degree of multiprogramming by introducing new processes to the system. A global page-replacement algorithm is used; it replaces pages without regard for the process to which they belong. Now suppose that a process enters a new phase in its execution and needs more frames. It starts faltering and taking frames away from other processes. These processes need those pages, however, and so they also falter, taking frames away from other processes. These faulting processes must use the paging device to swap pages in and out. As they queue up for the paging device (which, for example, might be a drive-space on the local disk or on a portable USB hard-disk drive [HDD]), the ready queue empties. As the processes wait for the paging device, CPU utilization decreases.

The CPU scheduler sees the decreasing CPU utilization and increases the degree of multiprogramming as a result. The new process tries to get started by taking frames from running processes, causing more page faults and a longer queue for the paging device. Subsequently, CPU utilization begins to drop significantly, and the CPU scheduler in turn tries to increase the degree of multiprogramming even more as a sort of counter-measure. The obvious flow-on is a compound effect. Thrashing has at this point said to have occurred, and system throughput subsequently plummets. The page fault rate increases tremendously thereafter. Lastly, the effective memory-access time significantly increases. It is typically at this point, no further tasks can be performed on the system and the system is often described as being 'locked up' or 'frozen'.

Limiting the effects of Thrashing

The effects of thrashing can be limited or minimized by using a local replacement algorithm. With local replacement, if one process starts thrashing, the process in question cannot use frames from another process and therefore cause the latter process to thrash as well. However, this does not entirely resolve the problem. If simultaneous processes are thrashing, they will remain in the queue for the paging device. The average service time for a page fault will increase accordingly because of the longer average queue for the paging device. Thus, the effective access time will increase even for a process that is not thrashing.

To prevent thrashing, a process must be provided with as many frames as it needs. The number of frames it needs can be determined with several techniques, including the working-set strategy. This approach defines the locality model of process execution.

References

• M. Morris Mano and Charles R. Kime, "Logic and Computer Design Fundamentals", pp. 622.
• P. J. Denning. 1968. Thrashing: Its Causes and Prevention. Proceedings AFIPS,1968 Fall Joint Computer Conference, vol. 33, pp. 915-922.
• Abraham Silberschatz, Peter Baer Galvin and Greg Gagne. "Operating System Principles", pp. 331, 348-353.