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

フェッチ・アンド・アッド（Fetch-and-Add）は、アトミックに指定されたメモリ位置の内容を更新する特別なCPU命令。マルチプロセッサシステムでのミューテックスや並列処理アルゴリズムを実装するのに使われる。

シングルプロセッサシステムでは、クリティカルセクションの前に割り込み不可とするだけで十分である。しかし、マルチプロセッサシステムでは全プロセッサの割り込みを不可とするだけでは不十分で、複数のプロセッサが同時に同じメモリ位置にアクセスするのを防ぐことはできない。フェッチ・アンド・アッド命令はプロセッサがアトミックに指定されたメモリ位置の値をインクリメントするもので、複数プロセッサによる衝突を防ぐ。

Maurice Herlihy (1993年)は、フェッチ・アンド・アッドがコンペア・アンド・スワップよりも劣っていることを証明した。

CPUによっては単純なインクリメントだけでなく、任意の値の加算および減算も可能である。この場合、フェッチ・アンド・アッドのみを用いてマルチプロセッサセーフな参照カウントを実装することができる。

実装

一般的なフェッチ・アンド・アッド命令は以下のような関数（擬似コード）と同等の動作をする。ただし、関数全体がアトミック操作として実行され、いかなるプロセスもその途中で割り込むことはできず、関数の途中の状態を見ることはできない。下記の関数は単にフェッチ・アンド・アッドの動作を説明するためのもので、アトミック性を実現するにはハードウェアのサポートを要するので単なる高級言語の関数としては実装できない。

<< 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 )
 }

以下の条件が満たされている時に、これらのルーチンはミューテックスとして動作する:

Locktype型データ構造は使用の前に関数LockInitで初期化される。
ロックを待っているタスクの数は常にINT_MAXを越えない。
ロックにおいて使われている整数型は継続的にインクリメントされ、最大値の次は最小値に戻る。

実装

関連項目