OS

Chapter 7 (Deadlocks)

Deadlocks: Deadlock이란 어떤 Process가 Resource를 얻지 못하여
               영영 수행되지 못하는 상태를 말한다.

1. 언제 발생하나??

하나의 resource를 소유하는 process가 다른 process가 소유한 resource를 획득 하려고
기다리는 경우에 발생한다.  (여기서 resource란 hardware,software..등등)

(P0는 현재 A라는 resource를 소유하고 있지만 B라는 자원을 요청하고있다.

             이럴경우 데드락이 발생한다.)                                                              

2. Deadlock시 해결 법

• 관련된 process를 kill
• rollback

3. Deadlock의 발생 조건(필요 조건)

• Mutual exclusion : 오직 하나의 process만이 해당 resource를 사용 할 수 있다.
• Hold and wait : resource를 하나 소유하고 있으면서 다른 사람이 소유한 resource를
  요청하는 경우.
• No preemption : preemption을 허용 안한다. (따라서 CPU는 Deadlock이  발생하지 않는다.)
• Circular wait : 

이 조건은 필요조건이다. 즉 4가지 조건들을 만족한다해서 항상 Deadlock이 발생하는건 아니다. (하지만 Resource가 1개인 경우에는 Deadlock이 발생한다.)

Resource-allocation graph

4.Deadlock Prevention

*위 4가지 조건은 필요 조건이므로 한가지라도 조건을 없애면 Deadlock이 발생하지 않는다.

• Mutual exclusion : 없앨수는 있지만 앞장에서 공부한 race condition같은 문제가 발생
• Hold and Wait : 1. 모든 Resource를 확보해야 프로그램 수행
                         2. Resource를  소유하고 있으면 다른 Resource 요청 불가
  
                         1,2의 방법으로 Hold and Wait을 방지하면 Low resource utilization,                           Starvation과 같은 문제가 발생한다.
• No Preemption : Resource의 종류에 따라서 다르다.
                       ex) Printer Printer에 preemption을 허용하면 인쇄시 문제가 발생한다.
• Circular Wait : Resource에 접근하는 Priority를 정한다.

ex)P2는 R1을 먼저 요청 할 수 없다.

5. Deadlock Avoidance

문자 그대로 Deadlock을 회피하는 것인데 위의 Prevention과는 다르다.
Prevention 소스코딩을 통해 문제의 발생을 처음부터 예방하는 것인데
Avoidance는 Deadlock이 발생 될 가능성이 있는 routine을 회피하는 것이다.
( safe한 상태를 유지 )

그럼 발생 될 가능성은 어떻게 알수있나?

• 1. Use a resource-allocation graph
• 2. Use Banker's algorithm

   1번의 경우는 Resource가 single instance 일 때
   2번의 경우는 Resource가 multiple instances 일 때


                          Banker's algorithm

예를 들면 Process P1부터 수행하면 추가로 요구(Need)하는 Resource는 2 즉,
3번째 instance가 현재 0 이므로 Unsafe하다. 따라서 다른 Process부터 수행을 행한다. 

P2부터 수행을 하면 P1, P2, P3는 잠시 중단한다.
완료하면 Resource를 반납 -> Available 2, 3, 0으로 바뀐다.
다음 P3수행 후 완료 시 ->  Available 3, 4, 1

다음 P4수행 후 완료 시 - > Available 4, 4, 2

마지막으로 P1을 수행한다.
(safe한 상황만 유지된다면 어떤 Process가 먼저 수행되는 것은 상관이 없다.)

6. Recovery

• 1. To inform the operator and let the operator deal with the deadlock manually
• 2. To let the system recover from the deadlock automatically

  1: 직접 없앤다. ex) kill process
  2: System이 자동으로 복구 (하지만 이것을 지원하는 OS는 거의 없다.)

1번을 조금 구체적으로 보면 크게 2가지 방법이 있다.

  1: Process kill

  2: Checkpoint & rollback

  1-1  특정한 녀석을 kill (ex 우선순위가 낮거나 많은 Resource를 갖고 있는 Process)
  1-2  all process kill

  2-1 프로그램 수행라인을 저장했다가 Deadlock발생시 rollback한다.
       (여기서 수행정보 저장된 register를 checkpoint라 한다. )

rollback은 overhead가 크기때문에 보통 fault가  절대로 허용이 안되는 곳에 사용을 한다.      (ex 자동차, 비행기)