Deadlock: 교착 상태 (2/2)

<Deadlock Detection and Recovery>

Deadlock Detection

* resource type 당 자원이 하나인 경우 = single instance

 - 자원 할당 그래프에서 cycle이 곧 deadlock임

* resource type 당 자원이 여러개인 경우 = multiple instance

 - banker's algorithm과 유사한 방법 활용

 

wait for graph algorithm - resource type당 single instance인 경우

  - 자원 할당 그래프의 변형

  - 프로세스만으로 node를 구성한다.

  - Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj

 

* Algorithm: wait for graph에 사이클이 존재하는지를 주기적으로 검사한다. 시간 복잡도는 n^2임.

오른쪽은 그냥 자원을 뺀 간소화한 버전이다. 자원의 최대 사용량을 미리 알릴 필요가 없기 때문에 그래프에 점선이 없다

 

resource type당 multiple instance인 경우

데드락 발생하지 않는다. P0, P3, P3, P1, P4 순으로 실행 request는 추가 요청 가능량이 아니라 현재 실제로 요청한 자원량을 나타낸다.

 

Recovery 

* Process Termination

 - abort all deadlocked processes (데드락인 프로세스를 전부 강제 종료한다.) 

 - Aboart one process at a time until the deadlock cycle is eliminated (데드락 사이클이 제거될 때까지 프로세스를 하나씩 종료시킨다.

 

* Resource Preemption

 - 비용을 최소화할 victim의 선정

 - safe state로 roll back 하여 process를 restart한다.

 - startvation 문제

    !. 동일한 프로세스가 계속해서 victim으로 선정되는 경우

    !. cost factor에 rollback 횟수도 같이 고려한다.