Race Condition

A RaceCondition is a design error in a concurrent program in which actions performed by concurrent threads or processes are only correct when performed in a particular order, but that order is not enforced by the use of synchronization mechanisms (SynchronizationStrategies).

A RaceCondition is hard to detect through normal testing, because errors are dependent on the scheduling of the concurrent threads. This is due to many factors: the number of processors, the scheduling algorithm used by the operating system, delays to the threads caused by communication with external processes or hardware, insertion of trace code or debug breakpoints, etc. Therefore, RaceConditions appear to be HeisenBugs.

One approach to detect if a concurrent algorithm contains a RaceCondition is to model it in some formalism, such as a ProcessCalculus, that expresses the concurrency concerns and then use model checker or a theorem prover to find errors.

Alternatively, race conditions can be eliminated entirely by language-enforced checking:

If you ever need to describe it to a non-software-type, a RaceCondition is when it crashes only some of the time. -- TimKing

I would rather say that a RaceCondition is when shared data can be modified concurrently by two processes, so that both break the data invariant.

One solution is to synchronize access to the shared data, as for example with the use of SoftwareMonitors? (in Java you can just use the SynchronizedKeyword?). This may lead to DeadLocks and LiveLocks.

Another solution is to use LockFreeSynchronization. -- GuillermoSchwarz.

Are not most cases of dead/live-lock race conditions? At least, in that if it doesn't deadlock every time, then the actions performed by the program are only correct (i.e., don't dead-lock) if they occur in the correct, but under-specified order?

Often. That doesn't cover all situations, though. A RaceCondition is exactly when a shared data structure is violated in its CodeInvariant?, because multiple threads or processes had access to it at the same time.

"It's a race, it's a race! I'm winning, I'm winning! **snore**" - Minix Race Conditions

View edit of November 12, 2014 or FindPage with title or text search