【エービーエーもんだい】
ABA問題 とは？
公開:
💡 同じ「A」に戻っても、途中で何もなかったとは限らない
共有値がA→B→Aと変わったのに、値だけの比較では途中の変化を見抜けない問題。古い状態を前提にCASで更新する処理で、不整合の原因になる。
📌 このページのポイント
- CASが比較するのは現在の値と期待値であり、途中の変更履歴ではない
- 問題になるのは、値が同じなら周辺の状態も変わっていないと仮定する処理
- 世代番号との一体比較や適切なメモリ回収方式など、構造に合った対策が必要
ひよこ A、B、Aって、何が問題なの？
ペンギン先生 ひよこ 値が同じなら、困らない気もするよ？
ペンギン先生 その値だけで処理の正しさが決まるなら、戻ったことが問題にならない場合もあるよ。危険なのは、ポインタが同じならリンク先の関係も以前のままだ、などと考える場合だね。取り外したノードや同じメモリアドレスの再利用が絡むと、古い関係を使って更新してしまうんだ。
ひよこ 入れ替わったことを記録すればいいの？
ペンギン先生 値と一緒に世代番号を持ち、更新ごとに進める方法があるよ。（A,7）→（B,8）→（A,9）なら、最初の（A,7）とは違うと分かる。値と番号は一体の原子的な比較・更新が必要で、別々に確認するだけでは間に変更が入るんだ。
ひよこ 番号を付ければ完全に解決？
ペンギン先生 有限の番号は周回するので、比較を待つ間に同じ組へ戻らない条件も必要だよ。また、番号だけで解放済みメモリを読んでよくなるわけではないんだ。ノードをいつ再利用してよいかまで含め、検証された並行データ構造を使うのが大切だね。
もっと詳しく知りたい人へ
世代番号を使うには、必ず倍幅CASが必要ですか？
必ずではありません。値と番号を収める表現や、CPU・言語実装が扱える原子的な幅によります。未使用のアドレスビットを利用できるかも環境依存です。原子的に操作できることと、内部でロックを使わないことは別に確認します。
まとめ：ざっくりこれだけ覚えればOK！
「ABA問題」って出てきたら「値の一致だけでは見えない、途中の入れ替わり」と思えればだいたいOK！