Fetch-and-add

fetch-and-add是 CPU 指令（FAA）， 對內存位置執行增加一个數量的原子操作。具體內容為：

令 x 變做是 _ x _ + _ a _，其中 x 是一个內存位，a 是一个值

FAA 通用佇實現互斥鎖、信號量。

一九九一年，Maurice Herlihy 證明 fetch-and-add 具有一个有限的 consensus 數，會當解決無超過兩个並發進程的無等待 consensus 問題。

用途

下述偽代碼用 ticket lock 算法實現互斥鎖：

` ` ` recordlocktype { _ int _ ticketnumber _ int _ turn } procedureLockInit ( _ locktype _ * lock ) { lock . ticketnumber  :=零 lock . turn  :=零 } procedureLock ( _ locktype _ * lock ) { _ int _ myturn  :=FetchAndIncrement ( & lock . ticketnumber ) / / must be atomic , since many threads might ask for a lock at the same time whilelock . turn ≠ myturn skip/ / _ spin until lock is acquired _ } procedureUnLock ( _ locktype _ * lock ) { FetchAndIncrement ( & lock . turn ) / / this need not be atomic , since only the possessor of the lock will execute this } ` ` `

硬體軟體支持

C + + 十一標準定義矣原子的 fetch \ _ add 函數。GCC 共伊做對 C 語言的擴展。

x 八十六實現

對八千空八十六起，以內存為目的操作數的 ADD 指令就是講 fetch-and-add。若使用 LOCK 前綴，按呢伊對較濟處理器是原子操作。但是袂使倒轉來原值，一直到四百八十六引入 XADD 指令。

後述 GCC 編譯的 C 語言函數，佇咧 x 八十六的三十二位佮六十四位平台頂，使用擴展 asm 語法：

參見

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