C++ Lock-Free 프로그래밍 실전 | CAS·ABA·메모리 순서·고성능 큐 [#34-3]

· 35분 읽기 · 수정 고급 개념
C++ Lock-Free 프로그래밍 실전 | CAS·ABA·메모리 순서·고성능 큐 [#34-3]

이 글의 핵심

C++ Lock-Free 프로그래밍 실전에 대한 실전 가이드입니다. CAS·ABA·메모리 순서·고성능 큐 [#34-3] 등을 예제와 함께 상세히 설명합니다.

들어가며: mutex가 병목이에요

”초당 100만 요청 처리하려는데 락 경합이 심해요”

고성능 서버에서 여러 워커 스레드가 작업 큐에서 작업을 가져와 처리하는 구조였습니다. std::mutex로 큐를 보호했더니, 스레드 수를 늘려도 처리량이 거의 늘지 않고 락 대기 시간이 전체 지연의 상당 부분을 차지했습니다. lock-free 큐로 바꾸니 동일 하드웨어에서 처리량이 2~3배 늘었습니다.

락 기반 코드에서는 큐에 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는 쓰지만, 블로킹으로 인한 지연 변동은 줄일 수 있습니다.

문제 시나리오

시나리오 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” 패턴을 적용하면 읽기가 거의 블로킹 없이 동작합니다.

목차

  1. 기본 개념
  2. 원자 연산과 CAS
  3. Lock-Free 스택 완전 예제
  4. Lock-Free 큐 완전 예제
  5. 메모리 순서 (memory_order)
  6. ABA 문제와 해결
  7. 자주 발생하는 에러와 해결법
  8. 모범 사례와 주의점
  9. 성능 벤치마크
  10. 프로덕션 패턴
  11. 실전 예제

1. 기본 개념

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-FreeWait-Free
정의최소 한 스레드는 진행모든 스레드가 유한 단계 내 완료
재시도CAS 실패 시 재시도 가능재시도 없이 완료 보장
구현 난이도상대적으로 낮음매우 높음
실무큐, 스택, 카운터 등제한적 (atomic fetch_add 등)

대부분의 lock-free 자료구조는 lock-free이지 wait-free는 아닙니다. CAS 실패 시 루프로 재시도하는 패턴이 일반적입니다.

2. 원자 연산과 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 없음. 한 번만 시도할 때 적합.

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);

3. Lock-Free 스택 완전 예제

단일 링크드 리스트 스택

스택은 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 등 필요 (아래 참조).

메모리 순서 설명

// push: release — 이 CAS 이전의 쓰기가 다른 스레드에 보임
head_.compare_exchange_weak(..., std::memory_order_release, ...);

// pop: acquire — 이 CAS 이전에 다른 스레드가 쓴 값을 읽을 수 있음
head_.compare_exchange_weak(..., std::memory_order_acquire, ...);

4. Lock-Free 큐 완전 예제

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이 아직 따라오지 않은 상태입니다.

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로 쓰기-읽기 순서가 보장됩니다.

5. 메모리 순서 (memory_order)

순서 종류

memory_order의미사용처
seq_cst순차 일관성 (가장 강함)기본값, 디버깅
acquire이 연산 이후 읽기/쓰기가 재배치되지 않음load, CAS 성공
release이 연산 이전 읽기/쓰기가 재배치되지 않음store, CAS 성공
acq_relacquire + releaseCAS (읽기-수정-쓰기)
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, ...);

6. 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 = head_.load(std::memory_order_acquire);
    do {
        Node* next = old_head ? old_head->next.load() : nullptr;
        hazard_ptr = old_head;  // 이 스레드가 old_head를 사용 중임을 선언
        if (head_.load() != old_head) continue;  // 재검증
    } 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로 하고, 쓰기는 복사본을 만들어 업데이트한 뒤 포인터를 한 번에 교체합니다. 구 버전은 모든 읽기가 끝난 뒤 재활용합니다.

7. 자주 발생하는 에러와 해결법

문제 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: compare_exchange의 expected를 참조로 전달하지 않음

증상: 무한 루프, CAS가 영원히 실패

원인: compare_exchange_weak는 실패 시 expected를 현재 값으로 갱신합니다. 값을 넘기면 갱신이 반영되지 않아 같은 값으로 계속 시도하게 됩니다.

// ❌ 잘못된 예
int expected = 0;
while (!atomic_val.compare_exchange_weak(expected, 1)) {
    // expected가 갱신되지 않음 (값으로 전달했을 경우)
}

// ✅ 올바른 예
int expected = 0;
while (!atomic_val.compare_exchange_weak(expected, 1)) {
    // expected가 현재 atomic 값으로 자동 갱신됨 (참조 전달)
}

문제 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)) {
    // 성공적으로 꺼냄
}

8. 모범 사례와 주의점

1. 단순한 경우 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)) {
    // 이 스레드만 초기화 수행
}

2. 검증된 라이브러리 우선

직접 lock-free 큐/스택을 구현하기보다 Folly, Boost.Lockfree, libcds 등 검증된 라이브러리를 사용하는 것이 안전합니다.

3. 프로파일링 후 도입

“lock-free가 빠르다”는 일반론이지만, 실제 병목이 mutex가 아닐 수 있습니다. 프로파일링으로 확인한 뒤 도입합니다.

4. 메모리 순서 최소화

seq_cst(기본값)는 가장 강한 보장이지만 비용이 큽니다. 필요한 최소한의 release/acquire만 사용합니다.

5. ABA와 메모리 재사용 고려

포인터 기반 lock-free 구조에서는 ABA 문제와 “pop 직후 delete”를 반드시 고려합니다. 태그 포인터, hazard pointer, RCU 중 하나를 적용합니다.

6. 테스트와 검증

lock-free 코드는 재현 어려운 버그가 많습니다. 스레드 샌티파이어(TSan), 스트레스 테스트, 정형 검증 도구를 활용합니다.

# TSan으로 data race 검사
g++ -fsanitize=thread -g -O2 -std=c++17 -pthread -o test test.cpp
./test

9. 성능 벤치마크

테스트 환경 (예시)

  • CPU: Intel Core i7-12700 (12코어)
  • 컴파일: 아래 명령 참조
g++ -O3 -std=c++17 -pthread -o lockfree_bench lockfree_bench.cpp
  • 스레드: 4 producer, 4 consumer
  • 연산: 1,000,000 push + 1,000,000 pop

벤치마크 결과 (예시)

자료구조총 시간 (ms)초당 연산 (ops)상대 속도
std::queue + mutex1805.5M1.0x
Lock-Free 큐 (MPMC)7213.9M2.5x
SPSC 큐 (링 버퍼)2835.7M6.4x

벤치마크 코드 예시

#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 vs mutex)

방식8스레드 100만 증가 (ms)상대 속도
mutex451.0x
atomic fetch_add85.6x
// atomic 카운터
std::atomic<int> counter{0};
for (int i = 0; i < 1'000'000; ++i) counter.fetch_add(1, std::memory_order_relaxed);

10. 프로덕션 패턴

패턴 1: 기존 라이브러리 활용

직접 구현보다 검증된 라이브러리를 쓰는 것이 안전합니다.

  • Folly (Facebook): folly::LockFreeQueue, folly::MPMCQueue
  • 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);
}

11. 실전 예제

예제 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_;
};

참고 자료

정리

항목설명
Lock-Free락 없이 최소 한 스레드는 진행 보장
CAScompare_exchange_strong/weak로 조건부 원자 업데이트
스택head만 CAS. push/pop 모두 CAS
큐head, tail CAS. 더미 노드로 일관성 유지
ABA태그 포인터, hazard pointer, RCU로 완화
메모리 순서release/acquire로 동기화
에러load+store 분리, relaxed 과용, 즉시 삭제
프로덕션검증된 라이브러리, bounded, 배치 처리

핵심 원칙:

  1. 단순한 경우(카운터, 플래그)는 atomic fetch_add, CAS로 충분
  2. 복잡한 자료구조는 검증된 라이브러리 우선 사용
  3. 직접 구현 시 ABA, 메모리 재사용, 메모리 순서를 반드시 고려
  4. 벤치마크로 실제 환경에서 mutex 대비 이득 확인

구현 체크리스트

  • CAS 사용 시 expected를 참조로 전달
  • 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. 이 내용을 실무에서 언제 쓰나요?

A. 락 없는 동기화: std::atomic, compare_exchange, lock-free 큐·스택, ABA 문제, 메모리 순서, hazard pointer, 성능 벤치마크, 프로덕션 패턴. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

다음 글: Python과 C++의 만남: pybind11 #35-1

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

  • C++ atomic | Mutex 없이 스레드 안전 카운터 만드는 법 (memory_order 포함)
  • C++ Data Race | “Mutex 대신 Atomic을 써야 하는 상황은?” 면접 단골 질문 정리
  • C++ 캐시 히트(Cache Hit)를 높이는 메모리 정렬과 패딩 | False Sharing 해결

이 글에서 다루는 키워드 (관련 검색어)

C++, lock-free, atomic, CAS, ABA, memory_order, 성능최적화, 멀티스레드, 면접 등으로 검색하시면 이 글이 도움이 됩니다.

관련 글

  • C++ Data Race |
  • C++ Lock-Free 프로그래밍 실전 | CAS·ABA·메모리 순서·고성능 큐 [#51-5]
  • C++ 캐시 히트(Cache Hit)를 높이는 메모리 정렬과 패딩 | False Sharing 해결
  • C++ Lock-Free Programming |
  • C++ 메모리 순서(Memory Ordering) 완벽 가이드 | relaxed·acquire/release