[C++] Lock-Based Stack 구현

mutex 기반으로 작성하고, condition variable로 단점을 보완해 본다

mutex 기반

틀

#include <mutex>

template<typename T>
class LockStack
{
public:
	LockStack() {}
	
	LockStack(const LockStack&) = delete;
	LockStack& operator=(const LockStack&) = delete;
	
private:
	stack<T> _stack;
	mutex _mutex;
};

push 연산

	void Push(T value)
	{
		lock_guard<mutex> lock(_mutex);
		_stack.push(std::move(value));	
	}

• lock_guard 이용
• cf) 이동이 가능한 것들은, move를 이용해서 빠른 연산 지원

pop 연산

• 고전적으로는 empty() 연산으로 체크 후, top, pop 실행: empty → top → pop
• 하지만, 멀티 스레드 환경이라면 데이터 불일치 상황이 가능함 (다른 스레드가 중간에 연산하는 경우가 가능)

	bool TryPop(&outValue)
	{
		lock_guard<mutex> lock(_mutex);
		if (_stack.empty())
		{
			return false;
		}
		
		outValue = std::move(_stack.top());
		_stack.pop();
		return true;
	}

• mutex로 락을 걸어두고, empty → top → pop
• 지금 구현에서는 한 번에 꺼내는 연산 지원
  • cf) top(), pop() 나눠서 하는 이유 : 한 번에 꺼낸다면, 크래쉬 발생 가능성이 존재
    • 메모리가 부족해서 복사과정에서 익셉션이 발생한다면, 자료구조가 망가짐
    • 따라서, 두 단계로 나눔
    • 다만, 그런 크래쉬라면 뻗게 두는 게 나을 것임 (익셉션처리가 아닌)

전체 코드

#include <mutex>

template<typename T>
class LockStack
{
public:
	LockStack() {}
	
	LockStack(const LockStack&) = delete;
	LockStack& operator=(const LockStack&) = delete;
	
	void Push(T value)
	{
		lock_guard<mutex> lock(_mutex);
		_stack.push(std::move(value));	
	}
	
	bool TryPop(&outValue)
	{
		lock_guard<mutex> lock(_mutex);
		if (_stack.empty())
		{
			return false;
		}
		
		outValue = std::move(_stack.top());
		_stack.pop();
		return true;
	}
	
private:
	stack<T> _stack;
	mutex _mutex;
};

아쉬운 점 (busy waiting)

데이터가 없더라도 데이터가 있는지 없는지를 체크할 수 없으니까, TryPop을 무한루프로 처리해야 한다. TryPop의 반환값이 false 임을 통해서 데이터가 없음을 확인하게 되는 것이다.

 

🔥 데이터가 채워지면 pop 할 수 있도록 하자

condition variable 기반

틀

#include <mutex>

template<typename T>
class LockStack
{
public:
	LockStack() {}
	
	LockStack(const LockStack&) = delete;
	LockStack& operator=(const LockStack&) = delete;
	
private:
	stack<T> _stack;
	mutex _mutex;
	condition_variable _condVar;
};

• 멤버변수로 condition_variable을 추가

push 연산

	void Push(T value)
	{
		lock_guard<mutex> lock(_mutex);
		_stack.push(std::move(value));	
		// TODO: 여기서 락 해제하는것이 좋을 것
		
		_condVar.notify_one(); // 대기하고있는 하나를 깨움
	}

pop 연산

	void WaitPop(T& outValue)
	{
		unique_lock<mutex> lock(_mutex); // condition variable 은 내부적으로 락을 풀었다가 막(?) 하기 때문에, lock_guard가 아닌 unique_lock 사용. 
		_condVar.wait(lock, [this] { return _stack.empty() == false; }); // 1. 인수로 unique_lock을 받음을 확인할 수 있음 2. predicate로 조건(데이터가 존재할때까지)
		// 락을 잡아서 들어갔다가, 조건을 체크해서
		// 만약 조건을 만족하지 않으면
		//    락을 풀어주고, 잠든다.
		
		// push연산 수행되면 (시그널(notify_one)의 발생), 일어나서 락을 잡고 다시 실행됨
		
		outValue = std::move(_stack.top());
		_stack.pop();
	}

 

전체코드

#include <mutex>

template<typename T>
class LockStack
{
public:
	LockStack() {}
	
	LockStack(const LockStack&) = delete;
	LockStack& operator=(const LockStack&) = delete;
	
	void Push(T value)
	{
		lock_guard<mutex> lock(_mutex);
		_stack.push(std::move(value));	
		// TODO: 여기서 락 해제하는것이 좋을 것
		
		_condVar.notify_one(); // 대기하고있는 하나를 깨움
	}
	
	bool TryPop(&outValue)
	{
		lock_guard<mutex> lock(_mutex);
		if (_stack.empty())
		{
			return false;
		}
		
		outValue = std::move(_stack.top());
		_stack.pop();
		return true;
	}
	
	void WaitPop(T& outValue)
	{
		unique_lock<mutex> lock(_mutex); // condition variable 은 내부적으로 락을 풀었다가 막(?) 하기 때문에, lock_guard가 아닌 unique_lock 사용. 
		_condVar.wait(lock, [this] { return _stack.empty() == false; }); // 1. 인수로 unique_lock을 받음을 확인할 수 있음 2. predicate로 조건(데이터가 존재할때까지)
		// 락을 잡아서 들어갔다가, 조건을 체크해서
		// 만약 조건을 만족하지 않으면
		//    락을 풀어주고, 잠든다.
		
		// push연산 수행되면 (시그널(notify_one)의 발생), 일어나서 락을 잡고 다시 실행됨
		
		outValue = std::move(_stack.top());
		_stack.pop();
	}
	
private:
	stack<T> _stack;
	mutex _mutex;
    condition_variable _condVar;
};

 

이로써, busy waiting 문제를 해결했다.