並行性におけるABA問題
1. 序章
このチュートリアルでは、並行プログラミングにおけるABA問題の理論的背景について説明します。 その根本的な原因と解決策を見ていきます。
2. コンペアアンドスワップ
根本的な原因を理解するために、コンペアアンドスワップの概念を簡単に確認しましょう。
コンペアアンドスワップ(CAS)は、ロックフリーアルゴリズムの一般的な手法であり、別のスレッドがその間に同じスペースを変更した場合に、あるスレッドによる共有メモリへの更新が失敗することを保証します。
これは、
もちろん、このシナリオは参照でも発生する可能性があります。
3. ABA問題
さて、ABA問題は、コンペアアンドスワップアプローチだけでは失敗するという異常です。
たとえば、あるアクティビティが更新の準備として共有メモリ(A)を読み取るとします。 次に、別のアクティビティがその共有メモリを一時的に変更し(B)、次にそれを復元します(A)。 その後、最初のアクティビティでCompare and Swapを実行すると、変更が加えられていないように見え、チェックの整合性が無効になります。
多くのシナリオではこれは問題を引き起こしませんが、時々、Aは私たちが考えるほどAと等しくありません。 これが実際にどのように見えるか見てみましょう。
3.1. ドメインの例
実際の例で問題を説明するために、整数変数が実際の残高の金額を保持する単純な銀行口座クラスを考えてみましょう。 また、引き出し用と預金用の2つの機能があります。 これらの操作では、CASを使用して、アカウントの残高を増減します。
3.2. 問題はどこだ?
スレッド1とスレッド2が同じ銀行口座で動作している場合のマルチスレッドシナリオについて考えてみましょう。
スレッド1がいくらかのお金を引き出したい場合、実際の残高を読み取り、後でCAS操作で金額を比較するためにその値を使用します。 ただし、何らかの理由で、スレッド1は少し遅いです—おそらくそれはブロックされています。
その間、スレッド2は、スレッド1が一時停止されている間、同じメカニズムを使用してアカウントに対して2つの操作を実行します。最初に、スレッド1によって既に読み取られている元の値を変更しますが、その後、変更します。元の値に戻します。
スレッド1が再開すると、何も変更されていないように見え、CASは成功します。
4. Javaの例
これをよりよく視覚化するために、いくつかのコードを見てみましょう。 ここではJavaを使用しますが、問題自体は言語固有ではありません。
4.1. アカウント
まず、アカウントクラスは、 AtomicInteger、に残高を保持します。これにより、Javaで整数のCASが得られます。 また、成功したトランザクションの数をカウントするための別のAtomicIntegerがあります。 最後に、 ThreadLocal 変数を使用して、特定のスレッドのCAS操作の失敗をキャプチャします。
public class Account {
private AtomicInteger balance;
private AtomicInteger transactionCount;
private ThreadLocal<Integer> currentThreadCASFailureCount;
...
}
4.2. 預金
次に、アカウントクラスのdepositメソッドを実装できます。
public boolean deposit(int amount) {
int current = balance.get();
boolean result = balance.compareAndSet(current, current + amount);
if (result) {
transactionCount.incrementAndGet();
} else {
int currentCASFailureCount = currentThreadCASFailureCount.get();
currentThreadCASFailureCount.set(currentCASFailureCount + 1);
}
return result;
}
AtomicInteger.compareAndSet(…)は、CAS操作のブール結果を反映する AtomicInteger.compareAndSwap()メソッドのラッパーにすぎないことに注意してください。
4.3. 撤退
同様に、引き出しメソッドは次のように作成できます。
public boolean withdraw(int amount) {
int current = getBalance();
maybeWait();
boolean result = balance.compareAndSet(current, current - amount);
if (result) {
transactionCount.incrementAndGet();
} else {
int currentCASFailureCount = currentThreadCASFailureCount.get();
currentThreadCASFailureCount.set(currentCASFailureCount + 1);
}
return result;
}
ABA問題を実証できるようにするために、 maybeWait()メソッドを作成して、他のスレッドが
ここで、スレッド1を2秒間中断します。
private void maybeWait() {
if ("thread1".equals(Thread.currentThread().getName())) {
// sleep for 2 seconds
}
}
4.4. ABAシナリオ
最後に、ABA問題が可能かどうかを確認するための単体テストを作成できます。
以前のスレッド1とスレッド2の2つのスレッドを作成します。 スレッド1は残高を読み取り、遅延します。 スレッド2は、スレッド1がスリープしているときに、バランスを変更してから元に戻します。
スレッド1がウェイクアップすると、それは賢明ではなくなり、その操作は引き続き成功します。
初期化後、CAS操作を実行するために余分な時間を必要とするスレッド1を作成できます。 それを終えた後、内部状態が変更されたことを認識しないため、CAS障害カウントはABAシナリオで予想される1ではなくゼロになります。
@Test
public void abaProblemTest() {
// ...
Runnable thread1 = () -> {
assertTrue(account.withdraw(amountToWithdrawByThread1));
assertTrue(account.getCurrentThreadCASFailureCount() > 0); // test will fail!
};
// ...
}
同様に、スレッド1の前に終了するスレッド2を作成し、アカウントの残高を変更して元の値に戻すことができます。 この場合、CASの障害は発生しません。
@Test
public void abaProblemTest() {
// ...
Runnable thread2 = () -> {
assertTrue(account.deposit(amountToDepositByThread2));
assertEquals(defaultBalance + amountToDepositByThread2, account.getBalance());
assertTrue(account.withdraw(amountToWithdrawByThread2));
assertEquals(defaultBalance, account.getBalance());
assertEquals(0, account.getCurrentThreadCASFailureCount());
};
// ...
}
スレッドを実行した後、スレッド1は期待されるバランスを取得しますが、スレッド2からの追加の2つのトランザクションは期待されません。
@Test
public void abaProblemTest() {
// ...
assertEquals(defaultBalance - amountToWithdrawByThread1, account.getBalance());
assertEquals(4, account.getTransactionCount());
}
5. 価値対 参照ベースのシナリオ
上記の例では、重要な事実を見つけることができます。シナリオの最後に戻った AtomicInteger は、最初に取得したものとまったく同じです。 スレッド2によって行われた2つの追加トランザクションのキャプチャに失敗したことを除いて、この特定の例では異常は発生しませんでした。
この背後にある理由は、基本的に参照型ではなく値型を使用したためです。
5.1. 参照ベースの異常
参照型を再利用する目的で使用すると、ABA問題が発生する可能性があります。 この場合、ABAシナリオの最後に、一致する参照が返されるため、CAS操作は成功しますが、参照が元のオブジェクトとは異なるオブジェクトを指している可能性があります。 これはあいまいさをもたらす可能性があります。
6. ソリューション
問題の全体像がわかったので、考えられる解決策をいくつか掘り下げてみましょう。
6.1. ガベージコレクション
参照型の場合、ガベージコレクション(GC)は、ほとんどの場合、ABA問題から私たちを保護することができます。
スレッド1が使用している特定のメモリアドレスにオブジェクト参照を持っている場合、スレッド2が行うことで、別のオブジェクトが同じアドレスを使用することはありません。 オブジェクトはまだ生きていて、そのアドレスへの参照がなくなるまでそのアドレスは再利用されません。
これは参照型では機能しますが、問題は、ロックフリーデータ構造でGCに依存している場合です。
もちろん、一部の言語がGCを提供していないことも事実です。
6.2. ハザードポインター
ハザードポインターは前のものとある程度関連しています–自動ガベージコレクションメカニズムを持たない言語でそれらを使用できます。
簡単に言えば、スレッドは共有データ構造内の問題のあるポインターを追跡します。 このようにして、各スレッドは、ポインタによって定義された特定のメモリアドレス上のオブジェクトが別のスレッドによって変更された可能性があることを認識します。
それでは、他のいくつかの解決策を見てみましょう。
6.3. 不変性
もちろん、不変オブジェクトの使用は、アプリケーション全体でオブジェクトを再利用しないため、この問題を解決します。何かが変更されるたびに、新しいオブジェクトが作成されるため、CASは確実に失敗します。
ただし、最終的なソリューションでは、可変オブジェクトも使用できます。
6.4. 二重比較と交換
二重比較およびスワップ方式の背後にある考え方は、もう1つの変数、つまりバージョン番号を追跡し、それを比較にも使用することです。 この場合、古いバージョン番号があるとCAS操作は失敗します。これは、その間に別のスレッドが変数を変更した場合にのみ可能です。
Javaでは、AtomicStampedReferenceおよびAtomicMarkableReferenceがこのメソッドの標準実装です。
7. 結論
この記事では、ABA問題とそれを防ぐためのいくつかのテクニックについて学びました。
いつものように、完全なソースコードとその他の例はすべてGitHubで利用できます。