Deadlocks

Deadlocks

---

multi programming 환경에서 여러 thread가 한정된 resource를 사용하려고 서로 경쟁할 수 있다.

한 thread가 resource를 요청했을 때, 그 시각에 그 resource를 사용할 수 없는 상황이 발생할 수 있고, 그때는 thread가 대기 상태로 들어간다.

대기 중인 thread가 결코 다시는 그 상태를 변경시킬 수 없는 상황을 deadlock이라고 한다. 이 때에는 더이상 process가 진행되지 못하는 상태로 매우 치명적인 상태이다.

 

필요조건

---

deadlock은 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있다.

1. 상호 배제(mutual exclusion): 최소한 하나의 resource가 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 thread만이 그 resource를 사용할 수 있다. -> 한 번에 한 process만 사용할 수 있는 resource가 있어서 발생한다.
2. Hold and wait: 어떤 process가 resource를 잡고 있는데 다른 resource를 또 요청하는 것. 
3. No preemption: 만약 resource를 요청, 언제든 그 resource를 뺐어 자신이 사용 가능한 process가 있다면 deadlock은 발생하지 않는다. 요청하는 resource를 언제든 막힘없이 가져오기 때문이다. no preemption의 경우 뺐어올 수 없으니 대기해야 하고 deadlock이 발생할 수 있다(그 resource를 잡고 있는 process가 release하지 않는다면)
4. Circular wait: 순환대기. 대기하고 있는 thread의 집합 { T0, T1, ..., Tn }에서 T0는 T1이 점유한 resource를 대기하고 T1은 T2가 점유한 resource를 대기하고, ..., Tn-1d은 Tn이 점유한 resource를 대기하며 Tn은 T0가 점유한 resource를 대기한다.

 

Resource Allocation Graph

---

deadlock을 판별하기 위한 그래프. 시스템의 자원 할당 상황을 그래프로 나타낸다.

• P: process
• R: resource
• P -> R: Request Edge, process가 해당 resource를 요청
• R -> P: Assignment Edge, 해당 resource가 process에 할당되어 있음

 

deadlock이 발생하는 cycle.

만약 요청하는 resource가 여러개 있다면 cycle이 발생하더라도 deadlock이 발생하지 않을 수 있다.

 

cycle이 있어도 deadlock이 발생 X

P2가 R1을 가진 상태에서 release할 수 있다.

R1 하나는 P1에게 주면 되므로 P1이 수행이 끝나면서 R2 하나가 release되고 그것이 P3에 할당 가능하다.

 

 

Methods for Handling Deadlocks

---

1. Deadlock prevention: 아에 deadlock에 접근 안 하도록. resource의 활용도가 떨어질 수 있다. deadlock 발생 조건 4가지를 부정하는 것을 통해 가능.(발생하지 않도록 미리 그 조건들을 피하게 코드를 짠다거나 수정) 제약 조건이 점점 붙게 되므로 resource활용도가 떨어지는 것
2. Deadlock avoidance: resource 활용도를 좀 더 높일 수 있게된다. 조건 4가지를 부정하기는 하는데(실제로 부정은 3가지가 최대) 이것에 대해서는 banker's algorithm이 있다.