まえがき

Java 並行プログラミングシリーズ番外編 C A S (比較と交換)、この記事スタイルは依然として写真と情報でいっぱいです。テキストは理解しやすく、読者は面接官とクレイジーな対決をすることができます。

C A S は並行プログラミングに欠かせない基礎知識です。C A S は面接でもよくテストされる場所なので、C A S は必須です。この記事は間違いなく、読者に C A S についての深い理解を提供します。

概要

#C A S 基本概念

C A S(compareAndSwap)比較交換と呼ばれる、ロックフリーのアトミックアルゴリズムです。cmpxchg ハードウェアアセンブリ命令 (保証されたアトミック性 ) としてオペレーティングシステムにマップされます。その機能は、## を作成することです。 #C P Uメモリ値を新しい値に更新しますが、条件があります。メモリ値は期待値と同じである必要があり、C A S 操作ではユーザーモードとユーザーモードを切り替える必要はありません。カーネルモード: ユーザーモードで直接メモリの読み取りと書き込みを行います ( はブロッキング/スレッドコンテキストの切り替えがないことを意味します)。

これには 3 パラメータが含まれています。 C A S (V, E, N) 、V は更新するメモリ値を表し、E は更新するメモリ値を表します。期待値、N は新しい値を表します。V 値が E 値と等しい場合、V 値は次のように更新されます。 N 値、V 値が E 値と異なる場合、更新は実行されません。これは C A S 操作です。

簡単に言うと、C A S では、追加の期待値、つまり、変数が次の場合にこの変数が現在どのように見えるかを指定する必要があります。ご想像のとおり、これは他の人によって変更されたことを意味します。必要なのは、それを再読み込みして、新しい期待値を設定し、再度変更してみることだけです。

C A S がアトミック性を保証する方法

アトミック性とは、C P U の実行中に 1 つ以上の操作が中断されないという特性を指します。途中で実行することはできません (中断できない 1 つまたは一連の操作 )。

C A S のアトミック性を確保するために、C P U は次の 2 つのメソッドを提供します

バスロック
キャッシュロック

バスロック

バス (B U S) は、コンピューターコンポーネント間でデータを送信する方法であり、C P U を意味します。 他のコンポーネントとの接続とデータの送信は、C P U メモリの読み書きなどのバスによって行われます。

バスロックは、C P U がバスロックを使用することを意味します。いわゆるバスロックは、C P U によって提供される ## です。 #LOCK# 信号、C P U がバス上に LOCK# 信号を出力すると、他の C P U のバスリクエストはブロックされます。

キャッシュロック

バスロック方式はアトミック性を保証しますが、ロック期間中に大量のブロッキングが発生し、システムのパフォーマンスのオーバーヘッドが増加します。そのため、パフォーマンスを向上させるために、最新の

C P U は次のように設計されています。ロック範囲を狭めるという考え方キャッシュラインロック ( キャッシュラインは C P U キャッシュストレージ の最小単位です)。

いわゆる キャッシュロックは、キャッシュラインをロックする C P U を指します。キャッシュライン内の共有変数がメモリに書き戻されるとき、 other C P U は、バススニッフィングメカニズムを通じてシェア変数が変更されたかどうかを検出します。変更された場合は、対応するシェア変数のキャッシュラインを無効にし、メモリから最新のデータを再度読み取ります。キャッシュロックは以下に基づいています。キャッシュ整合性メカニズム。キャッシュ整合性メカニズムにより、3 つ以上の C P U が同じ共有変数を同時に変更することが防止されるため、実装されています (Modern C P U は基本的にサポートし、使用します)キャッシュロックメカニズム) 。

C A S

C A S とロックの両方の問題は、アトミック性の問題を解決します。ロックと比較すると、ブロック、スレッドコンテキストの切り替え、またはロックがありません。ロックであるため、C A S はロックよりもパフォーマンスが優れていますが、C A S にも欠点があります。

C A S の質問は次のとおりです

共有変数のアトミック操作のみを保証できます
スピン時間が長すぎます (スピンロックに基づく)
ABA質問

アトミックに操作されることが保証できる共有変数は 1 つだけです

C A S 1つの変数のみを対象とすることができますシェア変数を使用しますシェア変数が複数ある場合はロックしか使用できませんもちろん複数の変数を1つの変数に統合する方法がある場合は C A S## を使用するのも良いです# (読み取り/書き込みロックの state など) の上位ビットと下位ビット。

スピン時間が長すぎます

スレッドがロックを取得したとき失敗してもブロックや中断は行われませんが、成功するまで一定時間後に再度取得を試みます。この周期的な取得メカニズムはスピンロック (spinlock) と呼ばれます。

スピンロックの利点は、ロックを保持しているスレッドが短時間でロックを解放し、ロックの競合を待機しているスレッドがブロッキング状態になる必要がないことです (スレッドは必要ありません)コンテキスト切り替え/ユーザーモードとカーネル状態の切り替えは必要ありません)、待機するだけで済み (spin)、ロックを保持しているスレッドがロックを解放した後に取得できるため、消費が回避されます。ユーザーモードとカーネルモードの切り替え。

スピンロックの欠点は明らかです。スレッドは長時間ロックを保持し、競合するロックを待機しているスレッドはスピンし続けます。つまり、CPU はアイドル状態になり、リソースが意味のない場所で無駄に消費されるため、スピンは一般に、周波数は制限されています。

最後に、スピンロックの実装について話しましょう。スピンロックの実装は、C A S に基づいて行うことができます。まず、lockValue オブジェクトのデフォルト値 を定義します。 1、1 はロックリソースが空いていることを意味し、0 はロックリソースが占有されていることを意味します。コードは次のとおりです。

public class SpinLock {
    
    //lockValue 默认值1
    private AtomicInteger lockValue = new AtomicInteger(1);
    
    //自旋获取锁
    public void lock(){

        // 循环检测尝试获取锁
        while (!tryLock()){
            // 空转
        }

    }
    
    //获取锁
    public boolean tryLock(){
        // 期望值1，更新值0，更新成功返回true，更新失败返回false
        return lockValue.compareAndSet(1,0);
    }
    
    //释放锁
    public void unLock(){
        if(!lockValue.compareAndSet(1,0)){
            throw new RuntimeException("释放锁失败");
        }
    }

}

ログイン後にコピー

タイプ AtomicInteger の lockValue 変数は上記で定義されています。AtomicInteger は、C A S# に基づいて Java によって実装されます。 ##IntegerAtomic 操作クラスでは 3 つの関数も定義されていますlock、tryLock、unLock

tryLock function-get lock

#期待値 1、更新値 0
##C A SUpdate
期待値が
lockValue 値と等しい場合、lockValue 値は 0 および # に更新されます。 ##true# が返される ##、それ以外の場合は次のロジックを実行します。
期待値が
値と等しくない場合は、更新は行われず、
false# が返されます ##unLock 関数リリースロック
- 期待値0、更新値1
- # C A SUpdate
- 期待値が lockValue 値と等しい場合、lockValue 値は次のようになります。 1 に更新された場合は、true を返します。それ以外の場合は、次のロジックを実行します。
- 期待値が次と等しくない場合lockValue value 、更新は行わず、false
lock 関数 - スピンしてロックを取得します
- #tryLock 関数を実行し、停止する場合は true を返します。そうでない場合はループし続けます。
上の図からわかるように、
tryLock が成功したスレッド (更新 lockValue を 0# に更新) # #)、コードブロックが実行されます。他のスレッド tryLock がスピンし、lockValue が 1、tryLock に更新されるまで待機します。 成功したスレッド unLock を実行します (Update lockValue を 1 に)、回転するスレッドは tryLock を実行します。成功しました。 <h2 data-tool="mdnice编辑器" style="font-size: 22px;text-align: center;font-weight: bold;line-height: 1.1em;padding-top: 12px;padding-bottom: 12px;margin: 70px 30px 30px;border-width: 1px;border-style: solid;border-color: rgb(0, 0, 0);"> <span style="display: block;width: 3px;margin-left: 5%;height: 3px;line-height: 3px;overflow: hidden;background-color: rgb(0, 0, 0);box-shadow: rgb(0, 0, 0) 3px 0px, rgb(0, 0, 0) 0px 3px, rgb(0, 0, 0) -3px 0px, rgb(0, 0, 0) 0px -3px;">ABA の質問<span style="display: block;width: 3px;margin-left: 95%;height: 3px;line-height: 3px;overflow: hidden;background-color: rgb(0, 0, 0);box-shadow: rgb(0, 0, 0) 3px 0px, rgb(0, 0, 0) 0px 3px, rgb(0, 0, 0) -3px 0px, rgb(0, 0, 0) 0px -3px;"> </h2> <code style='font-size: 14px;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(255, 100, 65);'>C A S要確認更新対象のメモリ値が変更されているかどうか、変更されていない場合は更新されますが、元々値が A だったものが B になり、その後、 # 再度 ##A を確認すると、C A S が変更されていないことがわかります。

2 つのスレッドがあると仮定します。スレッド 1 がメモリ値 ###A を読み取り、スレッド 1 がタイムスライスを使い果たし、スレッド 2# に切り替えます。 ##、スレッド 2 もメモリ値 ###A を読み取り、それを B 値に変更し、B 値を # に復元しました。 #A 値、簡単に言えば、変更シーケンスは A->B->A であり、スレッド 1 が実行を再開し、メモリ値がまだ残っていることがわかります。 A を実行し、C A S 操作を実行します。これは有名な ABA の問題ですが、問題はないようです。 これは単純なデータ構造なので特に問題はありませんが、複雑なデータ構造の場合は問題が発生する可能性があります (Using <code style='font-size: 14px;overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(255, 100, 65);'>AtomicReference can use C A S オブジェクト ) で、リンクリストデータ構造を例として、リンクリストに A->B# があると仮定して、2 つのスレッドが C A S を通じてヘッドノードを削除します。 ## ノード
- Thread1A ノードを削除すると、B ノードがヘッドノードになり、これから実行されます。 ##C A S(A,A,B) の場合、タイムスライスが使い果たされ、thread2
- thread## に切り替えられます。 #2
 A および B ノード
- 2
 を削除し、C および A ノードとリンクされたlist ノードは A- >C
- 1
 タイムスライスを再取得して実行C A S(A,A,B)
- C
 ノード
A B A 問題を解決するのも非常に簡単です。バージョン番号を追加し、変更されるたびに 1 (つまり A) を追加するだけです。 —> B — > A、1A —> 2B —> 3A になり、AtomicStampedRdference は、このソリューションを実装するために Java で提供されます ( 面接で C A S を尋ねる限り、必ず ABA を尋ねることになります。これを理解する必要があります )。