Fetch-and-add

From Wikipedia, the free encyclopedia

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.

[edit] 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) {
    int value := *location
    *location := value + 1
    return value
}

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

 record locktype {
    int ticketnumber
    int turn
 }
 procedure LockInit( locktype* lock ) {
    lock.ticketnumber := 0
    lock.turn  := 0
 }
 procedure Lock( locktype* lock ) {
    int myturn := FetchAndAdd( &lock.ticketnumber )
    while lock.turn ≠ myturn 
        skip // spin until lock is acquired
 }
 procedure UnLock( locktype* lock) {
    FetchAndAdd( &lock.turn )
 }

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