Namaran

Code daily. Without assist.

2026-10-26

door_state.cpp

#include <atomic>
#include <iostream>

struct State {
    bool open;
    unsigned char version;
};

std::atomic<State> state{State{false, 0}};

bool set_open(State seen, bool open) {
    State next{open, static_cast<unsigned char>(seen.version + 1)};
    return state.compare_exchange_strong(seen, next);
}

int main() {
    State seen = state.load();
    for (int i = 0; i < 256; ++i)
        set_open(state.load(), !state.load().open);
    std::cout << std::boolalpha << set_open(seen, true) << '\n';
}

set_open は、seen を読んだあとに state が一度でも書き換えられていれば失敗するつもりの更新です。書き換えのたびに version を1進め、compare_exchange_strong で seen と比べます。main は seen を読んだあと、ほかの書き手の代わりに open の反転を256回行い、それから seen を使って set_open を呼びます。本来の出力は false ですが、いまは true が出て、古い seen からの更新が通ってしまいます。

Answer

Wrong

struct State {
    bool open;
    unsigned char version;
};

bool set_open(State seen, bool open) {
    State next{open, static_cast<unsigned char>(seen.version + 1)};
    return state.compare_exchange_strong(seen, next);
}

version は unsigned char で、表せるのは 0 から 255 までです。seen.version + 1 は int で計算されますが、static_cast<unsigned char> で戻すときに256で割った余りになるので、255 の次は 0 です。256回の反転のあとでは version が 0 に戻り、open も偶数回の反転で false に戻っています。

state の中身は、seen を読んだときの {false, 0} とまったく同じです。compare_exchange_strong は中身を比べるだけなので成功し、true が返ります。版番号が一周すると、値がAからBを経てAに戻ったことを見逃す問題(ABA問題)が、版番号を入れる前と同じように起きます。

Right

struct State {
    bool open;
    unsigned version;
};

bool set_open(State seen, bool open) {
    State next{open, static_cast<unsigned>(seen.version + 1)};
    return state.compare_exchange_strong(seen, next);
}

version を unsigned にします。x86-64 の GCC では unsigned は32ビットなので、一周するには約43億回の書き換えが要り、1回読んでから更新するまでのあいだにそれだけの書き換えが起きることは現実にはありません。版番号の幅は、読んでから更新するまでに起こりうる書き換えの回数より十分に大きく取ります。