ABA問題

ABA問題（英: ABA problem）とは、マルチスレッドプログラミングにおいて同期化の過程で発生する問題であり、ある記憶域を二回読み出し、二回の読み出しが同じ値であることを「変更がない」とみなすことにしたとき、二回の読み出しの間に別のスレッドが値を変更し、他の作業を行った後また元の値に戻すと、最初のスレッドが誤って「変更がなかった」とみなしてしまうというものである。

ABA 問題は、複数のスレッドや(or プロセス)が共有されたメモリにアクセスする場合に生じる。下記のイベントの流れは、ABA 問題を発生させる。

プロセス $P_{1}$ が共有メモリから値 A を読み出す
$P_{1}$ はプリエンプトされ、プロセス $P_{2}$ が実行される
$P_{2}$ は、共有メモリの値 A を値 B に書き換え、さらにプリエンプションの前に A に書き戻す
$P_{1}$ は実行を再開し、共有メモリの値が変更していないことを確認して実行を継続する

$P_{1}$ は実行を継続するが、共有メモリの変更が分からなかったことにより、誤った振る舞いをする可能性がある。

ABA問題に遭遇する一般的なケースとして、ロックフリーのデータ構造を実現する場合がある。ある要素がリストから削除され、解放された後、新しい要素が割り当てられて、リストに追加されると、新規に割り当てられた要素と、削除された要素がメモリ管理上の最適化によって同じものになることがよくある。新しい要素のポインタは古いものと同一になり、ここで ABA 問題を生じる。

例

下記のロックフリースタックを考える:

  /* ABA 問題を生じるロックフリースタック */
  class Stack {
    volatile Obj* top_ptr;
    //
    // トップのオブジェクトをポップし、そのポインタを返す
    //
    Obj* Pop() {
      while(1) {
        Obj* ret_ptr = top_ptr;
        if (!ret_ptr) return NULL;
        Obj* next_ptr = ret_ptr->next;
        // トップのノードはまだ ret であり、スタックに変更があったと考えない
        // (これは、ABA 問題のために正しいとはいえない)
        // トップを次の要素に（アトミックに）変更
        if (CompareAndSwap(top_ptr, ret_ptr, next_ptr)) {
          return ret_ptr;
        }
        // スタックは変更され、最初からやり直し
      }
    }
    //
    // obj_ptr で指すオブジェクトをスタックにプッシュする
    //
    void Push(Obj* obj_ptr) {
      while(1) {
        Obj* next_ptr = top_ptr;
        obj->next = next_ptr;
        // トップノードがまだ next であると、スタックに変更があったと考えない
        // (これは、ABA 問題のために正しいとはいえない)
        // トップを obj に（アトミックに）変更
        if (CompareAndSwap(top_ptr, next_ptr, obj_ptr)) {
          return;
        }
        // スタックは変更され、最初からやり直し
      }
    }
  };

このコードは通常は並列的なアクセスの問題を生じないが、ABA 問題を生じる。下記のようなシーケンスを考える。

スタックが初期状態でトップ → A → B → C というデータを持っているとする。

まずスレッド 1 が top から開始し、

  ret = A;
  next = B;

CompareAndSwapの直前に割り込まれると、

  { // スレッド 2 が pop を実行:
    ret = A;
    next = B;
    CompareAndSwap(A, A, B)  // 成功, top = B
    return A;
  } // 新しいスタックは トップ -> B -> C
  { // スレッド 2 が pop を再び実行:
    ret = B;
    next = C;
    CompareAndSwap(B, B, C)  // 成功, top = C
    return B;
  } // 新しいスタックは トップ -> C
  delete B;
  { // スレッド 2 が A をトップに載せる:
    A->next = C;
    CompareAndSwap(C, C, A)  // 成功, top = A
  }

現在、スタックの内容は top → A → C である。

ここでスレッド 1 が再開すると、CompareExchange(A, A, B)が実行される。

この処理は、top == ret (いずれも A)であるから、必ず成功し、top を next (この場合B) に割り当てる。しかし、B は解放済みであるから、何らかの問題が生じる。

対策

一般的な対策としては、タグとなるビットを追加して変更を表現することである。たとえばポインタのコンペア・アンド・スワップでは、アドレスの下位のビットで、ポインタの示すデータが何回書き換わったかを表現する。これにより、アドレスが同じであってもタグビットが異なるため、次回のコンペア・アンド・スワップを失敗させることができる。タグビットはすぐに一周してしまうので、これで問題が完全に解決するわけではない。アーキテクチャによっては、ダブルワードのコンペア・アンド・スワップを提供しており、もっと大きなタグを使うことができる。この場合には A が最初とわずかに異なっているので、 ABA' 問題と呼ばれることもある。

確実だが高価な方法として、データ要素そのものではない中間ノードを用いる方法がある。中間ノードはデータ要素のように変更・削除されないようにできるので、要素が挿入されたり削除された場合でも不変性を保証できる[Valois]。

他には、ハザードポインタを用いる方法がある。これはリストにはない箇所を示すポインタである。ハザードポインタは変更中の状態を表現し、後でデータを同期する必要があることを示す[Doug Lea]。

アーキテクチャによってはもっと大きなアトミック操作を可能にするものがある。たとえば、二重リンクリストをアトミックに更新できるものもある。

また、アーキテクチャによってはLoad-Link/Store-Conditional命令を提供しているものがあり、これはアドレスの示す箇所に他のストアが行われない場合に限りストアを実行するというものである。記憶域がある値を持っていることと、記憶域が変化したことという二つの概念をうまく分離することができる。DEC Alpha や PowerPC がこの命令をサポートしている。

参考文献

Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup. Lock-free Dynamically Resizable Arrays

ABA問題

目次

例

対策

参考文献

関連項目