길리랩blog

CAS와 배리어로 설계하는 락 프리 동시성

락 프리 자료구조, CAS 루프, 스레드·메모리 배리어의 진전성 보장과 메모리 회수, 성능 관측 설계 방법을 정리한다.

2026-08-14 · 최초 발행 2024-04-29

락 없이도 시스템이 전진하려면

멀티코어 환경에서 낮은 지연 응답을 요구하는 경로는 전통적인 락 기반 동기화의 경합과 컨텍스트 스위치 비용에 민감하다. Lock-Free Data Structures, Compare-and-Swap(CAS), Barrier는 이 구간의 공유 상태와 실행 순서를 다루는 대표적인 동시성 도구다.

락 프리 자료구조는 상호배제 락 대신 원자적 연산으로 일관성을 유지한다. 일부 스레드가 멈추더라도 시스템 전체는 전진(progress)할 수 있어야 한다. CAS는 메모리 위치의 값이 기대값과 같을 때에만 새 값으로 원자적으로 바꾸는 하드웨어 프리미티브이며, 실패한 경우에는 재시도 루프가 필요하다.

배리어는 두 가지 맥락에서 쓰인다. 스레드 배리어는 참여 스레드가 모두 도착할 때까지 진행을 멈추는 동기화 지점으로, 페이즈 전환이나 배치 처리에 적합하다. 메모리 배리어(펜스)는 컴파일러와 CPU의 재배치를 제한해 가시성과 순서를 보장하며 acquire/release, seq_cst 같은 메모리 오더링 모델과 결합한다.

진전성 보장의 강도는 obstruction-free, lock-free, wait-free 순서로 높아진다. wait-free는 각 스레드의 완료까지 보장하지만, 구현 복잡도와 비용도 함께 커진다.

원자 연산만으로 끝나지 않는 설계

CAS, FAA(fetch-add), exchange, memory_order를 지정한 load/store가 핵심 원자 연산이다. acquire/release는 필요한 수준의 순서를 구성하는 데 쓰이며, seq_cst는 이해하기 쉽지만 비용이 증가한다. 성능에 민감한 경로에서는 필요한 최소 수준의 오더링을 선택해야 한다.

CAS는 언제든 실패할 수 있다. backoff, 티켓화, flat-combining은 기아와 캐시 스래싱을 완화하는 방법이다. compare_exchange_weak를 사용할 때는 스퓨리어스 실패도 가능하므로 재시도 로직이 반드시 필요하다.

포인터가 A→B→A로 변하는 사이 CAS가 잘못 성공할 수 있는 ABA 문제도 있다. 태그드 포인터, 카운터, hazard pointers, epoch-based reclamation(EBR/RCU)은 이를 완화하는 수단이다. 락 프리 자료구조를 실제로 적용할 때는 안전한 메모리 회수 방식을 분리할 수 없다.

스레드 배리어에서는 참여자 수 N이 맞아야 하며, 불일치는 교착으로 이어질 수 있다. 타임아웃과 취소 처리도 별도로 설계해야 한다. 반대로 메모리 배리어는 장치 I/O나 lock-free 공용체에서 가시성을 보장하지만, 펜스를 과도하게 사용하면 성능이 떨어진다.

선형화(Linearizability) 포인트를 명확히 두면 정형 검증이 쉬워진다. TSAN/LSAN과 릴리즈/아콰이어 검증 툴을 활용하고, P99/P999 레이턴시, CAS 실패율, LLC miss, 원자적 스톨 비율을 관측 대상으로 둔다.

락 기반 접근과 진전성 보장의 차이

구분 성능 확장성 일관성 안정성 운영 편의
락 기반 경합 시 급격한 저하, 컨텍스트 스위치 비용 큼 코어 증가 시 경합 폭증 구현 직관성 높음 우선순위 역전·교착 가능성 디버깅 용이, 튜닝 단순
락 프리 낮은 지연, 고경합에서도 평균 성능 우수 코어 확장성 우수, 캐시 친화 설계 필요 선형화 포인트 명확 시 높음 ABA·메모리 회수 실패 위험 구현·검증 난이도 높음
웨이트 프리 최악 지연 보장 우수 구현 난이도와 비용으로 제한적 일관성 보장 강함 알고리즘 복잡성으로 검증 부담 특수 도메인에 적합

CAS 재시도와 페이즈 동기화의 연결

⤢✕스레드 배리어 단계입력성공실패아니오예여러 스레드공유 상태(원자 변수)현재 값 로드(acquire)새 값 계산(순수 함수 권장)CAS시도(compare_exchange)상태 갱신 완료(release)백오프/재시도참여자 수 N 설정각 스레드 도달모두 도달?다음 페이즈 진행

적용되는 경로

고성능 큐와 스택에서는 MPSC/MPMC 링버퍼나 Michael-Scott 큐를 사용해 프로듀서-컨슈머 파이프라인의 P99 지연을 낮출 수 있다. 로깅과 텔레메트리에서는 경량 lock-free 링버퍼에 로그를 enqueue하고 백그라운드에서 플러시해 시스템 호출 병목을 줄인다.

공유 리소스 관리에는 FAA 기반의 원자적 레퍼런스 카운팅을 적용할 수 있으며, 메모리 오더링은 acquire/release로 최적화한다. 맵/리듀스 단계 전환이나 샤딩된 해시맵 리빌드 같은 일괄 작업에는 스레드 배리어가 맞는다. 커널과 드라이버 수준에서는 메모리 배리어가 MMIO 레지스터 접근 순서를 보장한다.

C++에서 확인하는 CAS 스택과 배리어

예시는 C++20 이상과 g++/clang++ -O2 -std=c++20을 전제로 한다. 하드웨어는 TSO(x86) 또는 ARMv8을 대상으로 하며, 메모리 오더를 명시해 아키텍처 독립성을 확보한다. 첫 예시는 노드 해제를 단순화했으므로 실서비스에서는 hazard pointers 또는 epoch 기반 회수가 필요하다.

CAS로 갱신하는 다중 스레드 스택

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>

struct Node {
  int val;
  Node* next;
  Node(int v, Node* n=nullptr) : val(v), next(n) {}
};

class LockFreeStack {
  std::atomic<Node*> head{nullptr};
public:
  void push(int v) {
    Node* n = new Node(v);
    Node* old;
    do {
      old = head.load(std::memory_order_acquire);
      n->next = old;
      // weak는 스퓨리어스 실패 가능, 루프로 재시도
    } while (!head.compare_exchange_weak(
        old, n, std::memory_order_release, std::memory_order_acquire));
  }

  bool pop(int& out) {
    Node* old;
    Node* next;
    do {
      old = head.load(std::memory_order_acquire);
      if (!old) return false;
      next = old->next;
    } while (!head.compare_exchange_weak(
        old, next, std::memory_order_acq_rel, std::memory_order_acquire));
    out = old->val;
    // 실전: hazard pointer/epoch으로 안전한 해제 필요
    delete old;
    return true;
  }
};

int main() {
  LockFreeStack s;
  constexpr int N = 4, K = 100000;
  std::vector<std::thread> ths;
  for (int i=0;i<N;i++) ths.emplace_back([&]{
    for (int k=0;k<K;k++) s.push(k);
  });
  for (auto& t:ths) t.join();
  int cnt=0,v;
  while (s.pop(v)) cnt++;
  std::cout << "popped=" << cnt << "\n";
}

이 코드에서 선형화 포인트는 head CAS가 성공하는 시점이다. push는 release, pop은 acq_rel로 최소한의 보장을 구성한다. ABA와 노드 해제의 안전성은 남는 위험이므로 태깅, HP, EBR 도입을 검토해야 한다.

모든 참여자를 맞추는 배리어

#include <barrier>
#include <thread>
#include <vector>
#include <iostream>

int main() {
  constexpr int N = 6;
  std::barrier sync_point(N, [](){ /* 페이즈 종료 훅 */ });
  std::vector<std::thread> ths;
  for (int i=0;i<N;i++) {
    ths.emplace_back([i,&sync_point]{
      // Phase 1
      // ... 작업 ...
      sync_point.arrive_and_wait(); // 모든 스레드 대기
      // Phase 2
      // ... 후속 작업 ...
    });
  }
  for (auto& t:ths) t.join();
  std::cout << "done\n";
}

참여자 수 N이 맞지 않으면 데드락이 발생할 수 있다. 이 배리어는 재사용 가능한 사이클릭 배리어이며, 페이즈별 훅에 체크포인트나 모니터링을 결합할 수 있다. 타임아웃과 취소 흐름은 별도로 설계한다.

펜스로 공개 경계를 만드는 패턴

#include <atomic>
#include <cstdint>

// 생산자-소비자 플래그 공개 패턴
std::atomic<uint64_t> data{0};
std::atomic<bool> ready{false};

void producer(uint64_t v){
  data.store(v, std::memory_order_relaxed);
  std::atomic_thread_fence(std::memory_order_release); // data 공개
  ready.store(true, std::memory_order_relaxed);
}
bool consumer(uint64_t& out){
  if (ready.load(std::memory_order_relaxed)) {
    std::atomic_thread_fence(std::memory_order_acquire); // data 관측
    out = data.load(std::memory_order_relaxed);
    return true;
  }
  return false;
}

펜스는 가시성 경계를 형성한다. 단일 원자 변수에 acquire/release를 부여하는 방법도 가능하며, 성능과 단순성의 트레이드오프를 함께 고려한다.

설계와 운영에서 확인할 지점

공유 상태의 레이아웃을 먼저 정하고 false sharing을 피할 수 있도록 캐시라인 패딩을 고려한다. 스레드 수와 작업 단위를 정한 뒤 CAS 루프를 구현하며, 실패 시의 backoff와 재시도 횟수 상한을 둔다. 선형화 포인트는 문서로 남겨야 한다.

메모리 오더링은 acquire/release를 우선하고, seq_cst는 검증 단계에서만 사용을 검토한다. 메모리 회수 방식은 HP, EBR, URCU 가운데 워크로드 특성에 맞춰 선택한다.

운영 지표는 스루풋, P99 지연, CAS 실패율, LLC miss를 포함한다. 안정성 지표로는 데드락 0, 기아율 0을 둔다. 배리어의 참여 누락이나 초과를 탐지하고, 타임아웃 시 롤백·중단 정책을 정의한다. CAS 반복 실패가 이어질 경우 랜덤 백오프나 워크 스틸링으로 경합을 완화한다.

고경합 구간에서는 스루풋 25배 향상과 P99 지연 3070% 감소를 기대 효과로 제시할 수 있다. 컨텍스트 스위치와 락 경합 이벤트는 70%+ 감소하며 CPU 유휴율도 개선된다. 교착과 우선순위 역전이 제거되면 안정성이 높아지고, 페이즈 동기화는 예측 가능한 스케줄링에 도움이 된다. 핫패스의 코드 경로를 단순화하고 캐시 친화적 접근 패턴을 확보하는 효과도 있다.

데이터 분할과 로컬라이티를 우선하고, 샤딩과 NUMA 인지 설계로 CAS 범위를 좁힌다. 선형화 포인트와 페일 패스를 계측하며, 마이크로벤치로 퍼포먼스 회귀를 확인한다. 그 대가로 구현과 디버깅은 어려워지고 ABA나 회수 실패에서 희귀 버그가 발생할 수 있다. wait-free는 최악 지연을 보장하지만 평균 성능과 코드 복잡도 비용을 수반한다.

동시성락 프리CAS메모리 배리어멀티스레딩