Java 잠금 동시성, 잠금 없는 동시성 및 CAS 예제 분석

잠긴 동시성

대부분의 프로그래머에게(물론 저도 기본적으로 그 중 한 명입니다) 동시 프로그래밍은 관련 데이터 구조에 잠금(Mutex)을 추가하는 것과 거의 동일합니다. 예를 들어 동시성을 지원하는 스택이 필요한 경우 가장 쉬운 방법은 단일 스레드 스택에 잠금을 추가하는 것입니다. 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에서는 거의 발생하지 않음) 외에도 교착 상태 문제(식사 철학자 문제)에 직면할 수 있습니다. 그리고 우선 순위가 낮은 일부 작업이 우선 순위가 높은 작업의 리소스를 오랫동안 점유할 수 있다는 점은 말할 것도 없습니다(잠금이 먼저 발생하기 때문). 스레드 수가 상대적으로 많으면 대부분의 시간이 동기화에 소비됩니다. 획득할 잠금) 성능이 매우 저하됩니다. 많은 수의 읽기와 간헐적인 쓰기가 있는 동시 데이터베이스를 고려하십시오. 이를 처리하기 위해 잠금을 사용하는 경우 데이터베이스에 업데이트가 없더라도 두 번의 읽기마다 동기화가 필요하므로 비용이 너무 많이 듭니다!

잠금 없는 동시성

그래서 많은 컴퓨터 과학자와 프로그래머가 잠금 없는 동시성에 관심을 돌렸습니다. 잠금 없는 개체: 공유 개체가 다른 스레드가 무엇을 하든 관계없이 일부 스레드는 제한된 수의 시스템 작업 단계 후에 항상 해당 개체에 대한 작업을 완료함을 보장합니다. Her91 . 즉, 적어도 하나의 스레드는 해당 작업의 결과를 얻습니다. 잠금을 사용하는 동시성은 분명히 이 범주에 속하지 않습니다. 잠금을 획득한 스레드가 지연되면 이 시간 동안 어떤 스레드도 작업을 완료할 수 없습니다. 극단적인 경우 교착 상태가 발생하면 어떤 스레드도 작업을 완료할 수 없습니다.

CAS(비교 및 교환) 원시

그렇다면 잠금 없는 동시성을 어떻게 달성할 수 있는지 궁금할 것입니다. 어떤 예가 있습니까? 그 전에, 잠금 없는 동시성에서 매우 중요하다고 인식되는 원자 기본 요소인 CAS를 살펴보겠습니다. CAS의 프로세스는 저장된 값과 지정된 값을 비교하는 것입니다. 동일한 경우에만 저장된 값이 새로운 지정된 값으로 수정됩니다. CAS는 원자성 작업입니다(x86 비교 및 ​​교환(CMPXCHG)과 같은 프로세서에서 지원됨). 이 원자성은 다른 스레드가 저장된 값을 변경한 경우 쓰기가 실패함을 보장합니다. Rust 표준 라이브러리에서 std::sync::atomic 의 유형은 원자 포인터와 같은 CAS 작업을 제공합니다. 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>

(여기서는 주문이 무엇인지 걱정하지 말고 그냥 무시하세요. 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>

팝이든 푸시든 아이디어가 동일하다는 것을 알 수 있습니다. 먼저 스냅샷을 팝하거나 푸시한 다음 원본 데이터를 CAS로 대체해 보세요. . 스냅샷과 데이터가 동일하다면 이 기간 동안 쓰기가 수행되지 않았으므로 업데이트가 성공한다는 의미입니다. 데이터가 일관되지 않으면 이 기간 동안 다른 스레드가 데이터를 수정했기 때문에 다시 시작해야 함을 의미합니다. 이것은 잠금이 없는 스택입니다. 모든 것이 완료된 것 같습니다!

메모리 해제

GC에서 Java나 다른 프로그래밍 언어를 사용하고 있다면 많은 작업을 수행했을 수도 있습니다. 이제 문제는 GC가 없는 Rust와 같은 언어에서는 아무도 팝

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

을 릴리스하지 않는다는 것입니다. head , 이것은 메모리 누수입니다! 잠금 없는 동시성은 쉽지 않은 것 같습니다.

위 내용은 Java 잠금 동시성, 잠금 없는 동시성 및 CAS 예제 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!