CAS (コンペアー・アンド・スワップ) ループ

問題

プレディケートが満たされるようにスカラー値をアトミックに更新する。

コンテキスト

多くの場合、共有変数は、新しい値が古い値にとって代わるように変更することで、アトミックに更新する必要があります。この変更は、有限状態機械の遷移、または大域的な情報の記録になります。例えば、共有変数は任意のスレッドにおいてこれまでに確認された最大値を記録しているかもしれません。

影響

• 変数は複数のスレッドによって読み取りおよび更新されます。

• ハードウェアは、その種の変数に「コンペアー・アンド・スワップ」を実装します。

• mutex による更新の保護は回避されます。

関連項目

• リダクション
• 参照カウント

ソリューション

アトミックに現在の値のスナップショットをとり、atomic<T>::compare_and_swap を使用して更新します。compare_and_swap が成功するまで再試行します。現在の値がある条件と一致した場合は、compare_and_swap が成功する前に終了することもあります。

以下のテンプレートは x=f(x) の更新をアトミックに行います。

// x=f(x) をアトミックに実行
template<typename F, typename T>
void AtomicUpdate( atomic<T>& x, F f ) {
   int o;
   do {
       // スナップショットをとる
       o = x;
       // スナップショットから計算した新しい値のインストールを試みる
   } while( x.compare_and_swap(f(o),o)!=o );
}

X の値はほかのスレッドによって変更される可能性があるため、スナップショットをとって中間の計算に使用することが非常に重要になります。

次のコードは、テンプレートを使用して RecordMax によって確認された任意の値のグローバルな最大値を維持する方法を示しています。

// UpperBound = max(UpperBound,y) をアトミックに実行
void RecordMax( int y ) {
   extern atomic<int> UpperBound;
   AtomicUpdate(UpperBound, [&](int value){return std::max(value,y);} );
}

y によって UpperBound が増えない場合、AtomicUpdate の呼び出しは冗長な操作 compare_and_swap(o,o) を実行して時間を浪費することになります。一般に、AtomicUpdate のループを f(o)==o の場合に早く終了することにより、この種の冗長な操作を省略できます。特に F==std::max<int> の場合は、テストをさらに単純化できます。RecordMax の次のバージョンでは、単純化されたテストを行っています。

// UpperBound = max(UpperBound,y) をアトミックに実行
void RecordMax( int y ) . . .
   extern atomic<int> UpperBound;
   do {
       // スナップショットをとる
       int o = UpperBound;
       // スナップショットが条件を満たした場合は終了
       if( o>=y ) break;
       // 新しい値のインストールを試みる
   } while( UpperBound.compare_and_swap(y,o)!=o );
}

関与しているすべてのスレッドが共通の場所を修正するため、高い競合により CAS ループのパフォーマンスが低くなることがあります。このため、より効率的なパターンが適用できるかどうかを最初に考慮するべきです。特に次の点を考慮してください。

• 全体的な目的がリダクションの場合は、リダクション・パターンを代わりに使用してください。

• 更新が加算または減算の場合は、atomic<T>::fetch_and_add を使用してください。また、更新が 1 の加算あるいは減算の場合は、atomic<T>::operater++ または atomic<T>::operator-- を使用してください。これらの方法では通常、CAS ループを回避する直接的なハードウェア・サポートが適用されます。