Lock-Based
Lock-Based Stack/Queue라는 것은 멀티쓰레드 환경에서 작동할 수 있도록 하기 위해 기존 자료구조에 Locking을 더해 하나의 자료구조로 동작할 수 있는 자료구조이다.
Lock-Based 자료구조를 구현하기 위해 해당 자료구조, lock을 위한 객체가 필요하고 lock 객체는 여러개가 될 수 있다.
1. stack/queue
기존의 stack과 queue를 사용하려면 아래와 같은 방식으로 사용할 수 있다.
queue<int32> q;
stack<int32> s;
void Push() {
while (true) {
int32 value = rand() % 100;
q.push(value);
this_thread::sleep_for(10ms);
}
}
void Pop() {
while (true) {
if (q.empty())
continue;
int32 data = q.front();
q.pop();
cout << data << endl;
}
}
int main() {
thread t1(Push);
thread t2(Pop);
thread t3(Pop);
t1.join();
t2.join();
t3.join();
return 0;
}1개의 Push 쓰레드와 2개의 Pop 쓰레드가 존재하는데 위의 코드를 보면 Lock을 하지 않는다. 즉, 임계영역을 형성하기 위해서 자료구조를 사용하기 전에 lock_guard<mutex>(mutex)와 같이 Lock을 걸어주어야 한다.
자료구조를 사용할 때마다 Lock을 걸고 해제하는 것은 매우 귀찮을수도 있고, 코드를 작성할때 Lock을 해제하는 것을 까먹는다거나 여러 문제가 발생할 수 있다.
2. LockStack
LockStack을 구현한 예제코드는 아래와 같다. Stack의 복사를 방지하기 위해, 복사 연산자나 복사 생성자가 없도록 delete 하였다.
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));
_condVar.notify_one();
}
bool TryPop(T& value) {
lock_guard<mutex> lock(_mutex);
if (_stack.empty())
return false;
value = std::move(_stack.top());
_stack.pop();
return true;
}
void WaitPop(T& value) {
unique_lock<mutex> lock(_mutex);
_condVar.wait(lock, [this] {return _stack.empty() == false; });
value = std::move(_stack.top());
_stack.pop();
}
private:
stack<T> _stack;
mutex _mutex;
condition_variable _condVar;
};기본적으로 사용되는 내부 변수는 다음과 같다.
- 자료를 저장할 stack
- Lock을 위한 mutex
- 다른 쓰레드를 깨워주기 위한 condition_variable
함수로는 기존 stack에서 지원하는 Push, Pop에 해당하는 함수가 존재한다. 하지만, stack과 비교하였을 때 다음과 같은 의문이 들 수 있다.
(1) Empty가 없는 이유
Empty를 구현해도 된다. 하지만, Empty에 대한 반환값을 받았을 경우 해당 값을 기준으로 어떠한 연산을 하게 될 탠데 그 때의 상태가 stack의 상태와 같다고 보장할 수는 없다. 아무리 return후에 값을 비교하여도 그 사이에 다른 쓰레드가 Push/Pop을 할 수 있는 상황이 충분히 있을 수 있다.
(2) Pop이 아닌 TryPop
Pop을 하는 단계는 empty 확인, top 확인, 실제 pop 실행의 순서로 진행된다. 위에서 LockStack외부에서 empty하는 것은 의미가 없다고 했기 때문에 실제 Pop함수 내에서 위의 단계가 실행되어야 한다.
결국, Pop을 호출했지만 실제로는 stack이 비어있어 반환할 값이 없을 수 있고 이를 위해 Pop을 시도한다는 의미의 TryPop으로 사용한다. true면 reference로 넘긴 값이 실제 가져온 값이고, false면 stack이 비어있어 값을 반환하지 못했음을 의미한다.
(3) WaitPop
위의 TryPop의 단점은 호출했을 때 확정적으로 값을 얻을 수 없을 수 있다는 것인데, 값이 필요할 경우 TryPop의 값이 true가 될 때까지 TryPop을 계속 호출할 것이고 이는 CPU 자원의 낭비가 될 수 있다. 이를 위해 condition_variable를 이용해 WaitPop을 구현할 수 있다.
TryPop과 다르게 값을 반환한다는 것을 보장할 수 있고, Lock을 잡고 stack에 값이 있는 것을 조건으로 대기상태에 들어가게 된다면 이후에 깨어나고 stack에서 값을 꺼내 반환하면 된다. 물론, 이를위해 Push에 notify_one를 이용해 대기중인 쓰레드를 깨워주어야 한다.
3. LockQueue
LockQueue의 예제코드는 아래와 같다. 위의 stack을 queue로 바꾼것과 동일하고 top대신 front를 쓰는 실제 자료구조의 차이가 존재한다.
template<typename T>
class LockQueue {
public:
LockQueue() {}
LockQueue(const LockQueue&) = delete;
LockQueue& operator=(const LockQueue&) = delete;
void Push(T value) {
lock_guard<mutex> lock(_mutex);
_queue.push(std::move(value));
_condVar.notify_one();
}
bool TryPop(T& value) {
lock_guard<mutex> lock(_mutex);
if (_queue.empty())
return false;
value = std::move(_queue.top());
_queue.pop();
return true;
}
void WaitPop(T& value) {
unique_lock<mutex> lock(_mutex);
_condVar.wait(lock, [this] {return _queue.empty() == false; });
value = std::move(_queue.front());
_queue.pop();
}
private:
queue<T> _queue;
mutex _mutex;
condition_variable _condVar;
};