[고성능] CAS(Compare and Swap)과 Lock-Free Queue

 

들어가며

동시성 프로그래밍을 진행하면서 가장 큰 문제는 데이터 동기화입니다. 스레드간 경합(race-condition)이 벌어졌을 때, 공유 자원에 대한 동기화를 진행하기 위해 대표적으로 Mutex Lock을 사용합니다. 고성능 프로그래밍에서 Lock은 절대악이라고 생각하시면 될 것 같습니다. 하지만 데이터 동기화에 대한 문제가 아직 남아있기 때문에 Lock을 최소화하면서 사용하는 것입니다. 오늘은 Lock을 사용하지 않은 락프리큐(Lock-Free Queue)에 대해 알아보겠습니다.

 

Producer and Consumer

출처: https://jenkov.com/tutorials/java-concurrency/producer-consumer.html

동시성을 처리하는 전통적인 방식인 생산자-소비자 패턴(Producer Consumer Pattern)을 살펴보겠습니다. 이벤트/이슈가 발생하면 생산자 스레드에서 Queue에 Job을 Push합니다. 그리고 Consumer 스레드에서 Job을 Pop해서 처리합니다. 생산자는 끊임없이 Job을 Queue에 넣고 소비자는 끊임없이 Job을 Queue에서 뺍니다. 만약 소비자가 Job을 처리하는 속도보다 생산자가 Job을 Push하는 속도가 더 빠른 경우에는 병목이 일어날 수 있습니다. 그래서 여러 소비자 스레드를 스레드 풀로 처리하는 경우가 많습니다.

 

Lcok-based 구조(출처: https://onseok.blog/lock-free/)

이 구조에서 공유 자원(Shared Resource)은 Queue입니다. 생산자가 push하는 동안 소비자는 pop을 못 하고, 소비자가 pop하는 동안 생산자는 push를 못 합니다. 여러 스레드들이 공유 자원을 놓고 경합을 벌이는 동안 Busy-waiting이 발생하고 Context Switching이 발생합니다. 물론 정말 리얼타임이 아니라 100ms~1000ms 정도의 딜레이가 허용된다면 생산자-소비자 패턴도 나쁘지 않은 선택입니다. 코드 복잡성과 CPU 가용률 측면에서 유리한 부분이 있습니다. SPSC/MPSC구조(Single Consumer)에서는 Lock이 필요하지 않기 때문에 이 패턴을 유용하게 사용할 수 있습니다.

고성능 프로그래밍에서는 Lock Free를 지향하기 때문에 여기서 더욱 발전된 형태의 구조를 사용해야 합니다.

 

CAS(Compare and Swap)

Compare and Swap(CAS, 비교 후 교환)은 동시성 제어를 위한 핵심 원자적 연산입니다. 락을 쓰지 않고 멀티스레드 환경에서 안전하게 데이터를 갱신할 수 있게 해주는 기본 빌딩 블록입니다. 멀티 스레드, 멀티 코어 환경에서 각 변수는 스레드 내의 스택(캐시)에 저장됩니다. 이 변수에 대해서 스레드에 저장된 값과 메인 메모리에 저장된 값을 비교하여 값이 같다면 새로운 값으로 치환해줍니다. 값이 다르면 계속 재시도를 합니다.

메인 메모리에 저장된 값과 CPU 캐시에 저장된 값이 다른 경우가 있는데 이를 가시성 문제라고 합니다. 이를 해결하기 위해 사용되는 것이 CAS 알고리즘입니다. 하드웨어 자원 측면에서 스레드간 충돌이 발생했을 때 이를 원자성으로 보장할 수 있는 방법입니다. 스레드 경합시 최신값을 유지하는 방식입니다.

CAS는 세 개의 값을 가지고 동작합니다.
1. 메모리 주소 (addr): 바꿀 값이 저장된 위치
2. 예상 값 (expected): 우리가 예상하는 현재 값
3. 새 값 (desired): 바꾸고 싶은 값

if (*addr == expected) {
    *addr = desired;
    return true;   // 성공
} else {
    expected = *addr;  // 실패 시 예상 값 갱신
    return false;
}

즉, 내가 바꾸려고 하는 값이 예상한 그대로라면 바꿔치기(성공, 진행)하고, 아니면 예상 값을 갱신(실패, 재시도)하는 방법입니다. 

std::atomic<int> x{10};
int expected = 10;
int desired  = 20;

if (x.compare_exchange_weak(expected, desired)) {
    // x == 20 으로 성공적으로 교체됨
} else {
    // 실패, expected에는 x의 실제 값이 들어있음
}

출처: https://www.semanticscholar.org/paper/Lock-free-linked-lists-using-compare-and-swap-Valois/c3c80b53e71dd65b66e712b99e19b21434cd43d3

CAS 알고리즘의 장점은 성능 그자체입니다. 높은 성능의 동시성 자료구조를 구현할 수 있습니다. 스레드 간 충돌이 있어도 전체 시스템이 멈추지 않고 계속 진행할 수 있습니다.

CAS 연산(출처: https://onseok.blog/lock-free/)

두 스레드 모두 메인 메모리에서 값 3을 읽습니다. Thread 2가 성공(녹색)하여 변수를 8로 업데이트합니다. Thread 1의 첫 번째 CAS는 값이 여전히 3이기를 기대하므로, CAS는 실패(빨간색)합니다. 따라서 Thread 1은 값을 다시 읽고, 두 번째 CAS는 성공합니다. 여기서 중요한 점은 CAS가 자료구조에 락을 획득하지 않고, 업데이트가 성공하면 'true'를 반환하고, 그렇지 않으면 'false'를 반환한다는 것입니다.

단점은 ABA문제와 Busy-wait이 있습니다. ABA는 값이 A -> B -> A로 변하면 CAS는 "안 바뀌었다"고 착각하게 됩니다. 이를 해결하기 위해 버전 번호를 붙이거나 별도의 Pointer를 달아주기도 합니다. 또한 스레드간 경합이 심해질 경우 CAS가 계속 실패하는데 이는 CPU낭비로 이어집니다. 경쟁 상태에서 락프리는 CPU를 태워서 기다리고 뮤텍스는 OS한테 맡기고 잠듭니다. "CPU 부하가 높더라도 Sleep보다는 좋지 않을까"라고 생각되는 부분입니다.

 

Lock-Free queue 예제

보편적으로 사용되는 Michael-Scott lock-free queue를 사용해보겠습니다. AI가 정리한 내용을 토대로 살펴보겠습니다.

// lock_free_queue_ms.hpp
#pragma once

#include <atomic>
#include <memory>
#include <optional>

// Michael-Scott lock-free queue (교육/실습용 구현)
// 주의: 생산 환경에서는 메모리 재사용/회수(ABA 방지)를 위한 추가 기법 필요.
// - 권장: Hazard pointers, Epoch-based reclamation, or use a well-tested library (boost::lockfree, folly).

template<typename T>
class LockFreeQueue {
private:
    struct Node {
        std::shared_ptr<T> data;       // shared_ptr로 데이터 수명 관리
        std::atomic<Node*> next;

        Node() : data(nullptr), next(nullptr) {}
        explicit Node(T const& value) : data(std::make_shared<T>(value)), next(nullptr) {}
    };

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

public:
    LockFreeQueue() {
        // 더미 노드로 초기화 (MS 알고리즘의 표준)
        Node* dummy = new Node();
        head.store(dummy, std::memory_order_relaxed);
        tail.store(dummy, std::memory_order_relaxed);
    }

    ~LockFreeQueue() {
        // 남아 있는 노드들 해제
        while (Node* old = head.load(std::memory_order_relaxed)) {
            head.store(old->next.load(std::memory_order_relaxed), std::memory_order_relaxed);
            delete old;
        }
    }

    // enqueue: 끝에 노드 추가
    void enqueue(T const& value) {
        Node* newNode = new Node(value);
        while (true) {
            Node* last = tail.load(std::memory_order_acquire);
            Node* next = last->next.load(std::memory_order_acquire);

            if (last == tail.load(std::memory_order_acquire)) {
                if (next == nullptr) {
                    // last->next가 비어있으면 새 노드를 연결 시도
                    if (std::atomic_compare_exchange_weak_explicit(
                            &last->next,
                            &next,
                            newNode,
                            std::memory_order_release,
                            std::memory_order_relaxed)) {
                        // 성공적으로 연결했으면 tail을 업데이트 시도
                        std::atomic_compare_exchange_weak_explicit(
                            &tail,
                            &last,
                            newNode,
                            std::memory_order_release,
                            std::memory_order_relaxed);
                        return;
                    }
                } else {
                    // 다른 스레드가 이미 연결했으므로 tail을 앞으로 당긴다
                    std::atomic_compare_exchange_weak_explicit(
                        &tail,
                        &last,
                        next,
                        std::memory_order_release,
                        std::memory_order_relaxed);
                }
            }
            // CAS 실패 시 루프 반복
        }
    }

    // try_pop: 성공하면 optional<T> 반환, 실패하면 nullopt
    std::optional<T> try_pop() {
        while (true) {
            Node* first = head.load(std::memory_order_acquire);
            Node* last  = tail.load(std::memory_order_acquire);
            Node* next  = first->next.load(std::memory_order_acquire);

            if (first == head.load(std::memory_order_acquire)) {
                if (first == last) {
                    if (next == nullptr) {
                        // 큐가 비어있음
                        return std::nullopt;
                    }
                    // tail이 뒤쳐져 있으므로 당겨준다
                    std::atomic_compare_exchange_weak_explicit(
                        &tail,
                        &last,
                        next,
                        std::memory_order_release,
                        std::memory_order_relaxed);
                } else {
                    // 실제로 pop 할 수 있는 노드(next)가 존재
                    std::shared_ptr<T> result = next->data;
                    // head를 next로 교체 (CAS)
                    if (std::atomic_compare_exchange_weak_explicit(
                            &head,
                            &first,
                            next,
                            std::memory_order_release,
                            std::memory_order_relaxed)) {
                        // 안전하게 첫 노드 삭제
                        // <-- 주의: 이 단계에서 메모리 재사용(ABA) 문제가 있을 수 있음.
                        delete first;
                        if (result) return *result;
                        else return std::nullopt;
                    }
                }
            }
            // CAS 실패 시 반복
        }
    }

    bool empty() const {
        Node* h = head.load(std::memory_order_acquire);
        Node* n = h->next.load(std::memory_order_acquire);
        return n == nullptr;
    }
};

 

1. 더미(dummy) 노드: MS 큐는 항상 하나의 더미 노드를 유지하여 head와 tail 업데이트를 단순화합니다. 실제 첫 유효 데이터는 head->next에서 시작합니다.
2. 원자성(atomic): head, tail, 그리고 각 노드의 next는 std::atomic<Node*>로 선언되어 CAS로 갱신합니다.
3. enqueue 흐름:
   • tail과 tail->next를 읽고, tail->next가 nullptr이면 여기에 새 노드를 CAS로 연결.
   • 연결 성공하면 tail을 새 노드로 CAS로 이동(실패해도 무해).
4. dequeue 흐름:
   • head, tail, head->next를 읽는다.
   • head == tail 이고 head->next == nullptr이면 큐는 비어있음.
   • head != tail이면 head를 head->next로 CAS로 옮기고, 성공 시 이전 head는 삭제.

 

추가 체크 포인트

1. ABA 문제: 포인터가 A -> B -> A처럼 재사용되면 CAS가 성공해도 잘못된 상태가 될 수 있음. 이 문제를 해결하려면 포인터에 태그(카운터)를 붙이거나 Hazard Pointers / epoch-based reclamation 등을 사용해야 합니다.
2. 메모리 재사용 및 안전한 삭제: 위 구현은 간단화 위해 delete first;를 사용했습니다. 하지만 다른 스레드가 여전히 해당 노드 주소를 참조하고 있을 수 있으므로 안전하지 않을 수 있습니다. 안전한 방법:
   • Hazard pointers (권장) — 노드를 접근 중인 스레드를 명시적으로 표시해서 안전할 때만 삭제.
   • Epoch-based reclamation (더 빠름, 복잡성 있음).
   • 혹은 이미 검증된 구현 사용: boost::lockfree::queue, Folly, concurrency kit 등.
3. 메모리 오버헤드 vs 성능: shared_ptr를 노드 데이터에 사용하면 안전하나 할당/참조 카운트 비용이 생깁니다. 초고성능(low-latency) 환경에서는 hazard/epoch 방식으로 raw pointer와 빠른 reclamation 조합이 선호됩니다.

 

조금 더 쉬운 버전인 CAS stack 예제도 함께 보겠습니다.

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

template <typename T>
struct Node {
    T value;
    Node* next;
    Node(T v) : value(v), next(nullptr) {}
};

template <typename T>
class LockFreeStack {
private:
    std::atomic<Node<T>*> head;

public:
    LockFreeStack() : head(nullptr) {}

    void push(T value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = head.load(std::memory_order_relaxed);

        // head를 newNode로 교체 시도 (CAS 루프)
        while (!head.compare_exchange_weak(
            newNode->next, newNode,
            std::memory_order_release,
            std::memory_order_relaxed)) {
            // 실패하면 newNode->next를 최신 head로 갱신하고 재시도
        }
    }

    bool pop(T& result) {
        Node<T>* oldHead = head.load(std::memory_order_relaxed);

        // head를 oldHead->next로 교체 시도 (CAS 루프)
        while (oldHead != nullptr &&
               !head.compare_exchange_weak(
                   oldHead, oldHead->next,
                   std::memory_order_acquire,
                   std::memory_order_relaxed)) {
            // 실패 시 oldHead가 최신 값으로 자동 갱신됨
        }

        if (oldHead == nullptr) return false;

        result = oldHead->value;
        delete oldHead;
        return true;
    }
};

int main() {
    LockFreeStack<int> stack;

    // 여러 스레드에서 동시에 push/pop
    std::thread t1([&]() {
        for (int i = 0; i < 5; i++) stack.push(i);
    });

    std::thread t2([&]() {
        for (int i = 5; i < 10; i++) stack.push(i);
    });

    t1.join();
    t2.join();

    int value;
    while (stack.pop(value)) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

CAS 기반의 Lock-Free Stack 기본 형태입니다. 락 없이 여러 스레드가 동시에 `push`와 `pop`을 안전하게 수행할 수 있습니다. 두 예제 모두 ABA 해결 전략과 메모리 회수 전략이 필수입니다. 보여드린 예제에서는 간단한 예제에서는 문제가 없지만 복잡한 실무에서는 추가적인 예외 장치가 반드시 필요할 것입니다. 그리고 C++에서의 compare_exchange_weak, memory_order는 따로 포스팅을 진행할 계획입니다. 

 

Lock-free구조(출처: https://onseok.blog/lock-free/)

마치며

CAS를 통한 경쟁상태 해결방식은 기존 Lock과는 조금 다릅니다. while문을 대기없이 무한루프처럼 반복하면서 waiting을 하는 모습입니다. 누군가는 backoff 전략으로 1~10ns sleep을 적용한다고 하지만, 이는 문맥 교환이 발생할 여지가 있습니다. 대기 없는 polling이 어쩌면 성능에는 가장 좋은 전략이 아닐까 싶습니다. Lock Free의 기초개념인 CAS 알고리즘은, CPU가 진행하려는 흐름을 OS 간섭(Context Switching) 없이 캐시 지역성을 높일 수 있는 중요 개념이라고 생각합니다.

 

 

참고

https://onseok.blog/lock-free/

https://en.wikipedia.org/wiki/Compare-and-swap