|This article needs additional citations for verification. (July 2010)|
A race condition or race hazard is the behavior of an electronic, software or other system where the output is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when events do not happen in the order the programmer intended. The term originates with the idea of two signals racing each other to influence the output first.
- 1 Electronics
- 2 Software
- 3 Examples outside of Computing
- 4 See also
- 5 References
- 6 External links
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 small 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 functions as a clock signal for further systems that contain memory, the system can rapidly depart from its designed behaviour (in effect, the temporary glitch becomes a permanent glitch).
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 true. However, if changes in the value of A take longer to propagate to the second input than the first 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.
Design techniques such as Karnaugh maps encourage designers to recognize and eliminate race conditions before they cause problems. Often logic redundancy can be added to eliminate some kinds of races.
As well as these problems, some logic elements can enter metastable states, which create further problems for circuit designers.
Critical and non-critical race conditions
A critical race occurs when the order in which internal variables are changed determines the eventual state that the state machine will end up in.
A non-critical race occurs when the order in which internal variables are changed does not alter the eventual state. In other words, a non-critical race occurs when moving to a desired state means that more than one internal state variable must be changed at once, but no matter in what order these internal state variables change, the resultant state will be the same.
Static, dynamic, and essential race conditions
- 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 no 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.
Race conditions arise in software when an application depends on the sequence or timing of processes or threads for it to operate properly. As with electronics, there are critical race conditions that result in invalid execution and bugs as well as non-critical race-conditions that result in unanticipated behavior. Critical race conditions often happen when the processes or threads depend on some shared state. Operations upon shared states are critical sections that must be mutually exclusive. Failure to obey this rule opens up the possibility of corrupting the shared state.
Race conditions have a reputation of being difficult to reproduce and debug, since the end result is nondeterministic and depends on the relative timing between interfering threads. Problems occurring in production systems can therefore disappear when running in debug mode, when additional logging is added, or when attaching a debugger, often referred to as a "Heisenbug". It is therefore better to avoid race conditions by careful software design rather than attempting to fix them afterwards.
As a simple example let us assume that two threads each want to increment the value of a global integer variable by one. Ideally, the following sequence of operations would take place:
|Thread 1||Thread 2||Integer value|
In the case shown above, the final value 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:
|Thread 1||Thread 2||Integer value|
The final value is 1 instead of the expected result of 2. This occurs because the increment operations of the second case are not mutually exclusive. Mutually exclusive operations are those that cannot be interrupted while accessing some resource such as a memory location.
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 organizing 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).
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 race 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. (Alternatively, each of those points can be equipped with error handling, or the success of the entire task can be verified afterwards, before continuing.) 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.
In networking, consider a distributed chat network like IRC, where a user who starts a channel automatically acquires channel-operator privileges. 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.)
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).
Race conditions can also exist when a computer program is written with non-blocking sockets, in which case the performance of the program can be dependent on the speed of the network link.
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 at least three 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.
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.
Examples outside of Computing
||This article possibly contains original research. (April 2015)|
Large high-rise apartments using single gravity-fed garbage chutes can be affected by race conditions when they are tasked with sorting falling trash by type. In these systems residents use a menu connected to their floor garbage chute to specify what kind of waste they are dropping in (e.g. garbage, recycling, compost), and this message is relayed to the bottom floor garbage collector so that it can properly sort falling incoming waste into the right waste receptacle. However this system is vulnerable to race conditions if residents on multiple floors are throwing garbage and recycling waste down the chute within close time frames of one another. Waste could arrive before the bottom garbage collector has time to redirect each item of trash, or arrive out of order relative to its floor chute message, causing waste to be incorrectly sorted.
- Concurrency control
- Synchronization (computer science)
- Racetrack problem
- Call collision
- Unger, S.H. (June 1995). "Hazards, Critical Races, and Metastability". IEEE Transactions on Computers 44 (6): 754–768. doi:10.1109/12.391185.
- "An Investigation of Therac-25 Accidents — I". Courses.cs.vt.edu. Retrieved 2011-09-19.
- Kevin Poulsen (2004-04-07). "Tracking the blackout bug". Securityfocus.com. Retrieved 2011-09-19.
- "How Brains Race to Cancel Errant Movements". Discover Magazine blogs. 2013-08-03.
- Schmidt, Robert; Leventhal, Daniel K; Mallet, Nicolas; Chen, Fujun; Berke, Joshua D (2013). "Canceling actions involves a race between basal ganglia pathways". Nature Neuroscience 16 (8): 1118–24. doi:10.1038/nn.3456. PMC 3733500. PMID 23852117.
- Karam, G.M.; Buhr, R.J.A. (August 1990). "Starvation and Critical Race Analyzers for Ada". IEEE Transactions on Software Engineering 16 (8): 829–843. doi:10.1109/32.57622.
- Fuhrer, R.M.; Lin, B.; Nowick, S.M. (27–29 Mar 1995). "Algorithms for the optimal state assignment of asynchronous state machines". Advanced Research in VLSI, 1995. Proceedings., 16th Conference on. pp. 59–75. doi:10.1109/ARVLSI.1995.515611. ISBN 0-8186-7047-9. as PDF
- Paper "A Novel Framework for Solving the State Assignment Problem for Event-Based Specifications" by Luciano Lavagno, Cho W. Moon, Robert K. Brayton and Alberto Sangiovanni-Vincentelli
- Wheeler, David A. (7 October 2004). "Secure programmer: Prevent race conditions—Resource contention can be used against you". IBM developerWorks.
- Chapter "Avoid Race Conditions" (Secure Programming for Linux and Unix HOWTO)
- Race conditions, security, and immutability in Java, with sample source code and comparison to C code, by Chiral Software
- Karpov, Andrey (11 April 2009). "Interview with Dmitriy Vyukov — the author of Relacy Race Detector (RRD)". Intel Software Library Articles.
- Microsoft Support description