C++ Lock-Free 자료구조: CAS로 스택·큐 만들기, 메모리 순서, ABA 문제와 Hazard Pointer
여러 워커 스레드가 하나의 작업 큐에서 작업을 꺼내 처리하는 서버를 생각해 봅시다. 큐를 std::mutex 하나로 보호하면 push와 pop이 모두 같은 잠금을 거치므로, 스레드를 늘려도 큐 접근은 한 번에 한 스레드씩만 일어납니다. 잠금을 쥔 스레드가 선점되면 나머지 스레드는 그동안 전부 기다립니다.
// 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 자료구조는 compare-and-swap(CAS) 같은 원자 연산으로 공유 상태를 갱신하므로, 한 스레드가 멈추더라도 다른 스레드는 계속 진행할 수 있습니다. 다만 lock-free가 항상 빠른 것은 아닙니다. 경합이 없을 때 뮤텍스는 원자 명령 한두 개로 잠그고 풀고, 경합이 심하면 lock-free 쪽도 캐시 라인 이동과 CAS 재시도로 느려집니다. 이득이 나는지는 실제 워크로드로 측정해 봐야 압니다.
lock-free 구조가 자주 거론되는 곳은 대체로 정해져 있습니다. 여러 스레드가 로그를 쌓고 한 스레드가 모아서 쓰는 로그 수집기(MPSC 큐), 수신 스레드와 처리 스레드가 하나씩인 패킷 버퍼(SPSC 링 버퍼), 게임 엔진의 작업 스케줄러(work-stealing 덱), 요청 수 같은 통계 카운터(fetch_add), 읽기가 압도적으로 많은 설정·캐시 포인터 교체가 대표적입니다. 공통점은 임계 구역이 아주 짧고 접근 빈도가 높다는 것입니다. 이 글은 CAS의 동작, Treiber 스택과 Michael-Scott 큐 구현, 메모리 순서, 그리고 lock-free 코드에서 가장 어려운 부분인 메모리 회수(ABA 문제, hazard pointer, epoch 기반 회수)를 차례로 다룹니다.
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 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는 값이 같아도 실패할 수 있습니다(가짜 실패, spurious failure). ARM처럼 LL/SC(load-linked/store-conditional) 명령으로 CAS를 구현하는 CPU에서는 그 사이에 인터럽트나 캐시 라인 이동이 있으면 store-conditional이 실패하기 때문입니다. 그 대신 strong보다 가벼운 코드가 나오므로, 어차피 재시도하는 루프 안에서는 weak를, 루프 없이 한 번의 결과로 분기해야 하는 곳에서는 strong을 씁니다. x86에서는 둘 다 lock cmpxchg 하나로 구현되어 차이가 없습니다.
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가 여전히 그 값일 때만 head를 새 노드로 바꿉니다. 그사이 다른 스레드가 push했다면 CAS가 실패하면서 new_node->next가 최신 head로 갱신되므로 그대로 다시 시도하면 됩니다. pop은 head를 읽고, head가 여전히 old_head일 때만 old_head->next로 바꿉니다. push의 CAS는 release로 새 노드의 내용을 공개하고, pop의 CAS는 acquire로 그 내용을 받아 옵니다.
이 구조는 “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를 켠 스트레스 테스트가 필수입니다.
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 읽기에 보이게 하고, 소비자가 칸을 비운 사실도 같은 방식으로 생산자에게 전달됩니다. 한 칸을 비워 두어 가득 참과 비어 있음을 구분하므로 실제로 담을 수 있는 원소는 Capacity - 1개입니다. 두 인덱스가 같은 캐시 라인에 있으면 생산자와 소비자가 서로의 캐시 라인을 계속 무효화하므로, 성능이 중요하다면 각 인덱스를 alignas(64)로 떼어 놓습니다.
메모리 순서 (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를 보장B의 acquire 읽기가 A의 release 저장이 쓴 값을 읽으면 두 연산 사이에 synchronizes-with 관계가 생깁니다. 그러면 A에서 ready 저장 전에 일어난 data = 42가 B에서 ready를 읽은 뒤의 코드에 보이는 것이 보장됩니다.
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 문제란?
Treiber 스택의 pop에서 스레드 A가 head로 노드 P를, 그 next로 Q를 읽은 직후 선점되었다고 합시다. 그사이 스레드 B가 P를 pop하고 Q도 pop해서 해제한 뒤 새 노드를 push하는데, 할당자가 해제된 P의 주소를 그대로 돌려줬습니다. head는 다시 P와 같은 주소입니다. A가 깨어나 CAS(head, P → Q)를 실행하면 head 값이 P와 같으므로 성공하고, 이미 해제된 Q가 head가 됩니다. 값만 비교하는 CAS는 그사이 값이 A→B→A로 바뀌었다가 돌아왔는지를 구분하지 못하므로 이를 ABA 문제라고 부릅니다.
sequenceDiagram
participant A as 스레드 A
participant B as 스레드 B
participant S as 스택
A->>S: head = P, P->next = Q 읽음
B->>S: pop() → P 제거
B->>S: pop() → Q 제거 후 해제
B->>S: push(새 노드) → 재사용된 주소 P
A->>S: CAS(P → Q) 성공
Note over A,S: 해제된 Q가 head가 됨
해결 1: 태그 포인터
포인터 옆에 버전 카운터를 두고 head를 바꿀 때마다 카운터를 올려서, 같은 주소라도 세대가 다르면 CAS가 실패하게 합니다. x86-64에서 4단계 페이지 테이블을 쓰는 사용자 공간 포인터는 하위 48비트만 쓰고 상위 16비트가 0이므로, 그 상위 16비트에 태그를 넣는 방법이 흔합니다. 5단계 페이지 테이블(LA57)이 켜진 시스템이나 ARM의 포인터 태깅(TBI, MTE)을 쓰는 환경에서는 이 가정이 깨질 수 있고, 16비트 태그는 65,536번 갱신마다 한 바퀴 돈다는 점도 알고 써야 합니다.
#include <atomic>
#include <cstdint>
struct Node { int data; Node* next; };
constexpr std::uintptr_t kPtrMask = (std::uintptr_t{1} << 48) - 1;
inline Node* ptr_of(std::uintptr_t v) { return reinterpret_cast<Node*>(v & kPtrMask); }
inline std::uintptr_t tag_of(std::uintptr_t v) { return v >> 48; }
inline std::uintptr_t pack(Node* p, std::uintptr_t tag) {
return ((tag & 0xFFFF) << 48) | reinterpret_cast<std::uintptr_t>(p);
}
std::atomic<std::uintptr_t> head_{0};
void push(Node* n) {
std::uintptr_t old = head_.load(std::memory_order_relaxed);
do {
n->next = ptr_of(old);
} while (!head_.compare_exchange_weak(old, pack(n, tag_of(old) + 1),
std::memory_order_release,
std::memory_order_relaxed));
}
Node* pop() {
std::uintptr_t old = head_.load(std::memory_order_acquire);
while (Node* p = ptr_of(old)) {
// p를 해제하는 구조라면 이 p->next 읽기 자체가 위험하므로 노드는 프리리스트로 재사용합니다
if (head_.compare_exchange_weak(old, pack(p->next, tag_of(old) + 1),
std::memory_order_acquire,
std::memory_order_relaxed))
return p;
}
return nullptr;
}위 시나리오에서 B의 pop과 push가 각각 태그를 올리므로, A가 들고 있는 값은 주소가 같아도 태그가 달라 CAS가 실패합니다. 다만 태그는 p->next를 읽는 순간의 use-after-free까지 막아 주지는 않습니다. 그래서 태그 포인터는 노드를 운영체제에 돌려주지 않고 프리리스트에서 재사용하는 구조와 함께 씁니다.
해결 2: Hazard Pointer
각 스레드가 지금 역참조하려는 포인터를 공유 슬롯에 공개하고, 노드를 해제하려는 스레드는 모든 슬롯을 확인해 아무도 공개하지 않은 노드만 해제합니다. 공개된 노드는 해제되지도, 같은 주소로 재할당되지도 않으므로 use-after-free와 ABA를 함께 막습니다.
// Hazard Pointer 개요 (간략화)
// 실제 구현에서는 스레드마다 전역 배열의 슬롯을 하나씩 차지하고,
// retire()가 그 배열 전체를 훑어 어떤 슬롯에도 없는 노드만 해제합니다.
bool pop(T& value) {
std::atomic<Node*>& hp = my_hazard_slot();
Node* old_head = head_.load();
for (;;) {
if (!old_head) { hp.store(nullptr); return false; }
hp.store(old_head); // 사용 중임을 공개 (seq_cst)
Node* current = head_.load(); // 공개한 뒤 head가 그대로인지 재확인
if (current != old_head) {
old_head = current;
continue;
}
Node* next = old_head->next; // 공개와 재확인이 끝난 뒤에만 역참조
if (head_.compare_exchange_strong(old_head, next)) break;
// 실패하면 old_head가 현재 head로 갱신되어 다시 공개부터 시작
}
hp.store(nullptr);
value = old_head->data; // 스택에서 떼어 낸 노드는 이 스레드만 retire할 수 있음
retire(old_head); // 다른 스레드의 슬롯에 없을 때 해제
return true;
}공개(hp.store)와 재확인(head_.load) 사이에는 저장이 나중 읽기보다 먼저 보이는 순서가 필요하므로, 둘 다 기본값 seq_cst로 두거나 사이에 std::atomic_thread_fence(std::memory_order_seq_cst)를 넣어야 합니다. release/acquire만으로는 저장이 뒤의 읽기 뒤로 밀리는 것을 막지 못합니다. 또 hazard 슬롯은 다른 스레드가 읽을 수 있어야 하므로 thread_local 일반 포인터로는 구현할 수 없습니다.
해결 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 분리
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가 순서를 바꿀 수 있어서 소비자가 ready == true를 보고도 data의 이전 값을 읽는 일이 생길 수 있고, 이런 버그는 x86에서는 잘 드러나지 않다가 ARM 같은 약한 메모리 모델에서 드물게 터집니다.
// ❌ 잘못된 예: 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한 노드 즉시 삭제 (다른 스레드가 아직 참조)
lock-free 스택에서 pop한 노드를 바로 delete하면, 같은 head를 읽어 둔 다른 스레드가 아직 그 노드의 next를 읽으려는 중일 수 있습니다. 결과는 use-after-free 크래시이거나, 주소가 재사용되면 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 변수가 같은 캐시 라인(대부분의 x86·ARM에서 64바이트)에 있으면, 한 스레드가 쓸 때마다 다른 코어의 캐시 라인이 무효화됩니다. 논리적으로는 공유하지 않는데도 경합이 생겨 예상보다 느려집니다.
// ❌ 잘못된 예
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 사용”
각 연산이 원자적이어도 여러 atomic을 조합한 알고리즘 전체가 lock-free인 것은 아닙니다. 다른 스레드가 특정 상태를 바꿔 주기를 기다리며 도는 루프가 있다면, 그 스레드가 멈출 때 나머지도 멈추므로 사실상 락입니다. “최소 한 스레드는 항상 진행한다”는 정의를 만족하는지 따져 봐야 합니다.
문제 7: empty()만으로 판단 후 pop
empty()가 false를 돌려준 직후에 다른 스레드가 마지막 원소를 꺼내 갈 수 있으므로, 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가 빠르다”는 일반론이지만, 실제 병목이 mutex가 아닐 수 있습니다. 프로파일링으로 확인한 뒤 도입합니다.
메모리 순서 최소화
seq_cst(기본값)는 가장 강한 보장이고, 비용은 주로 저장 쪽에서 듭니다. x86에서 seq_cst 저장은 xchg나 mfence가 필요하지만 seq_cst 읽기는 일반 mov와 같습니다. 정확성을 먼저 확보한 뒤, 프로파일링에서 병목으로 확인된 경로에만 release/acquire나 relaxed로 낮춥니다.
ABA와 메모리 재사용 고려
포인터 기반 lock-free 구조에서는 ABA 문제와 “pop 직후 delete”를 반드시 고려합니다. 태그 포인터, hazard pointer, RCU 중 하나를 적용합니다.
테스트와 검증
lock-free 코드는 재현하기 어려운 버그가 많으므로 ThreadSanitizer(TSan)와 스트레스 테스트를 기본으로 돌립니다. 메모리 순서 자체를 검증하려면 Relacy처럼 가능한 실행 순서를 탐색하는 도구가 필요합니다.
# 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 <atomic>
#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::steady_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::steady_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: 기존 라이브러리 활용
직접 구현보다 검증된 라이브러리를 쓰는 것이 안전합니다. boost::lockfree::queue는 원소 타입에 trivial한 복사 대입과 소멸자를 요구하므로, std::string 같은 타입은 포인터나 인덱스로 감싸서 넣어야 합니다.
- 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 가능.
패턴 3: 배치 처리로 CAS 횟수 줄이기
여러 항목을 미리 노드 사슬로 연결해 두고 한 번의 CAS로 큐에 붙이면, 항목마다 CAS를 하는 것보다 공유 포인터에 손대는 횟수가 줄어듭니다.
// Michael-Scott 큐에 배치 push: 노드 사슬을 먼저 만든 뒤 한 번에 연결
void push_batch(const std::vector<T>& items) {
if (items.empty()) return;
Node* first = new Node(items[0]);
Node* last = first;
for (size_t i = 1; i < items.size(); ++i) {
Node* n = new Node(items[i]);
last->next.store(n, std::memory_order_relaxed);
last = n;
}
// push()와 같은 루프로 old_tail->next를 nullptr에서 first로 CAS(release)한 뒤
// tail을 last로 옮깁니다. 사슬 전체가 한 번의 CAS로 큐에 들어갑니다.
}패턴 4: 스레드 로컬 버퍼와 주기적 플러시
각 스레드가 로컬 버퍼에 쌓았다가 일정량이 모이면 공유 큐로 넘깁니다. 공유 큐에 손대는 빈도가 줄어드는 효과는 플러시를 패턴 3의 배치 push로 할 때 생깁니다. 항목마다 push로 플러시하면 CAS 횟수는 그대로이고 로그가 늦게 보이는 비용만 남습니다. 스레드가 끝날 때 버퍼에 남은 항목을 플러시하는 것도 잊기 쉬운 부분입니다.
thread_local std::vector<LogEntry> local_buffer;
constexpr size_t FLUSH_THRESHOLD = 64;
void log(LogEntry e) {
local_buffer.push_back(std::move(e));
if (local_buffer.size() >= FLUSH_THRESHOLD) {
global_queue.push_batch(local_buffer); // 사슬 하나로 연결해 한 번에 추가
local_buffer.clear();
}
}패턴 5: 종료 시 drain
종료할 때는 생산자를 먼저 멈추고 모두 join한 뒤, 소비자가 남은 항목을 비우고 끝나게 합니다. 흔한 실수는 “pop이 실패했고 종료 플래그가 켜져 있으면 끝낸다”로 처리하는 것입니다. 종료 플래그를 세우기 직전에 push를 시작한 생산자가 있으면, 소비자가 pop에 실패하고 플래그를 확인하는 사이에 그 항목이 들어와 처리되지 않고 남습니다. 생산자를 모두 join한 뒤에 별도의 완료 플래그를 세우고, 소비자가 그 플래그를 본 다음 한 번 더 비우면 이 틈이 사라집니다.
std::atomic<bool> stop_{false}; // 생산자에게 멈추라고 알림
std::atomic<bool> producers_done_{false}; // 모든 생산자를 join한 뒤에 true
void producer() {
while (!stop_.load(std::memory_order_acquire)) {
produce_and_push();
}
}
void consumer() {
T value;
for (;;) {
if (queue.pop(value)) {
process(value);
} else if (producers_done_.load(std::memory_order_acquire)) {
while (queue.pop(value)) process(value); // 마지막으로 남은 항목 처리
break;
}
}
}
// 종료 순서: stop_ = true → 생산자 join → producers_done_ = true → 소비자 join패턴 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: 초기화를 맡을 스레드 하나 고르기
#include <atomic>
std::atomic<bool> claimed{false};
bool try_claim_init() {
bool expected = false;
// 여러 스레드가 동시에 불러도 true를 받는 스레드는 하나뿐입니다
return claimed.compare_exchange_strong(expected, true, std::memory_order_acq_rel);
}이 플래그는 누가 초기화를 맡을지만 정해 줍니다. 플래그가 true가 된 순간에는 초기화가 아직 끝나지 않았으므로, 다른 스레드가 이 플래그만 보고 초기화된 객체를 쓰면 안 됩니다. 초기화가 끝날 때까지 다른 스레드를 기다리게 해야 한다면 std::call_once나 함수 안의 static 지역 변수(C++11부터 스레드 안전하게 초기화됨)를 쓰는 편이 맞습니다.
예제 3: 공유 포인터 원자적 교체
#include <atomic>
#include <memory>
template <typename T>
class Cache {
public:
std::shared_ptr<T> get() const {
return cached_.load(std::memory_order_acquire);
}
void update(std::shared_ptr<T> new_val) {
cached_.store(std::move(new_val), std::memory_order_release);
}
private:
std::atomic<std::shared_ptr<T>> cached_; // C++20
};읽는 쪽은 받아 간 shared_ptr로 예전 버전을 계속 쓰고, 마지막 참조가 사라질 때 예전 버전이 해제되므로 RCU와 비슷한 효과를 냅니다. C++20 이전에 쓰던 std::atomic_load(&sp)/std::atomic_store(&sp, v) 자유 함수는 C++20에서 폐기 예정(deprecated)이 되었습니다. 또 std::atomic<std::shared_ptr<T>>는 주요 표준 라이브러리 구현에서 lock-free가 아니며 내부적으로 짧은 잠금을 씁니다. 원자적으로 교체된다는 것과 lock-free라는 것은 다른 이야기이므로, 읽기 경로가 정말 뜨겁다면 is_lock_free()와 프로파일링으로 확인합니다.
예제 4: 스핀 방식 카운팅 세마포어
#include <atomic>
class SpinSemaphore {
public:
explicit SpinSemaphore(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_;
};count가 0이면 다른 스레드가 release()할 때까지 계속 돌며 기다리므로, 이 클래스는 원자 연산으로 만들었을 뿐 진행 보장 면에서 lock-free가 아닙니다. 기다리는 시간이 길 수 있다면 스레드를 재우는 C++20 std::counting_semaphore를 씁니다.
참고 자료
- C++ std::atomic cppreference
- Folly MPMCQueue
- Boost.Lockfree
- Anthony Williams, C++ Concurrency in Action
이전 글: C++ 캐시 효율적인 코드: 데이터 지향 설계 가이드