World Library  
Flag as Inappropriate
Email this Article

Thrashing (computer science)

Article Id: WHEBN0000665891
Reproduction Date:

Title: Thrashing (computer science)  
Author: World Heritage Encyclopedia
Language: English
Subject: Working set, Virtual memory, Memory-mapped file, Silly window syndrome, Server hog
Collection: Virtual Memory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Thrashing (computer science)

In computer science, thrashing occurs when a computer's virtual memory subsystem is in a constant state of paging, rapidly exchanging data in memory for data on disk, to the exclusion of most application-level processing.[1] This causes the performance of the computer to degrade or collapse. The situation may continue indefinitely until the underlying cause is addressed.

Contents

  • Overview 1
  • Causes 2
  • Solutions 3
  • Other uses 4
  • See also 5
  • References 6

Overview

If a process does not have enough pages, thrashing is a high paging activity, and the page fault rate is high. This leads to low CPU utilization. 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. Thrashing is a state in which the CPU performs 'productive' work less and 'swapping' more. The CPU is busy in swapping pages, so much that it can not respond to users' programs as much as required. Thrashing occurs when there are too many pages in memory, and each page refers to another page. The real memory shortens in capacity to have all the pages in it, 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 in 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 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 the reduced amount of paging necessary.

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 points to a move instruction (which 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 fewer than eight pages of actual memory, 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.

Solutions

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

  • Increase the amount of RAM in the computer (generally the best long-term solution).
  • Decrease the number of programs being run on the computer.
  • Replace programs that are memory-heavy with equivalents that use less memory.
  • Assign working priorities to programs, i.e. low,normal,high.
  • Improve spatial locality by replacing loops like:
 // recall that in C, arrays use Row-major order
 int m[256][256]; 
 for (k=0; k<256; k++) { 
   for (i=0; i<256; i++) { 
     m[i][k] = something(); 
   } 
 } 
with
  int m[256][256]; 
  for (i=0; i<256; i++) { 
    for (k=0; k<256; k++) {
      // consecutive values of k reside in adjacent memory locations 
      m[i][k] = something(); 
    } 
  }

Other uses

The term is also used for misses between other levels of the memory hierarchy, not just paging (memory to disk): 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. Quite similar is TLB thrashing, where the translation lookaside buffer (TLB) is overrun by more requests than it can handle efficiently.

See also

References

  1. ^ Denning, Peter J. (1968). "Thrashing: Its causes and prevention". Proceedings AFIPS, Fall Joint Computer Conference 33: 915–922. Retrieved 2012-02-15. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.