CASを使ったロックフリー(Lock-free)共有カウンタの作成方法

CASとは何か

CAS = Compare And Swap
すなわち比較と交換をアトミックに行う命令のこと。

共有カウンタの利用方法

以下の順に従ってカウンタを操作する。
1. 共有カウンタをローカル変数oldに読み込む
2. oldの値に+1したものをローカル変数newとする
3. 共有カウンタの値がoldと一致したら、newの値を共有カウンタに書き込む

3.がCASの命令そのもの。

コードの例

シチュエーションは、共有カウンタを一つインクリメントした値が欲しい場合。
こんな感じで書く。

int global;

int cnt_inc(){
    int old,new;
    do{
        old = global;
        new = old+1;
    }while(!cas(&global,old,new));

    return new;
}

C++でのCASの利用方法について

c++11を使える環境の方

compare_exchange_weak()を利用するとよい。
既にありました。
http://qiita.com/episteme/items/9e6e17512ecadb2ccb40

c++11を使えない環境の方

__sync_bool_compare_and_swap()を利用するとよい。

どっちも使えるけど...

compare_exchange_weak()を利用する場合、CASしたい変数をatomic型でwrapして操作しないといけない。

int global;
atomic<int> global_atomic(global);

構造体のあるメンバに対してCASしたいという時は、いちいちatomic型の変数を用意する必要があるためやや面倒なので__sync__bool_compare_and_swap()を使うと良いかもしれない。
どちらがパフォーマンス的に優れているか等はちゃんと調べてないので分からないです。ごめんなさい。

参考資料

冬のLock free祭り safe
http://www.slideshare.net/kumagi/lock-free-safe