[OS] Deadlock handling (2)

Deadlock 이 발생하도록 놔두고 탐지한 뒤 복구하는 방법

Deadlock detectionSingle instance resource

wait-for 그래프를 통해 탐지

Resource allocation graph 에서 리소스를 제거하여 프로세스간의 의존 관계를 표현한 뒤 cycle 을 찾음

Serveral instances resource

1. Work = Available
   allocation[i] 가 0 이면 Finish[i] = true, 0이 아니면 Finish[i] = false   : Deadlock 여부를 판단할 때 hold and wait 특성에 의해 자원을 갖고 있지 않은 프로세스에 대해 체크하는 것은 무의미 하기 때문

2. Finish[i] == false 이면서 Request[i] <= Work 인 프로세스 i 를 찾고, 그런 프로세스가 없다면 4번으로 이동

3. Work = Work + Allocation[i]
   Finish[i] = true
   2번으로 이동

4. 모든 i 에 대해 Finish[i] 가 전부 true 이면 safe, 하나라도 false 가 있으면 Deadlock 발생 가능

 

O(MN2) 의 시간 복잡도

Detection 알고리즘의 사용

• 자원을 요청할 때마다 알고리즘 사용 : 오버헤드가 매우 큼

• 프로세스가 자원을 요청했는데 그것이 즉시 할당되지 않는 시점 : Deadlock 관련 프로세스를 알 수 있고, 누가 유발했는지 파악 가능

• 지정 된 시간 간격으로 호출 ( CPU utilization 이 40% 미만일 때 ) → CPU 사용률이 낮으면 Deadlock 일 확률이 높음. (Livelock 은 아님)

Deadlock restore

• 운영자에 의한 해결 (수작업)

• process termination : Deadlock 으로 인해 멈춘 프로세스를 종료시킴

• 모두 중지 : 다시 실행해야하니 오버헤드가 큼

• 하나씩 중지 : 하나씩 제거하고 Deadlock 이 풀렸는지 확인하는 Detection 알고리즘을 다시 돌리는 오버헤드도 큼

• 종료 프로세스 선정 시 고려되어야 할 점

• 프로세스 우선순위

• 프로세스 진행도

• 프로세스가 사용한 자원이 많은 순

• 프로세스가 완료되기 위해 필요한 자원이 많은 순

• 얼마나 많은 프로세스들이 종료될 필요가 있는지

• 프로세스가 대화형인지 일괄(batch)형인지

• resource preemption : Deadlock 으로 인해 멈춘 프로세스들로부터 자원을 내놓게 함

• Victim 의 선정 : 최소 비용을 고려

• Rollback : 프로세스를 안전한 상태로 되돌림 ( 재시작의 굴레 starvation 에 빠질 수 있음 )

• Starvation : 같은 프로세스가 항상 victim 으로 선정될 수 있으므로 rollback 된 횟수를 고려함(victim count)