(학부생 수준의, 연습용 프로그램임)
Deadlock을 어떻게 감지 할 것인가?
1. Concurrent Programming에서 사용되는 Lock.
Concurrent Programming에서 여러 프로세스(스레드)에 공유되는 데이터는 exclusive하게 사용되야 한다.
예를 들어 Thread A, Thread B가 실행중이고 공유된 데이터 x가 있다고 가정하자.
x는 0으로 초기화된 값을 가지는 변수라고 가정하자.
나는 x값을 3번 출력하기를 원해서 코드를 그렇게 짰다.(Thread A에서)
그리고 코드를 실행해서 x의 값인 0이 3번 출력되기를 기대했는데, 프로그램이 Concurrent하게 실행되면서 Thread B에서 x값에 10을 더하는 명령이 동시에 실행되었다.
그래서 실제 출력 값은
10
20
20
이 되었다.
exclusive한 실행이 보장되지 않아서 발생하는 대표적인 에러이다. 그래서 이 상황을 막기 위해 mutex를 활용했다.
Thread A에서 Lock을 hold하고 있으면 다른 Thread에서 같은 Lock을 hold하고자 하는 시도를 block시킨다. 즉, Thread B에서 x+=10; 명령 전에 Lock을 hold하는 명령을 추가했기 때문에 x+=10; 을 실행하지 못하고 멈춰있으며, Thread A 에서 Unlock이 되어야만 Thread B의 block이 풀리며 x+=10; 명령을 실행할 수 있게 된다.
즉, Lock는 변수 x에 대한 접근이 exclusive하도록 돕는 장치이다.
2. 그러나 Lock으로 인해 Deadlock이라는 에러가 발생할 수 있다.
Thread A,B 그리고 Lock a,b 가 있다고 가정하자.
- Thread A는 Lock a를 가진 상태에서 Lock b를 hold하려는 명령을 실행한다.
- 그러나 표를 보면 알 수 있듯이 Thread A가 Lock b명령을 실행하는 시점에서는 Lock b는 Thread B가 가지고 있다.
- 그러면 Thread A는, Thread B가 Unlock b를 할 때까지 block된다.
- Thread B는 Lock b를 가진 상태에서 Lock a를 hold하려는 명령을 실행한다.
- 그러나 표를 보면 알 수 있듯이 Thread B가 Lock a명령을 실행하는 시점에서는 Lock a는 Thread A가 가지고 있다.
- 그러면 Thread A는, Thread B가 Unlock b를 할 때까지 block된다.
즉, Thread A,B는 서로가 서로를 기다리며 block된 상태에 이르렀다. 이 상태를 Deadlock이라고 한다.
3. Deadlock Detect 알고리즘
Deadlock은 발생했을 때 에러 메시지가 뜨거나 panic되거나 프로그램이 종료되지 않고 아무 메시지 없이 프로그램이 멈춰있는 상태가 된다.
그렇기에 Detect프로그램을 통해 어디서 오류가 발생했는지 감지하는 것이 디버깅에 도움이 될 것이다.
알고리즘은 간단하다.
- If a thread has a mutex lock, it makes a node.
- If a thread has a mutex lock(lock B) holding another(lock A), it draws an edge (Node A, Node B).
- If a thread waits a mutex lock (lock B) holding lock A, it also draws an edge (Node A, Node B).
- When unlock, it erases edges related to the relesed mutex.
- Everytime it receives lock information, it updates the graph and detects the cycle.
사이클 = Deadlock 이다. 매 번 그래프가 업데이트 되고 cycle을 찾는 코드가 실행된다. cycle을 발견하면 그 즉시 Deadlock을 report해준다.
링크 : https://github.com/Yuhyeingjoo/Deadlock-detector/blob/master/ddtect.c
