Fetch-and-add. In computer science, the fetch-and-add (FAA) CPU instruction atomically increments the contents of a memory location by a specified value.

That is, fetch-and-add performs the following operation: increment the value at address  by , where  is a memory location and  is some value, and return the original value at .

in such a way that if this operation is executed by one process in a concurrent system, no other process will ever see an intermediate result.

Fetch-and-add can be used to implement concurrency control structures such as mutex locks and semaphores.

Overview
The motivation for having an atomic fetch-and-add is that operations that appear in programming languages as  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:

 load  into a register;
 add  to register;
 store register value back into .

When one process is doing  and another is doing  concurrently, there is a data race. They might both fetch  and operate on that, then both store their results with the effect that one overwrites the other and the stored value becomes either  or , not  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.

Implementation
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

Hardware and software support
An atomic  function appears in the C++11 standard. It is available as a proprietary extension to C in the Itanium ABI specification, and (with the same syntax) in GCC.

x86 implementation
In the x86 architecture, the instruction ADD with the destination operand specifying a memory location is a fetch-and-add instruction that has been there since the 8086 (it just wasn't called that then), and with the LOCK prefix, is atomic across multiple processors. However, it could not return the original value of the memory location (though it returned some flags) until the 486 introduced the XADD instruction.

The following is a C implementation for the GCC compiler, for both 32- and 64-bit x86 Intel platforms, based on extended asm syntax:
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;
}

History
Fetch-and-add was introduced by the Ultracomputer project, which also produced a multiprocessor supporting fetch-and-add and containing custom VLSI switches that were able to combine concurrent memory references (including fetch-and-adds) to prevent them from serializing at the memory module containing the destination operand.

See also
 Compare-and-swap
 Load-link/store-conditional
 Read–modify–write
 Test-and-set
 Test and test-and-set

References

Computer arithmetic
Concurrency control