[운영체제] Deadlock(교착상태)

다중프로그래밍 시스템에서 여러 프로세스들이 돌아가는데 자칫 이 프로세스들 간에 꼬이는 경우가 발생한다.

이렇게 꼬이는 현상을 Deadlock, 교착 상태라고 한다.

 

Deadlock

위의 사진은 데드락을 나타내는 사진이다.

도로에 있는 모든 차들은 앞으로 가야 하는데 다른 차가 자신의 진행 방향을 막고 있어서 앞으로 나가지 못한다. 한마디로 움직일 수 없는 상황이다. 이 때 어떤 하나의 차가 뒤로 후진하지 않는 이상 이런 상황은 해결되지 않는다.

 

데드락은 프로세스가 자신의 자원을 점유하면서 다른 프로세스가 점유한 자원을 기다릴 때, block된 상태를 의미한다.

여기서 말하는 자원은  I/O device, CPU cycle, momory space, semaphore 등의 hw/sw 자원을 모두 포함한다.

 

데드락 발생 조건

아래의 조건들을 만족하면 데드락이 발생한다. (= 아래의 조건 중 하나라도 만족하지 않으면 데드락이 해결된다.)

 

1. Mutual Exclusion
   상호 배제
   매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
2. No Preemption
   비선점
   프로세스는 자원을 스스로 내놓을 뿐, 강제로 빼앗기지 않는다.
3. Hold and Wait
   보유 대기
   자원을 가진 프로세스가 다른 자원을 기다릴 때 보유한 자원을 놓지 않고 계속 가지고 있는다.
4. Circular Wait
   순환 대기
   자원을 기다리는 프로세스 간의 사이클이 형성되어야 한다.
   (예를 들어서 P1, P2, P3, P4가 있을 때 P1 -> P2 -> P3 -> P4 -> P1)

 

데드락이 발생했는지 어떻게 알 수 있는가?

프로세스와 그 프로세스가 사용하는 자원 간의 관계를 도식화 한 것을 Resource - Allocation Graph라고 한다.

이 그래프의 사이클 유무/상태에 따라서 데드락의 유무를 확인할 수 있다.

 

1. Cycle이 없다면?

데드락이 아니다. 

 

- P1은 R2를 가지고 있으면서 R1을 필요로 한다.

- P2는 R1, R2를 가지고 있으면서 R3를 필요로 한다.

- P3는 R3를 가지고 있다.

 

이 상황의 경우 P3의 작업이 끝나면 순차적으로 각 프로세스가 원하는 자원을 할당 받게 되면서 작업이 진행된다.

 

 

2. Cycle이 있다면?

따져봐야 한다.

 

만약 각 자원에 인스턴스가 하나만 있다면 무조건 데드락이다.

하지만 각 자원에 여러 개의 인스턴스가 있다면 데드락일 가능성이 있다. (= 아닐 가능성도 있다.)

 

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

- P4가 작업이 마무리 되면, R2를 내놓고

- P3는 R2를 받아서 작업을 마무리하고 R1을 내놓고

- P1은 R1의 자원을 받아 작업을 마무리한다.

(=> 고로, 데드락이 발생하지 않는다.)

 

 

왼쪽의 경우 오른쪽의 경우처럼 하나의 프로세스가 작업을 마무리 하기 위해서는 다른 프로세스가 점유한 자원을 사용해야 한다.

즉, 그 자원을 점유한 프로세스가 내놓아야 하는데, 내놓기 위해서는 해당 프로세스가 작업을 마무리 해야 한다. 하지만 그 프로세스 역시 다른 프로세스가 점유한 자원을 사용해야 한다. 이 말은 그 자원을 점유한 .. (무한반복)

이렇게 모든 프로세스와 자원의 관계가 꼬리물기 식으로 되어 있으므로 Deadlock인 상황이다. 

 

---

데드락 해결 방법

1. Deadlock Prevention

자원 할당 시 데드락의 4가지 조건 중 하나를 차단해서 데드락 상태에 들어가지 못하도록 하는 것이다.

 

상호배제

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

 

비선점

프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원을 선점한 상태이다.

모든 필요한 자원을 얻었을 때 프로세스는 다시 시작된다.

 

상태(state)를 쉽게 저장하고 복구(restore)할 수 있는 자원에서 주로 사용한다. (CPU/Memory)

 

보유대기 

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

그러기 위해서는 아래 두가지 방법이 있다.

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

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

 

순환대기

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

예를 들어 순서가 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

(= 무시)

데드락이 일어나지 않는다고 생각하고 아무런 조치를 하지 않는 것이다. 실제로 데드락은 드물게 발생하기 때문에 이 조치를 하는 것 자체가 더 큰 오버헤드일 수 있다.

그래서 유닉스를 포함한 대부분의 OS는 이 방식을 사용하고 있다. 데드락이 발생하게 되면 사용자가 알아서 프로세스를 종료시키는 방식으로관리한다. 

 

---

Resource Allocation Graph Algorithm & Banker's Algorithm

Deadlock Avoidance는 프로세스가 시작할 때 본인이 평생 사용할 자원들을 미리 declare하고 그걸 이용해서 데드락이 발생할 수 있는 최악의 상황, 즉 현재 상황에서 만약에 어떤 프로세스가 어떤 자원에 대한 요청을 했을 때 생길 수 있는 경우를 피해가는 방법이다.

 

여기서 두 가지 알고리즘을 사용하는데, 각 자원에 인스턴스가 하나만 있는 경우에 Resource Allocation Graph (자원할당그래프) 알고리즘을 사용하고 두 개 이상 있는 경우에 Banker's 알고리즘 (= 은행원 알고리즘)을 사용한다.

 

 

자원 할당 그래프 알고리즘

 

위의 그림에서 각 실선은 아래를 의미한다.

- 자원 -> 프로세스 : 해당 자원이 프로세스에게 할당

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

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

 

그리고 그림의 각 상황을 말하자면,

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

2. P2가 R2의 자원을 요청했고 아직 할당 받지 못한 상황

3. P2가 R2의 자원을 할당 받은 상황 

 

위의 3번째 상황에서 만약 P1이 R2를 요청할 경우, 사이클이 생성되어 데드락이 발생한다.

물론 P2가 R2를 모두 사용하고 반납 후 P1이 R2를 요청하면 문제가 생기지 않겠지만 타이밍이 안좋을 경우는 데드락이 발생할 수 있다. 

Deadlock Avoidance는 애초에 자원 이용률에 손해를 보더라도 데드락이 발생하는 최악의 상황을 피하는 것이 목적이다. 

 

그러기 위해서 2번째 상황에서 P2가 R2를 요청할 때 자원을 할당하지 않은 것이다.

혹시나 미래에 데드락이 발생할 수 있기 때문이다.

반면에 같은 2번째 상황에서 P1이 R2를 요청해서 할당받는다면 사이클이 만들어지지 않기 때문에 데드락이 발생하지 않는다.

 

여기서 매 상황에 대해 사이클 생성 여부를 조사할 때,

프로세스의 수가 n개라고 한다면 O(n^2)의 시간이 걸린다. 

 

 

은행원 알고리즘

은행원 알고리즘은 항상 최악의 경우를 생각하는 보수적인 방법으로 데드락을 회피한다. 

 

✔️ 프로세스에 할당된 자원

✔️ 한번의 요청에 최대로 필요한 자원

을 계산하고 프로세스가 자원을 요청했을 때 최악의 상황 (= 최대로 자원을 사용할 경우)를 고려해서 가용자원으로 그 조건을 만족할 수 있다면 자원을 할당하고 그렇지 않는다면 자원을 할당하지 않는다. 

 

P0, P1, P2, P3, P4 총 5개의 프로세스와 A, B, C 3개의 자원이 있으며 각 자원의 인스턴스의 수는 10개, 5개, 7개이다.

 

• Allocation : 현재 프로세스에 할당된 자원
• Max : 프로세스가 한번에 필요로 하는 최대 자원
• Available : 각 프로세스에게 할당되고 남은 자원, (시스템 내의 가용 자원)
• Need : 현재 할당된 자원에서 Max를 만족하는데 추가적으로 필요한 자원

 

위의 상황에서 P0의 자원 요청과 P1의 자원 요청을 경우를 나눠서 생각해보자.

 

1) P0이 자원을 요청

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

 

2) P1의 자원 요청

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

 

🤔 근데 이렇게 생각할 수 있습니다. 일단 P0에게 가용자원을 모두 할당하고 그 나머지를 다른 프로세스들이 반납하는 자원으로 채워주면 되지 않을까? 물론 이런 경우 Deadlock이 발생하지 않습니다.

하지만 가용자원이 (0,0,0)이기 때문에 도중에 다른 프로세스들이 자원을 요청하게 되면 Deadlock이 발생할 수 있습니다. 위에도 설명했듯이 Banker's algorithm은 보수적이기 때문에 최악의 조건을 만족하지 못한다면 프로세스에게 자원을 할당하지 않습니다.   

 

위의 경우 P0부터 자원을 요청하면 할당을 못하지만

1. P1이 자원을 요청하고 반납,

2. P3이 자원을 요청하고 반납,

3. P4이 자원을 요청하고 반납,

4. P2이 자원을 요청하고 반납,

5. P0이 자원을 요청하고 반납을 하면 모든 프로세스가 자원을 사용할 수 있다.

이런 순서가 존재하는 경우 시스템은 safe state라고 하며 Banker's algorithm은 이런식으로 자원을 할당한다.

 

Banker's algorithm은 사실 자원을 이용하는데 비효율적이다.

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