DeadLock 탐지

🔒 1. DeadLock의 4가지 발생 조건

데드락이 발생하는 기본 조건은 다음과 같습니다:

조건	설명
상호 배제	하나의 자원은 동시에 하나의 프로세스만 접근 가능
점유 대기	하나의 자원을 점유한 상태에서 다른 자원을 기다림
비선점	점유한 자원을 강제로 빼앗을 수 없음
순환 대기	서로가 점유한 자원을 서로가 기다림

즉, 락 간의 사이클(Cycle)이 형성되면 데드락이 발생합니다.

---

📐 2. DeadLock 탐지의 핵심 원리 - 사이클 판별

락의 획득 관계를 방향 그래프로 나타내고, 사이클이 생기는지 여부를 DFS로 검사합니다.

• 정점(Vertex): 각각의 Lock
• 간선(Edge): A 락을 가진 상태에서 B 락을 획득 시도 → A → B
• 사이클: A → B → A 구조 → 데드락 가능성

🔁 간선 종류

간선 종류	의미	데드락 가능성
순방향 간선	선조 → 자손 (안전)	❌
역방향 간선	자손 → 선조 (사이클 발생)	✅
교차 간선	다른 트리 노드 간 연결	❌

---

🧠 3. DeadLockProfiler 구조 설명

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

private:
	void Dfs(int32 here);

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

	// DFS 탐색용
	vector<int32> _discoveredOrder;
	int32 _discoveredCount = 0;
	vector<bool> _finished;
	vector<int32> _parent;
};

• _nameToId, _idToName: 락 이름 ↔ ID 매핑
• _lockStack: 현재 스레드가 잡고 있는 락들 (순서 추적용)
• _lockHistory: 방향 그래프 (락 간 간선 정보)
• DFS용 변수들은 사이클 탐색용

---

⚙️ 4. 핵심 기능 코드 분석

🔸 PushLock()

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

	// ID 등록
	if (_nameToId.count(name) == 0)
	{
		int32 id = (int32)_nameToId.size();
		_nameToId[name] = id;
		_idToName[id] = name;
	}
	int32 lockId = _nameToId[name];

	// 현재 락을 이미 가지고 있는 경우는 무시
	if (_lockStack.empty() == false)
	{
		int32 prevId = _lockStack.top();
		if (lockId != prevId)
		{
			auto& history = _lockHistory[prevId];
			if (history.insert(lockId).second) // 새 간선이면
				CheckCycle();
		}
	}
	_lockStack.push(lockId);
}

• 락을 잡을 때마다 현재 락 간의 간선 정보를 _lockHistory에 등록
• 처음 보는 간선이면 CheckCycle() 호출

🔸 PopLock()

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

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

	_lockStack.pop();
}

• 락 해제 순서가 잘못되면 크래시 발생

---

🔍 5. DFS로 사이클 판별 (CheckCycle, Dfs)

CheckCycle()

void DeadLockProfiler::CheckCycle()
{
	int count = (int)_nameToId.size();
	_discoveredOrder.assign(count, -1);
	_finished.assign(count, false);
	_parent.assign(count, -1);
	_discoveredCount = 0;

	for (int i = 0; i < count; ++i)
		Dfs(i);
}

Dfs(here)

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

	_discoveredOrder[here] = _discoveredCount++;

	auto it = _lockHistory.find(here);
	if (it == _lockHistory.end())
	{
		_finished[here] = true;
		return;
	}

	for (int32 there : it->second)
	{
		if (_discoveredOrder[there] == -1)
		{
			_parent[there] = here;
			Dfs(there);
			continue;
		}

		// 순방향 간선은 안전
		if (_discoveredOrder[here] < _discoveredOrder[there])
			continue;

		// 역방향 간선 발견 시 -> 데드락!
		if (_finished[there] == false)
		{
			printf("DeadLock Detected Path:\n");
			int 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;
}

---

🧪 6. 데드락 발생 예제

AccountManager와 PlayerManager가 서로 락을 거는 경우:

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

void Lock() { WRITE_LOCK; }

// PlayerManager
void PlayerThenAccount()
{
	WRITE_LOCK;
	GAccountManager.Lock();
}

int main()
{
	GThreadManager->Launch([] { while (true) GPlayerManager.PlayerThenAccount(); });
	GThreadManager->Launch([] { while (true) GAccountManager.AccountThenPlayer(); });
	GThreadManager->Join();
}

💥 이 코드는 거의 100% 데드락이 발생합니다.
디버그 모드에서는 DeadLockProfiler가 즉시 사이클을 탐지하고 충돌(CRASH)시킵니다.

---

🛠️ 7. 개발 팁 - 디버깅 시 주의 사항

• 실제 데드락은 릴리즈 모드에서 잡기 어렵다 → 디버그 시 미리 탐지!
• 락 해제 순서가 잘못되면 탐지 불가
• 락 이름은 클래스마다 달라야 정확한 추적 가능

---