8.7 Deadlock Detection

일반적으로 시스템은 아래와 같은 dead lock을 예방하거나 피하는 알고리즘을 제공한다.

1. 데드락 발생 여부를 판단하기 위해 시스템의 상태를 조사하는 알고리즘
2. 데드락에서 회복하기 위한 알고리즘

해당 섹션에서는 1번에 대해서 알아본다.

알고리즘이 동작하는 방식은 2가지 요소에 의해 나누어진다.

1. Single Instance of Each Resource Type (하나의 인스턴스)
2. Several Instances of a Resource Type (여러 개의 인스턴스)

resource는 추상적 개체를 의미하고, instance는 실질적 요소를 의미한다.

알고리즘의 고려 사항

1. 런타임 비용 : 시스템이 필요한 정보를 계속해서 업데이트하고 유지하는데 필요한 비용과, 데드락을 확인하기 위해 감지 알고리즘을 실행하는 비용.
   
2. 잠재적 손실 : 데드락에서 회복하는 과정에서 발생할 수 있는 손실을 의미. 예를 들어, 데드락을 해결하기 위해 일부 작업을 중단시키거나, 데이터를 롤백(원래 상태로 되돌림)하는 등의 조치가 필요할 수 있으며, 이로 인해 시간이 소요되거나 데이터 손실이 발생할 수 있다.
   

요약하면 탐지 비용과 문제가 있을 경우 해결에 필요한 비용을 고려해야한다.

8.7.1 Single Instance of Each Resource Type

• 그래프의 종류와 방식
  1. 대기-그래프(wait-for graph) : 모든 자원이 하나의 인스턴스만 가질 경우, 자원 노드를 제거하고 만든 그래프
     
  2. 자원-할당 그래프(Resource-allocation graph) : 모든 자원을 표시한 그래프

  single “리소스 to 인스턴스”이기 때문에 표기만 다를 뿐 결과는 같다.

• 데드락 판단 : 대기-그래프에 사이클이 포함되어 있을 때, 데드락이 존재한다고 할 수 있다. 따라서 데드락 감지를 위해서는 사이클을 탐색하는 알고리즘을 사용하고 해당 알고리즘은 O($n^2$)의 연산을 요구한다. (정점의 수가 n)

  물론 문제가 생긴다면 $n^2$ 보다 적은 비용이 발생한다.

8.7.2 Several Instances of a Resource Type

8.7.3 Detection-Algorithm Usage