Fetch-and-add

Encyclopedia : F : FE : FET : Fetch-and-add

In computer science, the fetch-and-add CPU instruction is a special instruction that atomically modifies the contents of a memory location. It is used to implement Mutual exclusion and concurrent algorithms in multiprocessor systems.

In uniprocessor systems, it is sufficient to disable interrupts before accessing a critical region. However, in multiprocessor systems, it is impossible and undesirable to disable interrupts on all processors at the same time; and 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 location, preventing such multiple processor collisions.

Maurice Herlihy (1993) proved that fetch-and-add is inferior to compare-and-swap.

Implementation

The standard 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)

With fetch-and-add primitive a mutual exclusion lock can be implemented as:

record locktype 
procedure LockInit( locktype* lock ) 
procedure Lock( locktype* lock ) 
procedure UnLock( locktype* lock)

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

Fetch-and-add

Implementation

See also