CASにおけるABA問題

3017 ワード

アーカイブCASのABAの問題.
特に注意しなければならないのは、よくあるABA問題は2種類あり、それぞれ例を挙げて説明することが要求されている.
CASの使用については、以下を参照してください.

ソース|一枝の花を併発するConcurrentLinkedQueue【偽】

ソース|FutureTaskを使用した正しい姿勢

ソースコード|合併一枝花のReentrantLockとAQS(1):lock、unlock

ソースコード|1本の花を併発するReentrantLockとAQS(3):Condition

1定義
1.1基本的なABA問題
CASアルゴリズムでは,メモリ内のある時点のデータ(ユーザによる)を取り出し,次の時点で比較して置き換える必要がある(CPUによる操作は原子的である).この時間差では、データの変化を招きます.
次のイベント・シーケンスを想定します.

スレッド1は、メモリ位置VからAを取り出す.

スレッド2は、位置VからAを取り出す.

スレッド2は、Bを位置Vに書き込むためのいくつかの動作を行う.

スレッド2は、Aを再び位置Vに書き込む.

スレッド1はCAS動作を行い,位置Vでは依然としてAであり,動作に成功していることが分かった.

スレッド1のCAS操作は成功したが、このプロセスに問題がないわけではない.スレッド1では、スレッド2の変更が失われている.
1.2メモリモデルに関するABAの問題
ごみ回収メカニズムのないメモリモデル(C++など)では、プログラマは任意にメモリを解放できます.
次のイベント・シーケンスを想定します.

スレッド1はメモリ位置VからAを取り出し、Aはメモリ位置Wを指す.

スレッド2は、位置VからAを取り出す.

スレッド2はいくつかの操作を行い、Aが指すメモリを解放した.

スレッド2はメモリを再申請し、メモリ位置Wを適切に申請し、位置WをCの内容に格納する.

スレッド2は、メモリ位置Wを位置Vに書き込む.

スレッド1はCAS動作を行い、位置Vにおいて依然としてAが指すメモリ位置Wであることを発見し、動作は

に成功した.
ここでは問題1.1の結果よりも深刻であり,実際の内容は既に修正されているが,スレッド1はスレッド2の修正を感知できない.
さらに、スレッド2がAが指すメモリのみを解放し、スレッド1がCASの前にAのコンテンツにアクセスする場合、スレッド1はにアクセスする.
2例
2.1基本的なABA問題の例
位置Vにチェーンテーブルのヘッダノードが格納されている場合、ABA問題が発生したチェーンテーブルでは、元のヘッダノードがnode 1であり、スレッド2がヘッダノードを2回操作して変化している可能性があり、ヘッダノードがnode 2であることを先に修正してからnode 1(C++でも再割り当てされたノードnode 3であるが、ちょうどそのポインタが解放されたnode 1に等しい)をヘッダに挿入して新しいヘッダノードとなる可能性が高い.
スレッド1の場合、ヘッダノードは依然としてnode 1(または、C++ではアドレスが同じであるが、その内容がnode 3になる可能性があるため、ヘッダノードの値)であり、CAS操作は成功したが、ヘッダノードの後のサブチェーンテーブルの状態は予知できない.
脳補模式図.
2.2メモリモデルに関するABAの問題例
問題の定義が明らかになった.
3解決
Javaのゴミ回収メカニズムはすでに問題1.2を解決してくれた.問題1.1については、バージョン番号を追加すると解決します.
3.1 AtomicStampedReference
オブジェクト値に加えて、AtomicStampedReferenceの内部には「」が維持されています.ステータススタンプはタイムスタンプに類比でき、整数値であり、オブジェクト値を変更するたびにステータススタンプを変更し、同じオブジェクト値の異なるステータスを区別します.AtomicStampedReferenceがオブジェクト値を設定する場合、オブジェクト値およびステータススタンプは、書き込みが成功するまで所望の値を満たさなければなりません.
AtomicStampedReferenceのいくつかのAPIは、AtomicReferenceに基づいてタイムスタンプに関する情報を追加しました.

//          ：                   
public boolean compareAndSet(V expectedReference, V newReference, 
    int expectedStamp, int newStamp)
//        
public V getReference()
//       
public int getStamp()
//            
public void set(V newReference, int newStamp)

3.2 AtomicMarkableReference
AtomicMarkableReferenceとAtomicStampedReferenceの機能は似ていますが、AtomicMarkableReferenceはより簡単な関係を説明します.その定義は、ステータススタンプをtrue|falseに簡略化することである.次のようになります.

public final static AtomicMarkableReference ATOMIC_MARKABLE_REFERENCE 
    = new AtomicMarkableReference<>("abc" , false);

操作時:

ATOMIC_MARKABLE_REFERENCE.compareAndSet("abc", "abc2", false, true);

本文リンク:CAS中のABA問題作者:サル007出典:https://monkeysayhi.github.io本文は知識共有署名-同方式共有4.0国際許可協定の発表に基づいて、転載、演繹または商業目的に使用することを歓迎するが、本文の署名とリンクを保留しなければならない.

JavaScriptモードのオブザーバーモード(Observer Pattern)

JavaScript windowオブジェクトのatob()とbtoa()