17. Deadlock

 

1. Deadlock
   1. 2개 이상의 task들이 1개 이상의 resource를 요청하며, 서로 resource를 받기를 기다리고 있을 때 Deadlock이 발생한다.
2. Deadlock 발생 조건 4가지
   
   1. Mutual exclusion 
      1. 두 개 이상의 task들이 서로 share 해서 쓸 수 없는 resource 여만 한다.
      2. (하나의 쓰레드가 어떤 자원을 사용하고 있다면, 다른 쓰레드는 요청을 하고 반납이 될 때까지 대기해야 함) 
   2. Hold and wait 
      1. 어떤 resource가 필요한데 acquire하는 도중에, 다른 resource가 필요하면 내가 가지고 있는 것은 든 상태로 기다린다.
      2. (쓰레드는 반드시 적어도 1개의 자원을 가지고 있어야 하며, 추가적인 자원을 얻기 위해서는 다른 쓰레드의 사용이 끝나길 대기해야 함
   3. No preemption 
      1. 어떤 resource를 줬으면 함부로 뺏어가지 않는다.
      2. (사용중인 자원은 중간에 뺏어갈 수 없다.)
   4. Circular wait 
      1. P1부터 PN까지의 task가 있는데 언젠가는 circular한 상황이 발생한다.
3. 도로와 차의 관계에서 Deadlock
   1. Mutual Exclusion : 도로는 두 차가 다 차지할 수 없으므로, 도로는 Mutual Exclusive 한 resource이다.
   2. Hold and Wait : 내가 도로를 차지한 상황에서 다음 도로를 가져가야 한다.
   3. No preemption : 내가 도로를 차지한 상황에서 다른 차가 내 도로를 차지할 수 없다.
   4. Circular Wait : 돌고 돌아서 대기중인 상태이다.
4. 어떻게 하면 Deadlock이 발생하지 않을까?
   1.  Deadlock Prevention 
      1. Deadlock의 조건 중 하나라도 발생 안 되게 하면 된다.
      2. Mutual exclusion 부정
      3. Hold and wait 부정
         1. 단점
            1. 자원 활용성이 떨어진다 : Resource를 계획적으로 쓰지 않아서
            2. Starvation이 발생할 수 있다 : 요구하는 resouce가 적은 task들이 계속 가져간다면
      4. No preemption 부정
         1. preemptive하게 만들어주면 된다.
      5. Circular wait 부정
         1. total ordering 부여 : 한방향으로 리소스를 잡게끔 만들어준다.
   2.  Deadlock Avoidance 
      1. Safe한 상태
      2. Unsafe한 상태 : 모두가 필요한 리소스를 배분해줄 수 없을 때
      3. Unsafe할 때 리소스를 주지 않고 Safe할 때만 리소스를 준다.
      4. Banker’s Algorithm
         1. safe sequence가 있다면 할당해주는 방법 (그림 참조)
         2. 단점 : 최대 자원 요구량을 미리 알아야 한다.
   3.  Deadlock Recovery 
      1. Deadlock이 발생한 상황을 알아내고 해결하는 것
      2. Process termination
      3. Resource preemption
   4.  Ignoring Deadlock 
      1. 처음부터 Deadlock 안나게 하는 것

---

 

 

 

서로서로 상대방의 lock을 기다리면 Deadlock이 걸린다.

 

---

 

---

 Deadlock 이란? 

 

Deadlock : 2개 이상의 task 들이 서로서로 한 개 이상의 type이나 resource 인스턴스를 요청해야하고,

또 하나는 어떤 task가 resource를 잡고 있고, 또 다른 task가 그 resource를 받기를 기다리고 있어야 Deadlock이 발생한다.

---

 Deadlock이 발생하기 위한 조건 4가지 

 

Deadlock이 발생하기 위한 조건 4가지

 

1. Mutual exclusion : 두 개 이상의 task들이 서로 share 해서 쓸 수 없는 resource 여만 한다.
   (하나의 쓰레드가 어떤 자원을 사용하고 있다면, 다른 쓰레드는 요청을 하고 반납이 될 때까지 대기해야 함) 
   
   
2. Hold and wait : 어떤 resource가 필요한데 acquire하는 도중에, 다른 resource가 필요하면 내가 가지고 있는 것은 든 상태로 기다린다.
   (쓰레드는 반드시 적어도 1개의 자원을 가지고 있어야 하며, 추가적인 자원을 얻기 위해서는 다른 쓰레드의 사용이 끝나길 대기해야 함)
   
   
3. No preemption : 어떤 resource를 줬으면 함부로 뺏어가지 않는다.
   (사용중인 자원은 중간에 뺏어갈 수 없다.)
   
   
4. Circular wait : P1부터 PN까지의 task가 있는데 언젠가는 circular한 상황이 발생한다.

이 4가지 조건이 모두 성립되면 Deadlock이 발생한다.

---

 

도로와 차의 관계에서 Deadlock

Mutual Exclusion : 도로는 두 차가 다 차지할 수 없으므로, 도로는 Mutual Exclusive 한 resource이다.

Hold and Wait : 내가 도로를 차지한 상황에서 다음 도로를 가져가야 한다.

No preemption : 내가 도로를 차지한 상황에서 다른 차가 내 도로를 차지할 수 없다.

Circular Wait : 돌고 돌아서 대기중인 상태이다.

 

---

 어떻게 하면 Deadlock이 발생하지 않을까? 

---

 (1) Deadlock Prevention 

Deadlock 발생 조건 중 하나만이라도 발생 안시키게 하면 된다.

 

1) 상호 배제 (Mutual exclusion) 부정
- 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
2) 점유 대기 (Hold and wait) 부정
- 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
3) 비선점 (No preemption) 부정
- 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
4) 순환 대기 (Circular wait) 부정
- 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

---

Hold and Wait : 아예 시작할 때 모든 resource를 잡고 시작해라

task 0 : A B C

task 1 : B A D

각 task가 시작할 때 A 잡고 B 잡고 C 잡고, 모두 잡고 진행시키기.

다른 task 0이 B가 필요한데 task 1이 B를 잡고있다?

그러면 task 0이 모든 Resource를 다 놓고 처음으로 돌아가서 다시 A B C 순으로 잡는다.

 

문제점 :

1. Resource를 계획적으로 쓰는게 아니라서 활용성이 떨어진다.
   
   task 0 : A B
   task 1 : B A
   서로 잡고 놓고 잡고 놓고 하기 때문에 자원 활용이 떨어진다.
   
   
2. Starvation이 발생할 수 있다.
   
   task 0 : A B C D .... X Y Z
   task 1 : C Z D
   요구하는 resource가 적은 task들이 계속 가져가면 starvation이 발생할 수 있다.

---

No preemption : 누군가 resource를 할당해서 사용하고 있는데 가로채와서 쓰게 가능하게 하면 된다.

복잡하다.

---

 Circular wait를 막으려면 

Resource를 잡는 순서를 정해놓고 

순서가 작은것부터 큰것으로 잡는것처럼 한방향으로 잡게끔 만든다.

total ordering을 부여해서 Circular wait를 막는다.

---

 

순서대로 한방향으로 잡아놓으면 기차처럼 resource를 잡아간다.

---

 

---

 

---

이처럼 Deadlock을 막으려면 Deadlock의 필요조건 중 한가지만 막으면 된다.

 

---

 (2) Deadlock Avoidance 

프로그램의 상태는 Safe한 상태, Unsafe한 상태가 있다.

 

 Deadlock Avoidance : 교착 상태가 발생하면 피해나가는 방법

- 은행원 알고리즘 (Banker’s Algorithm)
E,J,Dijkstra가 제안한 방법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법이다.
프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피하는 기법
안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기함
교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 이용하는 방법

---

 

컴퓨터에서 모든 프로세스들이 자원을 요구하고 사용하고 release하는 것을 다 안다라고 가정했을 때

이러한 모든 요청을 다 완료할 수 있으면 Safe state라고 한다.

프로세스들이 리소스 요청이 올 때 모두가 필요한 리소스를 배분해줄 수 없다면 Unsafe state라고 한다.

---

 

처음부터 리소스가 100개가 필요하지 않으면 initially safe한다.

P0 : 5개 필요

P1 : 3개 필요

P2 : 5개 필요

 

---

 

현재 리소스는 2개 남아있고 P0 : 2개, P1 : 2개, P2 : 2개 가 필요한 상황이다.

P0에게 리소스를 다 주고, 다 쓴 다음에 반환하고

그 후 P1에 리소스를 다 주고, 다 쓴 다음에 반환하고

이렇게 하면 모두 safe state이다.

 

---

 

이 상황에서 만약 P1이 리소스를 할당해주라고 한다면?

 

---

 

P1에게 리소스를 할당해주더라도 P1에게 할당하고 그 다음 P0, 그 다음 P2에게 할당해주는

safe sequence가 있기 때문에 safe state로 갈 수 있으니까 resource allocation 할 수 있다.

---

 

 

P2가 필요하다고 했을 때는?

---

 

어디로 가든 safe sequence가 없으므로 unsafe state 이다.

그러면 리소스를 주지 않고 버틴다.  -> Deadlock avoidance

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 Banker's Algorithm 

 

리소스 타입 A,B,C 가 있다.

각 프로세스 P0, P1, ... P4 는 resource allocation plan이 있다 = MAX

---

P1에 할당한다고 하면, 할당 한 후 safe sequence가 있는지 확인해야 한다.

 

Allocation

   2 0 0

+ 1 0 2 

= 3 0 2

 

Need

   1 2 2

- 1 0 2

= 0 2 0

 

Available

  3 3 2

- 1 0 2

= 2 3 0

---

2 3 0 가지고 다 주면 일을 끝낼 수 있는 것을 찾는다. (Available ≥ Need)

P1 에 주면 일을 다 끝낼 수 있다.

 

P1 이 일을 다 끝내고 반환한다면

Available은 

   2 3 0

+ 3 0 2

= 5 3 2

가 된다.

---

---

 

P1은 끝나고 다른 사장님을 찾는다.

P3 사장님에게 빌려준다.

---

 

 

 

 

 

---

 

P4가 (3,3,0)을 달라고 하면 

safe sequence가 없으므로 할당해 줄 수 없다.

---

 

---

단점 :
할당할 수 있는 자원의 수가 일정해야 한다.
사용자 수가 일정해야 한다.
항상 unsafe state를 방지해야 하므로 자원 이용도가 낮다.
최대 자원 요구량을 미리 알아야 한다.
프로세스들은 유한한 시간 안에 자원을 반납해야 한다.

---

 (3) Deadlock Recovery 

Deadlock이 발생한 상황을 알아내고 해결하는 것

---

---

 (4) Ignoring Deadlock 

니가 알아서 해라. 애초에 짤 때 잘 짜라.

대부분 이 방식을 채택한다.