[OS] 9. Deadlock

1. 조건

1) Mutual exclusion

2) Hold & Wait

3) No Preemption

4) Circular Wait

: 모두를 만족해야 deadlock 생성 가능, 즉 하나만 방지하면 deadlock 불가능

 

 

2. Prevention

1) Mutual exclusion

- Mutual exclusion 속성을 가지지 않은 resource에 대해서만 가능

 

2) Hold & Wait

- 프로세스가 Task를 위한 모든 Resource를 점유해야 시작 가능하도록 설계, 하나라도 불가능하면 다시 release.

- Low resource utilization, possibility of Starvation

 

3) No preemption

- Preemption 속성을 가지지 않은 resource에 대해서만 가능

 

4) Circular Wait

- Resource들에 대해 total ordering한다.

- 이에 따라 프로세스가 resource를 점유하려고 할 때 이 순서에 따라 점유하도록 한다.

 

 

3. Avoidance

Unsafe state를 예측하고 그에 따라 동작하는 것

safe state	safe sequence가 하나라도 있을 때
unsafe state	safe sequence가 하나도 없을 때

* safe sequence : deadlock이 걸리지 않는 프로세스에 대한 resource 할당 순서

* safe sequence 찾는 방법 : Banker's algorithms

 

cf) Dynamic한 프로세스의 Join & Leave, Resource의 Adding & Removal로 사실상 예측하는 것은 불가능함.

 

 

4. Recovery

Kill Process ; 모두 혹은 Deadlock이 없어질 때까지

 

 

5. Ignoring Deadlock

- 실제로 대부분의 OS가 채택하는 방법

- Deadlock의 가능성은 실제로 희박하고 예방하기에는 Cost가 너무 높다. 즉 trade-off 관계.

- 이에 따라 개발자가 Deadlock이 걸리지 않게...

- "ostrich" algorithms이라고도 한다. (타조가 위험할 때 머리만 땅에 박고 숨는 것)