Fetch-and-add

fetch-and-add是CPU指令（FAA），对内存位置执行增加一个数量的原子操作。具体内容为：

令x 变为x \+ a，其中x是个内存位置，a是个值

FAA可用于实现互斥锁、信号量。

1991年，Maurice Herlihy（英语：Maurice Herlihy）证明fetch-and-add具有一个有限的consensus（英语：Consensus (computer science)）数，能解决不超过两个并发进程的无等待consensus问题。[1]

## 用途

[编辑]

下述伪代码用ticket lock算法实现了互斥锁：

record locktype {
int ticketnumber
int turn

procedure LockInit( locktype* lock ) {
lock.ticketnumber := 0
lock.turn := 0

procedure Lock( locktype* lock ) {
int myturn := FetchAndIncrement( &lock.ticketnumber ) //must be atomic, since many threads might ask for a lock at the same time
while lock.turn ≠ myturn
skip // spin until lock is acquired

procedure UnLock( locktype* lock ) {
FetchAndIncrement( &lock.turn ) //this need not be atomic, since only the possessor of the lock will execute this

## 硬件软件支持

[编辑]

C++11标准定义了原子的fetch_add函数。[2] GCC把它作为对C语言的扩展。[3]

### x86实现

[编辑]

从8086起，以内存为目的操作数的ADD指令就是fetch-and-add。如果使用LOCK前缀，那么它对多处理器是原子操作。但不能返回原值，直至486引入XADD指令。

void __fastcall atomic_inc (volatile int* pNum)

__asm

lock inc dword ptr [ECX]
ret

下述GCC编译的C语言函数，在x86的32位与64位平台上，使用扩展asm语法：

static inline int fetch_and_add(int* variable, int value)

__asm__ volatile("lock; xaddl %0, %1"
: "+r" (value), "+m" (*variable) // input+output
: // No input-only
: "memory"

return value;

## 参见

[编辑]

* Test-and-set
* Test and Test-and-set
* Compare-and-swap
* Load-Link/Store-Conditional

## 参考文献

[编辑]

1. ^ Herlihy, Maurice. Wait-free synchronization (PDF). ACM Trans. Program. Lang. Syst. January 1991, 13 (1): 124–149  [2007-05-20]. doi:10.1145/114005.102808. （原始内容存档 (PDF)于2011-06-05）.
2. ^ std::atomic::fetch_add. cppreference.com.  [1 June 2015]. （原始内容存档于2017-11-23）.
3. ^ Atomic Builtins. Using the GNU Compiler Collection (GCC). Free Software Foundation. 2005  [2017-11-22]. （原始内容存档于2017-11-08）.