Thrashing (computer science)

In computer science, thrashing describes a state where a computer system spends more time moving data than doing actual work. This happens within the memory paging system when a computer's real memory, known as RAM, is overcommitted. RAM is the physical storage used for active data. When RAM is full, the operating system uses virtual memory to allow processes to use more memory than is physically present. It does this by treating a portion of secondary storage, like a hard disk, as an extra layer of the memory hierarchy. Thrashing causes the performance of the computer to degrade significantly or even collapse entirely.

To understand how this happens, we must look at how memory paging works. The operating system assigns each process a virtual address space. To access data, the system must perform virtual address translation. This translates a virtual address into a physical address in the RAM. Physical main memory essentially acts as a cache for the virtual memory stored on the disk. Active memory pages exist in both RAM and on the disk. When the main memory becomes full and a process needs a new page, a page fault occurs. A page fault is a cascade of cache misses where the system must retrieve data from the disk. If the system must constantly move pages to the disk to make room for new ones, it enters a state of thrashing.

Every program has a specific requirement called a working set. This is the collection of code and data pages that a program accesses most frequently at any given time. When the total size of all active working sets is smaller than the total number of real storage page frames, the system works efficiently. In this state, the amount of computing spent resolving page faults is very small. However, if the working sets grow beyond the capacity of the RAM, the number of page faults increases dramatically. This leads to a cycle where satisfying a page fault requires freeing a page that will be needed again almost immediately. The CPU becomes so busy swapping these pages that it cannot respond to user programs or interrupts.

Historically, the term "thrashing" has different origins. It was first used during the era of tape operating systems. It described the actual sound that magnetic tapes made when they were being rapidly read from and written to. In older hardware, such as VAX processors, thrashing could reach extreme levels. For example, a single MOVL instruction could potentially reference ten different pages if it used certain addressing modes. If even one of those ten pages was not in the RAM, the instruction would fault. The system would then attempt to restart the instruction, but it would fail again unless all ten pages could be held in memory simultaneously.

Modern systems use specific mechanisms to protect against this performance collapse. One such method is called a swap-token. This is a lightweight and dynamic protection mechanism. When thrashing is detected, a token is randomly given to a process experiencing page faults. This token grants that process the privilege to allocate more physical memory pages to build its working set. The goal is for that process to finish its execution quickly and release its memory to others. The first version of this was implemented in Linux. A newer version is called the preempt swap-token, which uses a priority counter to give tokens to processes with a high number of swap-out pages.

Thrashing is not limited to main memory paging; it can occur in other areas of a computer's architecture. One type is cache thrashing, which happens when memory access patterns cause multiple locations to compete for the same cache lines. This often involves a lack of locality of reference. Another form is TLB thrashing. The Translation Lookaside Buffer, or TLB, acts as a cache for the memory management unit. If the working set of pages is too large for the TLB, the system will struggle even if the data fits in the main cache. There is also heap thrashing, which occurs when frequent garbage collection happens because the system cannot allocate enough contiguous free memory.

Ultimately, thrashing represents a breakdown in the efficiency of the memory hierarchy. When the CPU performs "productive" work less and "swapping" work more, the system's throughput and latency can degrade by multiple orders of magnitude. This can happen in the paging system or even in the I/O communications subsystem due to internal bus access conflicts. While it is a complex technical failure, it is often a direct result of a sudden spike in page demand. For a user, the most effective way to resolve thrashing is to close running applications to free up the vital RAM resources the system requires.