Differences between revisions 1 and 4 (spanning 3 versions)
Revision 1 as of 2009-02-04 20:56:56
Size: 2211
Editor: GreyCat
Comment: race condition
Revision 4 as of 2018-11-22 03:41:02
Size: 3473
Editor: ormaaj
Comment: yeah
Deletions are marked like this. Additions are marked like this.
Line 5: Line 5:
{{{
  #!/bin/sh
  # Program 1
  read number < file
  number=$(($number + 1))
  echo $number > file
{{{#!highlight text numbers=disable
#!/bin/sh
# Program 1
read -r number < file
number=$((number + 1))
echo "$number" > file
Line 13: Line 13:
{{{
  #!/bin/sh
  # Program 2
  read number < file
  number=$(($number - 1))
  echo $number > file
{{{#!highlight text numbers=disable
#!/bin/sh
# Program 2
read -r number < file
number=$((number - 1))
echo "$number" > file
Line 23: Line 23:
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? Naively, we would expect the final value in the file to be '''42'''. If OS schedules program 1 first, it reads 42 from the file and writes 43 to the file; then program 2 reads 43, subtracts 1, and writes '''42''' back out. Likewise, if the OS schedules program 2 first, we would expect the file to contain 41 after program 2, and then '''42''' when program 1 finishes. Right?
Line 36: Line 36:
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'''. 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'''.
Line 39: Line 39:

== Mutual exclusion (locking) ==

So, what can we do about this? The standard solution is to place a ''lock'' on some resource, in such a way that only one process at a time may use the resource. If another process tries to acquire the same lock, it will be denied. The second process may decide to wait a moment and retry, or it may abort.

 * For a discussion of locking solutions in shell scripts, please see [[BashFAQ/045|Bash FAQ 45]].

 * As discussed, Race conditions are of particular concern when [[http://mywiki.wooledge.org/ProcessManagement?highlight=%28parallel%29#I_want_to_process_a_bunch_of_files_in_parallel.2C_and_when_one_finishes.2C_I_want_to_start_the_next._And_I_want_to_make_sure_there_are_exactly_5_jobs_running_at_a_time.|multiple concurrent processes]] interact with the system or one another. Standard Unix [[SignalTrap|Signals]] are usually involved when coordinating processes, and their many quirks and gotchas frequently to blame for race issues.

 * Most traditional shells and derivatives can only directly utilize processes for concurrency. Other common mechanisms and APIs such as threads aren't generally available.

 * [[BashFAQ/027|Mutex]]

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 -r number < file
number=$((number + 1))
echo "$number" > file

#!/bin/sh
# Program 2
read -r 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 program 1 first, it reads 42 from the file and writes 43 to the file; then program 2 reads 43, subtracts 1, and writes 42 back out. Likewise, if the OS schedules program 2 first, we would expect the file to contain 41 after program 2, and then 42 when program 1 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.

Mutual exclusion (locking)

So, what can we do about this? The standard solution is to place a lock on some resource, in such a way that only one process at a time may use the resource. If another process tries to acquire the same lock, it will be denied. The second process may decide to wait a moment and retry, or it may abort.

  • For a discussion of locking solutions in shell scripts, please see Bash FAQ 45.

  • As discussed, Race conditions are of particular concern when multiple concurrent processes interact with the system or one another. Standard Unix Signals are usually involved when coordinating processes, and their many quirks and gotchas frequently to blame for race issues.

  • Most traditional shells and derivatives can only directly utilize processes for concurrency. Other common mechanisms and APIs such as threads aren't generally available.
  • Mutex

RaceCondition (last edited 2022-05-21 22:02:29 by larryv)