Lock Free Stack

Date: 2024.06.11 Updated: 2024.06.11

카테고리: Server

태그: Cpp CS

인프런에 있는 루키스님의 게임 서버 강의를 듣고 정리한 내용입니다.

Lock Free Structure

Lock Free 방식은 mutex와 같은 lock을 사용하지 않고 동기화 하는 방식이다. 물론 경합을 방지하기 위한 Compare-And-Swap 방식이 필요한건 마찬가지이지만 몇몇 상황에서는 충분한 장점이 존재한다. 예를 들어 Queue를 이용한 생성자-소비자 모델에서 Queue에 충분한 데이터가 담겨있다고 생각해보자. 데이터의 이때 Push/Pop은 Queue의 양 끝에서 발생하는데, 서로 lock을 걸면 불필요한 오버헤드가 발생하는 꼴이다. 따라서 이런 경우 Lock Free 방식의 이점이 존재하지만 기본적으로 Lock Free 구조는 구현하기가 매우 까다롭고 코드를 읽기도 어렵다.

Lock Free Stack

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;
	atomic<uint32> _popCount = 0;
	atomic<Node*> _pendingList;
};

Node

struct Node {
    Node(const T& value) : data(value), next(nullptr) {}

    T data;
    Node* next;
};

Lock Free 기반 Structure는 기본적으로 Node기반 List를 사용한다. 그 이유에 대해 생각해봤는데, 일단 멀티 쓰레드 환경이므로 데이터의 삽입/삭제가 매우 자주 일어날 것이다. 또한 동적 크기의 확장도 자주 일어날 수 있기 때문에 리스트 기반으로 작성한 듯하다.

Push

원래 Push는 아래와 같이 동작해야 한다.

1) 새로운 노드 생성
2) 새 노드의 next = head
3) head = 새 노드

이때 아래와 같은 상황을 고려해야 한다.

1) 새로운 노드 생성
2) 새 노드의 next = head
다른 쓰레드의 개입으로 _head != node->next 상황 발생
3) node->next = 수정된 _head
4) _head = 새 노드

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

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

    }
}

따라서 Push의 경우 새로 생성한 노드를 head로 바꾸는 과정에서 Atomic한 CAS 연산이 필요하다. compare_exchange_weak 함수는 atomic 클래스에 정의된 함수이다. 기본적으로 bool compare_exchange_weak(T& expected, T desired); 형태인데, atomic객체(_head)가 expected(node->next)와 같으면 desired로 값을 바꾼 후(_head = node) ture를 리턴한다. 반면 expected와 값이 다르다면, expected값을 atomic 객체(_head)로 바꾼 후 false를 리턴한다. 정리하자면 아래 코드를 atomic하게 실행한다고 보면 된다.

// _head.compare_exchange_weak(node->next, node) 

if (_head == node->next) {
    _head = node;
    return true;
}

else {
    node->next = _head;
    return false;
}

Pop

Pop의 작동 방식을 보면 아래와 같다.

1) head 읽기
2) head->next 읽기
3) head = head->next
4) data 추출해서 반환
5) 추출한 노드 삭제

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;
}

먼저 당연한 이야기지만 멀티 쓰레드 환경이므로 empty체크를 별도의 함수에서 하는 것은 의미가 없다. 따라서 empty체크를 겸해서 TryPop으로 구현하고, 성공 여부를 bool 값으로 리턴해준다. 또 하나 주의해야 할 점은 oldHead를 추출하고 데이터를 지울 때이다. 서로 다른 쓰레드가 TryPop을 거의 동시에 수행한다고 하면, CAS에 사용되고 있는 oldHead는 use-after-free 문제가 발생한다. 따라서 oldHead는 아무도 참조하지 않을 때까지 기다렸다가 삭제해야 한다. Smart Pointer의 Reference Counter와 매우 비슷한 상황이기 때문에 여기서도 Pop Count를 추적해서 만약 누군가가 사용하고 있다면 삭제 리스트(PendingList)에 노드를 담아두고 나중에 삭제해주는 방식을 택한다.

// 1) 데이터 분리
// 2) Count 체크
// 3) 나 혼자면 삭제
void TryDelete(Node* oldHead)
{
    // 나 이외에 누가 있는가?
    if (_popCount == 1)
    {
        // 이왕 혼자인거, 삭제 예약된 다른 데이터들도 삭제
        Node* node = _pendingList.exchange(nullptr);

        if (--_popCount == 0)
        {
            // 중간에 끼어든 애 없음 -> 삭제 진행
            // 이제와서 끼어들어도, 어차피 데이터는 분리되어 있어서 상관 없음
            DeleteNodes(node);
        }

        else if (node)
        {
            // 누가 끼어들었으니 다시 가져다 놓기 (기존의 pendingList를 누군가 참조하고 있다는 의미)
            ChainPendingNodeList(node);
        }

        // 내 데이터는 삭제
        delete oldHead;
    }

    else
    {
        // 누가 쓰고 있으니 삭제하지 않고 예약만
        ChainPendingNode(oldHead);
        --_popCount;
    }
}

Test

LockFreeStack<int32> s;

void Push()
{
	while (true) {
		int32 value = rand() % 100;
		s.Push(value);

		// this_thread::sleep_for(10ms);
	}
}

void Pop()
{
	while (true) {
		int32 data = 0;
		if (s.TryPop(OUT data))
			cout << data << endl;
	}
}

int main()
{
	thread t1(Push);
	thread t2(Pop);
	thread t3(Pop);

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

GameServer-MicrosoftVisualStudio2024-06-1202-29-17-ezgif com-video-to-gif-converter

Lock Free Stack의 경우 Push는 비교적 간단하지만, Pop을 하기 위해서는 경합 방지를 위한 여러 장치가 필요하다. 따라서 위 코드의 경우 Push를 하는 쓰레드 하나, Pop을 하는 쓰레드가 둘임에도 불구하고 Push하는 data가 훨씬 많아서 사용하는 메모리가 계속 증가하는 것을 볼 수 있다.

LockFreeStack<int32> s;

void Push()
{
	while (true) {
		int32 value = rand() % 100;
		s.Push(value);

		this_thread::sleep_for(10ms);
	}
}

void Pop()
{
	while (true) {
		int32 data = 0;
		if (s.TryPop(OUT data))
			cout << data << endl;
	}
}

int main()
{
	thread t1(Push);
	thread t2(Pop);
	thread t3(Pop);

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

GameServer-MicrosoftVisualStudio2024-06-1202-29-37-ezgif com-video-to-gif-converter

반면 Push를 하는 쓰레드에 Sleep_for 함수를 넣어주면 얼추 속도가 맞아 메모리의 사용량이 일정하게 유지되는 것을 볼 수 있다.

맨 위로 이동하기

등딱지빌런

Lock Free Stack

Lock Free Structure

Lock Free Stack

Node

Push

Pop

Test

Server 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)