yohhoyの日記

2012-07-25

atomic compare_exchange_weak/strong関数

C++11標準ライブラリのatomic操作関数 compare_exchange_weak と compare_exchange_strong についてメモ。

両関数ともに変数のatomicなCAS(compare-and-swap)操作を提供する。weak版とstrong版との動作仕様は、weak版では“交換可能な場合でもCAS操作失敗する可能性がある(spurious failure)”が*1、strong版では“交換可能な場合は常にCAS操作が成功する”という点のみ異なる。当初はweak版のみが定義されていたが、強いCAS操作命令をもつハードウェア性能を生かすために、N2748にてstrong版が追加された。

利用指針は下記の通り。大抵のケースでは ループ構造+compare_exchange_weak でよい(はず)。

  • アルゴリズム上、CAS操作をループで括る必要があれば compare_exchange_weak を利用する。(例:一般的なLock-Freeアルゴリズム実装など)
  • アルゴリズム上の制約が無く、かつspurious failureを許容しない場合は compare_exchange_strong を利用する。(例:pthread spinlock相当のtrylock操作実装*2

N3337 29.6.5/p25より引用。

Remark: A weak compare-and-exchange operation may fail spuriously. That is, even when the contents of memory referred to by expected and object are equal, it may return false and store back to expected the same memory contents that were originally there. [Note: This spurious failure enables implementation of compare-and-exchange on a broader class of machines, e.g., load-locked store-conditional machines. A consequence of spurious failure is that nearly all uses of weak compareand-exchange will be in a loop.
When a compare-and-exchange is in a loop, the weak version will yield better performance on some platforms. When a weak compare-and-exchange would require a loop and a strong one would not, the strong one is preferable. -- end note]



関連URL

*1PowerPCやARMなどLL/SC命令を提供するアーキテクチャの場合、compare_exchange_weakはハードウェアの“弱いLL/SC命令”にて実装されうる。wikipedia:en:Load-link/store-conditional, wikipedia:Load-Link/Store-Conditional などを参照のこと。

*2:C++11標準mutexのtry_lock操作セマンティクスであれば、その内部実装をcompare_exchange_weakで行っても良い。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/yohhoy/20120725/p1
リンク元