初心者も BAT 面接官と競争できる: CAS

まえがき

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# が返される ##、それ以外の場合は次のロジックを実行します。
  期待値が
lockValue
• 値と等しくない場合は、更新は行われず、
  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="float: left;display: block;width: 90%;border-top: 1px solid #000;height: 1px;line-height: 1px;margin-left: -5px;margin-top: -17px;"> </span><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;"></span><span style="display: block;-webkit-box-reflect: below 0em -webkit-gradient(linear,left top,left bottom, from(rgba(0,0,0,0)),to(rgba(255,255,255,0.1)));">ABA の質問</span><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;"></span><span style="float: right;display: block;width: 90%;border-bottom: 1px solid #000;height: 1px;line-height: 1px;margin-right: -5px;margin-top: 16px;"> </span> </h2> <p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;margin: 10px;line-height: 1.75;letter-spacing: 0.2em;font-size: 15px;word-spacing: 0.1em;"><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 の問題ですが、問題はないようです。 <p data-tool="mdnice编辑器" style="padding-top: 8px;padding-bottom: 8px;margin: 10px;line-height: 1.75;letter-spacing: 0.2em;font-size: 15px;word-spacing: 0.1em;"> これは単純なデータ構造なので特に問題はありませんが、複雑なデータ構造の場合は問題が発生する可能性があります (<strong>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
  Thread
  • 1
    タイムスライスを再取得して実行C A S(A,A,B)
  紛失
  • C
    ノード

  A B A 問題を解決するのも非常に簡単です。バージョン番号を追加し、変更されるたびに 1 (つまり A) を追加するだけです。 —> B — > A、1A —> 2B —> 3A になり、AtomicStampedRdference は、このソリューションを実装するために Java で提供されます ( 面接で C A S を尋ねる限り、必ず ABA を尋ねることになります。これを理解する必要があります )。

以上が初心者も BAT 面接官と競争できる: CASの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。