並行処理を1から — ロック・アトミック・メモリモデル

データ競合はなぜ起きるのか、なぜテストで再現しないのかを前提知識ゼロから解説。ロック・アトミック操作・CAS・メモリモデルまで、比喩と式とコードで順に積み上げます。

台所がひとつ、料理人がふたり

冷蔵庫に卵が10個。壁のメモには「残り: 10」と書いてあります。料理人の手順は「メモを読む → 卵を1個取る → 読んだ数から1を引いてメモを書き直す」。

1人ずつなら何も起きません。2人が同時に動くと壊れます。AもBもメモを読んで「10」。2人とも卵を取り、2人とも「9」と書き直す。冷蔵庫には8個しか残っていないのに、メモは9個。誰も手順を間違えていないのに、帳簿だけが合わなくなりました。

これがデータ競合です。卵が変数、メモがメモリ、料理人がスレッドにあたります。厄介なのは「たまに」しか起きないこと。タイミングが少しずれれば正しい答えが出るので、テストは通り、手元では再現せず、本番の混み合う時間帯にだけ帳簿が狂います。

なお並行（concurrency）は「複数の仕事の期間が重なる」という構造の話で、コアが1つでも成立します。並列（parallelism）は「物理的に同時に走る」という実行の話です。この記事のバグは並行の側から生まれます。コアが1つでも、OSがスレッドを途中で切り替える以上、同じことが起きるからです。

「1増やす」は1手ではない

いちばんよく壊れるのはこの1行です。

counter += 1

見た目は1動作ですが、機械語では最低3手に分かれます。メモリから読む（load）／レジスタで足す（add）／メモリに書く（store）。料理人と同じ「読んで・変えて・書く」（read-modify-write）で、この3手の途中に他のスレッドが割り込めます。2つのスレッドが10万回ずつ実行しても合計は20万になりません。失われた更新（lost update）の分だけ目減りし、実行のたびに違う数が出ます。

データ競合（data race）とは、「2つ以上のスレッドが同じメモリ位置にアクセスし、少なくとも一方が書き込みで、その間に順序づけがない」状態を指します。C/C++ の規格では、これを含むプログラムの動作は未定義です。コンパイラは競合が無い前提で最適化してよいので、「たまたま正しい値が出た」は何の保証でもありません。

似た言葉の競合状態（race condition）はもっと広く、タイミング次第で結果が変わる設計バグ全般を指します。個々の操作をロックで守っても、「残高を確認してから引き落とす」の合間に割り込まれれば残高はマイナスになりえます。守るべき区間を決めるのは人間の仕事です。

なぜ再現しないのか — 順番の組合せ爆発

再現しないのは運ではなく数の問題です。2つのスレッドがそれぞれ $n$ 手の命令を持つとき、起こりうる実行順（インターリーブ）の総数は、2つの列をトランプのように切り混ぜる方法の数になります。

つまり「全体 $2n$ 手のうち、どの $n$ 手をスレッド1の番に割り当てるか」を選ぶ数え方です。$n=10$ で 184,756通り、$n=20$ なら約1,378億通り。実際の関数は1つで数百手ありますし、スレッドが3本4本と増えれば桁はさらに跳ねます。そのうち壊れるのは、ほんの数通りかもしれません。テストを1回走らせるのは、この山からカードを1枚引くことに相当します。引いて当たらなかったことは、当たりが無いことの証明になりません。

さらに性質が悪いのは、観測すると消えることです。print を1行足す、ブレークポイントを張る、ログを増やす。どれもスレッドの実行時間を変えるので、当たりを引く確率そのものが動きます。「ログを足したら直った」は、直ったのではなく確率が下がっただけです。この種のバグはハイゼンバグと呼ばれます。

だから並行処理では「動いたから正しい」という普段の基準が使えません。実行して確かめるのではなく、構造として競合が起こりえないことを示すしかない。以下はそのための道具です。