[운영체제] 데드락(Deadlock, 교착 상태)이란

데드락(Deadlock, 교착 상태) 이란?

---

1. 데드락(Deadlock, 교착상태)

그림 1.

프로세스는 실행을 위해 여러 자원을 필요로 한다. CPU, 메모리, 파일 등등 여러 자원을 사용하여 프로세스가 실행된다. 그러나 어떤 자원은 갖고 있으나 다른 자원을 갖지 못할 경우 대기 상태에 들어가서 기다려야 한다. 자원은 한정되어 있는데 여러 프로세스가 같이 동작하는 상황이여서 이러한 상황이 발생하게 된다. 그러므로 운영체제는 이러한 자원을 프로세스에게 잘 할당을 해주어야 한다.  만약 운영체제가 잘 할당을 해주지 못하면 모든 프로세스가 자원을 가지려고 대기하는 교착상태에 빠질 수 있다. 

 

즉, 데드락(Deadlock, 교착상태)이란, 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 되어 더 이상 진행이 될 수 없는 상태를 의미한다.

 

---

2. 데드락(Deadlock) 발생 조건

✔ 상호 배제(Mutual exclusion) 

한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

 

✔ 점유 대기(Hold and wait)

최소 하나의 자원을 보유하고 있고 다른 프로세스에 할당 된 자원을 점유하기 위해 대기하고 있는 것이다.

 

✔ 비 선점(No Preemption)

프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.

 

✔ 순환 대기(Circular wait)

자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다. (그림 1.)

ex) 프로세스 p0, p1, p2, ..., pn이 있을 때, p0은 p1을 기다리고 p1은 p2를 기다리고,.., pn은 p0을 기다린다.

 

프로세스 간의 관계를 그래프로 도식화 해보면 데드락이 발생할지의 여부를 알 수 있다. 이 그래프를 Resource-Allocation Graph(자원 할당 그래프)라고 한다. 

 

(왼) 데드락 (오) 데드락 x

 

R은 자원이고 P는 프로세스를 의미한다. 자원 내의 동그라미는 자원(인스턴스)의 개수이다. 자원에서 프로세스로 향하는 간선

(자원 → 프로세스)은 해당 자원을 프로세스가 보유 중(Allocate)라는 의미이고, 프로세스에서 자원으로 향하는 간선

(프로세스 → 자원)은 프로세스가 해당 자원을 요청(Request)했다는 의미이다. 

 

만약 그래프에 사이클(Cycle)이 없다면 Deadlock이 아니다. 반면, 사이클이 존재한다면 Deadlock이 발생할 수 있다. 즉, 자원당 하나의 인스턴스만 있는 경우에는 Deadlock 이고, 여러 인스턴스가 존재하는 경우에는 Deadlock일 수도 아닐 수도 있다.

 

---

3. 데드락(Deadlock) 해결 법

• 데드락이 발생하지 않도록 예방(Prevention) 한다.
• 데드락 발생 가능성을 인정하면서도 적절하게 회피(Avoidance)한다.
• 데드락 발생을 허용하지만 데드락을 탐지(Detection)하여, 데드락에서 회복한다.

---

4. 데드락 예방(Prevention)

데드락의 발생조건 4가지 중 하나라도 발생하지 않도록 하는 것이 데드락을 예방하는 방법이다. 즉, 각각의 조건을 방지 하여 데드락 발생 가능성을 차단한다.

 

✔ 자원의 상호 배제 조건 방지:

한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다. 

 

✔ 점유 대기 조건 방지:

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

따라서 프로세스를 시작할 때 모든 필요한 자원을 할당 받게 하거나, 자원이 필요한 경우 보유하고있던 자원을 모두 반납하고 다시 요청하는 방식을 이용한다. 

 

✔ 비 선점 조건 방지:

프로세스가 어떤 자원을 기다려야 하는 경우 보유하고 있던 자원이 선점된다. 그리고 모든 필요한 자원을 얻을 수 있을 때 그 프로세스가 다시 시작된다. 

 

✔ 순환 대기 조건 방지:

자원의 타입에 따라 프로세스마다 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다. 

 

하지만 이렇게 사전에 Deadlock을 방지하는 방식은 효율성과 처리량을 감소시키고, Starvation이 발생할 수 있다. 

 

---

 5. 데드락 회피(Avoidance)

데드락(Deadlock)이 발생할 가능성이 있는 경우에는 아에 자원을 할당하지 않는 방식이다. 가장 단순하고 일반적인 모델은 프로세스들이 필요로하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.

• 시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해줄 수 있다면 안정 상태(Safe state)에 있다고 말한다.
• 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면 그것을 안전 순서(Safe sequence)라고 한다. 

5-1. 자원 할당 그래프 알고리즘(Resource Allocation Graph Algorithm)

 

점선으로 표시된 간선(Claim edge)은 프로세스가 자원을 미래에 요청할 수 있음을 의미한다. 그리고 해당 자원을 요청하는 경우 실선(Request edge)으로 바뀌게 된다. 자원을 할당받으면 방향이 반대인 간선(Assignment edge)이 된다. 만약 자원을 다 쓰고 반납하게 되면 다시 Claim edge로 바뀐다. 

 

Deadlock를 피하는 방법은, Request edge가 Assignment edge로 변경될 때 점선을 포함하여 사이클이 생기지 않는 경우에만 요청된 자원을 할당하는 방식으로 작업하는 것이다. 

 

 

5-2. 은행원 알고리즘(Banker's Algorithm)

여러 인스턴스가 존재하는 경우엔 사이클만으로 판단할 수는 없다.  Banker's Algorithm은 dijkstra가 고안한 알고리즘이며, 이는 프로세스가 자원을 요청할 때마다 수행된다. 

 

정의

✔ 모든 프로세스는 자원의 최대 사용량을 미리 명시한다.

✔ 프로세스가 요청 자원을 모두 할당 받은 경우 유한 시간 안에 자원들을 다시 반납한다. 

 

자원을 요청할 때 safe 상태를 유지하는 경우에만 할당한다. 즉, 총 요청 자원의 수가 남은 자원의 수보다 적은 프로세스만 선택하여 수행한다. 만약 그런 프로세스가 없다면 unsafe 상태인 것이다. 할당 받은 프로세스가 종료되면 모든 자원을 반납하고, 모든 프로세스가 종료될 때까지 이 과정을 반복한다. 

 

---

6. 데드락 탐지(Detection) 및 회복(Recovery)

 

✔ 탐지 기법

Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색한다. 즉, 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악한다.

 

✔ 회복 기법

데드락을 탐지 기법을 통해 발견한 경우 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다.

 

• 단순히 프로세스를 1개 이상 중단시키는 방법
  • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산 중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있다.
  • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드 락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있다. 
• 자원을 선점하는 방법
  • 프로세스에 할당된 자원을 선점해서 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법이다.