フェッチアンド追加

コンピュータ サイエンスでは、フェッチ アンド アド( FAA ) CPU命令は、メモリ位置の内容を指定された値だけ アトミックに増加します。

つまり、フェッチ アンド アドは次の操作を実行します。アドレスxの値をaだけ増分します。ここで、xはメモリ位置、aは何らかの値です。そして、 xの元の値を返します。

この操作が並行システム内の 1 つのプロセスによって実行される場合、他のプロセスは中間結果を参照することはありません。

フェッチ アンド アドは、ミューテックス ロックやセマフォなどの同時実行制御構造を実装するために使用できます。

アトミック フェッチ アンド アドを使用する理由は、プログラミング言語でx = x + aとして表示される操作が、複数のプロセスまたはスレッドが同時に実行される並行システム(マルチプロセッサシステム内、または一部のシングル コア システムにプリエンプティブにスケジュールされている) では安全ではないためです。その理由は、このような操作が実際には複数のマシン命令として実装されているためです。

1. x をレジスタにロードします。
2. 登録するを追加します。
3. レジスタ値をxに戻して保存します。

あるプロセスがx = x + a を実行し、別のプロセスがx = x + b を同時に実行している場合、データ競合が発生します。両方のプロセスがx _{old を}取得して操作し、両方のプロセスがその結果を保存すると、一方が他方を上書きし、保存された値はx _old + aまたはx _old + bになり、予想される x _old + a + bにはなりません。

カーネルのプリエンプションがサポートされていない単一プロセッサ システムでは、クリティカル セクションにアクセスする前に割り込みを無効にするだけで十分です。ただし、マルチプロセッサ システムでは (割り込みが無効であっても)、2 つ以上のプロセッサが同時に同じメモリにアクセスしようとする可能性があります。フェッチ アンド アド命令を使用すると、どのプロセッサでもメモリ内の値をアトミックに増分できるため、このような複数プロセッサの衝突を防ぐことができます。

モーリス・ハーリヒ（1991）は、比較スワップ操作とは対照的に、フェッチアンドアド操作には有限のコンセンサス数があることを証明した。フェッチアンドアド操作は、最大2つの同時プロセスに対して待機なしのコンセンサス問題を解決できる。^[1]

フェッチ アンド アド命令は、次の関数のように動作します。重要なのは、関数全体がアトミックに実行されることです。つまり、プロセスは関数の実行中に割り込むことができないため、関数の実行中にのみ存在する状態を見ることができます。このコードは、フェッチ アンド アドの動作を説明するためだけのものです。アトミック性には明示的なハードウェア サポートが必要であり、したがって単純な高レベル関数として実装することはできません。

<<アトミック>>
関数FetchAndAdd(アドレスlocation, int inc) {
     int value := *location
    *場所:=値+増分
    戻り値
}

排他ロックを実装するには、FetchAndIncrement 操作を定義します。これは、inc=1 の FetchAndAdd と同等です。この操作では、次のようにチケット ロックアルゴリズムを使用して排他ロックを実装できます。

レコードロックタイプ {
     intチケット番号
    intターン
}

手順LockInit(ロックタイプ* ロック) {
    ロック.チケット番号:= 0
    ロック.ターン:= 0
}

procedure Lock( locktype * lock) {
     int myturn := FetchAndIncrement(&lock.ticketnumber) // 多くのスレッドが同時にロックを要求する可能性があるため、アトミックである必要があります
    while lock.turn ≠ myturn
         skip //ロックが取得されるまでスピンします
 }

手順UnLock(ロックタイプ* ロック) {
    FetchAndIncrement(&lock.turn) // これはアトミックである必要はありません。ロックの所有者だけがこれを実行するからです。
 }

これらのルーチンは、次の条件が満たされた場合に相互排他ロックを提供します。

• Locktypeデータ構造は使用前に関数LockInitで初期化されます。
• ロックを待機しているタスクの数は、いつでもINT_MAXを超えません。
• ロック値で使用される整数データ型は、連続的に増分すると「ラップアラウンド」する可能性があります。

アトミックなfetch_add関数はC++11標準に登場しました。^[2]これはItanium ABI仕様のCの独自拡張として利用可能であり、^[3] GCCでも（同じ構文で）利用可能です。^[4]

x86 アーキテクチャでは、メモリ位置を指定する宛先オペランドを持つ命令 ADD は、 8086以来存在するフェッチ アンド アド命令であり(当時はそのように呼ばれていなかっただけです)、LOCK プレフィックスにより、複数のプロセッサ間でアトミックです。ただし、 486でXADD 命令が導入される まで、メモリ位置の元の値を返すことはできませんでした (ただし、いくつかのフラグは返しました) 。

以下は、拡張 asm 構文に基づいた、32 ビットおよび 64 ビットの x86 Intel プラットフォーム用 のGCCコンパイラのC実装です。

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

     
           
       
       
    
     

フェッチ アンド アドは、Ultracomputerプロジェクトによって導入されました。このプロジェクトでは、フェッチ アンド アドをサポートするマルチプロセッサも開発されました。このマルチプロセッサには、同時実行メモリ参照 (フェッチ アンド アドを含む) を組み合わせて、宛先オペランドを含むメモリ モジュールでシリアル化されるのを防ぐことができるカスタム VLSI スイッチも含まれていました。

• 比較と交換
• ロードリンク/ストア条件
• 読み取り、変更、書き込み
• テストと設定
• テストとテスト＆セット