C++ Lock-Free & std::atomic

Lock-Free 프로그래밍이 필요한 이유

뮤텍스(mutex) 기반 동기화는 간단하지만 몇 가지 근본적인 비용을 수반합니다.

• 컨텍스트 스위치: 잠금 대기 중인 스레드는 운영체제에 의해 블로킹됩니다.
• 우선순위 역전(Priority Inversion): 낮은 우선순위 스레드가 잠금을 보유하면 높은 우선순위 스레드가 대기해야 합니다.
• 데드락 가능성: 여러 뮤텍스를 순서 없이 획득하면 교착 상태가 발생합니다.

Lock-free 알고리즘은 이러한 문제를 하드웨어 수준의 원자적 연산으로 우회합니다. 단, 구현 복잡도가 높고 잘못 작성하면 미묘한 버그가 발생하므로 신중하게 사용해야 합니다.

---

std::atomic 기초

std::atomic<T>는 T 타입 변수에 대한 원자적(atomic) 읽기/쓰기/수정 연산을 보장합니다.

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

std::atomic<int> counter{0};

void increment(int n)
{
    for (int i = 0; i < n; ++i)
    {
        ++counter; // 원자적 증가: fetch_add(1)과 동일
    }
}

int main()
{
    std::thread t1(increment, 100000);
    std::thread t2(increment, 100000);
    t1.join();
    t2.join();

    // 뮤텍스 없이도 항상 200000 출력
    std::cout << counter.load() << "\n";
}

---

memory_order 완전 정리

memory_order는 원자적 연산이 메모리에 가시화되는 순서를 컴파일러와 CPU에 지시합니다. 잘못 선택하면 다른 스레드에서 연산 결과가 예상과 다른 순서로 보일 수 있습니다.

종류와 의미

memory_order	설명
relaxed	순서 보장 없음. 값만 원자적으로 변경
consume	의존성 있는 읽기만 순서 보장 (실용성 낮음)
acquire	이후의 모든 읽기/쓰기가 이 연산 뒤에 배치됨
release	이전의 모든 읽기/쓰기가 이 연산 앞에 배치됨
acq_rel	acquire + release 동시 적용 (RMW 연산용)
seq_cst	전체 순차적 일관성 보장. 가장 강력하지만 느림 (기본값)

acquire-release 패턴 예시

#include <atomic>
#include <cassert>

std::atomic<bool> ready{false};
int data = 0;

void producer()
{
    data = 42;                            // (1)
    ready.store(true, std::memory_order_release); // (2)
    // release: (1)이 반드시 (2)보다 먼저 메모리에 기록됨을 보장
}

void consumer()
{
    while (!ready.load(std::memory_order_acquire)) // (3)
    {
        // spin
    }
    // acquire: (3) 이후에 실행되는 모든 읽기는
    // release 이전에 쓰인 값을 볼 수 있음
    assert(data == 42); // 항상 성공
}

relaxed를 잘못 사용하면 CPU의 비순차 실행(Out-of-Order Execution)으로 인해 data == 42 어서션이 실패할 수 있습니다.

---

CAS(Compare-And-Swap) 패턴

CAS는 lock-free 알고리즘의 핵심 원시 연산입니다. “현재 값이 expected와 같으면 desired로 바꾼다”는 조건부 교환을 원자적으로 수행합니다.

// compare_exchange_weak / compare_exchange_strong
bool compare_exchange_weak(T& expected, T desired,
    std::memory_order success, std::memory_order failure);

• weak: 루프 안에서 사용. spurious failure(허위 실패)가 가능하지만 일부 아키텍처에서 더 효율적
• strong: 루프 없이 한 번만 시도할 때 사용

lock-free 카운터 증가 (CAS 루프)

std::atomic<int> value{0};

void safe_increment()
{
    int expected = value.load(std::memory_order_relaxed);
    // CAS 루프: 성공할 때까지 재시도
    while (!value.compare_exchange_weak(
        expected,          // 실패 시 현재 값으로 자동 업데이트됨
        expected + 1,      // 새 값
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected는 compare_exchange_weak가 자동으로 현재 값으로 갱신함
    }
}

---

Lock-Free 스택 구현

#include <atomic>
#include <memory>

template<typename T>
class LockFreeStack
{
private:
    struct Node
    {
        T data;
        Node* next;
        explicit Node(T val) : data(std::move(val)), next(nullptr) {}
    };

    std::atomic<Node*> head{nullptr};

public:
    void push(T value)
    {
        Node* newNode = new Node(std::move(value));
        // head를 새 노드의 next로 설정한 뒤 head를 교체
        newNode->next = head.load(std::memory_order_relaxed);
        while (!head.compare_exchange_weak(
            newNode->next, newNode,
            std::memory_order_release,
            std::memory_order_relaxed))
        {
            // 실패하면 newNode->next가 현재 head로 갱신됨
        }
    }

    std::shared_ptr<T> pop()
    {
        Node* oldHead = head.load(std::memory_order_acquire);
        while (oldHead &&
               !head.compare_exchange_weak(
                   oldHead, oldHead->next,
                   std::memory_order_release,
                   std::memory_order_acquire))
        {
            // 실패하면 oldHead가 현재 head로 갱신됨
        }

        if (!oldHead) return nullptr;

        auto result = std::make_shared<T>(std::move(oldHead->data));
        // 주의: 여기서 delete oldHead를 하면 ABA 문제 발생 가능
        // 실제 프로덕션 코드에서는 Hazard Pointer나 Epoch-Based Reclamation 필요
        delete oldHead;
        return result;
    }
};

---

Lock-Free SPSC 큐 구현

Single Producer Single Consumer(SPSC) 큐는 프로듀서와 컨슈머가 각각 하나일 때 가장 단순하고 빠른 lock-free 큐입니다. 게임 엔진의 렌더 스레드-메인 스레드 간 커맨드 큐에 자주 활용됩니다.

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue
{
    static_assert((Capacity & (Capacity - 1)) == 0,
        "Capacity must be a power of 2");

    std::array<T, Capacity> buffer;
    // head는 프로듀서만 쓰고, tail은 컨슈머만 씀
    // 각각 cache line을 분리해 false sharing 방지
    alignas(64) std::atomic<size_t> head{0};
    alignas(64) std::atomic<size_t> tail{0};

    static constexpr size_t MASK = Capacity - 1;

public:
    bool push(const T& item)
    {
        const size_t currentHead = head.load(std::memory_order_relaxed);
        const size_t nextHead = (currentHead + 1) & MASK;

        // 큐가 가득 찬 경우
        if (nextHead == tail.load(std::memory_order_acquire))
            return false;

        buffer[currentHead] = item;
        head.store(nextHead, std::memory_order_release);
        return true;
    }

    bool pop(T& item)
    {
        const size_t currentTail = tail.load(std::memory_order_relaxed);

        // 큐가 비어있는 경우
        if (currentTail == head.load(std::memory_order_acquire))
            return false;

        item = buffer[currentTail];
        tail.store((currentTail + 1) & MASK, std::memory_order_release);
        return true;
    }
};

alignas(64)로 head와 tail을 별도 캐시 라인에 배치하면 False Sharing으로 인한 성능 저하를 방지합니다.

---

ABA 문제

Lock-free 알고리즘의 가장 유명한 함정입니다.

1. 스레드 A가 head를 읽음 (값: ptr_X)
2. 스레드 B가 ptr_X를 pop하고, 새 노드를 push한 뒤, 우연히 같은 주소(ptr_X)를 재사용
3. 스레드 A의 CAS가 성공하지만 실제로는 잘못된 상태

해결책:

• Tagged Pointer: 포인터와 함께 버전 카운터를 원자적으로 관리 (std::atomic<std::pair<T*, uint64_t>>)
• Hazard Pointer: 사용 중인 포인터를 등록해 해제를 지연
• Epoch-Based Reclamation: 특정 에포크가 끝날 때까지 메모리 해제 지연

---

실무 적용 가이드

상황	권장 방식
단순 카운터, 플래그	std::atomic<int/bool> with relaxed or seq_cst
프로듀서-컨슈머 시그널	release/acquire 쌍
멀티 프로듀서/컨슈머 큐	검증된 라이브러리 사용 (folly, moodycamel)
성능 크리티컬 게임 루프	SPSC 큐 + False Sharing 방지

---

마무리

std::atomic과 memory_order는 C++ 멀티스레딩의 가장 강력하면서도 위험한 도구입니다. seq_cst는 안전하지만 느리고, relaxed는 빠르지만 잘못 쓰면 재현하기 어려운 버그를 만듭니다.

실제 프로젝트에서는 직접 lock-free 자료구조를 구현하기보다 folly::MPMCQueue, moodycamel::ConcurrentQueue 같은 검증된 라이브러리를 우선 고려하고, 성능 병목이 확인된 후에만 맞춤 구현을 시도하는 것을 권장합니다.