# Atomic Operations

You can avoid mutual exclusion using atomic operations. When a thread performs an atomic operation, the other threads see it as happening instantaneously. The advantage of atomic operations is that they are relatively quick compared to locks, and do not suffer from deadlock and convoying. The disadvantage is that they only do a limited set of operations, and often these are not enough to synthesize more complicated operations efficiently. But nonetheless you should not pass up an opportunity to use an atomic operation in place of mutual exclusion. Class `atomic<T>` implements atomic operations with C++ style.

A classic use of atomic operations is for thread-safe reference counting. Suppose x is a reference count of type `int`, and the program needs to take some action when the reference count becomes zero. In single-threaded code, you could use a plain `int` for x, and write `--x; if(x==0) action().` But this method might fail for multithreaded code, because two threads might interleave their operations as shown in the following table, where ta and tb represent machine registers, and time progresses downwards:

Interleaving of Machine Instructions
Thread A | Thread B
--- | ---
    ta  = x

    x = ta - 1

    if( x==0 )
    tb = x

    x = tb – 1

    if( x==0 )

Though the code intended for `x` to be decremented twice, it ends up with only one less than its original value. Also, another problem results because the test of x is separate from the decrement: If x starts out as two, and both threads decrement x before either thread evaluates the `if` condition, both threads would call `action()`. To correct this problem, you need to ensure that only one thread at a time does the decrement and ensure that the value checked by the "if" is the result of the decrement. You can do this by introducing a mutex, but it is much faster and simpler to declare x as `atomic<int>` and write "`if(--x==0) action()`". The method `atomic<int>::operator--` acts atomically; no other thread can interfere.

`atomic<T>` supports atomic operations on type T, which must be an integral, enumeration, or pointer type. There are five fundamental operations supported, with additional interfaces in the form of overloaded operators for syntactic convenience. For example, `++`, `--`, `-=`, and `+=` operations on `atomic<T>` are all forms of the fundamental operation fetch-and-add. The following are the five fundamental operations on a variable x of type `atomic<T>`.

Fundamental Operations on a Variable x of Type atomic<T>
`= x` | read the value of x
`x=` | write the value of x, and return it
`x.fetch_and_store(y)` | do `x=y` and return the old value of x
`x.fetch_and_add(y)` | do `x+=y` and return the old value of x
`x.compare_and_swap(y,z)` | if x equals z, then do `x=y`. In either case, return old value of x.

Because these operations happen atomically, they can be used safely without mutual exclusion. Consider the following example:

    atomic<unsigned> counter;

    unsigned GetUniqueInteger() {
        return counter.fetch_and_add(1);
    }

The routine `GetUniqueInteger` returns a different integer each time it is called, until the counter wraps around. This is true no matter how many threads call `GetUniqueInteger` simultaneously.

The operation `compare_and_swap` is a fundamental operation to many non-blocking algorithms. A problem with mutual exclusion is that if a thread holding a lock is suspended, all other threads are blocked until the holding thread resumes. Non-blocking algorithms avoid this problem by using atomic operations instead of locking. They are generally complicated and require sophisticated analysis to verify. However, the following idiom is straightforward and worth knowing. It updates a shared variable `globalx` in a way that is somehow based on its old value:

    atomic<int> globalx;

    int UpdateX() {      // Update x and return old value of x.
        do {
            // Read globalX
            oldx = globalx;
            // Compute new value
            newx = ...expression involving oldx....
            // Store new value if another thread has not changed globalX.
        } while( globalx.compare_and_swap(newx,oldx)!=oldx );
        return oldx;
    }

Worse, some threads iterate the loop until no other thread interferes. Typically, if the update takes only a few instructions, the idiom is faster than the corresponding mutual-exclusion solution.

### Caution

If the following sequence thwarts your intent, then the update idiom is inappropriate:

1. A thread reads a value A from `globalx`

2. Other threads change `globalx` from A to B to A

3. The thread in step 1 does its `compare_and_swap`, reading A and thus not detecting the intervening change to B.

The problem is called the ABA problem. It is frequently a problem in designing non-blocking algorithms for linked data structures. See the Internet for more information.

Parent topic: Intel® Threading Building Blocks (Intel® TBB) User Guide

- Why atomic<T> Has No Constructors
- Memory Consistency