교착상태(Deadlock)

다중 프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁할 수 있다. 한 프로세스가 자원을 요청했을 때, 자원을 사용할 수 없는 상황이 발생할 수 있고, 그 경우 프로세스는 대기 상태로 들어간다. 이처럼 대기 중인 프로세스들이 대기 상태를 변경할 수 없는 상황을 교착상태라고 한다.

​즉, 교착상태는 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 의미한다.

​

교착상태가 발생하기 위해서는 다음 네 가지 조건이 모두 충족되어야 한다.

 

현재의 대부분의 운영체제들은 교착상태를 막을 수 없다. 따라서 교착상태가 발생했을 때 이를 처리하는 3가지 방법이 존재한다.

 

그렇다면 교착상태를 처리하는 방법들에 대해서 간단하게 알아보자.

​먼저 교착상태 예방(Deadlock Prevention)이다. 교착상태 예방은 자원의 요청 조건을 제한함으로써 교착상태가 발생하기 위한 네 가지 조건 중 적어도 한 조건을 성립하지 않도록 보장하는 방법이다.

​

그렇다면 교착상태가 발생하기 위한 네 가지 조건들을 어떻게 제한할까? 다음과 같이 제한한다.

 

하지만 mutex 락과 세마포어 같은 자원에는 적용할 수 없는 등 많은 문제들이 발생하게 된다. 또한, 자원 낭비가 굉장히 심하기 때문에 사실상 교착상태를 예방하는 것은 불가능한 수준이다.

​

다음으로 교착상태 회피(Deadlock Avoidance)이다. 교착상태 회피는 교착상태에 빠질 가능성이 있는지 없는지를 운영체제가 검사하고 빠질 가능성이 없을 경우에만 자원을 할당함으로써 교착상태 발생을 피하는 방법이다.

​교착상태에 빠질 가능성이 있는지 없는지를 판단하기 위해 '안전 상태'와 '불안전 상태'로 구분한다. 운영체제는 안전 상태를 유지할 수 있는 친구에게만 자원을 할당해 줌으로써 교착상태 발생을 회피한다.

​상태를 구분하기 시스템은 프로세스들이 실행되기 전에 각자 자원이 얼마나 필요하고 어떻게 요청할 것인지에 대한 추가 정보를 제공하도록 요구한다.

​교착상태 회피를 위한 대표적인 알고리즘으로는 은행원 알고리즘(Banker's Algorithm)이 있다.

​

다음으로 교착상태 탐지(Deadlock Detection)이다.

​교착상태 탐지는 시스템에 교착상태가 발생했는지를 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미한다. 이를 위해 교착상태 탐지 알고리즘과 자원 할당 그래프 등을 활용한다.

​교착상태 탐지 알고리즘이나 자원 할당 그래프를 통해 교착상태가 존재한다고 결정되면 이를 처리해야 한다. 한 가지 방법은 교착상태가 발생한 것을 운영자에게 통지해, 운영자가 수작업으로 처리하게 하는 방법이고 다른 방법은 시스템이 자동적으로 교착상태로부터 회복하게 하는 교착상태 회복(Deadlock Recovery)이다.

 

​회복을 위해선 교착상태를 깨뜨려야 하는데 두 가지 방법이 존재한다. 첫 번째 방법은 순환 대기를 깨뜨리기 위해 단순히 한 개 이상의 프로세스를 중지(abort) 시키는 프로세스 종료(Process Termination)이다.

​프로세스 종료하는 방법은 교착상태 프로세스를 모두 중지시키는 방법과 교착상태가 제거될 때까지 한 프로세스 씩 종료하는 방법이 있다.

​모두 중지시키는 방법은 확실하게 교착상태의 사이클을 깨뜨릴 수 있지만 이에 따른 비용이 크다. 왜냐하면 현재 프로세스 중 오랫동안 연산했을 프로세스가 존재할 수도 있기 때문이다. 현재 작업 중인 프로세스도 종료되기 때문에 그만큼의 손실을 가지게 된다.

​한 프로세스씩 종료하는 방법 역시 매번 탐지 알고리즘을 호출하여 교착상태에 빠졌는지를 확인해야 하기 때문에 상당한 오버헤드를 유발한다. 또한 비용을 최소화시키기 위해 어떤 프로세스부터 종료시킬 건 지를 결정해야 한다. 프로세스의 우선순위를 매기기 위한 다양한 요인들이 존재하기 때문에 이 또한 쉽지 않은 문제이다.

​

두 번째 방법은 교착상태에 있는 하나 이상의 프로세스들로부터 자원을 선점(Resource Preemption) 하는 방법이다. 자원 선점을 이용해 교착상태를 제거하려면, 교착상태가 깨어질 때까지 프로세스로부터 자원을 계속적으로 선점해 이들을 다른 프로세스들에게 주어야 한다.

​선점이 필요할 경우 다음의 세 가지 사항들을 고려해야 한다.

 

현대에 우리가 주로 사용하는 Linux와 Windows 등 대부분의 운영체제들은 교착상태가 발생하게 되면 무시하는 방법을 사용한다.

​그 이유는 첫 번째로 대부분의 시스템에서 교착상태가 발생할 확률이 상당히 낮기 때문이다. 또한 위에서 각 방법들을 살펴봤듯이 교착상태 예방, 회피, 탐지, 회복 방법은 별로 발생하지 않는 교착상태를 위해 많은 자원과 비용이 필요하기 때문에 굉장히 비효율적인 방법이다.