유튜브 링크

이 글은 CppCon 2024에서 카네기 멜런 대학교의 조교수(assistant teaching professor), Daniel Anderson이 발표한 자료를 바탕으로 작성되었다.

배울 내용

• 동시성과 lock-free 프로그래밍에 대한 간단한 복습
• lock-free 설계 패턴의 "기본적인" 내용 검토
• wait-free 알고리즘의 정의와 실제 적용에 대한 이해
• 우아한 wait-free 알고리즘과 wait-free 설계의 예시
• 간단한 벤치마크 결과

해결하고자 하는 문제

sticky counter (0에서 멈추는 카운터)를 구현하고 싶다고 가정하자.

Counter 구조체의 기본적인 인터페이스는 다음과 같다.

// Precondition: The counter is not zero
struct Counter {
    // If the counter is greater than zero, add one and return true
    // otherwise do nothing and return false
    bool increment_if_not_zero();
    
    // Decrement the counter. If the counter now equals zero,
    // return true. Otherwise return false.
    bool decrement();
    
    uint64_t read(); // Return the current value of the counter
};

Counter 구조체는 다음과 같은 세 가지 주요 기능을 제공한다.

• increment_if_not_zero() : 카운터 증가를 시도
  • 카운터가 0보다 크면 1을 더하고 true 반환
  • 카운터가 0이면 아무것도 하지 않고 false 반환
• decrement() : 카운터를 감소
  • 카운터를 감소시킨 후 0이 되면 true 반환
  • 카운터를 감소시킨 후 0이 아니라면 false 반환
• read() : 현재 카운터 값을 반환

<aside> 💡

이런 방식의 카운터는 매우 실용적이다. 동시성 자료구조나, 멀티스레딩 환경에서의 메모리 관리에 매우 적합하다.

예로 들어 std::weak_ptr<T>::lock에 이런 방식의 카운터가 필요하다.

std::weak_ptr<T>::lock 의 주요 기능은 다음과 같다.

• weak_ptr가 가리키는 객체가 아직 유효한지 확인
• 유효하다면 해당 객체에 대한 shared_ptr를 반환
• 객체가 이미 삭제되었다면 빈 shared_ptr (nullptr을 가리킴)을 반환

따라서 weak_ptr은 다음과 같이 동작해야 한다.

• 객체의 수명을 추적하되 reference count는 증가되지 않음
• lock() 호출 시 객체가 아직 존재하는지 확인해야 함
• 확인하는 동안 다른 스레드에서 객체를 삭제할 수 있음

여기서 Counter 의 역할은 다음과 같다.

• 객체가 아직 살아있는지(reference count > 0) 확인
• 살아있다면 reference count를 증가시켜 객체 수명 연장
• 이 두 작업이 atomic하게 이뤄져야 함 </aside>

이제 인터페이스를 구현해보자.