跳至內容

Fetch-and-add

維基百科,自由的百科全書

fetch-and-addCPU指令(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;
  }

參見

[編輯]

參考文獻

[編輯]
  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).