C++11: lockせずにデータ競合を防ぐ

データ競合(data-race)を引き起こす典型例:

#include <iostream>
#include <thread>
using namespace std;

int value = 0;

void increment(int n) {
    for (int i = 0; i < n; ++i) {
        value = value + 1;
    }
}

void decrement(int n) {
    for (int i = 0; i < n; ++i) {
        value = value - 1;
    }
}

int main() {
    const int N = 100000;
    thread th0(&increment, N);
    thread th1(&decrement, N);
    th0.join(); th1.join();
    cout << value << endl; // はたして0か!?
}

複数のスレッドがひとつのデータを読み書きするときは排他制御が必要になります。

#include <iostream>
#include <thread>
#include <mutex>
using namespace std;

int value = 0;

void increment(int n, mutex& mtx) {
    for (int i = 0; i < n; ++i) {
        lock_guard<mutex> guard(mtx); // こいつが有効な間は他のスレッドに邪魔されない
        value = value + 1;
    }
}

void decrement(int n, mutex& mtx) {
    for (int i = 0; i < n; ++i) {
        lock_guard<mutex> guard(mtx); // こいつが有効な間は他のスレッドに邪魔されない
        value = value - 1;
    }
}

int main() {
    const int N = 100000;
    mutex mtx;
    thread th0(&increment, N, ref(mtx));
    thread th1(&decrement, N, ref(mtx));
    th0.join(); th1.join();
    cout << value << endl; // はたして0か!?
}

多くのシチュエーションではこれでいいのですが、mutexによる排他制御はかなりコスト高です。
排他しなければならない期間が短く、しかもさほどに競合しないのであれば、

「書く前に現在値を読み、以前と変わりないなら変更する。
　変わってたら(途中で誰かが変更したとみなして)書くのをあきらめる」

...ってことを行えばいい。で、あきらめたときは再度書くのを試みるという、なんとも楽観的な戦術。
そのためには上記「...」がアトミックに(途中割り込まれることなく)行われにゃなりません。
それを実現するのが atomic<T>::compare_exchange_weak

#include <iostream>
#include <thread>
#include <atomic>
using namespace std;

atomic<int> value = 0;

/* bool atomic<T>::compare_exchange_weak(T& expected, T desired 
 * 現在の値が expected に等しければ desired を書いて true を返す
 * さもなくば expected を現在の値に書き換えて false を返す
 */

void increment(int n) {
    for (int i = 0; i < n; ++i) {
        int expected = value.load();
        int desired;
        do {
            desired = expected + 1;
        } while ( !value.compare_exchange_weak(expected, desired));
    }
}

void decrement(int n) {
    for (int i = 0; i < n; ++i) {
        int expected = value.load();
        int desired;
        do {
            desired = expected - 1;
        } while (!value.compare_exchange_weak(expected, desired));
    }
}

int main() {
    const int N = 100000;
    thread th0(&increment, N);
    thread th1(&decrement, N);
    th0.join(); th1.join();
    cout << value << endl; // はたして0か!?
}