- 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 implementMutual exclusion and concurrent algorithms in multiprocessor systems.In
uniprocessor systems, it is sufficient to disableinterrupt s before accessing acritical region .However, in multiprocessor systems, it is impossible and undesirable to disableinterrupt s 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 tocompare-and-swap [cite journal |last=Herlihy |first=Maurice |title=Wait-free synchronization |journal=ACM Trans. Program. Lang. Syst. |volume=13 |issue=1 |date=January, 1991 |pages=124–149 |url=http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf |accessdate=2007-05-20 |doi=10.1145/114005.102808 ] .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 incrementedx86 implementation
In the x86 architecture, the instruction ADD with the first 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.
References
ee also
*
Test-and-set
*Test and Test-and-set
*Compare-and-swap
*Load-Link/Store-Conditional
Wikimedia Foundation. 2010.