Fetch-and-add |
In computer science, the fetch-and-add Central processing unit instruction is a special instruction that atomic (computer science)ally 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 atomic (computer science): 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.
> function FetchAndAdd( address location) { int value := *location value := value + 1 *location := value 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 := 1 } 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:
=See also=
*Test-and-set *Test and Test-and-set *Load-Link/Store-Conditional|
|