Fetch-and-add

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

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

1991年，证明fetch-and-add具有一个有限的数，能解决不超过两个并发进程的无等待consensus问题。

用途
下述伪代码用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标准定义了原子的函数。 GCC把它作为对C语言的扩展。

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

参考文献

Category:并发控制