14

マルチスレッドコードで問題を引き起こすABA問題の実例を探しています。

ABA問題は、アトミックなコンペアアンドスワップ命令を実行するときに並行コードで発生します。コンペアアンドスワップを実行する直前にスレッドが中断された場合、2番目のスレッドは、コンペアアンドスワップのターゲットを初期値Aから別の値Bに変更する可能性があります。その後、値をAに戻します。最初のスレッドが再開する前に、ターゲット値が変更されても、コンペアアンドスワップは成功します。

多くの場合、ABAは問題ではありません。共有参照カウントを例にとると、refcountが同時に変更されても、すでに0に低下したrefcountから増加しない限り、問題はありません。したがって、ターゲットがターゲットと一致するかどうかにのみ関心があることは明らかです。スワップ時の期待値であり、過去に変更されたかどうかではありません。

ウィキペディアのページには、ABAに悩まされているロックフリースタック実装の例がありますが、私は個人的にこれまでのところ本番コードで問題に遭遇していません。誰かがABAについて共有するいくつかの素晴らしい戦争の話を持っているかどうか私はちょうど興味がありました。

4

1 に答える 1

12

従来の連結リストを使用して順序付きリストを実装するとします。新しい値 V をリストに追加するとします。まず、補助ポインタ AUX を使用して新しい要素を挿入する正しい位置を見つけ、それを V より小さい値を持つ最後のノードに配置し、AUX->next を保存して CAS 操作で比較を行う必要があります。参照を取得したら、NEW-> next を AUX-> next にポイントし、CAS を使用して AUX-> next を NEW に切り替えます (AUX-> next が保存した参照と同じ場合)。次のようになります。

AUX = list.HEAD;
WHILE( AUX->next.value < V)
    AUX = AUX->next;
OLD = AUX->next; //line 4
NEW->next = AUX->next; //line 5
IF( CAS(AUX->next, NEW, OLD)) //line 6
    Success!!!
ELSE
    Try again or whatever

これが最も簡単な方法です。問題は、4 行目と 5 行目の間で、別のスレッドが "OLD" を削除し、V よりも小さいが AUX.value よりも大きい別の要素 X を挿入した可能性があることです。これが発生し、値 X を持つノードに割り当てられたメモリが、OLD を持っていたのと同じアドレスにある場合、CAS は成功しますが、リストは順序付けされません。2 番目のスレッドのアクションが 5 行目と 6 行目の間で発生すると、値 X を持つノードが失われます。これらはすべて ABA 問題が原因です。

于 2013-01-28T00:36:10.320 に答える