A race hazard (or race condition) is a flaw in a system or process where the output exhibits unexpected critical dependence on the relative timing of events. The term originates with the idea of two signals racing each other to influence the output first. Flaw - A Brief History Flaw was a Nu Metal band from Louisville, Kentucky formed in 1996 when singer Chris Volz answered an ad in a local paper placed by a guitar player, Jason Daunt, looking for a singer for an alternative/industrial band. ... Look up system in Wiktionary, the free dictionary. ... Timing refers to how events are spaced in time. ... An event is something that takes place; an occurrence and arbitrary point 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 hazards occur in poorly-designed electronics systems, especially logic circuits, but they may also arise in computer software. The field of electronics is the study and use of systems that operate by controlling the flow of electrons (or other charge carriers) in devices such as thermionic valves and semiconductors. ... Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is most often said to be the study of criteria for the evaluation of arguments, although the exact definition of logic is a matter of controversy among philosophers. ... An electrical network is an interconnection of electrical elements such as resistors, inductors, capacitors, and switches. ... A computer is a machine designed for manipulating data according to a list of instructions known as a program. ... Computer software (or simply software) refers to one or more computer programs and data held in the storage of a computer for some purpose. ...

In 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. Fig. ...

Solution: Design a machine so that each state is sensitive to only one input change.

Types

Static Race Hazards 

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

Dynamic race Hazards 

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

Essential Race Hazards 

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.

Electronics

A typical example of a race hazard 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). A logic gate is an arrangement of controlled switches used to calculate operations using Boolean logic in digital circuits. ... Glitch City, a Pokémon programming error that creates a jumble of pixels. ...

For example, consider a two input AND gate fed with a logic signal X on input A and its negation, NOT X, on input B. In theory, the output (X AND NOT X) should never be high. However, if changes in the value of X take longer to propagate to input B than to input A then when X 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—note, the Karnaugh map article includes a concrete example of a race hazard and how to eliminate it) encourage designers to recognise and eliminate race hazards before they cause problems. 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. ...

As well as these problems, logic gates 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). ...

See critical race and non-critical race for more information on specific types of race hazards. 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. ...

Computing

Race hazards may arise in software, especially when communicating between separate processes or threads of execution.

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.

If the two threads run simultaneously without locking or synchronization, the outcome of the operation could be wrong

1. Integer i = 0;
2. T1 reads the value of i into a register : 0
3. T2 reads the value of i into a register : 0
4. T1 increments the value of i : (current value of i) + 1 = 1
5. T2 increments the value of i : (current value of i) + 1 = 1

The final value of i is 1 instead of the expected result of 2.

For another example, consider the following two tasks, in pseudocode: Pseudocodes can refer to the technique of using short codes, especially within the language with singular name Short Code, which was the first ever language developed for an electronic computing device. ...

 global integer A = 0; task Received() { A = A + 1; print "RX"; } task Timeout() // Print only the even numbers { if (A is divisible by 2) { print A; } } 

task Received is activated whenever an interrupt is received from the serial controller, and increments the value of A.

task Timeout occurs every second. If A is divisible by 2, it prints 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 concurrent use of un-shareable resources by pieces of computer code called critical sections. ...

In filesystems, 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). In computing, a file lock can be a mutex lock or a shared lock on a file. ... 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. ...

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 instant communication over the Internet. ... Internet Relay Chat (IRC) is a form of instant communication over the Internet. ...

In this case of a race hazard, 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 hazard has occurred; and 2) repair the ill effects. A resource is anything that has identity. ... Latency is a time delay between the moment something is initiated, and the moment one of its effects begins. ...

A race condition exemplifies an anti-pattern. Anti-patterns, also referred to as pitfalls, are classes of commonly-reinvented bad solutions to problems. ...

A particularly poignant example of a race condition was one of the problems that plagued the Therac-25 (a Life-critical system) accidents. Another example is the Energy Management System used by Ohio-based FirstEnergy Corp., that had a race condition in the alarm subsystem; when three sagging power lines were tripped simultaneously, the condition prevented alerts being raised to the monitoring technicians. This software flaw eventually led to the North American Blackout of 2003. Therac-25 was a radiation therapy machine produced by Atomic Energy of Canada Limited. ... A life-critical system or safety-critical system is a system whose failure or malfunction may result in: death or serious injury to people, or loss or severe damage to equipment or environmental harm. ... The 2003 North America blackout was a massive power outage which 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 is the act of establishing or confirming something or someone as authentic. ... 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. ... Computer security is a field of computer science concerned with the control of risks related to computer use. ... 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. ...

Examples

• Injuries and fatalities caused by the Therac 25 medical linear accelerator treatment machine, partially caused by a race condition between the equipment setup and user interface software routines.

Therac-25 was a radiation therapy machine produced by Atomic Energy of Canada Limited. ...

See also

• Synchronization
• Concurrency control
• Word tearing
• Therac-25

To meet Wikipedias quality standards, this article or section may require cleanup. ... 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. ... 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)
• Citations from CiteSeer