Java lock concurrency, lock-free concurrency dan analisis contoh CAS

Konkurensi terkunci

Bagi kebanyakan pengaturcara (sudah tentu saya salah seorang daripada mereka), pengaturcaraan serentak hampir sama dengan menambah kunci pada struktur data yang berkaitan (Mutex). Sebagai contoh, jika kita memerlukan tindanan yang menyokong konkurensi, cara paling mudah ialah menambah kunci pada tindanan satu benang. std::sync::Mutex . (Arc ditambah untuk membolehkan berbilang benang memiliki pemilikan tindanan)

<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>

Kod ini sangat mudah untuk ditulis, kerana ia hampir sama dengan versi satu-benang, yang jelas memberi manfaat. Tulis sahaja versi berbenang tunggal, tambahkan kunci pada struktur data, dan kemudian peroleh dan lepaskan kunci (pada asasnya automatik dalam Rust) apabila perlu.

Jadi apa masalahnya? Pertama sekali, selain daripada fakta bahawa anda mungkin terlupa untuk memperoleh dan melepaskan kunci (yang hampir mustahil berlaku dalam Rust terima kasih kepada Rust), anda mungkin menghadapi masalah kebuntuan (Masalah Ahli Falsafah Makan). Dan apatah lagi bahawa beberapa tugas keutamaan rendah mungkin merampas sumber tugas keutamaan tinggi untuk masa yang lama (kerana kunci diutamakan Apabila bilangan utas agak besar, kebanyakan masa dihabiskan untuk penyegerakan ( Menunggu kunci yang akan diperolehi), prestasi akan menjadi sangat lemah. Pertimbangkan pangkalan data serentak dengan bilangan bacaan yang banyak dan penulisan sekali-sekala Jika kunci digunakan untuk mengendalikannya, walaupun pangkalan data tidak mempunyai sebarang kemas kini, penyegerakan akan diperlukan antara setiap dua bacaan, yang terlalu mahal!

Konkurensi tanpa kunci

Hasilnya, sebilangan besar saintis komputer dan pengaturcara menumpukan perhatian mereka kepada konkurensi tanpa kunci. Objek bebas kunci: Jika objek kongsi menjamin bahawa tidak kira apa yang dilakukan oleh utas lain, sesetengah utas akan sentiasa menyelesaikan operasi padanya selepas beberapa langkah operasi sistem yang terhad. Her91 . Dalam erti kata lain, sekurang-kurangnya satu utas akan mencapai hasil daripada operasinya. Concurrency menggunakan kunci jelas tidak termasuk dalam kategori ini: jika benang yang memperoleh kunci ditangguhkan, tiada benang boleh menyelesaikan sebarang operasi pada masa ini. Dalam kes yang melampau, jika kebuntuan berlaku, tiada benang boleh menyelesaikan sebarang operasi.

CAS (bandingkan dan tukar) primitif

Maka anda mungkin tertanya-tanya, bagaimana untuk mencapai konkurensi tanpa kunci? Adakah terdapat sebarang contoh? Sebelum itu, mari kita lihat primitif atom yang diakui sangat penting dalam konkurensi bebas kunci: CAS. Proses CAS adalah untuk membandingkan nilai yang disimpan dengan nilai yang ditentukan Hanya apabila ia adalah sama, nilai yang disimpan akan diubah suai kepada nilai yang ditentukan baharu. CAS ialah operasi atom (disokong oleh pemproses, seperti perbandingan dan pertukaran x86 (CMPXCHG) ini menjamin bahawa jika utas lain telah menukar nilai yang disimpan, penulisan akan gagal. dalam perpustakaan standard Rust std::sync::atomic Jenis dalam menyediakan operasi CAS, seperti penunjuk atom std::sync::atomic::AtomicPtr

<code>
   
   
  <p>pub fn compare_and_swap(<br>    &self,<br>    current: *mut T,<br>    new: *mut T,<br>    order: Ordering<br>) -> *mut T<br>
  
    

   
   
  </p></code>

(Di sini, jangan risau tentang apa itu pesanan, maksudnya, sila abaikan sahaja. Acquire , Release , Relaxed )

Timbunan tanpa kunci (versi naif)

<code>
   
   
  <p>#![feature(box_raw)]<br><br>use std::ptr::{self, null_mut};<br>use std::sync::atomic::AtomicPtr;<br>use std::sync::atomic::Ordering::{Relaxed, Release, Acquire};<br><br>pub struct Stack<T> {<br>    head: AtomicPtr<Node<T>>,<br>}<br><br>struct Node<T> {<br>    data: T,<br>    next: *mut Node<T>,<br>}<br><br>impl<T> Stack<T> {<br>    pub fn new() -> Stack<T> {<br>        Stack {<br>            head: AtomicPtr::new(null_mut()),<br>        }<br>    }<br><br>    pub fn pop(&self) -> Option<T> {<br>        loop {<br>            // 快照<br>            let head = self.head.load(Acquire);<br><br>            // 如果栈为空<br>            if head == null_mut() {<br>                return None<br>            } else {<br>                let next = unsafe { (*head).next };<br><br>                // 如果现状较快照并没有发生改变<br>                if self.head.compare_and_swap(head, next, Release) == head {<br><br>                    // 读取内容并返回<br>                    return Some(unsafe { ptr::read(&(*head).data) })<br>                }<br>            }<br>        }<br>    }<br><br>    pub fn push(&self, t: T) {<br>        // 创建node并转化为*mut指针<br>        let n = Box::into_raw(Box::new(Node {<br>            data: t,<br>            next: null_mut(),<br>        }));<br>        loop {<br>            // 快照<br>            let head = self.head.load(Relaxed);<br><br>            // 基于快照更新node<br>            unsafe { (*n).next = head; }<br><br>            // 如果在此期间，快照仍然没有过时<br>            if self.head.compare_and_swap(head, n, Release) == head {<br>                break<br>            }<br>        }<br>    }<br>}<br>
  
    

   
   
  </p></code>

Kita dapat melihat sama ada ia pop atau push, ideanya adalah sama: pop pada syot kilat dahulu atau tolak, dan kemudian cuba gantikan data asal dengan CAS. Jika syot kilat dan data adalah sama, ini bermakna tiada penulisan dilakukan dalam tempoh ini, jadi kemas kini akan berjaya. Jika data tidak konsisten, ini bermakna rangkaian lain telah mengubah suainya dalam tempoh ini dan perlu bermula semula. Ini ialah tindanan tanpa kunci. Nampaknya semuanya sudah selesai!

Keluaran Memori

Jika anda menggunakan Java atau bahasa pengaturcaraan lain dengan GC, anda mungkin telah melakukan banyak kerja. Masalahnya sekarang ialah dalam bahasa seperti Rust tanpa GC, tiada siapa yang mengeluarkan

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

dalam pop head , ini adalah kebocoran ingatan! Hei, nampaknya konkurensi tanpa kunci bukanlah mudah.

Atas ialah kandungan terperinci Java lock concurrency, lock-free concurrency dan analisis contoh CAS. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!