(39) Deadlock - Resource Allocation Graph

### Resource Allocation Graph ###

: Graph는 V: vertices, E: edges(link, 연결성), node 로 구성)

​

: Request edge

=> thread 가 리소스(여러개 가능)를 요청하고 대기하는 상황)

​

: Assignment edge

=> 구체적인 리소스가 요청 thread에게 실제 할당되는 연결성

 

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018)

 

 

 

<Example>

1.

: graph내에서 사이클이 존재 할때 deadlock을 발생시킬 수 있는 risk가 있다

(circular wait과 관련)

 

: 리소스에서 instance가 여유가 있으면 deadlock 발생 하지 않는다(hold and wait관련)

 

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018)

 

 

 

2.

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018)

 

: T3랑 R2사이에 Request edge가 되어 있는 상태입니다. 그래서 2개의 사이클이 존재하고 있는 것을

알수 있습니다.

 

첫번째 사이클은 T1->R1->T2->R3->T3->R2->T1 으로 request edge와 assignment edge가 교차로 이뤄지는 사이클입니다.

 

두번째 사이클은 T2->R3->T3->R2->T2 인 사이클입니다.

 

이 사이클로 인해 T1,T2,T3는 deadlock상태에 있습니다.

조금더 자세히 설명을 하자면 T1이 R1을 요청하고 있는데 R1은 T2에 의해서 적용이 되고 있고 T2는 R3에 대해 대기하고 있고

 

R3는 T3에 적용하고 있고 T3 는 R2를 대기하고 있고 R2(instance가 2개)는 T1과 T2에의해 적용되고 있는 형태 즉 사이클이 발생한 것을 보여주고 있습니다.

(+ 각 thread(T)에 가용한 리소스는 instance 1개 씩입니다.)

 

결국

=> 사이클이 있을 때 가용 리소스 instance가 사이클당 1개 씩만 포함이 되어 있다면 deadlock이 발생합니다.

그러나 여유 리소스 instance가 있으면 deadlock을 막을 수 있습니다.

 

 

 

3.

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018)

가용 instance는 사이클에 여러개 있을 수 있다.