Fetch-and-add

The motivation for having an atomic fetch-and-add is that operations that appear in programming languages as

x = x + a

are not safe in a concurrent system, where multiple processes or threads are running concurrently (either in a multi-processor system, or preemptively scheduled onto some single-core systems). The reason is that such an operation is actually implemented as multiple machine instructions:

1. Fetch the value at the location x, say x_old, into a register;
2. add a to x_old in the register;
3. store the new value of the register back into x.

When one process is doing x = x + a and another is doing x = x + b concurrently, there is a race condition. They might both fetch x_old and operate on that, then both store their results with the effect that one overwrites the other and the stored value becomes either x_old + a or x_old + b, not x_old + a + b as might be expected.

In uniprocessor systems with no kernel preemption supported, it is sufficient to disable interrupts before accessing a critical section. However, in multiprocessor systems (even with interrupts disabled) two or more processors could be attempting to access the same memory at the same time. The fetch-and-add instruction allows any processor to atomically increment a value in memory, preventing such multiple processor collisions.

Maurice Herlihy (1991) proved that fetch-and-add has a finite consensus number, in contrast to the compare-and-swap operation. The fetch-and-add operation can solve the wait-free consensus problem for no more than two concurrent processes.[1]

The fetch-and-add instruction behaves like the following function. Crucially, the entire function is executed atomically: no process can interrupt the function mid-execution and hence see a state that only exists during the execution of the function. This code only serves to help explain the behaviour of fetch-and-add; atomicity requires explicit hardware support and hence can not be implemented as a simple high level function.

<< atomic >>
function FetchAndAdd(address location, int inc) {
    int value := *location
    *location := value + inc
    return value
}

To implement a mutual exclusion lock, we define the operation FetchAndIncrement, which is equivalent to FetchAndAdd with inc=1. With this operation, a mutual exclusion lock can be implemented using the ticket lock algorithm as:

record locktype {
    int ticketnumber
    int turn
}

procedure LockInit(locktype* lock) {
    lock.ticketnumber := 0
    lock.turn := 0
}

procedure Lock(locktype* lock) {
    int myturn := FetchAndIncrement(&lock.ticketnumber) // must be atomic, since many threads might ask for a lock at the same time
    while lock.turn ≠ myturn 
        skip // spin until lock is acquired
 }

procedure UnLock(locktype* lock) {
    FetchAndIncrement(&lock.turn) // this need not be atomic, since only the possessor of the lock will execute this
 }

These routines provide a mutual-exclusion lock when following conditions are met:

• Locktype data structure is initialized with function LockInit before use
• Number of tasks waiting for the lock does not exceed INT_MAX at any time
• Integer datatype used in lock values can 'wrap around' when continuously incremented

An atomic fetch_add function appears in the C++11 standard.[2] It is available as a proprietary extension to C in the Itanium ABI specification,[3] and (with the same syntax) in GCC.[4]

static inline int fetch_and_add(int* variable, int value)
{
    __asm__ volatile("lock; xaddl %0, %1"
      : "+r" (value), "+m" (*variable) // input + output
      : // No input-only
      : "memory"
    );
    return value;
}

• Test-and-set
• Test and Test-and-set
• Compare-and-swap
• Load-Link/Store-Conditional