[Server] Lock Free Stack (上편)

 

 

Lock-Free Stack 학습 정리 (上편)

 

멀티스레드 환경에서 Stack을 공유할 경우, 일반적으로는 mutex를 사용해 동기화합니다.
하지만 잠금(lock)은 성능을 떨어뜨릴 수 있습니다.

그래서 오늘은 Lock-Free Stack, 즉 락 없이 작동하는 스택에 대해 공부했습니다!

compare_exchange_weak 같은 CAS(Compare-And-Swap) 연산을 사용해서 락 없이도
다중 스레드 환경에서 안전하게 Push와 Pop을 수행할 수 있다는 게 핵심입니다.

 

---

 

 

Lock-Free Stack이란?

 

Lock-Free Stack은 이름 그대로 락(mutex 등)을 사용하지 않고도 멀티스레드 환경에서 안전하게 동작하는 자료구조입니다.
이 스택은 atomic 포인터와 연산을 기반으로 구현되며, 핵심은 다음 두 가지입니다.

1. Push 연산: 스택에 새 노드를 추가
2. TryPop 연산: 스택에서 데이터를 꺼내되, 동시에 다른 스레드와 충돌 없이 동작

 

 

핵심 요약

• head: 스택의 가장 위 노드를 가리키는 atomic<Node*>
• popCount: 현재 Pop 작업을 수행 중인 스레드 수
• pendingList: 삭제 예약된 노드들의 연결 리스트

노드 삭제 시점이 중요하기 때문에 나 외에 Pop 중인 스레드가 있는지 확인한 후 혼자라면 삭제를 진행하고

아니면 삭제 예약만 해두는 식입니다.

 

---

 

주요 함수별 설명

Push

1. 새 노드를 생성
2. 새 노드의 next를 현재 head로 설정
3. CAS로 head를 새 노드로 교체 (실패하면 다시 시도)

TryPop

1. 현재 head를 읽고
2. head를 head->next로 교체 (CAS 반복)
3. 데이터를 가져온 후 삭제 예약 혹은 직접 삭제

TryDelete

• 내가 Pop을 수행 중인 유일한 스레드면 → 직접 삭제
• 그렇지 않으면 → pendingList에 삭제 예약

---

 

예시 코드

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

		T data;
		Node* next;
	};

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

		while (_head.compare_exchange_weak(node->next, node) == false)
		{
		}
	}

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

		Node* oldHead = _head;

		while (oldHead && _head.compare_exchange_weak(oldHead, oldHead->next) == false)
		{
		}

		if (oldHead == nullptr)
		{
			--_popCount;
			return false;
		}

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

	void TryDelete(Node* oldHead)
	{
		if (_popCount == 1)
		{
			Node* node = _pendingList.exchange(nullptr);

			if (--_popCount == 0)
			{
				DeleteNodes(node);
			}
			else if (node)
			{
				ChainPendingNodeList(node);
			}

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

	void ChainPendingNodeList(Node* first, Node* last)
	{
		last->next = _pendingList;

		while (_pendingList.compare_exchange_weak(last->next, first) == false)
		{
		}
	}

	void ChainPendingNodeList(Node* node)
	{
		Node* last = node;
		while (last->next)
			last = last->next;

		ChainPendingNodeList(node, last);
	}

	void ChainPendingNode(Node* node)
	{
		ChainPendingNodeList(node, node);
	}

	static void DeleteNodes(Node* node)
	{
		while (node)
		{
			Node* next = node->next;
			delete node;
			node = next;
		}
	}

private:
	atomic<Node*> _head = nullptr;
	atomic<uint32> _popCount = 0;
	atomic<Node*> _pendingList = nullptr;
};

 

---

정 리

• compare_exchange_weak는 반복문에서 사용하는 게 일반적이다. (성공할 때까지 반복)
• 메모리 해제 타이밍이 중요하기 때문에 삭제를 지연시키는 전략 중요!!

 

다음 포스팅에서는 Lock Free Stack 下편을 다루겠습니다.

 

끝!