[운영체제] Deadlock

다중 프로그래밍 시스템에서 여러 프로세스들이 서로 얽혀서 돌아가는데 자칫 프로세스들 간에 꼬이는 경우가 발생합니다. 이렇게 꼬이는 현상을 Deadlock이라고 하는데요 Deadlock이 왜 발생하고 언제, 또 어떻게 해결할 수 있는 이번 시간에 알아 보겠습니다.

---

Deadlock

위의 그림을 Deadlock을 잘 설명해주고 있는 사진 입니다. 도로에 있는 모든 차들은 앞으로 가야 하지만 다른 차가 자신의 진행방향을 막고 있어 앞으로 가지 못합니다. 한마디로 아무도 움직일 수 없는 상황인데요, 먼저 뒤로 후진하지 않으면 이런 상황은 절대 풀리지 않을 것입니다.

 

Deadlock은 일련의 프로세스가 자신의 자원을 점유하면서 다른 프로세스가 점유한 자원을 기다리면서 block된 상태를 의미합니다. 여기서 자원은 I/O device, CPU cycle, momory space, semaphore 등의 hw/sw 자원을 모두 포함합니다.

---

Deadlock의 발생조건

 만약 아래의 조건을 모두 만족하면 Deadlock이 발생합니다

 

1. Mutual Exclusion

상호배제, 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

 

2. No Preemption

비선점, 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

 

3. Hold and wait

보유대기, 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유한 자원을 놓지 않고 계속 가지고 있음

 

4. Circular wait

순환대기, 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함

P1,P2,P3,P4프로세스가 있을 때 P1 → P2 → P3 → P4 → P1 

---

Deadlock이 있는지 어떻게 알 수 있을까 ?

프로세스와 그 프로세스가 사용하는 자원간의 관계를 도식환 한 것을 Resource - Allocation Graph라고 합니다. 이 그래프의 사이클 유무에 따라 현재 상태에서 Deadlock의 유무를 확인할 수 있습니다. 

 

1. 그래프에 사이클이 없으면 Deadlock이 아닙니다

 

- P1은 R2를 가지고 있으며 R1을 필요로 합니다

- P2는 R1,R2를 가지고 있으며 R3를 필요로 합니다

- P3는 R3를 가지고 있습니다

 

2. 그래프에 cycle이 있으면...따져 봐야 합니다

 

만약 각 자원에 instance(사진에서 네모 박스의 검은 점)가 하나만 있다면 무조건 deadlock입니다. 그렇지 않고 각 자원에 여러개의 instance가 있다면 deadlock 가능성이 있습니다

 

> 오른쪽의 경우 사이클이 만들어 졌지만 R2자원을 가진 P4가 작업을 마무리 하면 R2의 자원을 내놓기 때문에 사이클이 만들어 졌음에도 Deadlock이 되지 않습니다

 

> 왼쪽의 경우 오른쪽의 경우처럼 하나의 프로세스가 작업을 마무리 하기 위해서는 다른 프로세스가 점유한 자원을 사용해야 합니다. 이 말은 그 자원을 점유한 프로세스가 내놓아야 하는데, 내놓기 위해서는 해당 프로세스가 작업을 마무리 해야 합니다. 하지만 그 프로세스 역시 다른 프로세스가 점유한 자원을 사용해야 합니다. 이 말은 그 자원을 점유한......이렇게 모든 프로세스와 자원의 관계가 꼬리물기 식으로 되어 있으므로 Deadlock인 상황입니다

---

Deadlock의 처리 방법

 

1. Deadlock Prevention

자원 할당 시 Deadlock의 4가지 필요조건 중 하나를 차단하여 Dealock에 들어가지 못하도록 하는 방법

 

- Mutual Exclusion

자원을 배타적으로 사용하는 것은 막을 수 있는 조건이 아님

 

- Hold and Wait

프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야함

방법 1 : 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 방법

방법 2 : 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청

 

- No Preemption

process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨

모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작됨

state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)

 

- Circular wait

모든 자원 유헝에 할당 순서를 정하여 정해진 순서대로만 자원 할당

예를 들어 순서가 3인 자원 R1을 보유 중인 프로세스가 순서가 1인 자원 R1을 할당받기 위해서는 우선 R1를 반납해야 함

 

→ Deadlock을 원천적으로 막을 순 있지만 자원의 이용률, 전체 시스템의 성능, 기아 문제가 발생할 수 있음

 

2. Deadlock Avoidance

회피, 자원 요청에 대한 부가적인 정보를 이용해서 Deadlock의 가능성이 없는 경우에만 자원을 할당 하거나 시스템 state가 원래 state로 돌아올 수 있는 경우에만 할당

 

- 자원 요청에 대한 부가정보를 이용해서 자원 할당이 Deadlock으로 부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당

- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임

 

- 각 자원에 하나의 instance만 있는 경우 Resource Allocation Graph algorithm을 사용하고

- 각 자원에 두개 이상의 instance가 있는 경우 Banker's algorithm을 사용합니다. 

 

3. Deadlock Detection and Recover

탐지와 회복, Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 Deadlock 발견시 recover, 여기서 Deadlock의 존재 여부는 Resource - Allocation Graph를 통해 알 수 있음.

 

Deadlock 발생시 recovery 2가지 방법

- process termination : 연루된 모든 process를 죽이거나, Deadlock이 없어질 때 까지 하니씩 죽임

- resource preemption : 비용이 가장 적은 process를 선정해 자원을 회수 

 

4. Deadlock ignorance

무시, Deadlock이 일어나지 않는다고 생각하고 아무런 조치를 하지 않으며 Deadlock이 매우 드물게 발생하므로 Deadlock의 조치에 자체가 더 큰 overhead일 수 있음, UNIX를 포함한 대부분의 OS가 사용하며 사람이 프로세스가 문제 생겼을 때 프로세스를 죽이든 알아서 처리

---

Resource Allocation Graph algorithm & Banker's algorithm

Deadlock 회피(avoidance)는 프로세스가 시작할 때 본인이 평생 사용할 자원들을 미리 declare하고 그걸 이용해서 Deadlock이 발생할 수 있는 최악의 상황, 즉 현재 상황에서 만약에 어떤 프로세스가 어떤 자원에 대한 요청을 하였을 때 생길 수 있는 1%의 경우를 피해가는 방법입니다. 여기에 2가지 알고리즘을 사용하는데 각 자원에 instance가 하나만 있는 경우 Resource Allocation Graph algorithm, 두개 이상있는 경우 Banker's algorithm을 사용합니다.

1. Resource Allocation Graph algorithm

- 자원 -> 프로세스(실선) : 해당 자원이 프로세스에게 할당됨

- 프로세스 -> 자원(실선) : 프로세스가 해당 자원을 요청했지만 아직 할당받지 못함

- 프로세스 -> 자원(점선) : 프로세스가 평생에 적어도 한번은(언젠간) 해당 자원을 사용할 일이 있음

 

그림에서 각각의 3가지 상황을 나누어 설명하면,

 

1. R1자원은 P1에게 할당되어 있고 P2는 R1자원을 요청한 상황입니다. 또한 P1, P2모두 R2자원에 대해 언젠간 한번 자원을 요청할 것입니다.

2. P2이 R2의 자원을 요청하였고 아직 할당받지는 못한 상태입니다.

3. P2가 R2의 자원을 할당받은 상태 입니다.

 

위 3번째 상황에서 만약 P1이 R2를 요청하는 경우 어떻게 될까요 ? 사이클이 생성되며 Deadlock이 발생합니다. 물론 P2가 R2를 모두 사용하고 반납 후 P1이 R2를 요청하면 전혀 문제가 안생기겠죠. 하지만 타이밍이 안좋은 경우 Deadlock이 생기는 최악의 경우가 발생합니다. Deadlock Avoidance는 애초에 자원이용률에 손해를 보더라도 Deadlock이 발생하는 최악의 상황을 피하는 것이 목적입니다.

 

그러기 위해서는 2번째 상황에서 P2가 R2를 요청할 때 자원을 할당하지 않는 것이죠. 혹시나 미래에 Deadlock이 발생할 수 있으 니깐요. 반면에 2번째 상황에서 P1이 R2를 요청하여 할당받는 경우라면 괜찮습니다. 사이클이 만들어지지 않기 때문에 Deadlock이 발생하기 않습니다.

 

여기서 Cycle 생성 여부를 조사시 프로세스의 수가 n일 때 O(n^2)의 시간이 걸립니다.

 

2. Banker's algorithm

Banker's algorithm은 항상 최악의 경우를 생각하는 굉장히 보수적인 방법으로 Deadlock을 회피합니다. 프로세스의 할당된 자원과 한번의 요청에 최대로 필요한 자원을 계산하고 프로세스가 자원을 요청했을 때 최악의 상황을 고려(최대로 필요한 자원)하여 만약 가용자원으로 그 조건을 만족할 수 있으면 자원을 할당하고 그렇지 않으면 자원을 할당하지 않습니다.

 

P0, P1, P2, P3, P4프로세스와 A,B,C자원이 있으며 각각의 instance 수는 (10,5,7)입니다.

- Allocation : 프로세스에게 할당된 자원

- Max : 프로세스가 한번에 필요로하는 최대 자원

- Available : 각 프로세스에게 할당되고 남은 자원, 시스템 내의 가용자원

- Need : 현재 할당된 자원에서 Max를 만족하는데 추가적으로 필요한 자원

 

1) P1의 자원 요청

P1이 자원을 요청하는 경우 요청하는 자원의 양이 아주 적은 양인지 Max양인지 모릅니다. 하지만 Banker's algorithm에서는 최악의 경우 즉, Max를 요청한다고 가정합니다. 현재 가용 자원은 (3,3,2)이고 Max를 만족하는데 더 필요한 양은 (1,2,2)이기 때문에 P1에게 자원을 할당할 수 있습니다.

 

2) P0이 자원을 요청

P0이 자원 요청을 하는 경우 현재 가용 자원은 (3,3,2)인데 현재 프로세스에 할당된 자원에서 Max를 만족하려면 (7,4,3)이 더 필요합니다. 이는 가용자원보다 더 많은 양이기 때문에 P0에게는 자원을 할당할 수 없습니다. 

 

근데 이렇게 생각할 수 있습니다. 일단 P0에게 가용자원을 모두 할당하고 그 나머지를 다른 프로세스들이 반납하는 자원으로 채워주면 되지 않을까 ? 물론 이런 경우 Deadlock이 발생하지 않습니다. 하지만 가용자원이 (0,0,0)이기 때문에 도중에 다른 프로세스들이 자원을 요청하게 되면 Deadlock이 발생할 수 있습니다. 위에도 설명했듯이 Banker's algorithm은 보수적이기 때문에 최악의 조건을 만족하지 못한다면 프로세스에게 자원을 할당하지 않습니다.   

 

위의 경우 P0부터 자원을 요청하면 할당을 못하지만 P1이 자원을 요청하고 반납, P3이 자원을 요청하고 반납, P4이 자원을 요청하고 반납, P2이 자원을 요청하고 반납, P0이 자원을 요청하고 반납을 하면 모든 프로세스가 자원을 사용할 수 있습니다. 이런 순서가 존재하는 경우 시스템은 safe state라고 하며 Banker's algorithm은 이런식으로 자원을 할당합니다.

 

Banker's algorithm은 사실 자원을 이용하는데 비효율 적입니다. Deadlock이 생길것은 두려워하여 가용자원이 있음에도 자원을 할당하지 않기 때문이죠. 보통 Deadlock이 생기지 않습니다. 위에서 말한 것처럼 여러 프로세스가 항상 자원을 필요로 하는 것이 아니기 때문에 반납하는 자원을 사용하여 다른 프로세스가 필요한 자원을 보충하기 때문이죠. 하지만 Banker's algorithm에서는 최악의 경우를 고려하여 자원을 할당여부를 결정합니다.