C++ Lock-Free 자료구조: CAS로 스택·큐 만들기, 메모리 순서, ABA 문제와 Hazard Pointer
들어가며: mutex가 병목입니다
고성능 서버에서 여러 워커 스레드가 작업 큐에서 작업을 가져와 처리하는 구조였습니다. std::mutex로 큐를 보호했더니, 스레드 수를 늘려도 처리량이 거의 늘지 않고 락 대기 시간이 전체 지연의 상당 부분을 차지했습니다. 이럴 때 검토하는 선택지가 lock-free 큐입니다. 다만 이 글 뒤쪽에서 보듯 lock-free가 항상 이득인 것은 아니고, 이득이 나는지는 실제 워크로드로 측정해 봐야 압니다.
락 기반 코드에서는 큐에 push/pop할 때마다 mutex를 잡아야 합니다. 스레드가 많을수록 락을 기다리는 시간이 길어지고, 한 스레드가 락을 잡는 동안 나머지는 블로킹됩니다. lock-free 방식에서는 compare-and-swap(CAS) 같은 원자 연산으로 락 없이 동기화하므로, 스레드가 서로를 기다리지 않고 진행(progress) 할 수 있습니다.
느린 코드 (mutex):
// mutex로 보호한 큐 - 락 경합 발생
std::queue<Task> queue;
std::mutex mtx;
void push(const Task& t) {
std::lock_guard<std::mutex> lock(mtx);
queue.push(t);
}
bool pop(Task& t) {
std::lock_guard<std::mutex> lock(mtx);
if (queue.empty()) return false;
t = queue.front();
queue.pop();
return true;
}빠른 코드 (lock-free):
// lock-free 큐 - CAS로 락 없이 동기화
template <typename T>
class LockFreeQueue {
struct Node {
T data;
std::atomic<Node*> next;
};
std::atomic<Node*> head;
std::atomic<Node*> tail;
// push/pop에서 CAS 사용 (본문 예제 참조)
};원인: mutex는 한 번에 한 스레드만 큐에 접근 → lock-free는 여러 스레드가 동시에 CAS로 시도 → 경합 시 재시도만 하고 블로킹 없음 이 글을 읽으면:
- lock-free의 개념과 CAS(compare-and-swap) 동작을 이해할 수 있습니다.
- lock-free 스택·큐를 완전한 코드로 구현할 수 있습니다.
- ABA 문제, 메모리 순서, 메모리 재사용 등 흔한 실수를 피할 수 있습니다.
- 성능 벤치마크로 mutex 대비 이득을 확인할 수 있습니다.
- 프로덕션에서 hazard pointer, RCU 등 패턴을 적용할 수 있습니다.
개념을 잡는 비유
Mutex는 은행 창구에 한 줄로 서서 차례를 기다리는 방식에 가깝습니다. Lock-free의 CAS는 번호표 기계가 “지금 표시된 숫자가 내가 본 값과 같을 때만” 새 번호로 바꿔 준다처럼, 한 번에 한 스레드만 성공하는 규칙으로 줄을 서지 않고도 진행합니다. 재시도가 잦으면 CPU는 쓰지만, 블로킹으로 인한 지연 변동은 줄일 수 있습니다.
로그 수집기, 오더북, 작업 스케줄러: lock-free가 거론되는 곳
시나리오 1: 고빈도 로그 수집기
수십 개 스레드가 동시에 로그를 버퍼에 씁니다. mutex로 보호하면 로그 쓰기마다 락을 잡아, 고빈도 로깅 시 지연이 커집니다. lock-free 링 버퍼나 MPSC(다중 생산자 단일 소비자) 큐를 쓰면 락 없이 로그를 쌓으며, 별도 스레드가 배치로 flush할 수 있습니다.
시나리오 2: 실시간 트레이딩 오더북
주문 추가/취소가 밀리초 단위로 들어옵니다. 오더북을 mutex로 보호하면 락 대기로 인해 주문 처리 지연이 발생하며, 시장 가격 변동 시 불리해질 수 있습니다. lock-free 자료구조로 오더북을 구현하면 지연 시간 변동(latency jitter)이 줄어듭니다.
시나리오 3: 게임 엔진 작업 스케줄러
매 프레임 수백 개 작업을 여러 스레드에 분배합니다. 작업 큐가 mutex 기반이면 프레임 시작 시 모든 워커가 큐 락을 기다리며, 프레임 드랍이 발생할 수 있습니다. lock-free 작업 큐(work stealing 포함)를 쓰면 워커가 블로킹 없이 작업을 가져와 처리할 수 있습니다.
시나리오 4: 네트워크 패킷 버퍼
수신 스레드가 패킷을 버퍼에 넣으며, 처리 스레드가 꺼냅니다. 단일 mutex로 보호하면 패킷 수신률이 높을 때 처리 스레드가 락을 기다리는 동안 버퍼가 넘칠 수 있습니다. lock-free SPSC(single producer single consumer) 큐를 쓰면 수신과 처리가 거의 독립적으로 동작합니다.
시나리오 5: 통계 카운터 집계
여러 스레드가 요청 수, 바이트 수 등을 증가시킵니다. mutex로 카운터를 보호하면 고빈도 업데이트 시 경합이 심합니다. std::atomic::fetch_add로 lock-free 카운터를 쓰면 락 없이 안전하게 집계할 수 있습니다.
시나리오 6: 캐시 무효화/업데이트
여러 스레드가 공유 캐시 포인터를 읽으며, 업데이트 시 새 포인터로 교체합니다. mutex로 전체 캐시를 잡으면 읽기 경로까지 블로킹됩니다. std::atomic 포인터와 CAS로 “읽기 lock-free, 쓰기 CAS” 패턴을 적용하면 읽기가 거의 블로킹 없이 동작합니다.
lock-free란 무엇이고 wait-free와 어떻게 다른가
Lock-Free란?
Lock-free는 락(뮤텍스, 스핀락 등)을 사용하지 않고 여러 스레드가 동시에 자료구조에 접근해도, 최소한 한 스레드는 항상 진행할 수 있도록 설계된 알고리즘입니다. 데드락이 없으며, 락 대기로 인한 우선순위 역전이 없습니다.
flowchart TB
subgraph lock_based[락 기반]
L1[스레드 A: 락 획득] --> L2[스레드 B: 대기]
L2 --> L3[스레드 C: 대기]
L3 --> L4[A 완료 후 B, C 순차 진행]
end
subgraph lock_free[Lock-Free]
F1[스레드 A: CAS 시도] --> F2[성공 → 진행]
F3[스레드 B: CAS 시도] --> F4[실패 → 재시도]
F4 --> F5[다음 CAS로 진행]
end
비유: 락 기반은 “화장실 열쇠를 가진 사람만 들어갈 수 있으며, 나머지는 기다린다”. lock-free는 “여러 사람이 동시에 문을 열려고 시도하며, 먼저 연 사람만 들어가고 나머지는 다시 시도한다”.
Lock-Free vs Wait-Free
| 구분 | Lock-Free | Wait-Free |
|---|---|---|
| 정의 | 최소 한 스레드는 진행 | 모든 스레드가 유한 단계 내 완료 |
| 재시도 | CAS 실패 시 재시도 가능 | 재시도 없이 완료 보장 |
| 구현 난이도 | 상대적으로 낮음 | 매우 높음 |
| 실무 | 큐, 스택, 카운터 등 | 제한적 (atomic fetch_add 등) |
대부분의 lock-free 자료구조는 lock-free이지 wait-free는 아닙니다. CAS 실패 시 루프로 재시도하는 패턴이 일반적입니다.
“락 프리”는 막연히 “뮤텍스를 안 쓴다”는 뜻이 아니라 진행 보장에 대한 정의라는 점을 기억해 두면 판단이 쉬워집니다. 어떤 스레드가 임의의 지점에서 멈추더라도(선점, 페이지 폴트) 시스템 전체로는 누군가 반드시 진척한다면 lock-free입니다. 뮤텍스는 잠금을 쥔 스레드가 멈추면 전원이 멈추므로 어느 쪽도 아닙니다. CAS 루프는 한 스레드가 계속 실패할 수는 있어도, 실패는 곧 다른 스레드가 성공했다는 뜻이므로 lock-free입니다. 또 std::atomic<T>라고 해서 항상 락 프리는 아닙니다. 큰 구조체의 atomic은 내부적으로 락을 쓸 수 있으므로 static_assert(std::atomic<T>::is_always_lock_free)로 확인해 두는 편이 안전합니다.
성능 면에서도 “뮤텍스는 커널을 거친다”는 통념은 절반만 맞습니다. 현대 뮤텍스는 경합이 없을 때 원자 명령 한두 개로 잠그고 풀며(리눅스 futex의 빠른 경로), 커널에 들어가는 것은 실제로 기다려야 할 때뿐입니다. 그래서 경합이 없으면 둘의 차이는 생각보다 작고, 차이가 크게 벌어지는 것은 잠금을 쥔 스레드가 선점되어 다른 스레드들이 줄줄이 잠드는 경우입니다.
원자 연산과 CAS
std::atomic 기본 사용
#include <atomic>
#include <iostream>
#include <thread>
// 복사해 붙여넣은 뒤: g++ -std=c++17 -pthread -o atomic_basic atomic_basic.cpp && ./atomic_basic
int main() {
std::atomic<int> counter{0};
std::thread t1([&]() {
for (int i = 0; i < 100000; ++i)
counter.fetch_add(1, std::memory_order_relaxed);
});
std::thread t2([&]() {
for (int i = 0; i < 100000; ++i)
counter.fetch_add(1, std::memory_order_relaxed);
});
t1.join();
t2.join();
std::cout << "counter = " << counter.load() << "\n"; // 200000
return 0;
}설명: fetch_add는 원자적으로 값을 증가시키므로 data race가 발생하지 않습니다. memory_order_relaxed는 순서 보장이 필요 없을 때(카운터 등) 사용합니다.
Compare-And-Swap (CAS)
CAS는 “이 메모리 위치의 값이 예상 값이면 새 값으로 바꾸고, 아니면 바꾸지 않는다”는 원자적 연산입니다. C++에서는 std::atomic::compare_exchange_strong / compare_exchange_weak가 CAS에 해당합니다.
#include <atomic>
std::atomic<int> value{0};
// "0이면 1로" — 한 스레드만 성공
bool try_claim() {
int expected = 0;
return value.compare_exchange_strong(expected, 1);
}
// lock-free 증가 (실제로는 fetch_add가 더 적합)
void cas_increment() {
int old_val = value.load(std::memory_order_relaxed);
while (!value.compare_exchange_weak(old_val, old_val + 1,
std::memory_order_release,
std::memory_order_relaxed)) {
// 실패 시 old_val이 현재 값으로 자동 업데이트됨
}
}compare_exchange_weak vs strong:
- weak: ARM, PowerPC 등에서 spurious failure 가능. 루프 안에서 사용 시 더 효율적.
- strong: spurious failure 없음. 한 번만 시도할 때 적합.
weak의 가짜 실패는 ARM처럼 LL/SC(load-linked/store-conditional) 명령으로 CAS를 구현하는 CPU에서 생깁니다. 그 대신 코드가 더 가볍기 때문에, 어차피 재시도하는 루프 안에서는 weak가, 루프 없이 한 번의 결과로 분기해야 하는 곳에서는 strong이 맞습니다.
CAS 루프에서 가장 흔한 실수는 실패 뒤에 desired를 다시 계산하지 않는 것입니다. compare_exchange_*는 실패하면 expected를 현재 값으로 덮어써 주므로 루프 안에서 load()를 다시 부를 필요는 없지만, desired는 갱신된 expected를 기준으로 새로 계산해야 합니다. 예전 값 기준으로 계산해 둔 desired를 그대로 다시 넣으면 CAS는 결국 성공하지만, 그 사이 다른 스레드가 한 갱신을 덮어쓰는 “잃어버린 업데이트”가 생깁니다.
int expected = value.load();
int desired;
do {
desired = compute(expected); // 매 시도마다 최신 expected로 다시 계산
} while (!value.compare_exchange_weak(expected, desired));CAS 동작 흐름
flowchart TD
A[CAS 시도] --> B{현재값 == expected?}
B -->|Yes| C[desired로 교체]
C --> D[true 반환]
B -->|No| E[expected를 현재값으로 갱신]
E --> F[false 반환]
F --> G[루프에서 재시도]
주요 원자 연산 요약
#include <atomic>
std::atomic<int> a{0};
// 읽기/쓰기
a.load(std::memory_order_acquire);
a.store(42, std::memory_order_release);
// 산술
a.fetch_add(1); // a++
a.fetch_sub(1); // a--
a.fetch_and(0xFF);
a.fetch_or(1);
// 교환
a.exchange(100); // 이전 값 반환
// 조건부 교환 (CAS)
int expected = 0;
a.compare_exchange_strong(expected, 1); // expected가 참조로 갱신됨
a.compare_exchange_weak(expected, 1);스핀락은 lock-free가 아닙니다
std::atomic_flag만으로 간단한 락을 만들 수 있습니다.
class SpinLock {
std::atomic_flag flag = ATOMIC_FLAG_INIT;
public:
void lock() {
while (flag.test_and_set(std::memory_order_acquire)) {
std::this_thread::yield();
}
}
void unlock() {
flag.clear(std::memory_order_release);
}
};원자 연산으로 만들었지만 이것은 “락 프리 자료구조”가 아니라 락을 직접 구현한 것입니다. 여전히 한 번에 한 스레드만 임계 구역에 들어가고, 잠금을 쥔 스레드가 멈추면 나머지도 전부 멈춥니다. 커널 뮤텍스처럼 스레드를 재우는 대신 계속 확인(busy-wait)할 뿐입니다. 임계 구역이 아주 짧고 컨텍스트 스위칭 비용이 그보다 크다고 확신할 때만 뮤텍스 대신 쓸 가치가 있습니다.
사용자 공간 스핀락이 특히 위험한 것은 잠금을 쥔 스레드가 선점될 때입니다. 운영체제는 스핀 중인 스레드가 무엇을 기다리는지 모르므로, 잠금 보유자가 CPU를 다시 받을 때까지 나머지 스레드가 타임 슬라이스를 통째로 태웁니다. yield()가 이 피해를 줄여 주긴 하지만 근본 해결은 아닙니다. 또 test_and_set은 매번 캐시 라인을 쓰기 모드로 가져오므로 여러 코어가 동시에 돌면 캐시 라인이 코어 사이를 계속 오갑니다. 실무 구현은 먼저 읽기만으로 풀릴 때까지 기다린 뒤(C++20의 flag.test()) test_and_set을 시도하는 test-and-test-and-set 방식과, x86의 pause 명령을 넣은 백오프를 씁니다. C++20부터는 atomic_flag::wait()/notify_one()으로 스핀 대신 잠들 수도 있고, ATOMIC_FLAG_INIT 없이도 기본 생성이 clear 상태로 초기화됩니다.
Treiber 스택 구현
단일 링크드 리스트 스택
스택은 head 포인터만 CAS로 업데이트하면 됩니다. push는 새 노드를 head에 연결하며, pop은 head를 다음 노드로 바꿉니다.
#include <atomic>
#include <memory>
template <typename T>
class LockFreeStack {
public:
struct Node {
T data;
Node* next;
explicit Node(const T& d) : data(d), next(nullptr) {}
};
LockFreeStack() : head_(nullptr) {}
void push(const T& value) {
Node* new_node = new Node(value);
new_node->next = head_.load(std::memory_order_relaxed);
while (!head_.compare_exchange_weak(new_node->next, new_node,
std::memory_order_release,
std::memory_order_relaxed)) {
// CAS 실패 시 new_node->next가 현재 head로 갱신됨
}
}
bool pop(T& value) {
Node* old_head = head_.load(std::memory_order_acquire);
while (old_head &&
!head_.compare_exchange_weak(old_head, old_head->next,
std::memory_order_acquire,
std::memory_order_relaxed)) {
// CAS 실패 시 old_head가 현재 head로 갱신됨
}
if (!old_head) return false;
value = old_head->data;
delete old_head; // 프로덕션에서는 hazard pointer 등 필요 (아래 ABA 참조)
return true;
}
bool empty() const {
return head_.load(std::memory_order_acquire) == nullptr;
}
private:
std::atomic<Node*> head_;
};코드 설명:
- push: 새 노드의 next를 현재 head로 두며, head가 next와 같을 때만 head를 새 노드로 CAS. 다른 스레드가 push하면 CAS가 실패하며,
new_node->next가 갱신된 head가 되므로 재시도. - pop: head를 읽으며, head가 old_head일 때만 head를 old_head->next로 CAS.
- 주의: 위 구현은 ABA 문제와 메모리 재사용 문제가 있음. 프로덕션에서는 hazard pointer 등 필요 (아래 참조).
이 구조는 “Treiber 스택”이라는 이름으로 알려진 고전적인 구현입니다. 위험은 delete 한 줄에만 있지 않고, pop 루프에서 old_head->next를 읽는 순간 자체에 있습니다. 스레드 A가 old_head를 읽은 직후 선점되고, 그사이 스레드 B가 같은 노드를 pop해서 delete하면, A가 깨어나 old_head->next를 읽는 것은 해제된 메모리 읽기입니다. 게다가 그 주소에 새 노드가 할당되어 스택에 다시 push되면, A의 CAS는 “head가 여전히 old_head”라고 판단해 성공하면서 엉뚱한 next를 head로 설치합니다. 아래에서 다룰 ABA 문제가 바로 이 시나리오입니다. 단위 테스트로 수없이 돌려도 재현되지 않다가 코어 수가 많은 서버에서만 가끔 크래시가 나는 전형적인 버그이므로, ThreadSanitizer와 AddressSanitizer를 켠 스트레스 테스트가 필수입니다.
메모리 순서 설명
// push: release — 이 CAS 이전의 쓰기가 다른 스레드에 보임
head_.compare_exchange_weak(..., std::memory_order_release, ...);
// pop: acquire — 이 CAS 이전에 다른 스레드가 쓴 값을 읽을 수 있음
head_.compare_exchange_weak(..., std::memory_order_acquire, ...);Michael-Scott 큐, MPSC, SPSC 큐
Michael-Scott Lock-Free 큐 (MPMC)
두 개의 atomic 포인터(head, tail)를 사용하는 고전적인 lock-free 큐입니다. 더미 노드를 두어 빈 큐와 비어 있지 않은 큐를 일관되게 처리합니다.
#include <atomic>
#include <memory>
template <typename T>
class LockFreeQueue {
public:
struct Node {
std::atomic<Node*> next;
T data;
Node() : next(nullptr), data() {}
explicit Node(const T& d) : next(nullptr), data(d) {}
};
LockFreeQueue() {
Node* dummy = new Node();
head_.store(dummy);
tail_.store(dummy);
}
~LockFreeQueue() {
while (Node* n = head_.load()) {
head_.store(n->next.load());
delete n;
}
}
void push(const T& value) {
Node* new_node = new Node(value);
Node* old_tail = nullptr;
Node* next = nullptr;
while (true) {
old_tail = tail_.load(std::memory_order_acquire);
next = old_tail->next.load(std::memory_order_acquire);
if (old_tail == tail_.load(std::memory_order_acquire)) {
if (next == nullptr) {
if (old_tail->next.compare_exchange_weak(next, new_node,
std::memory_order_release,
std::memory_order_relaxed)) {
tail_.compare_exchange_weak(old_tail, new_node,
std::memory_order_release,
std::memory_order_relaxed);
return;
}
} else {
tail_.compare_exchange_weak(old_tail, next,
std::memory_order_release,
std::memory_order_relaxed);
}
}
}
}
bool pop(T& value) {
Node* old_head = nullptr;
Node* old_tail = nullptr;
Node* next = nullptr;
while (true) {
old_head = head_.load(std::memory_order_acquire);
old_tail = tail_.load(std::memory_order_acquire);
next = old_head->next.load(std::memory_order_acquire);
if (old_head == head_.load(std::memory_order_acquire)) {
if (old_head == old_tail) {
if (next == nullptr) return false;
tail_.compare_exchange_weak(old_tail, next,
std::memory_order_release,
std::memory_order_relaxed);
} else {
value = next->data;
if (head_.compare_exchange_weak(old_head, next,
std::memory_order_release,
std::memory_order_relaxed)) {
delete old_head;
return true;
}
}
}
}
}
bool empty() const {
return head_.load(std::memory_order_acquire)->next.load(
std::memory_order_acquire) == nullptr;
}
private:
std::atomic<Node*> head_;
std::atomic<Node*> tail_;
};코드 설명:
- 더미 노드: head와 tail이 항상 유효한 노드를 가리키도록 합니다.
- push: tail->next가 nullptr이면 새 노드를 연결하며, tail을 새 노드로 옮깁니다. 다른 스레드가 먼저 push했으면 tail을 다음 노드로 진행시킵니다.
- pop: head->next가 데이터 노드이면 그 값을 반환하고 head를 다음으로 옮깁니다. head == tail이면 큐가 비었거나 tail이 아직 따라오지 않은 상태입니다.
- 메모리 회수: pop의
delete old_head에는 스택과 같은 문제가 있습니다. 다른 소비자가 방금 읽은old_head의next를 역참조하는 중일 수 있으므로, 실제 구현은 아래 ABA 절의 hazard pointer나 epoch 기반 회수가 필요합니다.
흔히 보는 exchange 기반 큐는 MPSC입니다
인터넷에서 “lock-free 큐”로 자주 소개되는 다음 형태는 Michael-Scott 큐가 아닙니다.
void enqueue(T value) {
Node* newNode = new Node{value};
Node* oldTail = tail.exchange(newNode);
oldTail->next.store(newNode);
}
bool dequeue(T& result) {
Node* oldHead = head.load();
Node* next = oldHead->next.load();
if (next == nullptr) return false;
result = next->data;
head.store(next);
delete oldHead;
return true;
}tail.exchange로 생산자 쪽만 원자화한 다중 생산자·단일 소비자(MPSC) 구조입니다(Dmitry Vyukov의 MPSC 큐와 같은 형태). 생산자 여러 명이 동시에 enqueue해도 exchange가 각자에게 서로 다른 oldTail을 돌려주므로 안전하지만, dequeue는 head를 CAS 없이 store하므로 소비자가 둘 이상이면 두 스레드가 같은 노드를 꺼내고 같은 oldHead를 두 번 delete합니다.
또 tail.exchange(newNode)와 oldTail->next.store(newNode) 사이에 틈이 있습니다. 그 순간 생산자가 선점되면 소비자는 next == nullptr을 보고 “큐가 비었다”고 판단하는데, 실제로는 뒤에 원소가 더 있을 수 있습니다. 생산자 하나가 멈추면 그 뒤의 원소들도 소비자에게 보이지 않으므로 엄밀히는 소비자 쪽이 lock-free가 아닙니다. 위의 Michael-Scott 큐가 tail을 대신 전진시키는(helping) 분기를 두는 이유가 이것입니다. 소비자가 하나로 정해진 로그 수집기 같은 곳에서는 이 단순함이 장점이지만, 그 조건을 코드 주석과 API 이름에 분명히 남겨 두어야 합니다.
SPSC (Single Producer Single Consumer) 큐
생산자·소비자가 각각 하나일 때는 더 단순하고 빠른 구현이 가능합니다. 락이나 CAS 없이 순서 보장만으로 동작할 수 있습니다.
#include <atomic>
#include <vector>
template <typename T, size_t Capacity>
class SPSCQueue {
public:
SPSCQueue() : write_idx_(0), read_idx_(0) {
buffer_.resize(Capacity);
}
bool push(const T& value) {
size_t current = write_idx_.load(std::memory_order_relaxed);
size_t next = (current + 1) % Capacity;
if (next == read_idx_.load(std::memory_order_acquire))
return false; // full
buffer_[current] = value;
write_idx_.store(next, std::memory_order_release);
return true;
}
bool pop(T& value) {
size_t current = read_idx_.load(std::memory_order_relaxed);
if (current == write_idx_.load(std::memory_order_acquire))
return false; // empty
value = buffer_[current];
read_idx_.store((current + 1) % Capacity, std::memory_order_release);
return true;
}
private:
std::vector<T> buffer_;
std::atomic<size_t> write_idx_;
std::atomic<size_t> read_idx_;
};코드 설명: SPSC에서는 생산자와 소비자가 각각 하나의 인덱스만 수정하므로, CAS 없이 load/store와 메모리 순서만으로 동기화할 수 있습니다. release/acquire로 쓰기-읽기 순서가 보장됩니다.
메모리 순서 (memory_order)
순서 종류
| memory_order | 의미 | 사용처 |
|---|---|---|
| seq_cst | 순차 일관성 (가장 강함) | 기본값, 디버깅 |
| acquire | 이 연산 이후 읽기/쓰기가 재배치되지 않음 | load, CAS 성공 |
| release | 이 연산 이전 읽기/쓰기가 재배치되지 않음 | store, CAS 성공 |
| acq_rel | acquire + release | CAS (읽기-수정-쓰기) |
| relaxed | 순서 보장 없음, 원자성만 | 카운터 등 |
Release-Acquire 쌍
// 스레드 A (생산자)
data = 42;
ready.store(true, std::memory_order_release); // data 쓰기가 이전에 완료됨을 보장
// 스레드 B (소비자)
while (!ready.load(std::memory_order_acquire))
;
std::cout << data; // 42를 보장release로 쓴 스레드와 acquire로 읽는 스레드 간에 synchronizes-with 관계가 생깁니다. 따라서 data 쓰기가 ready 쓰기 이전에 완료되고, B가 ready를 읽으면 data도 최신 값을 봅니다.
Lock-Free에서의 권장
// push: release — 새 노드의 내용이 다른 스레드에 보이기 전에 head/tail이 갱신되면 안 됨
head_.compare_exchange_weak(..., std::memory_order_release, ...);
// pop: acquire — head를 읽은 후 노드 내용을 읽어야 함
head_.compare_exchange_weak(..., std::memory_order_acquire, ...);ABA 문제와 해결
ABA 문제란?
스레드 A가 head를 읽어 P를 봅니다. 그 사이 스레드 B가 P를 pop하며, P를 다시 push합니다. head는 여전히 P이지만, P->next는 이전과 다를 수 있습니다. A가 CAS를 시도할 때 “예상 값 = P”이므로 성공하는데, 그때 P->next가 이미 바뀐 상태일 수 있어 논리적 오류가 발생할 수 있습니다.
sequenceDiagram
participant A as 스레드 A
participant B as 스레드 B
participant Q as 큐
A->>Q: head 읽음 = P
B->>Q: pop() → P 제거
B->>Q: push(P) → P 다시 추가
A->>Q: CAS(P, P->next) → 성공!
Note over A: P->next가 이미 변경됐을 수 있음
해결 1: ABA 카운터 (Tagged Pointer)
포인터의 하위 비트에 버전/카운터를 넣어, 같은 주소라도 “세대”가 다르면 CAS가 실패하도록 합니다. 64비트에서 포인터가 48비트만 쓰는 경우 나머지 비트를 활용합니다.
#include <atomic>
#include <cstdint>
struct TaggedPtr {
uintptr_t ptr : 48; // 포인터 (정렬로 하위 비트 0)
uintptr_t tag : 16; // ABA 방지 카운터
};
std::atomic<uintptr_t> head_{0};
void push(Node* new_node) {
uintptr_t old_head = head_.load(std::memory_order_relaxed);
TaggedPtr old_tp;
old_tp.ptr = old_head & 0x0000FFFFFFFFFFFF;
old_tp.tag = old_head >> 48;
new_node->next = reinterpret_cast<Node*>(old_tp.ptr);
TaggedPtr new_tp;
new_tp.ptr = reinterpret_cast<uintptr_t>(new_node);
new_tp.tag = old_tp.tag + 1;
uintptr_t new_val = (static_cast<uintptr_t>(new_tp.tag) << 48) | new_tp.ptr;
while (!head_.compare_exchange_weak(old_head, new_val,
std::memory_order_release,
std::memory_order_relaxed)) {
old_tp.ptr = old_head & 0x0000FFFFFFFFFFFF;
old_tp.tag = old_head >> 48;
new_node->next = reinterpret_cast<Node*>(old_tp.ptr);
new_tp.ptr = reinterpret_cast<uintptr_t>(new_node);
new_tp.tag = old_tp.tag + 1;
new_val = (static_cast<uintptr_t>(new_tp.tag) << 48) | new_tp.ptr;
}
}해결 2: Hazard Pointer
노드를 즉시 삭제하지 않으며, “어떤 스레드가 이 포인터를 사용 중인지” 추적합니다. 사용 중인 포인터는 재사용하지 않으므로 ABA가 발생하지 않습니다.
// Hazard Pointer 개요 (간략화)
thread_local Node* hazard_ptr = nullptr;
bool pop(T& value) {
Node* old_head = nullptr;
Node* next = nullptr;
do {
old_head = head_.load(std::memory_order_acquire);
if (!old_head) return false;
hazard_ptr = old_head; // 이 스레드가 old_head를 사용 중임을 선언
if (head_.load() != old_head) continue; // 선언 사이에 바뀌었으면 다시 시도
next = old_head->next; // 선언 후에만 역참조
} while (!head_.compare_exchange_weak(old_head, next, ...));
value = old_head->data;
hazard_ptr = nullptr;
// old_head를 retire 리스트에 넣으며, 다른 스레드의 hazard_ptr에 없을 때만 삭제
retire(old_head);
return true;
}해결 3: RCU (Read-Copy-Update)
읽기는 lock-free로 하며, 쓰기는 복사본을 만들어 업데이트한 뒤 포인터를 한 번에 교체합니다. 구 버전은 모든 읽기가 끝난 뒤 재활용합니다.
회수 기법 고르기
lock-free 자료구조에서 가장 어려운 부분은 CAS 루프가 아니라 “언제 안전하게 메모리를 해제할 수 있는가”입니다. 기법마다 비용이 드는 곳이 다릅니다. Hazard Pointer는 포인터를 읽을 때마다 공개하고 재확인하는 비용이 들지만, 멈춘 스레드가 있어도 해제되지 못하고 남는 메모리 양이 제한됩니다. Epoch 기반 회수(EBR)는 읽기 비용이 거의 없는 대신 한 스레드가 오래 멈춰 있으면 세대가 넘어가지 않아 해제 대기 메모리가 계속 쌓입니다. 태그 포인터는 해제 문제 자체를 풀지 않고 ABA만 막으므로, 노드를 운영체제에 돌려주지 않고 프리리스트에서 재사용하는 구조와 함께 씁니다. Boost.Lockfree가 노드를 내부 프리리스트에 재사용하는 것도 같은 이유입니다.
위의 16비트 태그 방식 대신 struct { Node* ptr; uint64_t version; }를 통째로 std::atomic에 넣는 방법도 있는데, 이 크기를 원자적으로 CAS하려면 x86-64의 CMPXCHG16B 같은 더블 워드 CAS가 필요합니다. 컴파일은 되지만 is_lock_free()가 false인 플랫폼에서는 내부적으로 락을 쓰므로 반드시 확인해야 합니다. 표준도 이 문제를 다루기 시작해서, C++26에는 std::hazard_pointer와 RCU(std::rcu_obj_base)가 들어갑니다.
load+store 분리, 과도한 완화, 즉시 delete 같은 에러
문제 1: CAS 대신 load + store 분리
증상: 가끔 데이터 손실, 논리 오류 원인: “읽기-조건 확인-쓰기”를 여러 단계로 나누면, 그 사이에 다른 스레드가 값을 바꿀 수 있습니다.
// ❌ 잘못된 예
void set_if_zero() {
if (flag.load() == 0) {
flag.store(1); // 다른 스레드가 이미 1로 바꿨을 수 있음
}
}
// ✅ 올바른 예
void set_if_zero() {
int expected = 0;
flag.compare_exchange_strong(expected, 1);
}문제 2: 메모리 순서 과도한 완화
증상: 매우 드물게 잘못된 값 읽기, 재현 어려운 버그
원인: memory_order_relaxed만 쓰면, 컴파일러/CPU가 연산 순서를 바꿔 이전 쓰기가 아직 보이지 않은 상태에서 읽을 수 있습니다.
// ❌ 잘못된 예: relaxed만 사용
ready.store(true, std::memory_order_relaxed);
// consumer가 data를 읽기 전에 ready를 볼 수 있음 (이론상)
// ✅ 올바른 예: release/acquire 쌍
ready.store(true, std::memory_order_release);
// consumer
while (!ready.load(std::memory_order_acquire))
;
int x = data; // data 쓰기가 반드시 이전에 완료됨문제 3: pop한 노드 즉시 삭제 (다른 스레드가 아직 참조)
증상: use-after-free, 크래시
원인: lock-free 스택에서 pop한 노드를 바로 delete하면, 다른 스레드가 아직 그 노드를 읽고 있을 수 있습니다 (ABA 또는 지연된 읽기).
// ❌ 위험: pop 직후 delete
Node* old_head = ...;
head_.compare_exchange_weak(old_head, old_head->next);
delete old_head; // 다른 스레드가 old_head를 아직 참조할 수 있음
// ✅ 해결: hazard pointer, RCU, 또는 ABA 카운터로 재사용 지연
retire(old_head); // 나중에 안전할 때 삭제문제 4: 실패한 CAS 뒤에 desired를 다시 계산하지 않음
증상: 가끔 갱신이 사라짐(잃어버린 업데이트)
원인: compare_exchange_weak는 실패 시 expected를 현재 값으로 갱신해 주지만, desired는 알아서 바뀌지 않습니다. 루프 밖에서 한 번 계산한 desired를 계속 넣으면, CAS는 결국 성공하면서 다른 스레드의 갱신을 덮어씁니다.
// ❌ 잘못된 예
int expected = counter.load();
int desired = expected * 2;
while (!counter.compare_exchange_weak(expected, desired)) {
// expected는 갱신되지만 desired는 예전 값 기준 그대로
}
// ✅ 올바른 예
int expected = counter.load();
while (!counter.compare_exchange_weak(expected, expected * 2)) {
// 매 시도마다 갱신된 expected로 새 값을 계산
}문제 5: False Sharing
증상: atomic 변수 여러 개를 쓸 때 예상보다 느림 원인: 서로 다른 atomic이 같은 캐시 라인에 있으면, 한 스레드가 쓸 때 다른 스레드의 캐시 라인이 무효화됩니다.
// ❌ 잘못된 예
struct Counters {
std::atomic<int> a;
std::atomic<int> b; // a와 같은 캐시 라인
};
// ✅ 올바른 예 (캐시 라인 패딩)
struct alignas(64) Counters {
std::atomic<int> a;
char padding1[64 - sizeof(std::atomic<int>)];
std::atomic<int> b;
char padding2[64 - sizeof(std::atomic<int>)];
};문제 6: Lock-Free가 아닌 “그냥 atomic 사용”
증상: “lock-free”라고 생각했는데 데드락이나 livelock 원인: 여러 atomic을 사용할 때, 각 연산은 원자적이지만 전체 알고리즘은 그렇지 않을 수 있습니다. lock-free 정의(최소 한 스레드 진행)를 만족하는지 검증이 필요합니다.
문제 7: empty()만으로 판단 후 pop
증상: empty()인데 pop이 성공하거나, 그 반대 원인: lock-free에서는 empty()와 pop() 사이에 다른 스레드가 끼어들 수 있습니다.
// ❌ 잘못된 사용
if (!queue.empty()) {
T value;
queue.pop(value); // 그 사이에 다른 스레드가 pop해서 비었을 수 있음
}
// ✅ 올바른 사용
T value;
if (queue.pop(value)) {
// 성공적으로 꺼냄
}atomic으로 충분한지, 검증된 라이브러리가 있는지 먼저 따지기
단순한 경우 atomic만 사용
카운터, 플래그, 한 번만 실행하는 초기화 등은 fetch_add, compare_exchange_strong만으로 충분합니다. 복잡한 자료구조를 만들 필요가 없습니다.
// 카운터: fetch_add
std::atomic<uint64_t> count_{0};
count_.fetch_add(delta, std::memory_order_relaxed);
// 플래그: compare_exchange
std::atomic<bool> done_{false};
bool expected = false;
if (done_.compare_exchange_strong(expected, true)) {
// 이 스레드만 초기화 수행
}검증된 라이브러리 우선
직접 lock-free 큐/스택을 구현하기보다 Folly, Boost.Lockfree, libcds 등 검증된 라이브러리를 사용하는 것이 안전합니다.
프로파일링 후 도입
“lock-free가 빠르다”는 일반론이지만, 실제 병목이 mutex가 아닐 수 있습니다. 프로파일링으로 확인한 뒤 도입합니다.
메모리 순서 최소화
seq_cst(기본값)는 가장 강한 보장이지만 비용이 큽니다. 필요한 최소한의 release/acquire만 사용합니다.
ABA와 메모리 재사용 고려
포인터 기반 lock-free 구조에서는 ABA 문제와 “pop 직후 delete”를 반드시 고려합니다. 태그 포인터, hazard pointer, RCU 중 하나를 적용합니다.
테스트와 검증
lock-free 코드는 재현 어려운 버그가 많습니다. 스레드 샌티파이어(TSan), 스트레스 테스트, 정형 검증 도구를 활용합니다.
# TSan으로 data race 검사
g++ -fsanitize=thread -g -O2 -std=c++17 -pthread -o test test.cpp
./test무엇을 재야 하는가: lock-free 벤치마크
무엇을 재야 하나
여기에 “lock-free가 몇 배 빠르다”는 표를 싣지 않는 이유는, 그 배수가 코어 수, 경합 정도, 페이로드 크기, 할당자에 따라 뒤집히기 때문입니다. 경합이 낮은 단순 카운터라면 fetch_add가 뮤텍스보다 일관되게 빠릅니다. 하지만 수십 개 스레드가 같은 카운터를 갱신하면 fetch_add도 재시도는 없지만 그 캐시 라인을 코어들이 번갈아 독점해야 하므로 명령 하나가 크게 느려지고, CAS 루프를 쓰는 자료구조라면 여기에 재시도까지 급증합니다. 이때의 정석은 원자 연산을 더 빠르게 만드는 것이 아니라 공유 자체를 줄이는 것입니다. 스레드마다 로컬 카운터를 두고 가끔 합치거나(아래 스레드 로컬 버퍼 패턴), 서로 다른 원자 변수를 alignas(64)로 다른 캐시 라인에 떨어뜨려 false sharing을 막습니다. 복잡한 자료구조라면 경합 상황에서 최신 뮤텍스 구현(어댑티브 스핀 뮤텍스 등)이 비슷하거나 더 나은 처리량을 보이기도 합니다.
그래서 비교할 때는 같은 바이너리에서 스레드 수를 1, 2, 4, 8, 코어 수까지 늘려 가며 처리량과 지연 분포(평균만이 아니라 p99)를 함께 봅니다. -O2 이상으로 빌드하고, 스레드를 코어에 고정하지 않으면 결과가 실행마다 크게 흔들린다는 점도 감안합니다.
벤치마크 코드 예시
#include <chrono>
#include <iostream>
#include <thread>
#include <vector>
template <typename Queue>
void benchmark(Queue& q, int num_producers, int num_consumers, int ops_per_thread) {
std::vector<std::thread> producers, consumers;
std::atomic<int> consumed{0};
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < num_producers; ++i) {
producers.emplace_back([&, i]() {
for (int j = 0; j < ops_per_thread; ++j) {
q.push(i * ops_per_thread + j);
}
});
}
for (int i = 0; i < num_consumers; ++i) {
consumers.emplace_back([&]() {
int val;
while (consumed.fetch_add(1) < num_producers * ops_per_thread) {
while (!q.pop(val))
;
}
});
}
for (auto& t : producers) t.join();
for (auto& t : consumers) t.join();
auto end = std::chrono::high_resolution_clock::now();
double ms = std::chrono::duration<double, std::milli>(end - start).count();
int total_ops = num_producers * ops_per_thread * 2; // push + pop
std::cout << "Time: " << ms << " ms, Ops/sec: " << (total_ops / (ms / 1000.0)) << "\n";
}카운터 비교 코드
// atomic 카운터
std::atomic<int> counter{0};
for (int i = 0; i < 1'000'000; ++i) counter.fetch_add(1, std::memory_order_relaxed);
// mutex 카운터 (비교용)
std::mutex m; int plain = 0;
for (int i = 0; i < 1'000'000; ++i) { std::lock_guard lk(m); ++plain; }Bounded 큐, 배치 CAS, 스레드 로컬 버퍼, shutdown drain
패턴 1: 기존 라이브러리 활용
직접 구현보다 검증된 라이브러리를 쓰는 것이 안전합니다.
- Folly (Meta):
folly::MPMCQueue(유한 크기 MPMC),folly::ProducerConsumerQueue(SPSC) - Boost.Lockfree:
boost::lockfree::queue,boost::lockfree::stack - libcds: 다양한 lock-free 자료구조
#include <boost/lockfree/queue.hpp>
boost::lockfree::queue<int> q(128);
void producer() {
q.push(42);
}
void consumer() {
int value;
if (q.pop(value)) {
// 처리
}
}패턴 2: Bounded vs Unbounded
- Bounded: 고정 크기 버퍼. 메모리 예측 가능, 오버플로우 시 실패 또는 블로킹.
- Unbounded: 동적 할당. 메모리 사용량 변동, OOM 가능. 프로덕션에서는 대부분 bounded 큐를 쓰며, full 시 재시도 또는 백프레셔를 적용합니다.
패턴 3: 배치 처리로 CAS 비용 분산
한 번의 CAS로 여러 항목을 넣거나 빼면, CAS 비용을 분산할 수 있습니다.
// 배치 push: 여러 항목을 한 번에 연결한 뒤 tail만 한 번 CAS
void push_batch(const std::vector<T>& items) {
Node* first = new Node(items[0]);
Node* last = first;
for (size_t i = 1; i < items.size(); ++i) {
last->next = new Node(items[i]);
last = last->next;
}
// last를 tail에 CAS로 연결 (한 번의 CAS로 여러 항목 추가)
// ...
}패턴 4: 스레드 로컬 버퍼 + 주기적 플러시
각 스레드가 로컬 버퍼에 쌓으며, 가득 차거나 주기적으로 lock-free 큐에 flush합니다. CAS 횟수를 줄입니다.
thread_local std::vector<LogEntry> local_buffer;
constexpr size_t FLUSH_THRESHOLD = 64;
void log(LogEntry e) {
local_buffer.push_back(e);
if (local_buffer.size() >= FLUSH_THRESHOLD) {
for (auto& entry : local_buffer) {
global_queue.push(entry);
}
local_buffer.clear();
}
}패턴 5: Shutdown 플래그와 drain
종료 시 생산자를 먼저 멈추고, 큐가 비워질 때까지 소비자가 drain합니다.
std::atomic<bool> shutdown_{false};
void producer() {
while (!shutdown_.load(std::memory_order_acquire)) {
produce_and_push();
}
}
void consumer() {
T value;
while (true) {
if (queue.pop(value)) {
process(value);
} else if (shutdown_.load(std::memory_order_acquire)) {
break;
}
}
}패턴 6: 메트릭 수집
lock-free 구조에서도 CAS 실패 횟수, 대기 시간 등을 수집해 모니터링합니다. fetch_add로 통계를 갱신합니다.
std::atomic<uint64_t> cas_failures{0};
// CAS 루프 내
while (!head_.compare_exchange_weak(...)) {
cas_failures.fetch_add(1, std::memory_order_relaxed);
}카운터, 한 번만 실행 플래그, 캐시 포인터 예제
예제 1: Lock-Free 카운터 (다중 스레드 집계)
#include <atomic>
#include <thread>
#include <vector>
class LockFreeCounter {
public:
void add(uint64_t delta) {
count_.fetch_add(delta, std::memory_order_relaxed);
}
uint64_t get() const {
return count_.load(std::memory_order_acquire);
}
private:
std::atomic<uint64_t> count_{0};
};
// 사용: 여러 스레드가 요청 수, 바이트 수 등을 집계예제 2: Lock-Free 플래그 (한 번만 실행)
#include <atomic>
std::atomic<bool> initialized{false};
void init_once() {
if (!initialized.load(std::memory_order_acquire)) {
bool expected = false;
if (initialized.compare_exchange_strong(expected, true,
std::memory_order_acq_rel)) {
// 이 스레드만 초기화 수행
do_actual_init();
} else {
// 다른 스레드가 초기화 중. 대기 또는 스킵
}
}
}예제 3: Lock-Free 캐시 포인터 (읽기 최적화)
#include <atomic>
#include <memory>
template <typename T>
class Cache {
public:
std::shared_ptr<T> get() {
return std::atomic_load(&cached_); // lock-free 읽기
}
void update(std::shared_ptr<T> new_val) {
std::atomic_store(&cached_, new_val); // 한 번에 교체
}
private:
std::shared_ptr<T> cached_;
};예제 4: 세마포어 대체 (간단한 카운팅)
#include <atomic>
class LockFreeSemaphore {
public:
explicit LockFreeSemaphore(int initial) : count_(initial) {}
void acquire() {
int expected;
do {
expected = count_.load(std::memory_order_acquire);
while (expected == 0) {
expected = count_.load(std::memory_order_acquire);
}
} while (!count_.compare_exchange_weak(expected, expected - 1,
std::memory_order_acq_rel));
}
void release() {
count_.fetch_add(1, std::memory_order_release);
}
private:
std::atomic<int> count_;
};참고 자료
- C++ std::atomic cppreference
- Folly MPMCQueue
- Boost.Lockfree
- Anthony Williams, C++ Concurrency in Action
- Intel, Lock-Free Programming
lock-free 코드 점검 항목
- CAS 실패 후 갱신된 expected로 desired를 다시 계산
- push/pop에 적절한 memory_order (release/acquire) 적용
- pop한 노드 즉시 삭제 금지 (hazard pointer 등 고려)
- ABA 가능 시 태그 포인터 또는 hazard pointer 적용
- False sharing 방지 (캐시 라인 정렬)
- empty() 대신 pop() 반환값으로 판단
- 프로덕션: Folly, Boost.Lockfree 등 검증된 라이브러리 검토 CAS와 메모리 순서를 이해하며, ABA와 메모리 재사용을 고려하면 lock-free 자료구조를 안전하게 활용할 수 있습니다.
이전 글: C++ 캐시 히트를 높이는 메모리 정렬과 패딩 #34-2
자주 묻는 질문 (FAQ)
Q. lock-free 스택에서 pop한 노드를 바로 delete하면 왜 크래시가 나나요?
A. CAS에 성공한 스레드가 노드를 떼어 낸 순간에도, 다른 스레드는 직전에 읽은 같은 head를 가지고 next를 역참조하는 중일 수 있습니다. 이때 바로 delete하면 다른 스레드가 해제된 메모리를 읽는 use-after-free가 되고, 해제된 주소가 재사용되면 ABA 문제로 이어집니다. hazard pointer나 epoch 기반 회수, 참조 카운트처럼 아무도 노드를 보고 있지 않다는 것을 확인한 뒤 해제하는 방식을 써야 합니다.