Java ロック同時実行性、ロックフリー同時実行性、および CAS サンプル分析

ロックされた同時実行性

ほとんどのプログラマ (もちろん、私も基本的にその一人です) にとって、同時プログラミングは、関連するデータ構造にロック (ミューテックス) を追加することとほぼ同じです。たとえば、同時実行をサポートするスタックが必要な場合、最も簡単な方法は、シングルスレッド スタックにロックを追加することです。 std::sync::Mutex 。 (複数のスレッドがスタックの所有権を持てるようにするために Arc が追加されています)

<code>
   
   
  <p>use std::sync::{Mutex, Arc};<br><br>#[derive(Clone)]<br>struct ConcurrentStack<T> {<br>    inner: Arc<Mutex<Vec<T>>>,<br>}<br><br>impl<T> ConcurrentStack<T> {<br>    pub fn new() -> Self {<br>        ConcurrentStack {<br>            inner: Arc::new(Mutex::new(Vec::new())),<br>        }<br>    }<br><br>    pub fn push(&self, data: T) {<br>        let mut inner = self.inner.lock().unwrap();<br>        (*inner).push(data);<br>    }<br><br>    pub fn pop(&self) -> Option<T> {<br>        let mut inner = self.inner.lock().unwrap();<br>        (*inner).pop()<br>    }<br><br>}<br>
  
    

   
   
  </p></code>

コードはシングルスレッド バージョンとほぼ同じであるため、記述するのが非常に便利であり、明らかに利点です。シングルスレッド バージョンを作成し、データ構造にロックを追加し、必要に応じて (Rust では基本的に自動で) ロックを取得および解放するだけです。 ＃＃＃＃＃＃だから問題は何ですか？まず第一に、ロックの取得と解放を忘れる可能性があるという事実 (Rust のおかげで、Rust ではこのようなことはほとんど起こりません) のほかに、デッドロックの問題 (ダイニング哲学者問題) に直面する可能性があります。また、言うまでもなく、一部の優先度の低いタスクは、長時間にわたって優先度の高いタスクのリソースを占有する可能性があります (ロックが最初に行われるため)。スレッドの数が比較的多い場合、ほとんどの時間は同期に費やされます (取得するロック)、パフォーマンスが非常に低下します。大量の読み取りと時折の書き込みを行う同時データベースを考えてみましょう。ロックを使用して処理すると、データベースに更新がない場合でも、2 回の読み取りごとに同期が必要になり、コストがかかりすぎます。

ロックフリーの同時実行性

その結果、多くのコンピューター科学者やプログラマーがロックフリーの同時実行性に注目するようになりました。ロックフリー オブジェクト: 他のスレッドが何をしようと共有オブジェクトが保証している場合、一部のスレッドは限られた数のシステム操作ステップの後に常にその操作を完了します。 Her91 。言い換えれば、少なくとも 1 つのスレッドがその操作の結果を達成します。ロックを使用した同時実行は明らかにこのカテゴリに当てはまりません。ロックを取得したスレッドが遅延すると、その間はどのスレッドも操作を完了できなくなります。極端な場合、デッドロックが発生すると、どのスレッドも操作を完了できなくなります。

CAS (比較および交換) プリミティブ

次に、ロックフリーの同時実行をどのように達成するかに興味があるかもしれません。例はありますか?その前に、ロックフリーの同時実行において非常に重要であると認識されているアトミック プリミティブである CAS を見てみましょう。 CAS の処理は、保存された値と指定された値を比較し、それらが同じである場合にのみ、保存された値を新しい指定された値に変更します。 CAS はアトミック操作です (x86 の比較および交換 (CMPXCHG) など、プロセッサによってサポートされています)。このアトミック性により、他のスレッドが保存された値を変更した場合、書き込みは失敗することが保証されます。 Rust標準ライブラリ内

std::sync::atomic

の型は、アトミック ポインターなどの CAS 操作を提供します。 std::sync::atomic::AtomicPtr <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">&lt;code&gt;      &lt;p&gt;pub fn compare_and_swap(&lt;br&gt;    &amp;self,&lt;br&gt;    current: *mut T,&lt;br&gt;    new: *mut T,&lt;br&gt;    order: Ordering&lt;br&gt;) -&gt; *mut T&lt;br&gt;            &lt;/p&gt;&lt;/code&gt;</pre><div class="contentsignin">ログイン後にコピー</div></div> (ここでは、順序については気にしないでください。つまり、無視してください。 ＃＃＃取得する＃＃＃ 、 ＃＃＃リリース＃＃＃ 、

リラックスした

)ロックフリー スタック (単純なバージョン)<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">&lt;code&gt;      &lt;p&gt;#![feature(box_raw)]&lt;br&gt;&lt;br&gt;use std::ptr::{self, null_mut};&lt;br&gt;use std::sync::atomic::AtomicPtr;&lt;br&gt;use std::sync::atomic::Ordering::{Relaxed, Release, Acquire};&lt;br&gt;&lt;br&gt;pub struct Stack&lt;T&gt; {&lt;br&gt;    head: AtomicPtr&lt;Node&lt;T&gt;&gt;,&lt;br&gt;}&lt;br&gt;&lt;br&gt;struct Node&lt;T&gt; {&lt;br&gt;    data: T,&lt;br&gt;    next: *mut Node&lt;T&gt;,&lt;br&gt;}&lt;br&gt;&lt;br&gt;impl&lt;T&gt; Stack&lt;T&gt; {&lt;br&gt;    pub fn new() -&gt; Stack&lt;T&gt; {&lt;br&gt;        Stack {&lt;br&gt;            head: AtomicPtr::new(null_mut()),&lt;br&gt;        }&lt;br&gt;    }&lt;br&gt;&lt;br&gt;    pub fn pop(&amp;self) -&gt; Option&lt;T&gt; {&lt;br&gt;        loop {&lt;br&gt;            // 快照&lt;br&gt;            let head = self.head.load(Acquire);&lt;br&gt;&lt;br&gt;            // 如果栈为空&lt;br&gt;            if head == null_mut() {&lt;br&gt;                return None&lt;br&gt;            } else {&lt;br&gt;                let next = unsafe { (*head).next };&lt;br&gt;&lt;br&gt;                // 如果现状较快照并没有发生改变&lt;br&gt;                if self.head.compare_and_swap(head, next, Release) == head {&lt;br&gt;&lt;br&gt;                    // 读取内容并返回&lt;br&gt;                    return Some(unsafe { ptr::read(&amp;(*head).data) })&lt;br&gt;                }&lt;br&gt;            }&lt;br&gt;        }&lt;br&gt;    }&lt;br&gt;&lt;br&gt;    pub fn push(&amp;self, t: T) {&lt;br&gt;        // 创建node并转化为*mut指针&lt;br&gt;        let n = Box::into_raw(Box::new(Node {&lt;br&gt;            data: t,&lt;br&gt;            next: null_mut(),&lt;br&gt;        }));&lt;br&gt;        loop {&lt;br&gt;            // 快照&lt;br&gt;            let head = self.head.load(Relaxed);&lt;br&gt;&lt;br&gt;            // 基于快照更新node&lt;br&gt;            unsafe { (*n).next = head; }&lt;br&gt;&lt;br&gt;            // 如果在此期间，快照仍然没有过时&lt;br&gt;            if self.head.compare_and_swap(head, n, Release) == head {&lt;br&gt;                break&lt;br&gt;            }&lt;br&gt;        }&lt;br&gt;    }&lt;br&gt;}&lt;br&gt;            &lt;/p&gt;&lt;/code&gt;</pre><div class="contentsignin">ログイン後にコピー</div></div>ポップでもプッシュでも考え方は同じであることがわかります。最初にスナップショットをポップするか、またはをプッシュして、元のデータを CAS に置き換えてみます。スナップショットとデータが等しい場合は、この期間中に書き込みが実行されなかったことを意味するため、更新は成功します。データに一貫性がない場合は、この期間中に他のスレッドがデータを変更したため、再起動する必要があることを意味します。これはロックフリーのスタックです。すべてが完了したようです！

メモリ解放

Java または他のプログラミング言語を GC で使用している場合は、多くの作業を行ったことがあるかもしれません。今の問題は、GC のない Rust のような言語では、ポップで

return Some(unsafe { ptr::read(&(*head).data) })

をリリースする人がいないことです。 ＃＃＃頭＃＃＃ 、これはメモリリークです。どうやら、ロックなしの同時実行は簡単ではないようです。

以上がJava ロック同時実行性、ロックフリー同時実行性、および CAS サンプル分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。