フェッチ・アンド・アッド

フェッチ・アンド・アッド（Fetch-and-Add）は、アトミックに指定されたメモリ位置の内容を更新する特別なCPU命令。マルチプロセッサシステムでのミューテックスや並列処理アルゴリズムを実装するのに使われる。
シングルプロセッサシステムでは、クリティカルセクションの前に割り込み不可とするだけで十分である。しかし、マルチプロセッサシステムでは全プロセッサの割り込みを不可とするだけでは不十分で、複数のプロセッサが同時に同じメモリ位置にアクセスするのを防ぐことはできない。フェッチ・アンド・アッド命令はプロセッサがアトミックに指定されたメモリ位置の値をインクリメントするもので、複数プロセッサによる衝突を防ぐ。
Maurice Herlihy (1993年)は、フェッチ・アンド・アッドがコンペア・アンド・スワップよりも劣っていることを証明した。
実装.
一般的なフェッチ・アンド・アッド命令は以下のような関数（擬似コード）と同等の動作をする。ただし、関数全体がアトミック操作として実行され、いかなるプロセスもその途中で割り込むことはできず、関数の途中の状態を見ることはできない。下記の関数は単にフェッチ・アンド・アッドの動作を説明するためのもので、アトミック性を実現するにはハードウェアのサポートを要するので単なる高級言語の関数としては実装できない。
 « atomic »
 function FetchAndAdd("address" location) {
 "int" value := *location
 *location := value + 1
 return value
フェッチ・アンド・アッドを使ったミューテックスは以下のように実装される。
 record locktype {
 "int" ticketnumber
 "int" turn
 procedure LockInit( "locktype"* lock ) {
 lock.ticketnumber := 0
 lock.turn := 0
 procedure Lock( "locktype"* lock ) {
 "int" myturn := FetchAndAdd( &lock.ticketnumber )
 while lock.turn ≠ myturn 
 skip // "ロック獲得までスピン"
 procedure UnLock( "locktype"* lock) {
 FetchAndAdd( &lock.turn )
以下の条件が満たされている時に、これらのルーチンはミューテックスとして動作する: