데드락 특성

필요조건

1. 상호배제
   최소하나의 스레드만 자원에 접근할 수 있으며 해당 자원은 반납되기 전까지 누구도 접근할 수 없도록 한다.
2. 점유대기
   스레드는 자원을 점유한 채, 다른 스레드가 점유하고 있는 자원을 접근하기 위해선 반드시 대기하여야 한다.
3. 비선점
   자원들을 선점할 수 없다. 자원은 강제적으로 반납할 수 없으며, 스레드에 의해 자발적으로만 반납 가능하다.
4. 환형대기
   각 스레드가 점유하고자하는 자원이 원형을 유지한다. 예를 들어 p1은 p2가 가진 자원을 요청하고 p2는 p3가 가진 자원을 요청하고 p3는 p1이 가진 자원을 요청한다. p1->p2->p3->p1와 같은 형태로 자원을 대기하는것을 환형대기라고 한다.

교착상태가 발생하기 위해선 위 4가지 조건이 성립되어야한다.

자원 할당 그래프

데드락은 자원 할당 그래프를 통한 방향 그래프로 더 정확하게 확인할 수 있다.
간단하게 스레드 집합(T), 자원 집합(R), 스레드와 자원을 요청하는 간선의 집합(E)으로 표현된다.

위 그림에서 T1->R1의 간선의 의미는 T1의 스레드가 R1의 자원을 대기하고 있다는 의미이다.
반대로 R2->T1의 의미는 R2자원이 T1이 점유하고 있다는 의미이다.

우리는 이 그래프를 통해서 데드락을 파악할 수 있다. 자원 할당 그래프에서 사이클이 발생하지 않으면 데드락이 발생하지 않는다 확신할 수 있으며 사이클이 발생하게 되면 데드락이 발생할 수 도 있음을 나타낸다. 아래의 예제들을 통해 확인 해보겠다.

사이클이 있고 데드락이 발생하는 경우

위 그래프는 T1->R1->T2->R3->T3->R2->T1와 T2->R3->T3->R2->T2 같은 경로에서 사이클이 발생하고 있음을 알 수 있다. 스레드 상태를 보면 필요한 자원은 모두 점유 상태이며 어느 누구도 반납할 수 없는 데드락 상태임을 확인할 수 있다.

사이클이 있고 데드락이 발생 하지 않는 경우

위 그래프는 T1->R1->T3->R2->T1의 경로에서 사이클이 발생함을 알 수 있다. 하지만 R2, R1자원은 2개이며 사이클이 발생하는 스레드에서 요청하는 자원의 수는 각각 하나씩이다. 이때 T1가 R2을 점유하고 있더라도 T4는 R2의 자원을 반납할 수 있으며 이후 T3는 R2의 자원을 점유 할 수 있다. 이런식으로 사이클이 발생하더라도 필요한 자원에 대해 점유와 대기가 원활히 이루어지는것을 확인할 수 있다.