Fetch-and-add
外观
fetch-and-add是CPU指令(FAA),对内存位置执行增加一个数量的原子操作。具体内容为:
- 令x 变为x + a,其中x是个内存位置,a是个值
1991年,Maurice Herlihy证明fetch-and-add具有一个有限的consensus数,能解决不超过两个并发进程的无等待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;
}
参见
[编辑]参考文献
[编辑]- ^ 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).
- ^ std::atomic::fetch_add. cppreference.com. [1 June 2015]. (原始内容存档于2017-11-23).
- ^ Atomic Builtins. Using the GNU Compiler Collection (GCC). Free Software Foundation. 2005 [2017-11-22]. (原始内容存档于2017-11-08).