17. DeadLock 탐지

전에도 말했듯 데드락을 탐지하는 방법 중 사이클의 존재를 확인하는 방법이 있다.

락을 잡을 때 방향그래프를 만들고 이를 DFS로 탐색하여 확인한다.

 

DeadLockProfiler.h

#pragma once
#include <stack>
#include <map>
#include <vector>

//--------------------
//  DeadLockProfiler
//--------------------

class DeadLockProfiler
{
public:
	void PushLock(const char* name);
	void PopLock(const char* name);
	void CheckCycle();

private:
	void Dfs(int32 index);

private:
	unordered_map<const char*, int32>	_nameToId;
	unordered_map<int32, const char*>	_idToName;
	stack<int32>				_lockStack;
	map<int32, set<int32>>			_lockHistory;

	Mutex _lock;

private:
	vector<int32>	_discoveredOrder; // 노드가 발견된 순서를 기록
	int32		_discoveredCount = 0; // 노드가 발견된 순서
	vector<bool>	_finished; // Dfs(i)가 종료되었는지 판별
	vector<int32>	_parent; // 발견한 노드
};

DeadLockProfiler.cpp

#include "pch.h"
#include "DeadLockProfiler.h"

//--------------------
//  DeadLockProfiler
//--------------------

void DeadLockProfiler::PushLock(const char* name)
{
	LockGuard guard(_lock);

	// 아이디 찾거나 발급
	int32 lockId = 0;

	auto iter = _nameToId.find(name);
	if (iter == _nameToId.end())
	{
		lockId = static_cast<int32>(_nameToId.size());
		_nameToId[name] = lockId;
		_idToName[lockId] = name;
	}
	else
	{
		lockId = iter->second;
	}

	// 잡고있는 락이 있었다면
	if (_lockStack.empty() == false)
	{
		// 기존에 발견되지 않은 케이스라면 데드락 여부 판별
		const int32 prevId = _lockStack.top();
		if (lockId != prevId)
		{
			set<int32>& history = _lockHistory[prevId];
			if (history.find(lockId) == history.end())
			{
				history.insert(lockId);
				CheckCycle();
			}
		}
	}

	_lockStack.push(lockId);
}

void DeadLockProfiler::PopLock(const char* name)
{
	LockGuard guard(_lock);

	if (_lockStack.empty())
		CRASH("MULTIPLE_UNLOCK");

	int32 lockId = _nameToId[name];
	if (_lockStack.top() != lockId)
		CRASH("INVALID_UNLOCK");

	_lockStack.pop();
}

void DeadLockProfiler::CheckCycle()
{
	// 초기화
	const int32 lockCount = static_cast<int32>(_nameToId.size());
	_discoveredOrder = vector<int32>(lockCount, -1);
	_discoveredCount = 0;
	_finished = vector<bool>(lockCount, false);
	_parent = vector<int32>(lockCount, -1);

	for (int32 lockId = 0; lockId < lockCount; lockId++)
		Dfs(lockId);

	_discoveredOrder.clear();
	_finished.clear();
	_parent.clear();
}

void DeadLockProfiler::Dfs(int32 here)
{
	if (_discoveredOrder[here] != -1)
		return;

	_discoveredOrder[here] = _discoveredCount++;

	// 모든 인접한 정점 순회
	auto iter = _lockHistory.find(here);
	if (iter == _lockHistory.end())
	{
		_finished[here] = true;
		return;
	}

	set<int32>& nextSet = iter->second;
	for (int32 there : nextSet)
	{
		// 아직 방문한 적이 없다면 방문
		if (_discoveredOrder[there] == -1)
		{
			_parent[there] = here;
			Dfs(there);
			continue;
		}

		// here가 there보다 먼저 발견되었다면, there는 here의 후손(순방향 간선)
		if (_discoveredOrder[here] < _discoveredOrder[there])
			continue;

		// 순방향이 아니고, Dfs(there)가 종료되지 않았다면, there는 here의 선조(역방향 간선)
		if (_finished[there] == false)
		{
			printf("%s -> %s\n", _idToName[here], _idToName[there]);

			int32 now = here;
			while (true)
			{
				printf("%s -> %s\n", _idToName[_parent[now]], _idToName[now]);
				now = _parent[now];
				if (now == there)
					break;
			}

			CRASH("DEADLOCK_DETECTED");
		}
	}

	_finished[here] = true;
}

 

PushLock은 스레드가 락을 잡게 되면 데드락 탐지를 위해 스택에 푸시하는 함수이다. 락을 재귀적으로 중복해서 잡을 수 있으므로 락을 잡고있다면 아이디를 찾고 그렇지 않다면 아이디를 새로 발급해준다. 락스택이 비어있지 않고(락을 누군가가 잡고 있다면) 마지막으로 락을 잡은 스레드가 자신이 아니라면(중복으로 락을 잡는 것을 허용했기 때문) 락 히스토리에 추가하고 사이클을 탐지한다. 과거에 해당 케이스가 존재했다면 그냥 락스택에 푸시한다.

 

PopLock은 락을 해제할 때 락스택에서 pop해준다. 여기서는 별 다른 코드 없이 에러 체크만 해준다.

 

CheckCycle은 사이클을 탐지한다. 필요한 정보들을 초기화 해준 후 각 정점 별로 Dfs를 실행한다.

 

Dfs는 본격적으로 데드락을 탐지하는 함수이다. 일반적인 Dfs와 동일하고 _discoveredOrder와 _discoveredCount를 사용해 락이 잡힌 순서를 체크하고 만약 역방향 간선(데드락)이 존재하면 크래시를 낸다.

 

그럼 이 클래스를 어떻게 활용하냐?

CoreGlobal.h

#pragma once

extern class ThreadManager* GThreadManager;

extern class DeadLockProfiler* GDeadLockProfiler;

일단 전역변수로 활용하기 위해 CoreGlobal에 추가를 해준다.

 

CoreGlobal.cpp

#include "pch.h"
#include "CoreGlobal.h"
#include "ThreadManager.h"
#include "DeadLockProfiler.h"

ThreadManager* GThreadManager = nullptr;
DeadLockProfiler* GDeadLockProfiler = nullptr;

class CoreGlobal
{
public:
	// 매니저가 추가될 경우 객체의 생성, 소멸 순서 맞추기
	CoreGlobal()
	{
		GThreadManager = new ThreadManager();
		GDeadLockProfiler = new DeadLockProfiler();
	}
	~CoreGlobal()
	{
		delete GThreadManager;
		delete GDeadLockProfiler;
	}
} GCoreGlobal;

다음 혹시나 하는 불상사를 막기 위해 순서를 맞춰준다.

 

CoreMacro.h

#pragma once

//------------------
//	Lock
//------------------

#define USE_MANY_LOCKS(count)	Lock _locks[count];
#define USE_LOCK		USE_MANY_LOCKS(1);
#define READ_LOCK_INDEX(index)	ReadLockGuard readLockGuard_##index(_locks[index], typeid(this).name());
#define READ_LOCK		READ_LOCK_INDEX(0);
#define WRITE_LOCK_INDEX(index)	WriteLockGuard writeLockGuard_##index(_locks[index], typeid(this).name());
#define WRITE_LOCK		WRITE_LOCK_INDEX(0);

메크로도 클래스의 이름을 받아와야 하므로 위와 같이 수정해준다.

 

Lock.cpp

...

void Lock::WriteLock(const char* name)
{
#if _DEBUG
	GDeadLockProfiler->PushLock(name);
#endif

...

void Lock::WriteUnlock(const char* name)
{
#if _DEBUG
	GDeadLockProfiler->PopLock(name);
#endif

...

Lock도 Read, Write의 Lock, Unlock 모두 디버그 상태에서만 작동하도록 위와 같이 코드를 추가해준다.

 

그럼 제대로 동작하는지 데드락 상황을 만들어 확인해보자.

AccountManager.h

AccountManager.cpp

#pragma once
class AccountManager
{
	USE_LOCK

public:
	void AccountThenPlayer();
	void Lock();
};

extern AccountManager GAccountManager;

----------------------------------------

#include "pch.h"
#include "AccountManager.h"
#include "PlayerManager.h"

AccountManager GAccountManager;

void AccountManager::AccountThenPlayer()
{
	WRITE_LOCK;
    
	GPlayerManager.Lock();
}

void AccountManager::Lock()
{
	WRITE_LOCK;
}

 

PlayerManager.h

PlayerManager.cpp

#pragma once
class PlayerManager
{
	USE_LOCK

public:
	void PlayerThenAccount();
	void Lock();
};

extern PlayerManager GPlayerManager;

-----------------------------------------

#include "pch.h"
#include "PlayerManager.h"
#include "AccountManager.h"

PlayerManager GPlayerManager;

void PlayerManager::PlayerThenAccount()
{
	WRITE_LOCK;

	GAccountManager.Lock();
}

void PlayerManager::Lock()
{
	WRITE_LOCK;
}

 

Main.cpp

#include "pch.h"
#include "CorePch.h"
#include <Windows.h>
#include "ThreadManager.h"

#include "AccountManager.h"
#include "PlayerManager.h"

int main()
{
	GThreadManager->Launch([=]
		{
			while (true)
			{
				cout << "PlayerThenAccount" << endl;
				GPlayerManager.PlayerThenAccount();
				this_thread::sleep_for(100ms);
			}
		});
	
	GThreadManager->Launch([=]
		{
			while (true)
			{
				cout << "AccountThenPlayer" << endl;
				GAccountManager.AccountThenPlayer();
				this_thread::sleep_for(100ms);
			}
		});

	GThreadManager->Join();
}

 

간단하게 데드락이 걸리는 상황을 만들었다. 릴리즈 모드로 실행을 하면 정상적으로 실행은 된다. 하지만 위의 코드는 분명 데드락의 가능성이 있기 때문에 사용자가 많아지게 된다면 데드락이 발생할 것이다.

릴리즈 모드 실행

그럼 이제 디버그 모드로 실행해보자. 

디버그 모드 실행

출력 화면

데드락 발생 가능성이 있는 사이클을 출력해주고 크래시가 나버린다.

 

코드를 하나하나 살펴보면 그렇게 어려운 코드가 아니니 잘 읽어보자.