ABA問題
From Wikipedia, the free encyclopedia
ABA問題（英: ABA problem）とは、マルチスレッドプログラミングにおいて同期化の過程で発生する問題であり、ある記憶域を二回読み出し、二回の読み出しが同じ値であることを「変更がない」とみなすことにしたとき、二回の読み出しの間に別のスレッドが値を変更し、他の作業を行った後また元の値に戻すと、最初のスレッドが誤って「変更がなかった」とみなしてしまうというものである。
ABA 問題は、複数のスレッドや(or プロセス)が共有されたメモリにアクセスする場合に生じる。下記のイベントの流れは、ABA 問題を発生させる。
- プロセス が共有メモリから値 A を読み出す
- はプリエンプトされ、プロセス が実行される
- は、共有メモリの値 A を値 B に書き換え、さらにプリエンプションの前に A に書き戻す
- は実行を再開し、共有メモリの値が変更していないことを確認して実行を継続する
は実行を継続するが、共有メモリの変更が分からなかったことにより、誤った振る舞いをする可能性がある。
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 は解放済みであるから、何らかの問題が生じる。