Lock free stack

Lock free stack을 구현해보자. 먼저 링크드 리스트 자료구조를 이용해 stack을 만든다.

 

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

		}

		T data;
		Node* next;
	};
public:

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

		_head = node;
	}

private:
	atomic<Node*> _head;
};

 

위 코드가 싱글 쓰레드에서 작동할 때는 문제가 없다. 그러나 멀티 쓰레드 환경에서 작동하면, _head를 여러 쓰레드에서 동시에 접근 가능할 때 문제가 생긴다. 예를 들어 1)node->next를 _head 가리키고 2)_head를 node가리키기 전에 다른 쓰레드가 1)을 하면 node가 의도치않은 node를 가리키는 문제가 발생한다.

 

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


    //if (_head == node->next)
    //{
    //	_head = node;
    //	return true;
    //}
    //else
    //{
    //	node->next = _head;
    //	return false;
    //}
    // 위의 코드를 아래 구문으로 원자적으로 실행
    while (_head.compare_exchange_weak(node->next, node) == false)
    {
        // node->next = _head;
    }

    //_head = node;
}

 

위 처럼 compare_exchange를 이용하여 경합상황을 처리한다.

같은 방법으로 TryPop을 구현한다.

 

// 1) head를 읽는다.
// 2) head->next 읽기
// 3) head = head -> next
// 4) 데이터 추출 반환
// 5) 추출한 노드 삭제
bool TryPop(T& value)
{
    Node* oldHead = _head;

    //if (_head == oldHead)
    //{
    //	_head = oldHead->next;
    //	return true;
    //}
    //else
    //{
    //	oldHead = _head;
    //	return false;
    //}

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

    }

    if (oldHead == nullptr)
        return false;

    // 메모리 복사할 때 메모리 고갈등
    // exception은 신경쓰지 않는다.
    value = oldHead->data;

    // 잠시 삭제 보류
    // delete oldHead; // oldHead 삭제할 때 다른 쓰레드에서 접근 중이면 크래시!!

    return true;
}

 

이번에 만든 lock free stack은 메모리 해제 기능이 없어서 메모리가 계속 증가한다. 이를 해결하기 위한 방법은 다음 포스팅에서 알아보자.

 

참조 : [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part4: 게임 서버 - 인프런 | 강의 (inflearn.com)