Lock-based-Stack / Queue

🚀 개요

멀티스레드 환경에서 자료구조를 안전하게 사용하려면, 동기화는 필수다. 특히 Stack, Queue와 같은 구조는 여러 쓰레드가 동시에 Push/Pop 작업을 시도할 수 있기 때문에, 데이터 경합(Race Condition) 이 발생할 가능성이 높다.

이때 우리는 두 가지 방법을 사용할 수 있다:

• 🔒 Lock-Based 방식: mutex를 사용해 간단하고 직관적으로 구현
• 🔓 Lock-Free 방식: 락을 사용하지 않고 성능을 높이는 고급 방식

이번 글에서는 Lock-Based Stack과 Queue를 집중적으로 다루고, 마지막에 Lock-Free 구조에 대한 실마리도 소개한다.

---

✅ 핵심

방식	특징
Lock-Based Stack/Queue	mutex와 condition_variable을 이용하여 간단하게 동기화
TryPop vs WaitPop	TryPop은 즉시 반환, WaitPop은 대기 후 처리
Lock-Free 구조	성능은 높지만 구현이 복잡하고 위험요소 존재 (ABA, 삭제 중 접근 등)

---

🧵 Lock-Based Stack – 구현 및 분석

🔧 구현 코드

#pragma once
#include <stack>
#include <mutex>
#include <condition_variable>

template<typename T>
class LockStack
{
public:
    LockStack() = default;
    LockStack(const LockStack&) = delete;
    LockStack& operator=(const LockStack&) = delete;

    void Push(T value)
    {
        std::lock_guard<std::mutex> lock(_mutex);
        _stack.push(std::move(value));
        _condVar.notify_one();
    }

    bool TryPop(T& value)
    {
        std::lock_guard<std::mutex> lock(_mutex);
        if (_stack.empty())
            return false;

        value = std::move(_stack.top());
        _stack.pop();
        return true;
    }

    void WaitPop(T& value)
    {
        std::unique_lock<std::mutex> lock(_mutex);
        _condVar.wait(lock, [this] { return !_stack.empty(); });
        value = std::move(_stack.top());
        _stack.pop();
    }

private:
    std::stack<T> _stack;
    std::mutex _mutex;
    std::condition_variable _condVar;
};

📌 주요 특징

• Push: 락을 잡고 안전하게 데이터 추가
• TryPop: 즉시 Pop 시도, 실패 시 false 반환
• WaitPop: 데이터가 들어올 때까지 기다림 (Condition Variable)

---

📥 Lock-Based Queue – 구현 및 분석

#pragma once
#include <queue>
#include <mutex>
#include <condition_variable>

template<typename T>
class LockQueue
{
public:
    LockQueue() = default;
    LockQueue(const LockQueue&) = delete;
    LockQueue& operator=(const LockQueue&) = delete;

    void Push(T value)
    {
        std::lock_guard<std::mutex> lock(_mutex);
        _queue.push(std::move(value));
        _condVar.notify_one();
    }

    bool TryPop(T& value)
    {
        std::lock_guard<std::mutex> lock(_mutex);
        if (_queue.empty())
            return false;

        value = std::move(_queue.front());
        _queue.pop();
        return true;
    }

    void WaitPop(T& value)
    {
        std::unique_lock<std::mutex> lock(_mutex);
        _condVar.wait(lock, [this] { return !_queue.empty(); });
        value = std::move(_queue.front());
        _queue.pop();
    }

private:
    std::queue<T> _queue;
    std::mutex _mutex;
    std::condition_variable _condVar;
};

---

🧪 실습 예제: Producer/Consumer 구현

#include "ConcurrentQueue.h"
#include <thread>
#include <iostream>
#include <chrono>

LockQueue<int> gQueue;

void Producer()
{
    while (true)
    {
        int value = rand() % 100;
        gQueue.Push(value);
        std::this_thread::sleep_for(std::chrono::milliseconds(10));
    }
}

void Consumer()
{
    while (true)
    {
        int value = 0;
        if (gQueue.TryPop(value))
            std::cout << "Consumed: " << value << std::endl;
    }
}

int main()
{
    std::thread t1(Producer);
    std::thread t2(Consumer);
    std::thread t3(Consumer);

    t1.join();
    t2.join();
    t3.join();
}

💡 팁

• TryPop은 데이터를 즉시 꺼내고 싶을 때,
• WaitPop은 대기 후 안전하게 꺼내고 싶을 때 사용하면 좋다.

---

🚧 C++의 pop() 주의점

// C++ 표준 스택, 큐의 pop()은 void 반환
// 따라서 top() → pop() 순으로 접근해야 함
// BUT! 멀티스레드 환경에서는 비추천 ⚠️

empty() → top() → pop() 순은 race condition 발생 가능
🔥 크래시 나더라도 TryPop으로 처리하는 방식이 더 안전함

---

💣 Lock-Free Stack이란?

• 락 없이 멀티스레드 접근을 허용
• ABA 문제, 접근 중 삭제 등의 위험 존재
• InterlockedCompareExchange128 같은 저수준 함수 사용
• 고성능이지만 복잡도와 디버깅 난이도가 높다

void PushEntyrSList(SListHeader* header, SListEntry* entry)
{
    SListHeader expected = *header;
    // ...
    ::InterlockedCompareExchange128(...);
}

🚧 Lock-Free 구조는 다음 포스트에서 더 깊이 있게 다룰 예정!

---