데드락_순환대기 부정

순환대기란 서로가 서로의 자원을 요청하는 상태를 말한다.

데드락이 걸린 상황에서 순환대기 부정을 하게되면 DeadLock을 빠져 나올 수 있다.

순환대기 부정

자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

각 락 객체 마다 고유한 번호를 부여하여 번호가 작은 순서에서 큰 순서로 락 객체를 잡는다.

이미 필요한 락을 잡았다는 것은 추가로 필요한 락 객체는 나와 경쟁하고 있는 다른 스레드가 선점하고 있지 않음을 보장한다.

고유한 번호를 부여하기 위해 별도의 처리를 할 것은 아니고 락 객체의 메모리 주소를 고유 번호로 삼고 메모리 주소가 작은 것에서 큰 순으로 락을 잡아나간다.

구현

deadlock 상태에 빠지는 현상
우선 deadlock에 빠진 코드를 살펴보면 Finish deadLock!!의 구문이 터미널 창에 나오지 못한 것을 보고 DeadLock상황에 빠진 것을 볼 수 있다.
(count는 실행 할 때마다 다르게 나오며 운이 좋다면 Finish deadLock!! 구문을 볼 수 있다.)

#include <iostream>
#include <mutex>
#include <thread>

using namespace std;

struct Resource
{
	mutex lock;
	int count;

	Resource() : count(0)
	{
	}
};

Resource resource1;
Resource resource2;

int main()
{
	cout << "start deadLock!!" << endl;
	thread thread1([]() {
		for (int i = 0; i < 10000; i++)
		{
			lock_guard<mutex> lo1(resource1.lock);
			lock_guard<mutex> lo2(resource2.lock);
			cout << "thread 1: " << resource1.count++ << endl;
		}
		});

	thread thread2([]() {
		for (int i = 0; i < 10000; i++)
		{
			lock_guard<mutex> lo2(resource2.lock);
			lock_guard<mutex> lo1(resource1.lock);
			cout << "thread 2: " << resource2.count++ << endl;
		}
		});

	thread1.join();
	thread2.join();
	cout << "Finish deadLock!!" << endl;
}

순환 대기 방지 방법으로 deadlock 빠져오는 방법
인자로 받은 락 객체들의 인자 순서와 상관 없이 메모리 주소 순서로 정렬한 후 락을 잡음으로써 순환 대기 상태를 방지할 수 있다.

#include <iostream>
#include <mutex>
#include <thread>
#include <set>

using namespace std;

template <class LOCK>
class deadlockfree_guard
{
public:
	template <class... LOCKS>
	deadlockfree_guard(LOCKS&&... locks)
	{
		Sort(locks...);
		for (LOCK* lock : ordered_locks)
		{
			lock->lock();
		}
	}

	~deadlockfree_guard()
	{
		for (LOCK* lock : ordered_locks)
		{
			lock->unlock();
		}
	}

	deadlockfree_guard& operator = (const deadlockfree_guard& other) = delete;
private:
	template <class... LOCKS>
	void Sort(LOCK& lock, LOCKS&... others)
	{
		ordered_locks.insert(&lock);
		Sort(others...);
	}

	void Sort(LOCK& lock)
	{
		ordered_locks.insert(&lock);
	}
private:
	set<LOCK*> ordered_locks;
};

struct Resource
{
	mutex lock;
	int count;

	Resource() : count(0)
	{
	}
};

Resource resource1;
Resource resource2;

int main()
{
	cout << "start deadLock!!" << endl;
	thread thread1([]() {
		for (int i = 0; i < 10000; i++)
		{
			deadlockfree_guard<mutex> lo(resource1.lock, resource2.lock);
			cout << "thread 1: " << resource1.count++ << endl;
		}
		});

	thread thread2([]() {
		for (int i = 0; i < 10000; i++)
		{
			deadlockfree_guard<mutex> lo(resource2.lock, resource1.lock);
			cout << "thread 2: " << resource2.count++ << endl;
		}
		});

	thread1.join();
	thread2.join();
	cout << "Finish Test!!" << endl;
}

set<LOCK*> ordered_locks;

락 객체의 메모리 주소로 정렬하기 위해 포인터를 저장함

---

deadlockfree_guard(LOCKS&&... locks)

불특정 다수 개의 락 객체를 인자로 받을 수 있도록 하기 위해 생성자의 파라미터 리스트를 Parameter Pack으로 선언했다.

---

Sort(locks...);

...

void Sort(LOCK& lock, LOCKS&... others)
{
	ordered_locks.insert(&lock);
	Sort(others...);
}

...

void Sort(LOCK& lock)
{
	ordered_locks.insert(&lock);
}

함수 오버로딩을 통해 인자로 넘어온 Parameter pack을 쪼개 set에 저장 및 정렬을 한다.

---

for (LOCK* lock : ordered_locks)
{
	lock->lock();
}

정렬된 락 객체들을 순서대로 잡는다.

---

for (LOCK* lock : ordered_locks)
{
	lock->unlock();
}

정렬된 락 객체들을 순서대로 해제한다.