13. Lock-Free Stack #1

전에 락 기반 큐/스택을 만들어 보았는데 이번에는 락을 사용하지 않는 스택에 대해 알아보자.

Lock-Free는 이름만 보면 락을 사용하지 않아 더 빠를 것이라고 생각이 되는데 실상은 그렇지 않다.

락을 사용하지 않기 때문에 동기화 작업을 해주어야 하고 그로 인해서 성능 차이가 거의 나지 않는다고 볼 수 있다.

 

락 프리 스택은 락 기반 스택처럼 기존의 스택을 락으로 감싸는 형식이 아니라 아예 새로 만들어야 한다.

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

		T data;
		Node* next;
	};
public:

private:
	atomic<Node*> _head;
};

기본적인 스택의 틀이다. 이제 Push와 Pop을 만들어보자.

 

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

싱글스레드라면 위와 같이 구현을 하면 문제없이 잘 돌아간다. 하지만 멀티스레드는 다르다. 딱 보면 알 수 있듯이 node->next에 head를 넣는 작업과 head에 node를 넣는 작업 사이에 다른 스레드가 접근하게 되면 한 노드는 버려지게 된다.(접근조차 할 수 없게 되어버린다!) 따라서 CAS 기법을 사용하여 이러한 문제를 해결해야 한다.

 

void Push(const T& value)
{
	Node* node = new Node(value);
	node->next = _head;
    
	while (_head.compare_exchange_strong(node->next, node) == false)
	{
	}
	/*
	compare_exchange_strong 작동방식
	if (_head == node->next)
	{
		_head = node;
        
		return true;
	}
	else
	{
		node->next = _head;

		return false;
	}
	*/
}

compare_exchange_strong을 활용하여 Push함수를 수정한 모습이다. 예전의 코드에서는 while문 안에서 초기값을 다시 세팅해주었는데 공교롭게도 이 코드의 경우 compare_exchange_strong를 만족하지 못할 경우 실행되는 node->next = _head의 과정이 우리가 원하는 과정과 같으므로 따로 초기화를 해주지 않았다.

 

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

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

	if (oldHead == nullptr)
		return false;

	value = oldHead->data;

	//문제 발생
	delete oldHead;
	return true;
}

지난 글과 같이 TryPop을 간단히 만들어 보았다. oldHead라는 변수를 두어 _head와 CAS을 해주도록 하였다. oldHead가 null일 수 있으므로 while문에 조건을 추가하였다. 문제 없어보이는 이 코드도 delete를 할 때 문제가 생기는데 서로 다른 스레드에서 oldHead가 같은 노드를 가르키고 있을 수가 있다. 이 때 한 스레드가 그 노드를 삭제하게 되면 다른 스레드는 가르킬 수 없는 위치를 가르키게 되므로 크래시가 나버리게 된다. C#이나 Java의 경우는 가비지 컬렉터가 있으므로 따로 delete를 해주지 않아도 자동으로 메모리를 해제해주기 때문에 delete를 해주는 코드를 빼면 해결이 된다. 하지만 C++은 그러한 기능이 없으므로 다른 방법을 사용해야 한다. 아무도 그 노드를 참조하지 않을 때까지 기다렸다가 해제를 해주는 것이 핵심으로 구현 방법은 여러가지이다.

 

락 프리는 현재 많은 연구가 이루어지고 있고 논문 뿐만 아니라 특허로 등록 되어있는 기법도 있다고 한다. 그래서 어떠한 기법을 알더라도 실제로 상용화 할 때 사용할 수 있을지는 미지수라고 한다.(새로운 사실을 알게 되었다...)