Lock-Free-Stack

🔄 Step 1 – 단순 구현 (싱글 쓰레드용)

template<typename T>
class LockFreeStack
{
    struct Node
    {
        Node(const T& value) : data(value), next(nullptr) {}
        T data;
        Node* next;
    };

    atomic<Node*> _head;

public:
    void Push(const T& value)
    {
        Node* node = new Node(value);
        node->next = _head;
        _head = node; // ❌ 멀티쓰레드에서 위험
    }

    bool TryPop(T& value)
    {
        Node* oldHead = _head;
        if (oldHead == nullptr)
            return false;

        _head = oldHead->next;
        value = oldHead->data;
        delete oldHead;
        return true;
    }
};

✅ 작동은 되지만 멀티스레드 환경에서는 위험하다. 동시에 _head를 변경하려는 쓰레드들이 충돌하게 된다.

---

🔄 Step 2 – compare_exchange_weak 도입

void Push(const T& value)
{
    Node* node = new Node(value);
    node->next = _head;

    while (_head.compare_exchange_weak(node->next, node) == false)
    {
        // node->next는 자동으로 _head로 갱신됨
    }
}

• compare_exchange_weak(expected, desired)
_head == expected일 경우에만 _head = desired
• 이 연산은 원자적으로 수행된다!

---

🧨 TryPop 시 메모리 해제 문제

bool TryPop(T& value)
{
    Node* oldHead = _head;

    while (oldHead && !_head.compare_exchange_weak(oldHead, oldHead->next))
        ;

    if (!oldHead)
        return false;

    value = oldHead->data;
    // ❌ delete oldHead 는 위험하다! 다른 쓰레드가 접근 중일 수 있음
    return true;
}

delete oldHead 시점에 다른 쓰레드가 oldHead를 참조하고 있을 가능성이 있어 크래시가 발생할 수 있다.

---

🧠 Step 3 – 안전한 삭제를 위한 _popCount & _pendingList 도입

atomic<uint32> _popCount = 0;
atomic<Node*> _pendingList = nullptr;

TryPop

bool TryPop(T& value)
{
    ++_popCount;

    Node* oldHead = _head;
    while (oldHead && !_head.compare_exchange_weak(oldHead, oldHead->next))
        ;

    if (!oldHead)
    {
        --_popCount;
        return false;
    }

    value = oldHead->data;
    TryDelete(oldHead);
    return true;
}

TryDelete

void TryDelete(Node* oldHead)
{
    if (_popCount == 1)
    {
        Node* pending = _pendingList.exchange(nullptr);
        if (--_popCount == 0)
            DeleteNodes(pending);
        else if (pending)
            ChainPendingNodeList(pending);

        delete oldHead;
    }
    else
    {
        ChainPendingNode(oldHead);
        --_popCount;
    }
}

---

🛠️ Step 4 – Smart Pointer 버전 (shared_ptr)

struct CountedNodePtr
{
    int externalCount = 0;
    Node* ptr = nullptr;
};

struct Node
{
    shared_ptr<T> data;
    atomic<int> internalCount = 0;
    CountedNodePtr next;

    Node(const T& value) : data(make_shared<T>(value)) {}
};

Push

void Push(const T& value)
{
    CountedNodePtr node;
    node.ptr = new Node(value);
    node.externalCount = 1;
    node.ptr->next = _head;

    while (!_head.compare_exchange_weak(node.ptr->next, node))
        ;
}

TryPop

shared_ptr<T> TryPop()
{
    CountedNodePtr oldHead = _head;
    while (true)
    {
        IncreaseHeadCount(oldHead);
        Node* ptr = oldHead.ptr;

        if (!ptr)
            return shared_ptr<T>();

        if (_head.compare_exchange_strong(oldHead, ptr->next))
        {
            shared_ptr<T> res;
            res.swap(ptr->data);

            int countIncrease = oldHead.externalCount - 2;
            if (ptr->internalCount.fetch_add(countIncrease) == -countIncrease)
                delete ptr;

            return res;
        }
        else if (ptr->internalCount.fetch_sub(1) == 1)
        {
            delete ptr;
        }
    }
}

---

❓ compare_exchange_strong vs weak

구분	설명
compare_exchange_weak	간헐적 실패(spurious fail) 허용, 반복문에서 빠름
compare_exchange_strong	신뢰성 높지만 느릴 수 있음

💡 루프 안에서 계속 시도할 거라면 weak가 유리
단발성으로 확실하게 성공해야 할 땐 strong을 쓰자!

---