Java lock concurrency, lock-free concurrency and CAS example analysis

Locked concurrency

For most programmers (of course I am basically one of them), concurrent programming is almost equivalent to adding a lock to the relevant data structure. (Mutex). For example, if we need a stack that supports concurrency, the easiest way is to add a lock to a single-threaded stack std::sync::Mutex . (Arc is added to allow multiple threads to have ownership of the stack)

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

The code is very convenient to write, because it is almost the same as the single-threaded version, which is obviously a benefit. You only need to write the single-threaded version, add a lock to the data structure, and then acquire and release (basically automatic in Rust) the lock when necessary.

So what’s the problem? First of all, aside from the fact that you may forget to acquire and release the lock (which is almost impossible to happen in Rust thanks to Rust), you may face the problem of deadlock (the Dining Philosopher Problem). And not to mention that some low-priority tasks may seize the resources of high-priority tasks for a long time (because locks come first). When the number of threads is relatively large, most of the time is spent on synchronization ( Waiting for the lock to be acquired), performance will become very poor. Consider a concurrent database with a large number of reads and occasional writes. If locks are used to handle it, even if the database does not have any updates, synchronization will be required between every two reads, which is too costly!

Lock-free concurrency

As a result, a large number of computer scientists and programmers turned their attention to lock-free concurrency. Lock-free object: If a shared object guarantees that no matter what other threads do, some thread will always complete an operation on it after a limited number of system operation steps. Her91 . In other words, at least one thread will achieve results from its operation. Concurrency using locks obviously does not fall into this category: if the thread that acquired the lock is delayed, no thread can complete any operation during this time. In extreme cases, if a deadlock occurs, no thread can complete any operation.

CAS (compare and swap) primitive

Then you may be curious, how to achieve lock-free concurrency? Are there any examples? Before that, let's take a look at an atomic primitive that is recognized to be very important in lock-free concurrency: CAS. The process of CAS is to compare a stored value with a specified value. Only when they are the same, the stored value will be modified to the new specified value. CAS is an atomic operation (supported by the processor, such as x86 compare and exchange (CMPXCHG)). This atomicity guarantees that if other threads have changed the stored value, the write will fail. in the Rust standard library std::sync::atomic The types in provide CAS operations, such as atomic pointers 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>

(Here, don’t worry about what ordering is, that is to say, please just ignore it. Acquire , Release , Relaxed )

Lock-free stack (naive version)

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

We can see that the idea is the same whether it is pop or push: pop on the snapshot first or push, and then try to replace the original data with CAS. If the snapshot and data are equal, it means that no writes were performed during this period, so the update will succeed. If the data is inconsistent, it means that other threads have modified it during this period and need to start again. This is a lock-free stack. It seems everything is done!

Memory Release

If you are using Java or other programming languages ​​with GC, you may have done a lot of work. The problem now is that in a language like Rust without GC, no one releases

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

in pop head , this is a memory leak! Hey, it seems that lock-free concurrency is not easy.

The above is the detailed content of Java lock concurrency, lock-free concurrency and CAS example analysis. For more information, please follow other related articles on the PHP Chinese website!