LockfreeQueueについて

mutexを使わなくても共有できるデータ構造について。
Compare and Setという不可分な操作を直列化の拠り所として共有するデータ構造です。

コア数が増えて来たときに高い並列性を期待出来るのではないかと思われます。

キモとなるeunque,deque操作のソースコードを貼っておきます。

void enq(const T& v){
    Node* const node = new Node(v);
        while(1){
            const Node* const last = mTail;
            const Node* const next = last->mNext;
            if(last != mTail){ continue; } // 確保中にデータが書き換わってしまったのでやり直し
            if(next == NULL){ // 正常な形のバッファだったら
                if(compare_and_set(&last->mNext, next, node)){ // 最後尾に新規ノードを付け足して
                    compare_and_set(&mTail, last, node); // 最後尾情報を更新
                    return;
                }
            }else{ // 異常な形のバッファだったら
                compare_and_set(&mTail, last, next); // 最後尾情報を訂正する
            }
        }
    }
}
T deq(void){
    unsigned int backoff = 2; // ランダム時間待機用
    while(1){
        const Node* const first = mHead;
        const Node* const last = mTail;
        const Node* const next = first->mNext;
        if(first != mHead){ continue;} // 情報取得中に書き換わったのでやり直し

        if(first == last){
            if(next == NULL){ // バッファが空なら
                usleep(rand()&(backoff - 1)); // 乱数時間だけ待機
                backoff <<= 1; // 待機回数が長くなるほど待機時間も長くなる
                continue;
            }
            compare_and_set(&mTail,last,next); // 異常な形のバッファだったら訂正する
        }else{
            const T v = next->mValue; // 値を確保して
            if(compare_and_set(&mHead, first, next)){ // バッファの先頭を更新させて
                delete first;
                return v; // deque
            }
        }
    }
}

スライド中にも書いてありますが、ソースコード全体はgithubに置いてあります。興味のある方は覗いてみてください。
http://github.com/kumagi/lockfree
シングルスレッドではstd::queueの半分程度の速度でした。