障害・アンチパターン図鑑 · 基礎から応用へ

ABA問題

値がAへ戻る間に変わった状態を追い、CASの比較と参照先の寿命管理を分けて考えます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 同じ値でも同じ状態とは限らない
  2. スタックの先頭がAへ戻る例
  3. 値の比較と寿命管理を分ける
  4. 変更履歴を追える対策を選ぶ
  5. この記事をロゲイアに質問する理解を確かめる

同じ値でも同じ状態とは限らない

ABA問題は、比較対象がAから別の値へ変化し、再びAへ戻ったため、値の一致だけでは途中の変化を検出できない現象です。CASが故障しているのではありません。CASは指定された値の比較と更新を原子的に行っていますが、アルゴリズム側が必要とする「読み取った後で状態が変わっていない」という条件までは保証しません。更新回数やオブジェクトの寿命が意味を持つ処理で問題になります。

スタックの先頭がAへ戻る例

単方向スタックA→B→Cを考えます。スレッドT1は先頭Aと次のBを読み、一時停止します。T2はAとBを取り除き、Aを再び先頭へ戻してA→Cにします。T1が先頭をAから保存済みのBへCASすると、先頭の値はAなので成功し得ます。しかしBはすでにスタックに属しておらず、古いnextに基づく更新が構造を壊します。これは処理順を説明する模式例で、実装には安全な参照の読み取りも必要です。

値の比較と寿命管理を分ける

ポインタを比較するCやC++では、メモリが解放されて同じアドレスに別のノードが配置される場合も考える必要があります。解放済みノードを読む問題はuse-after-freeであり、ABAとの関係はありますが同一ではありません。危険な参照が残る間の再利用を防ぐ方法と、論理的に一度取り除いたノードを再挿入できるかという規則を別々に確認します。ガベージコレクションがあっても論理的なABAが自動で消えるとは限りません。

変更履歴を追える対策を選ぶ

参照と世代番号の組を原子的に比較すれば、A・世代7とA・世代9を区別できます。JavaのAtomicStampedReferenceは、このような参照と整数の組を扱うためのAPIです。ただし世代番号の周回、複合更新の実装、メモリ回収の安全性は別途検討します。ハザードポインタなどの回収方式も、それを使うアルゴリズムの再利用規則と合わせて評価します。小さな処理では、通常のロックで不変条件を守る方が検証しやすい場合があります。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

学習コースから次を選ぶ