Fetch-and-add
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, a generalization of semaphores.
In uniprocessor
systems, it is sufficient to disable interrupt
s 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 location, 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.
<< 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:
The following is a C++ implementation for the GCC compiler, for both 32 and 64 bit x86 Intel platforms, based on extended asm syntax:
inline int fetch_and_add( int * variable, int value ){
asm volatile(
"lock; xaddl %%eax, %2;"
:"=a" (value) //Output
: "a" (value), "m" (*variable) //Input
:"memory" );
return value;
}
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the fetch-and-add CPU
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
instruction is a special instruction that atomically modifies the contents of a memory location. It is used to implement mutual exclusion
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
and concurrent algorithms in multiprocessor systems, a generalization of semaphores.
In uniprocessor
Uniprocessor
A uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
systems, it is sufficient to disable interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
s before accessing a critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
.
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 location, preventing such multiple processor collisions.
Maurice Herlihy
Maurice Herlihy
Maurice Herlihy is a computer scientist active in the field of multiprocessor synchronization. Herlihy has contributed to the design of concurrent algorithms, and in particular to the exposition and quantification of the properties and uses of hardware synchronization operations...
(1991) proved that fetch-and-add has a finite consensus number, in contrast to the compare-and-swap
Compare-and-swap
In computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...
operation. The fetch-and-add operation can solve the wait-free consensus problem for no more than two concurrent processes.
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
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:
inline int fetch_and_add( int * variable, int value ){
asm volatile(
"lock; xaddl %%eax, %2;"
:"=a" (value) //Output
: "a" (value), "m" (*variable) //Input
:"memory" );
return value;
}
See also
- Test-and-setTest-and-setIn computer science, the test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin...
- Test and Test-and-setTest and Test-and-setIn computer science, the test-and-set CPU instruction is used to implementmutual exclusion in multiprocessor environments. Although a correct lock can be implemented with test-and-set, it can lead to resource contention in busy lock .To lower the overhead a more elaborate locking...
- Compare-and-swapCompare-and-swapIn computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value...
- Load-Link/Store-ConditionalLoad-Link/Store-ConditionalIn computer science, load-link and store-conditional are a pair of instructions that together implement a lock-free atomic read-modify-write operation....