Lock-Free 자료구조 원리와 구현

개요

Lock-Free 자료구조는 뮤텍스 없이 원자적(atomic) 연산으로 스레드 안전성을 보장합니다. 적어도 하나의 스레드는 항상 진전(progress)합니다. 게임 서버의 메시지 큐, 메모리 풀, 이벤트 시스템에서 뮤텍스 병목을 제거하는 데 활용됩니다.

---

1. CAS — Compare-And-Swap

// CAS: 원자적으로 "현재 값이 expected이면 desired로 교체"
template<typename T>
bool CompareAndSwap(std::atomic<T>& target, T& expected, T desired) {
    return target.compare_exchange_weak(expected, desired);
    // 성공: true, target = desired
    // 실패: false, expected = 현재 값 (루프에서 재시도)
}

// 원자적 증가 (spin loop)
void AtomicIncrement(std::atomic<int>& counter) {
    int expected = counter.load();
    while (!counter.compare_exchange_weak(expected, expected + 1))
        ; // expected가 자동으로 현재 값으로 갱신됨
}

---

2. Lock-Free 스택

#include <atomic>
#include <memory>

template<typename T>
class LockFreeStack {
    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));
        newNode->next = head.load(std::memory_order_relaxed);

        // CAS 루프: head가 변경되면 재시도
        while (!head.compare_exchange_weak(
            newNode->next, newNode,
            std::memory_order_release,
            std::memory_order_relaxed));
    }

    std::optional<T> Pop() {
        Node* oldHead = head.load(std::memory_order_relaxed);

        while (oldHead) {
            if (head.compare_exchange_weak(
                oldHead, oldHead->next,
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                T value = std::move(oldHead->data);
                // ⚠️ 메모리 해제는 Hazard Pointer 등으로 안전하게 처리
                delete oldHead;
                return value;
            }
            // oldHead가 자동으로 현재 head로 갱신됨
        }

        return std::nullopt; // 빈 스택
    }
};

---

3. ABA 문제

시나리오:
Thread 1: head = A → Pop 준비, A의 next = B 읽음
Thread 2: Pop(A), Push(C), Push(A) → head = A로 복귀
Thread 1: CAS 성공 (head == A) → head = B로 변경
결과: C가 영원히 손실됨 (B→C 연결이 끊어짐)

해결법 1: ABA 카운터 (Tagged Pointer)

struct TaggedPtr {
    Node* ptr;
    uintptr_t tag; // 버전 카운터
};

std::atomic<TaggedPtr> head;

bool CAS_Tagged(TaggedPtr& expected, Node* newPtr) {
    TaggedPtr desired{newPtr, expected.tag + 1}; // 태그 증가
    return head.compare_exchange_weak(expected, desired);
    // 포인터가 같아도 태그가 다르면 실패
}

해결법 2: Hazard Pointer

// 각 스레드가 "사용 중인 포인터"를 등록
// 다른 스레드는 등록된 포인터를 해제하지 않음
thread_local Node* hazardPtr = nullptr;

std::optional<T> SafePop() {
    Node* oldHead = head.load();

    while (oldHead) {
        hazardPtr = oldHead; // 해당 포인터 보호 등록

        if (head.load() != oldHead) {
            oldHead = head.load();
            continue;
        }

        if (head.compare_exchange_weak(oldHead, oldHead->next)) {
            hazardPtr = nullptr;
            T val = std::move(oldHead->data);
            RetireNode(oldHead); // 즉시 삭제 대신 퇴역 큐에 추가
            return val;
        }
    }

    return std::nullopt;
}

---

4. Lock-Free 큐 (Michael-Scott Queue)

template<typename T>
class LockFreeQueue {
    struct Node {
        std::optional<T> data;
        std::atomic<Node*> next{nullptr};
        Node() = default;
        explicit Node(T val) : data(std::move(val)) {}
    };

    std::atomic<Node*> head;
    std::atomic<Node*> tail;

public:
    LockFreeQueue() {
        Node* dummy = new Node(); // 더미 노드
        head.store(dummy);
        tail.store(dummy);
    }

    void Enqueue(T value) {
        Node* newNode = new Node(std::move(value));
        Node* prevTail;

        while (true) {
            prevTail = tail.load(std::memory_order_acquire);
            Node* tailNext = prevTail->next.load(std::memory_order_acquire);

            if (prevTail == tail.load()) {
                if (tailNext == nullptr) {
                    if (prevTail->next.compare_exchange_weak(
                        tailNext, newNode,
                        std::memory_order_release))
                    {
                        break;
                    }
                } else {
                    // tail이 뒤처진 경우 전진
                    tail.compare_exchange_weak(prevTail, tailNext);
                }
            }
        }
        tail.compare_exchange_weak(prevTail, newNode);
    }
};

---

5. 메모리 순서 (Memory Order)

std::atomic<int> x{0}, y{0};

// 가장 강한 순서 보장 (기본값)
x.store(1, std::memory_order_seq_cst);   // 모든 스레드에 일관된 순서

// 발행-소비 패턴
// 생산자
data = prepare();
flag.store(true, std::memory_order_release); // 이전 쓰기가 여기서 보임

// 소비자
while (!flag.load(std::memory_order_acquire)); // release 이전 쓰기 모두 보임
use(data);

// 성능: relaxed > acquire/release > seq_cst

---

6. Lock vs Lock-Free 선택

상황	추천
짧은 임계 구간	spin lock 또는 lock-free
긴 임계 구간	mutex
높은 경쟁	lock-free (뮤텍스 컨텍스트 스위치 회피)
낮은 경쟁	mutex (구현 단순)
실시간 요구	lock-free (우선순위 역전 없음)

---

정리

• CAS = Lock-Free의 핵심 원시 연산
• ABA 문제: 포인터 재사용으로 CAS가 잘못 성공하는 현상
• Hazard Pointer로 안전한 메모리 해제
• Memory Order: seq_cst (안전) → acquire/release (빠름) → relaxed (최소 보장)
• Lock-Free ≠ 항상 빠름 → 경쟁이 높을 때 뮤텍스보다 유리

참고 자료

• cppreference — std::atomic
• Herb Sutter — Lock-Free Programming