Race condition

Race condition #

Definition. A race condition occurs when the outcome of a program may vary depending on the order in which two threads access a resource.

Illustrations #

Example. The following program (in pseudocode) apparently increments variable i twice. However, it may output either 1 or 2, depending on the execution environment:

int i = 0

spawn i++

i++

sync

print(i)

The reason is that a core does not increment the value of a variable as an atomic operation. Instead, an increment is a sequence of three instructions:

  1. read the value of i and fetch it to one of the core’s registers
  2. increment the value of this register
  3. write the register’s value back to memory

If the two threads are executed in parallel (i.e. on different cores), or if a context switch occurs during the execution of these three operations, then the outcome may be unexpected. Among other possibilities, the following may happen:

  • the current thread executes step 1, copying the value 0 from memory to a register,
  • then the child thread executes step 1 as well, copying the value 0 to another register,
  • then the current thread executes steps 2 and 3, writing the value 1 back to memory,
  • then the child thread executes step 2 and 3, writing the value 1 back again to memory.

However, the following sequence of actions would (for instance) produce the expected result:

  • the current thread executes steps 1, 2 and 3,
  • then the child thread executes steps 1, 2 and 3.

Non determinism #

Warning. In general, a bug caused by a race condition cannot be consistently reproduced, even on the same hardware.

This is why race conditions are notoriously difficult to identify and/or debug, even for a program that has been extensively tested (a famous example of a race condition with a dramatic impact is the Northeastern United States blackout of 2003).

Caution #

Multithreading is a good example (together for instance with caching the results of a computation) of an error-prone optimization technique, which may impact code readability and/or correctness.

A common mistake made by less experienced developers is to use multithreading “because we can”.

Instead, it is often recommended to use multithreading cautiously, and only if some bottleneck has been identified in an application (e.g. with a profiler): unacceptable processing time, non-responsive GUI, etc.

We reproduce here three (loosely) related citations made in Effective Java (Item 67, “Optimize judiciously”):

More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason—including blind stupidity.

William A. Wulf, 1972

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Donald Knuth, 1974

We follow two rules in the matter of optimization: Rule 1. Don’t do it. Rule 2 (for experts only). Don’t do it yet — that is, not until you have a perfectly clear and unoptimized solution.

M. A. Jackson, 1975