교착상태 탐지

교착상태 발생이 가능한 시스템에서 지원해야할 것

교착상태가 발생했는지 결정하기 위해 시스템의 상태를 결정하는 알고리즘

교착상태로부터 회복하는 알고리즘

 

교착상태 탐지 시 실행 시간이 소요되며 교착 상태로부터 회복할 때는 오버헤드가 발생한다.

 

 

각 자원 타입이 한 개씩 있는 경우

모든 자원들이 한 개의 인스턴스만 가진다면 대기 그래프를 사용해 교착상태를 탐지할 수 있다

대기 그래프가 사이클을 포함하는 경우에만 시스템에 교착 상태가 존재하므로 주기적으로 그래프에서 사이클을 조사하여 교착상태를 탐지한다.

그래프에서 사이클을 탐지하는 알고리즘은 O(n^2)의 연산을 요구한다.

여기서 n은 정점의 수이다.

 

 

각 타입의 자원을 여러 개 가진 경우

각 자원이 복수의 인스턴스를 가질 경우 은행원 알고리즘에서 설명한 안전성 검사 알고리즘을 이용한다.

 

 

탐지 알고리즘 사용

교착상태를 탐지하는 알고리즘을 사용할 시기는 교착상태가 얼마나 자주 발생하는지,

교착상태가 일어나면 몇 개의 프로세스가 거기에 연루되는지에 따라 달려있다.

자원을 할당할 때마다 탐지 알고리즘을 사용할 경우 어디서 교착상태가 발생했는지 알 수 있지만 오버헤드가 너무 크게 된다.