데드락 디텍터(deadlock detector) : 순환대기(Circular wait) 제거

말머리
코드 변경이 될 수 있으므로 되도록 링크로 가져 가시길 바라지만, 꼭 그렇게 하지 않으셔도 됩니다.

6년 전쯤 저의 코드에서 데드락이 발생 된 적이 있었습니다. 그때 락을 위에서 아래로 내려가게 걸면, 데드락에 빠지지 않는다고 알려 주신 분이 있었고, 저는 아이디어를 좀 더 보태서 코드로 데드락 디텍터(deadlock-detector)를 만든 것입니다.

모쪼록 모두 도움 되었으면 좋겠습니다.


서론
데드락-디텍터(deadlock-detector)란 말 그대로 "데드락 탐지기" 입니다. 데드락이란 제가 정의 하기에 락 자원 획득 시도가 무제한 대기하는 상태를 뜻하는 합니다. 데드락 디텍터(deadlock-detector)는 이러한 상태를 탐지하는 장치입니다. 데드락이 생기는 이유를 알면, 데드락 회피할 수 있으므로, 데드락 발생 이유를 알아봐야 합니다.

1971년에 E. G. 코프만 교수가 다음 4가지 모두 만족할 때, 발생한다고 정리 하였습니다.

1. 상호배제(Mutual exclusion)
 - 임계영역을 뜻하는데, 프로세스 또는 쓰레드의 루틴이 동시에 들어갈 수 없는 영역을 뜻합니다.
 - 프로그래밍 할 때, lock { ... } unlock 에서 { } 안쪽 영역을 뜻합니다.

2. 점유대기(Hold and wait)
 - 이미 임계영역 안에서 다른 임계영역 획득을 대기하는 일을 뜻합니다.
 - lock1 { ... lock2 { ... } unlock2  ... } unlock2 에서 lock2 를 시도 후 대기하는 상태를 뜻합니다.

3. 비섬점(No preemption)
 - 다른 프로세스 혹은 쓰레드가 획득한 락 자원이 반환될 때까지 획득할 수 없는 것을 뜻합니다.

4. 순환대기 (Circular wait)
 - 락 자원 획득이 T1(A -> B), T2(B -> C), T3(C -> D), T4(D -> A) 로 되어 있고, 서로가 물려 있는 상태를 뜻합니다.

이 4개 중에 한개만 발생하지 않게 하면, 데드락에 걸리지 않습니다.

   
1. 상호배제 제거 방법
 - 싱글 쓰레드이거나 공유 데이터가 없도록 하면, 상호배제 영역이 제거 됩니다.

2. 점유대기 제거 방법
 - 쉽게 생각해 lock 걸고 lock 거는 코드를 없앱니다.

3. 비선점 제거 방법
 - 이미 걸려 있는 락을 임의로 해제시킵니다.

4. 순환대기 제거 방법
 - 락에 방향성을 넣어, 단방향으로 락을 걸도록 처리 합니다.


현재 저의 경험을 기준으로 보면 3번은 본적이 없고, 1, 2, 4 으로 해결해 왔던 거 같습니다.

저는 특히 4번으로 데드락 제거를 해왔고, 그 노력으로 데드락 디텍터(deadlock-detector)를 만들게 되었습니다. 이 데드락 디텍터(deadlock-detector)는 순환대기(Circular wait) 제거를 통해 데드락을 방지/탐지 하며 응용하면, 점유대기(Hold and wait)를 없앨 수 있습니다.  방법은 모든 락의 순번을 같게 하면, 락 중 락을 찾을 수 있게 됩니다.

하지만 한계도 있습니다. 코드가 실행 되어야 하고 락을 정렬해 두어야 합니다. 누군가 더 좋은 방법을 아시면 알려 주세요.

본론
순환대기 상태를 없애기 위해선 락이 서로 순환되지 않게 만들면 됩니다. 이 뜻은 락 자원 획득을 양방향이 아닌 단방양으로 하겠다는 뜻하고 같습니다. 위의 예에서 D -> A 로 락 거는 상태를 탐지 할 수 있으면 됩니다.

먼저 준비해야 할것은 "쓰레드 로컬 스토리지 싱글턴", "정렬된 락 자원", "정렬된 락 자원의 락 가더"가 필요 합니다.

쓰레드 로컬 스토리지 싱글턴
- 구현은 자유롭습니다. 조건은 해당 쓰레드에서만 접근 방법을 제공하면 됩니다.
- 각 쓰레드마다 락 거는 순번을 체크하는 객체에 접근하기 위해 사용합니다.

정렬된 락 자원
- 각 락 자원이 정렬 되어 있어, 단방향으로 가고 있는지 체크하기 위한 std::mutex + int order 입니다.
- 순번을 기록하기 위해선 변수 1개가 필요하므로 int order 를 선언하여 사용하고 있습니다.

정렬된 락 자원의 락 가더
- 정렬된 락 자원을 획득할 때, 쓰레드 로컬 스토리지 싱글턴과 정렬된 락 자원을 연결하기 위해 사용합니다.
- 또한 생성/소멸 관용구로 편한 방법 획득/해제를 위해 사용합니다.

코드

full - https://github.com/ikpil/deadlock-detector

sample

#include <iostream> #include <string> #include "dldetector.hpp" class scope_log_log final { public: scope_log_log(const scope_log_log&) = delete; scope_log_log& operator=(const scope_log_log&) = delete; public: ~scope_log_log() { std::cout << "unlock : " << log_ << std::endl; } scope_log_log(const std::string& log) : log_(log) { std::cout << "lock : " << log_ << std::endl; } private: std::string log_; }; ordered_mutex a(1000); ordered_mutex b(100); ordered_mutex c(10); ordered_mutex d(1); void test_case_1() { std::cout << "test case 1" << std::endl; std::cout << std::endl; ORDERED_LOCK_GUARDING(a) { scope_log_log scope_a("a"); } std::cout << std::endl; ORDERED_LOCK_GUARDING(b) { scope_log_log scope_b("b"); } std::cout << std::endl; ORDERED_LOCK_GUARDING(c) { scope_log_log scope_c("c"); } std::cout << std::endl; ORDERED_LOCK_GUARDING(d) { scope_log_log scope_d("d"); } } void test_case_2() { std::cout << "test case 2" << std::endl; std::cout << std::endl; // a -> b ORDERED_LOCK_GUARDING(a) { scope_log_log scope_a("a"); ORDERED_LOCK_GUARDING(b) { scope_log_log scope_b("b"); } } std::cout << std::endl; // c -> d ORDERED_LOCK_GUARDING(c) { scope_log_log scope_c("c"); ORDERED_LOCK_GUARDING(d) { scope_log_log scope_d("d"); } } std::cout << std::endl; // a -> d ORDERED_LOCK_GUARDING(a) { scope_log_log scope_a("a"); ORDERED_LOCK_GUARDING(d) { scope_log_log scope_d("d"); } } } void test_case_3_error() { std::cout << "test case 3" << std::endl; // a -> b -> d -> c(error) ORDERED_LOCK_GUARDING(a) { scope_log_log scope_a("a"); ORDERED_LOCK_GUARDING(b) { scope_log_log scope_b("b"); ORDERED_LOCK_GUARDING(d) { scope_log_log scope_d("d"); // deadlock - circular wait error ORDERED_LOCK_GUARDING(c) { scope_log_log scope_c("c"); } } } } // b -> a(error) ORDERED_LOCK_GUARDING(b) { scope_log_log scope_b("b"); // deadlock - circular wait error ORDERED_LOCK_GUARDING(a) { scope_log_log scope_a("a"); } } std::cout << std::endl; } int main(char argc, char *argv[]) { test_case_1(); std::cout << std::endl; test_case_2(); std::cout << std::endl; test_case_3_error(); tls_template<deadlock_detector<ordered_mutex>>::all_tls_release(); return 0; }

결론
 - 코드 자체는 별거 없습니다. 개념을 이용하는 부분이 조금 어려울 수 있습니다.
 - 모르면 알기 어렵지만, 알고나면 참 쉬운 개념입니다. 각자 나름데로 짜보는것도 재미있을 것 같습니다.

 - 기본 개념만 이해 되면, 어떤 언어에서도 사용 가능하게 바꿀 수 있습니다. 꼭 서론/본론을 이해하세요.

 - 쓰레드 로컬 스토리지 싱글턴(TLS Singleton)만 분리해서 따로 프로그래밍 해야 될것 같습니다.

참조 문헌

- https://ko.wikipedia.org/wiki/%EA%B5%90%EC%B0%A9_%EC%83%81%ED%83%9C

여담

 - 대학 강의도 들어야 하는데, 피곤하네요. 내일로 미루면 후회 하겠죠? : )

 - 예전부터 그랬지만 조사를 이상하게 쓰는 버릇이 있네요. 혹시 이상한 조사 있으면 알려 주세요.

:wq!