ABA問題
ABA問題(英: ABA problem)とは、マルチスレッドプログラミングにおいて同期化の過程で発生する問題であり、ある記憶域を二回読み出し、二回の読み出しが同じ値であることを「変更がない」とみなすことにしたとき、二回の読み出しの間に別のスレッドが値を変更し、他の作業を行った後また元の値に戻すと、最初のスレッドが誤って「変更がなかった」とみなしてしまうというものである。
ABA 問題は、複数のスレッドや(or プロセス)が共有されたメモリにアクセスする場合に生じる。下記のイベントの流れは、ABA 問題を発生させる。
プロセス P 1 {\displaystyle P_{1}} が共有メモリから値 A を読み出す
P 1 {\displaystyle P_{1}} はプリエンプトされ、プロセス P 2 {\displaystyle P_{2}} が実行される
一般的な対策としては、タグとなるビットを追加して変更を表現することである。たとえばポインタのコンペア・アンド・スワップでは、アドレスの下位のビットで、ポインタの示すデータが何回書き換わったかを表現する。これにより、アドレスが同じであってもタグビットが異なるため、次回のコンペア・アンド・スワップを失敗させることができる。タグビットはすぐに一周してしまうので、これで問題が完全に解決するわけではない。アーキテクチャによっては、ダブルワードのコンペア・アンド・スワップを提供しており、もっと大きなタグを使うことができる。この場合には A が最初とわずかに異なっているので、 ABA' 問題と呼ばれることもある。
確実だが高価な方法として、データ要素そのものではない中間ノードを用いる方法がある。中間ノードはデータ要素のように変更・削除されないようにできるので、要素が挿入されたり削除された場合でも不変性を保証できる[Valois]。