This article may require cleanup to meet Wikipedia's quality standards. Please discuss this issue on the talk page or replace this tag with a more specific message. This article has been tagged since April 2006.

A race condition or race hazard is a flaw in a system or process whereby the output of the process is unexpectedly and critically dependent on the sequence or timing of other events. The term originates with the idea of two signals racing each other to influence the output first. Image File history File links Broom_icon. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ... System (from Latin systēma, in turn from Greek systēma) is a set of entities, real or abstract, comprising a whole where each component interacts with or is related to at least one other component and they all serve a common objective. ... Timing refers to how events are spaced in time. ... In information theory, a signal is the sequence of states of a communications channel that encodes a message. ... // Information processing In information processing, output is the process of transmitting information by an object (verb usage). ...

Race conditions can occur in poorly-designed electronics systems, especially logic circuits, and in computer software, especially multithreaded or distributed programs. Electronics is the study of the flow of charge through various materials and devices such as, semiconductors, resistors, inductors, capacitors, nano-structures, and vacuum tubes. ... A logic gate performs a logical operation on one or more logic inputs and produces a single logic output. ... The NASA Columbia Supercomputer. ... Computer software (or simply software) refers to one or more computer programs and data held in the storage of a computer for some purpose. ... Many programming languages, operating systems, and other software development environments support what are called threads of execution. ... This article or section should include material from Distributed programming This article or section should include material from Distributed system Distributed computing is the process of aggregating the power of several computing entities to collaboratively run a single computational task in a transparent and coherent way, so that they appear...

Electronics

Race condition in a logic circuit. Here, ∆t₁ and ∆t₂ represent the propagation delays of the logic elements. When the input value (A) changes, the circuit outputs a short spike of duration ∆t₁.

A typical example of a race condition may occur in a system of logic gates, where inputs vary. If a particular output depends on the state of the inputs, it may only be defined for steady-state signals. As the inputs change state, a finite delay will occur before the output changes, due to the physical nature of the electronic system. For a brief period, the output may change to an unwanted state before settling back to the designed state. Certain systems can tolerate such glitches, but if for example this output signal functions as a clock for further systems that contain memory, the system can rapidly depart from its designed behaviour (in effect, the temporary glitch becomes permanent). Image File history File links This is a lossless scalable vector image. ... In computer science, the propogation delay is the amount of time starting from when the input to a logic gate becomes stable and valid to the time that the output of that logic gate is stable and valid. ... A logic gate performs a logical operation on one or more logic inputs and produces a single logic output. ... Glitch City, a Pokémon programming error that creates a jumble of tiles. ...

For example, consider a two input AND gate fed with a logic signal A on one input and its negation, NOT A, on another input. In theory, the output (A AND NOT A) should never be high. However, if changes in the value of A take longer to propagate to the second input than when A changes from false to true, a brief period will ensue during which both inputs are true, and so the gate's output will also be true.

Proper design techniques (e.g. Karnaugh maps) encourage designers to recognise and eliminate race conditions before they cause problems. See critical race and non-critical race for more information on specific types of race conditions. An example Karnaugh map The Karnaugh map, also known as a Veitch diagram (K-map or KV-map for short), is a tool to facilitate management of Boolean algebraic expressions. ... Overview A critical race is a specific type of race hazard found in digital logic circuits. ... Overview A non-critical race is a specific type of race hazard found in digital logic circuits. ...

As well as these problems, some logic elements can enter metastable states, which create further problems for circuit designers. Metastability in electronics is the ability of a non-equilibrium electronic state to persist for a long period of time (see asynchronous circuit). ...

Types

Static race conditions 

These are caused when a signal and its complement are combined together.

Dynamic race conditions 

These result in multiple transitions when only one is intended. They are due to interaction between gates (Dynamic race conditions can be eliminated by using not more than two levels of gating).

Essential race conditions 

These are caused when an input has two transitions in less than the total feedback propagation time. Sometimes they are cured using inductive delay-line elements to effectively increase the time duration of an input signal.

Computing

Race conditions arise in software when separate processes or threads of execution depend on some shared state. In computing, a process is a running instance of a program, including all variables and other state. ... For the form of code consisting entirely of subroutine calls, see Threaded code. ...

Here is a simple example:

Let us assume that two threads T1 and T2 each want to increment the value of a global integer by one. Ideally, the following sequence of operations would take place:

1. Integer i = 0;
2. T1 reads the value of i from memory into a register : 0
3. T1 increments the value of i in the register: (register contents) + 1 = 1
4. T1 stores the value of the register in memory : 1
5. T2 reads the value of i from memory into a register : 1
6. T2 increments the value of i in the register: (register contents) + 1 = 2
7. T2 stores the value of the register in memory : 2
8. Integer i = 2

In the case shown above, the final value of i is 2, as expected. However, if the two threads run simultaneously without locking or synchronization, the outcome of the operation could be wrong. The alternative sequence of operations below demonstrates this scenario:

1. Integer i = 0;
2. T1 reads the value of i from memory into a register : 0
3. T2 reads the value of i from memory into a register : 0
4. T1 increments the value of i in the register: (register contents) + 1 = 1
5. T2 increments the value of i in the register: (register contents) + 1 = 1
6. T1 stores the value of the register in memory : 1
7. T2 stores the value of the register in memory : 1
8. Integer i = 1

The final value of i is 1 instead of the expected result of 2. This occurs because the increment operations of the second case are non-atomic. Atomic operations are those that cannot be interrupted while accessing some resource, such as a memory location. In the first case, T1 was not interrupted while accessing the variable i, so its operation was atomic. It has been suggested that this article or section be merged into Linearizability. ...

For another example, consider the following two tasks, in pseudocode: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

 global integer A = 0; // increments the value of A and print "RX" // activated whenever an interrupt is received from the serial controller task Received() { A = A + 1; print "RX"; } // prints out only the even numbers // is activated every second task Timeout() { if (A is divisible by 2) { print A; } } 

Output would look something like:

 0 0 0 RX RX 2 RX RX 4 4 

Now consider this chain of events, which might occur next:

1. timeout occurs, activating task Timeout
2. task Timeout evaluates A and finds it is divisible by 2, so elects to execute the "print A" next.
3. data is received on the serial port, causing an interrupt and a switch to task Received
4. task Received runs to completion, incrementing A and printing "RX"
5. control returns to task Timeout
6. task timeout executes print A, using the current value of A, which is 5.

Mutexes are used to address this problem in concurrent programming. Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ...

Real life examples

File systems

In file systems, two or more programs may "collide" in their attempts to modify or access a file, which could result in data corruption. File locking provides a commonly-used solution. A more cumbersome remedy involves reorganizing the system in such a way that one unique process (running a daemon or the like) has exclusive access to the file, and all other processes that need to access the data in that file do so only via interprocess communication with that one process (which of course requires synchronization at the process level). It has been suggested that Crash counting be merged into this article or section. ... File locking is a mechanism that enforces access to a computer file by only one user or process at any specific time. ... In Unix and other computer multitasking operating systems, a daemon is a computer program that runs in the background, rather than under the direct control of a user; they are usually instantiated as processes. ...

A different form of race condition exists in file systems where unrelated programs may affect each other by suddenly using up available resources such as disk space (or memory, or processor cycles). Software not carefully designed to anticipate and handle this rare situation may then become quite fragile and unpredictable. Such a risk may be overlooked for a long time in a system that seems very reliable. But eventually enough data may accumulate or enough other software may be added to critically destabilize many parts of a system. Probably the best known example of this occurred with the near-loss of the Mars Rover "Spirit" not long after landing, but this is a commonly overlooked hazard in many computer systems. A solution is for software to request and reserve all the resources it will need before beginning a task; if this request fails then the task is postponed, avoiding the many points where failure could have occurred. (Alternately, each of those points can be equipped with error handling, or the success of the entire task can be verified afterwards, before continuing on.) A more common but incorrect approach is to simply verify that enough disk space (for example) is available before starting a task; this is not adequate because in complex systems the actions of other running programs can be unpredictable. The mission patch for Spirit, featuring Marvin the Martian. ...

Networking

In networking, consider a distributed chat network like IRC, where a user acquires channel-operator privileges in any channel he starts. If two users on different servers, on different ends of the same network, try to start the same-named channel at the same time, each user's respective server will grant channel-operator privileges to each user, since neither server will yet have received the other server's signal that it has allocated that channel. (Note that this problem has been largely solved by various IRC server implementations.) Internet Relay Chat (IRC) is a form of real-time Internet chat or synchronous conferencing. ... Internet Relay Chat (IRC) is a form of real-time Internet chat or synchronous conferencing. ...

In this case of a race condition, the concept of the "shared resource" covers the state of the network (what channels exist, as well as what users started them and therefore have what privileges), which each server can freely change as long as it signals the other servers on the network about the changes so that they can update their conception of the state of the network. However, the latency across the network makes possible the kind of race condition described. In this case, heading off race conditions by imposing a form of control over access to the shared resource—say, appointing one server to control who holds what privileges—would mean turning the distributed network into a centralized one (at least for that one part of the network operation). Where users find such a solution unacceptable, a pragmatic solution can have the system 1) recognize when a race condition has occurred; and 2) repair the ill effects. A resource, also referred to as system resource, is any physical or virtual system component of a computer system with limited availability. ... Latency is a time delay between the moment something is initiated, and the moment one of its effects begins. ...

Life-critical systems

Software flaws in life-critical systems can be disastrous. Race conditions were among the flaws in the Therac-25 radiation therapy machine, which led to the death of five patients and injuries to several more. Another example is the Energy Management System provided by GE Energy and used by Ohio-based FirstEnergy Corp. (among other power facilities). A race condition existed in the alarm subsystem; when three sagging power lines were tripped simultaneously, the condition prevented alerts from being raised to the monitoring technicians, delaying their awareness of the problem. This software flaw eventually led to the North American Blackout of 2003. GE Energy later developed a software patch to correct the previously undiscovered error. ‹ The template below (Expand) is being considered for deletion. ... Therac-25 was a radiation therapy machine produced by Atomic Energy of Canada Limited. ... Clinac 2100 C100 accelerator Radiation therapy (or radiotherapy) is the medical use of ionizing radiation as part of cancer treatment to control malignant cells (not to be confused with radiology, the use of radiation in medical imaging and diagnosis). ... FirstEnergy provides power, natural gas and services to parts of Ohio, Pennsylvania and New Jersey. ... The 2003 North America blackout was a massive power outage that occurred throughout parts of the northeastern United States and eastern Canada on Thursday, August 14, 2003. ...

Computer security

A specific kind of race condition involves checking for a predicate (e.g. for authentication), then acting on the predicate, while the state can change between the time of check and the time of use. When this kind of bug exists in security-conscious code, a security vulnerability called a time-of-check-to-time-of-use (TOCTTOU) bug is created. Authentication (from Greek αυθεντικός; real or genuine, from authentes; author) is the act of establishing or confirming something (or someone) as authentic, that is, that claims made by or about the thing are true. ... A computer bug is an error, flaw, mistake, failure, or fault in a computer program that prevents it from working as intended, or produces an incorrect result. ... This article describes how security can be achieved through design and engineering. ... In computer software a security vulnerability is a software bug that can be used deliberately to violate security. ... In Computer Security, a time-of-check-to-time-of-use (TOCTTOU − pronounced TOCK too) bug is a specific type of race condition that exists in security-conscious software, leading to a security vulnerability. ...

Asynchronous finite state machines

Even after ensuring that single bit transitions occur between states, the asynchronous machine will fail if multiple inputs change at the same time. The solution to this is to design a machine so that each state is sensitive to only one input change. Fig. ...

See also

• Concurrency control
• Deadlock
• Synchronization
• Therac-25

In computer science -- more specifically, in the field of databases -- concurrency control is a method used to ensure that database transactions are executed in a safe manner (i. ... It has been suggested that Circular wait be merged into this article or section. ... Synchronization (or Sync) is a problem in timekeeping which requires the coordination of events to operate a system in unison. ... Therac-25 was a radiation therapy machine produced by Atomic Energy of Canada Limited. ...

External links

• Article "Secure programmer: Prevent race conditions—Resource contention can be used against you" by David A. Wheeler
• Chapter "Avoid Race Conditions" (Secure Programming for Linux and Unix HOWTO)