[EnglishFrontPage] [TitleIndex] [WordIndex

A race condition is a situation in which two or more things are happening concurrently, and the final result depends on the precise timing of the events.

For example, consider two programs that are running at the same time:

  #!/bin/sh
  # Program 1
  read number < file
  number=$(($number + 1))
  echo $number > file

  #!/bin/sh
  # Program 2
  read number < file
  number=$(($number - 1))
  echo $number > file

The first program reads a number from a file, adds 1 to it in memory, and then writes it back out. The second program read the number, subtracts 1 from it, and then writes it back out. Suppose we put the number 42 in the file, and run both programs at the same time. What happens?

Naively, we would expect the final value in the file to be 42. If OS schedules the first program first, then it writes 43 to the file; then the second program reads 43, subtracts 1, and writes 42 back out. Likewise, if the OS schedules the second program first, we would expect the file to contain 41, and then 42 when the first program finishes. Right?

Well, that's certainly one possible outcome. But that is not the only possible outcome, because the programs are not atomic -- that is, they do not perform all their steps without interruption.

Another possible sequence of events goes like this:

  1. Program 1 reads the number 42 from the file.
  2. Program 2 reads the number 42 from the file.
  3. Program 1 adds 1 to its number, and now has 43 in memory.
  4. Program 2 subtracts 1 from its number, and now has 41 in memory.
  5. Program 1 writes 43 to the file.
  6. Program 2 writes 41 to the file. Final result: 41

If the last two lines happen to be reversed, then the final answer would be 43. So, depending on the whims of the operating system's scheduling, we can have final results of 41, 42 or 43.

Race conditions appear in many forms. They are a matter of concern in several sorts of programming. Any time asynchronous signal handlers must be written, or interactions with the file system on a multi-user operating system occur, extra care should be taken to avoid race conditions.


2012-07-01 04:11