Dead Lock
카테고리: Server
인프런에 있는 루키스님의 게임 서버 강의를 듣고 정리한 내용입니다.
모두의 코드 씹어먹는 C++ 자료를 참고했습니다.
Dead Lock
void worker1(mutex& m1, mutex& m2) {
for (int i = 0; i < 10000; i++) {
lock_guard<mutex> lock1(m1);
lock_guard<mutex> lock2(m2);
// Do Something
}
}
void worker2(mutex& m1, mutex& m2) {
for (int i = 0; i < 10000; i++) {
lock_guard<mutex> lock2(m2);
lock_guard<mutex> lock1(m1);
// Do Something
}
}
int main()
{
mutex m1, m2;
thread t1(worker1, ref(m1), ref(m2));
thread t2(worker2, ref(m1), ref(m2));
t1.join();
t2.join();
cout << "End Program" << endl;
}
위 코드를 실행하면 프로그램이 끝나지 않아 강제로 종료해야 한다. m1의 lock을 풀기 위해서는 m2가 unlcok되어야 하고, m2가 unlock되기 위해서는 m1이 unlcok되어야 한다. 결과적으로 이러지도 저러지도 못하는 상황인 것이다. 이런 식으로 서로 lock을 잡고 무한 대기 상태에 빠진 상황을 데드락이라 한다.
void worker2(mutex& m1, mutex& m2) {
for (int i = 0; i < 10000; i++) {
while (true) {
m2.lock();
// m1 이 이미 lock 되어 있다면 "야 차 빼" 를 수행하게 된다.
if (!m1.try_lock()) {
m2.unlock();
continue;
}
// Do something
m1.unlock();
m2.unlock();
break;
}
}
}
데드락 상황을 해결하고자 할 때 가장 먼저 생각할 수 있는 것은 특정 쓰레드에게 우선 순위를 부여하는 것이다. 하지만 이러한 방식은 특정 쓰레드만 열심히 일하고 다른 쓰레드는 일을 하지 않는 기아 상태(Startvation State)에 빠지게 된다. 데드 락을 빠져 나올 수 있는 방법들을 살펴보자.
Spin Lock
첫 번째 방법은 Spin Lock 방식이다. Spin Lock은 내가 사용하고자 하는 데이터가 lock되어 있을 때 해당 lock이 풀릴 때까지 계속 체크하면서 대기하는 것이다. 쓰레드가 커널에 왔다갔다 하는 오버헤드는 줄겠지만, 한 쓰레드가 오래 점유하는 경우 나머지 쓰레드들이 무식하게 while문을 돌기 때문에 CPU 점유율이 확 올리간다. 따라서 바로바로 반납하는 상황에서 적합하다.
class SpinLock {
public:
void lock()
{
while (_locked) {
// 통과할 때 까지 계속 체크
}
_locked = true;
}
void unlock()
{
_locked = false;
}
private:
atomic<bool> _locked = false;
};
Spin Lock의 pseudo code를 보면 위와 같이 생각할 수 있을 것이다. 하지만 위 코드의 경우 lock이 풀렸는지 체크하는 부분과 조건이 통과되어 내가 잠구는 코드가 분리되어 있어 문제가 발생할 수 있다. 따라서 check와 lock이 동시에 이루어져야 하는데 이는 atomic 객체의 compare_exchange 함수를 이용하면 된다.
void lock()
{
bool expected = false;
bool desired = true;
while (_locked.compare_exchange_strong(expected, desired) == false) {
expected = false;
}
}
compare_exchange_strong 함수는 비교 및 교환(Compare-and-Swap, CAS) 연산을 원자적으로 수행해주는 함수이다. 함수의 작동 방식은 기존 값과 예상 값을 비교하여 일치하면 true를 반환함과 동시에 새 값으로 교환한다. 만약 예상 값과 일치하지 않으면 아무 작업도 하지 않고 false를 반환한다.
Sleep
두 번째 방법은 Sleep 방식이다. 내가 사용하고자 하는 데이터가 lock되어 있으면 깔끔하게 포기하고 해당 쓰레드의 소유권을 반납한다.
void lock()
{
bool expected = false;
bool desired = true;
while (_locked.compare_exchange_strong(expected, desired) == false) {
expected = false;
this_thread::sleep_for(5ms);
// or
this_thread::yeild();
}
}
구현 방식은 Spin Lock과 크게 다르지 않다. 만약 lock 되어 있다면 sleep_for나 yeild로 돌려 보내면 된다. sleep_for의 경우 내가 지정한 시간만큼은 다시 스케쥴링 되지 않고, yeild는 sleep_for(0ms)와 똑같이 동작한다.
생산자-소비자 패턴
생산자-소비자 패턴은 멀티 쓰레드 프로그램에서 가장 많이 등장하는 패턴이다. 예를 들어 인터넷에서 특정 데이터를 크롤링하고 분석하는 프로그램을 만든다고 해보자. 이 경우 페이지를 긁어 오는 쓰레드가 생성자, 글어온 페이지를 분석하는 쓰레드가 소비자 역할을 담당할 것이다. 이때 페이지를 긁어오는 작업은 대기 시간이 길기 떄문에 소비자 쓰레드에서 무식하게 체크하는 Spin Lock 형태는 적합하지 않다. 이를 Sleep 방식으로 구현해보자
void producer(queue<string>* downloaded_pages, mutex& m, int index)
{
for (int i = 0; i < 5; i++) {
// 각 쓰레드 별로 웹사이트를 다운받는 시간이 다르다고 가정
this_thread::sleep_for(chrono::milliseconds(100 * index));
string content = "website " + to_string(i) + " from thread(" + to_string(index) + ")\n";
m.lock();
downloaded_pages->push(content);
m.unlock();
}
}
void consumer(queue<string>* downloaded_pages, mutex& m, int* num_processed)
{
// 전체 처리하는 페이지 수는 5 * 5 = 25
while (*num_processed < 25) {
m.lock();
if (downloaded_pages->empty()) {
m.unlock();
// 10ms 뒤에 다시 체크
this_thread::sleep_for(10ms);
continue;
}
string content = downloaded_pages->front();
downloaded_pages->pop();
(*num_processed)++;
m.unlock();
cout << content;
// 현재 대기 중인 다른 쓰레드들 처리
this_thread::sleep_for(80ms);
}
}
int main()
{
queue<string> downloaded_pages;
mutex m;
vector<thread> producers;
for (int i = 0; i < 5; i++) {
producers.push_back(thread(producer, &downloaded_pages, ref(m), i + 1));
}
int num_processed = 0;
vector<thread> consumers;
for (int i = 0; i < 3; i++) {
consumers.push_back(thread(consumer, &downloaded_pages, ref(m), &num_processed));
}
for (int i = 0; i < 5; i++) {
producers[i].join();
}
for (int i = 0; i < 3; i++) {
consumers[i].join();
}
}
Event & Condition Variable
마지막 방법은 Event 기반 방식이다. 당장 할 수 있는 것이 없을 떄 해당 쓰레드를 재우고, 특정 조건이 만족할 때 깨우는 방식이다. 물론 커널이 개입하는 오버헤드가 발생하기 때문에 조건이 자주 발생하는 상황에서는 적합하지 않다. Event 방식으로 생성자-소비자 패턴을 다시 구현해보자
void producer(queue<string>* downloaded_pages, mutex& m, int index, condition_variable* cv)
{
for (int i = 0; i < 5; i++) {
// 각 쓰레드 별로 웹사이트를 다운받는 시간이 다르다고 가정
this_thread::sleep_for(chrono::milliseconds(100 * index));
string content = "website " + to_string(i) + " from thread(" + to_string(index) + ")\n";
m.lock();
downloaded_pages->push(content);
m.unlock();
// content가 준비되었으므로 consumer 쓰레드 깨우기
cv->notify_one();
}
}
void consumer(queue<string>* downloaded_pages, mutex& m, int* num_processed, condition_variable* cv)
{
// 전체 처리하는 페이지 수는 5 * 5 = 25
while (*num_processed < 25) {
unique_lock<mutex> lk(m);
cv->wait(lk, [&] {return !downloaded_pages->empty() || *num_processed == 25; });
if (*num_processed == 25) {
lk.unlock();
return;
}
string content = downloaded_pages->front();
downloaded_pages->pop();
(*num_processed)++;
lk.unlock();
cout << content;
// 현재 대기 중인 다른 쓰레드들 처리
this_thread::sleep_for(80ms);
}
}
int main()
{
queue<string> downloaded_pages;
mutex m;
condition_variable cv;
vector<thread> producers;
for (int i = 0; i < 5; i++) {
producers.push_back(thread(producer, &downloaded_pages, ref(m), i + 1, &cv));
}
int num_processed = 0;
vector<thread> consumers;
for (int i = 0; i < 3; i++) {
consumers.push_back(thread(consumer, &downloaded_pages, ref(m), &num_processed, &cv));
}
for (int i = 0; i < 5; i++) {
producers[i].join();
}
// 자고 있는 나머지 쓰레드들 깨우기
cv.notify_all();
for (int i = 0; i < 3; i++) {
consumers[i].join();
}
}
하나씩 살펴보면
condition_variable cv;
mutex 객체와 짝지어 다니는 condition_variable 정의
// content가 준비되었으므로 consumer 쓰레드 깨우기
cv->notify_one();
Producer에서 content가 추가되면 notify_one으로 자고 있는 쓰레드 하나 깨우기
unique_lock<mutex> lk(m);
cv->wait(lk, [&] {return !downloaded_pages->empty() || *num_processed == 25; });
lock_guard는 lock과 unlock이 생성자와 소멸자에 정의되어 있기 때문에 프로그래머 마음대로 lock, unlock을 할 수 없게 막아놨다. 하지만 unique_lock은 mutex를 동적으로 잠구고 해제할 수 있다. 또한 소유권을 이전할 수 있는 등 자유성이 보장된다. condition_variable의 경우 lock과 unlock이 동적으로 일어나기 때문에 unique_lock을 사용한다. 참고로 생성자를 호출하지 않고 선언만 한다면 뮤텍스는 잠기지 않는다.
cv->wait() 함수의 경우 두 번째 인자로 들어가는 조건이 참일 경우 wait을 빠져나와 나머지 코드가 실행된다. 반면 탈출 조건이 false라면, lk를 unlock하고 다른 누군가 깨워주기 전까지 계속 Sleep 상태로 기다리게 된다.
// 자고 있는 나머지 쓰레드들 깨우기
cv.notify_all();
condition_variable을 사용할 때 한 가지 주의할 점은, cv.notify_all()로 자고 있는 쓰레드들을 깨워주지 않는다면 join()이 실행되지 않기 때문에 문제가 발생하게 된다.
댓글 남기기