Atomic operation
From Wikipedia, the free encyclopedia
An atomic operation in computer science refers to a set of operations that can be combined so that they appear to the rest of the system to be a single operation with only two possible outcomes: success or failure.
Contents |
[edit] Conditions
A set of operations can be considered atomic when two conditions are met:
- Until the entire set of operations completes, no other process can know about the changes being made (invisibility); and
- If any of the operations fail then the entire set of operations fails, and the state of the system is restored to the state it was in before any of the operations began.
Even without the complications of multiple processing units, this can be non-trivial to implement. As long as there is the possibility of a change in the flow of control, without atomicity there is the possibility that the system can enter an invalid state (invalid as defined by the program, a so-called invariant).
[edit] Example
[edit] One process
For example, imagine a single process is running on a computer incrementing a value in a given memory location. To increment the value in that memory location:
-
- the process reads the value in the memory location;
- the process adds one to the value;
- the process writes the new value back into the memory location.
[edit] Two processes
Now, imagine two processes are running incrementing a single, shared memory location:
- the first process reads the value in memory location;
- the first process adds one to the value;
but before it can write the new value back to the memory location it is suspended, and the second process is allowed to run:
- the second process reads the value in memory location, the same value that the first process read;
- the second process adds one to the value;
- the second process writes the new value into the memory location.
The second process is suspended and the first process allowed to run again:
- the first process writes a now-wrong value into the memory location, unaware that the other process has already updated the value in the memory location.
This is a trivial example. In a real system, the operations can be more complex and the errors introduced extremely subtle. For example, reading a 64-bit value from memory may actually be implemented as two sequential reads of two 32-bit memory locations. If a process has only read the first 32-bits, and before it reads the second 32-bits the value in memory gets changed, it will have neither the original value nor the new value but a mixed-up garbage value.
Furthermore, the specific order in which the processes run can change the results, making such an error difficult to detect and debug.
[edit] Locking
While an atomic operation is functionally equivalent to a "critical section" (protected by a lock), it requires great care to not suffer significant overhead compared to direct use of atomic operations, with many computer architectures offering dedicated support. To improve program performance, it is therefore often a good idea to replace simple critical sections with atomic operations for non-blocking synchronization, instead of the other way around, but unfortunately a significant improvement is not guaranteed and lock-free algorithms can easily become too complicated to be worth the effort.
[edit] Common primitives
Most modern processors have instructions which can be used to implement locking and lock-free and wait-free algorithms. The ability to temporarily turn off interrupts, ensuring that the currently running process cannot be context switched, also suffices on a uniprocessor. These instructions are used directly by compiler and operating system writers but are also abstracted and exposed as bytecodes and library functions in higher-level languages.
- Atomic read and write
- Test-and-set
- Fetch-and-add
- Compare-and-swap
- Load-Link/Store-Conditional
Many of these primitives can be implemented in terms of each other.
[edit] Implementations
- atomic.h - most operating systems provide a low level C API to atomic operations, however, naming, order of arguments, return values and semantics vary significantly between operating systems, thus libraries and application software using these interfaces directly will be tied to a particular operating system.
- APR - the Apache Portable Runtime library provides a selection of atomic operation function macros for use within MPL licensed software.
- Atomic Operations in GLib
- open-std.org: "An Atomic Operations Library for C++"
- java.util.concurrent.atomic in JDK
