[운영체제] 데드락(Deadlock)이란? 교착상태에 대하여

목차
 데드락이란?
 데드락의 발생조건
 데드락의 처리

---

 

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

 시스템 자원에 대한 요구가 뒤엉킨 상태. 프로세스가 자원을 얻지 못하여 다음 처리를 하지 못하는 '교착상태'를 의미한다. 시스템적으로 말하면, 멀티 프로그래밍 환경에서 한정된 자원을 여러 프로세스가 사용하려고 할 때 발생하며, 그 프로세스는 서로 원하는 자원을 얻기 위하여 무한정한 대기를 한다.  간단히 말하자면, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있는 상태이다. 결과적으로는 아무것도 완료되지 못한다. 

 예를 들어, Process① 이 어떤 작업을 하기 위하여, 자원인 Resource(1)을 사용하고 있다. 근데 그 작업을 위해서는 Resource (2)도 필요하여, Resource(2)를 가져오려고 시도하였으나 이미 다른 곳에서 사용하고 있는 중이다.

바로 Process②다.  Process②는 본인의 작업을 위해 Resource(2)를 사용하고 있다. 근데, Process②는 Resource(1)가 필요한 상황이다.

 이러한 상황에서 Process①이 Resource(2)를 사용하려고 시도한다. 그러나, Process(2)가 사용중이라 대기한다. Process②는 Resource(1)을 사용하려고 하는데, Process(1)가 사용중이라 대기한다.

 두 개의 프로세스는 서로의 작업이 끝나기만을 기다리며 교착상태를 발생시킨다.

 

---

데드락의 발생조건

하단의 네가지 조건이 모두 성립하여야 데드락이 발생된다. 단, 네가지 조건이 다 성립한다고하여 꼭 교착상태가 일어나는 것은 아니다. 단지 필요조건이다.

1. 상호배제(Mutual Exclusion)

 자원은 한번에 하나의 프로세스만 사용 가능하다. 상호를 배제 한다. 즉, 오로지 나만 쓴다!

2. 점유대기(Hold and wait)

 하나의 자원을 점유하면서, 다른 프로세스에서 할당된 자원을 추가 점유하려면 대기하는 다른 프로세스가 존재하여야 한다. 이미 자신이 어떤 공유되어진 자원을 가지고 있으면서, 다른 것을 요구 할 때. 

3. 비선점(No preemption)

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

4. 순환대기(Circular Wait)

 프로세스의 집합에서 순환 형태로 자원을 대기하여야 한다. 자신에게 할당된 자원을 가지면서도, 상대방 프로세스의 자원을 상호 요청하는 경우. 서로 맞물리는 원형 구조의 형태일 때 발생한다는 의미!

 

---

데드락의 처리

1. 예방

데드락 필요조건을 부정. 애초에 데드락이 발생 할 가능성이 없게 알고리즘을 만드는 것. 개발자의 역량이 중요하다.

상호 배제 부정/점유대기 부정/비선점 부정/순환대기 부정

2. 회피

데드락 가능성을 배제하지 않고 데드락 발생하기 전, 데드락을 예상하여 안전한 상태에서만 자원 요청을 허용. 하지만, 자원 요청이 있을때마다 데드락 회피 알고리즘을 사용한다는 것은 상당히 부담스럽다. 회피에 대한 대표적 방법으로는 은행원 알고리즘이 있다.

 

* 은행원 알고리즘
자원의 총 수, 할당된 자원의 수를 계산하여 이것을 기준으로 시스템의 안정상태 유지하도록 자원을 할당하는 알고리즘.
전체 자원 : 시스템 내 전체 자원의 수
가용 자원 : 시스템 내 현재 사용할 수 있는 자원의 수 (전체자원 - 모든 프로세스의 할당 자원)
최대 자원 : 각 프로세스가 선언한 최대 자원의 수
할당 자원 : 각 프로세스에 현재 할당된 자원의 수
기대 자원 : 각 프로세스가 앞으로 사용할 자원의 수 (최대 자원 - 할당 자원)

 

예를 들어, 가용 자원이 기대 자원보다 크면 프로세스는 안정적인 상태다.

가용자원이 기대 자원보다 크지 않다면, 할당하지 않는다. 불안정한 상태이기 때문이다.

은행원 알고리즘의 안정적 상태를 그리자면 이렇다.

 

은행원 알고리즘의 안정적 상태

2개의 가용 자원을 P2 프로세스에게 할당하면, P2의 작업이 종료되면서 6개의 자원을 반환한다. 

만약, 가용 자원이 1개라면 P1, P2, P3 어느 프로세스에 할당되어도 작업이 종료되지 않기 때문에 데드락이 해소되지 않는다.

3. 탐지

 교착상태가 발생했는지 탐지하고, 탐지되었다면 교착상태를 복구한다. 원인을 규명하여 해결한다. 이 또한, 지속적 확인 작업이 들어가야하기 때문에 성능에 저하가 발생한다. 복구 방법에는 데드락 프로세스 종료/데드락 프로세스의 자원 선점 등이 있다.

4. 무시

 무시한다. 데드락의 발생 확률이 비교적 낮은 경우에는 별 다른 조치를 취하지 않는다. 해결 시 발생하는 오버헤드로 인한 성능저하가 방치할 때보다 더 클 수 있기 때문이다.

 

---

 

 

References

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