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
 
 
tb = x
x = ta -1
 
 
x = tb1
if( x==0 )
 
 
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.

Per informazioni più dettagliate sulle ottimizzazioni basate su compilatore, vedere il nostro Avviso sull'ottimizzazione.