운영체제 7-2 Deadlock

Deadlock Detection and Recovery

• Deadlock Detection
  Resource type 당 single instance인 경우
  자원할당 그래프에서의 cycle이 곧 deadlock을 의미
  Resource type 당 multiple instance인 경우
  Banker's algorithm과 유사한 방법 활용

• Wait-for graph 알고리즘
  - Resource type 당 single instance인 경우
  - Wait-for graph
  자원할당 그래프의 변형
  프로세스만으로 node구성
  Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
  -Algorithm
  Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
  On2

• Recovery
  *Process termination
  Abort all deadlocked processes
  Abort one process at a time until the deadlock the cycle is eliminated

*Resource Preemption
비용을 최소화할 victim의 선정
safe state로 rollback하여 process를 restart
starvation문제
-동일한 프로세스가 계속해서 victim으로 선정되는 경우
-cost factor에 rollback횟수도 같이 고려

Deadlock Ignorance

• Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
  - Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
  - 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
  - UNIX, Windows 등 대부분의 범용 OS가 채택