14. [Deadlock Problem] : Deadlock 문제는 언제 발생하는가

Deadlock은 흔히 차선이 하나뿐인 도로 위에 마주보고 오도가도 못하는 자동차들에 비유를 한다. 

1차선 도로에 두 자동차가 마주보고 서있다면, 두 자동차 중 하나는 차를 뒤로 빼주어야 한다.

이를 프로세스에 비유하자면, deadklock 문제가 발생하였을 때 프로세스들은 자원을 preempt 하고, rollback 해야 한다. 

Deadlock 문제는 특정 자원(resource)을 잡고 있으면서, 동시에 다른 특정 자원을 사용하기 위해 기다리는 blocked process 들에 의해 발생한다. 

문제를 접근할 때 두가지만 기억하면 된다. 자원을 잡고 있는 (Holding), 자원을 기다리는 (Waiting).

 

모든 프로세스는 자원을 request 하여 --> hold 하여 사용하고 --> 사용을 다 하면 release 한다.

다른 프로세스가 그 자원을 이미 사용 중이라면 wait 한다. 

 

 

그렇다면, Hold and Wait 하고 있는 프로세스들이 정확히 어떤 상황에서 Deadlock problem을 마주하게 되는걸까? 원인을 알면 해결할 수 있지 않을까?

 

Deadlock 이 발생하는 상황을 시각적으로 쉽게 이해하기 위해서 우리는 Resource Allocation Graph (RAG) 라는 그래프를 이용한다. Vertex, Edge, 그리고 부수적으로 자원을 나타내는 점을 이용하여 그림으로 나타내는 것이다. 아래의 그림에서 R1 타입의 자원이 3개, R2 타입의 자원이 1개 있고, 프로세스는 2개 있는 것을 확인할 수 있다.

 

아래 예제는 Deadlock 이 발생한 상황이다. 두 프로세스가 hold and wait 을 하고 있고, cycle을 이루고 있다.

 

 

Deadlock 이 발생하는 조건에 대한 첫번째 가설을 생각해낼 수 있다.

Theorem 1 : RAG 에 cycle 이 없다면, deadlock 문제는 일어나지 않는다. cycle 은 필요조건일 뿐이다.

 

Cycle 이 있다고 해서 무조건 deadlock 문제가 생기는 것은 아니라는 건데, 이는 어떻게 증명할 수 있을까?

아래와 같이 노는 자원이 있는 반례를 그릴 수 있겠다. 

 

 

Deadlock 이 발생하는 조건에 대한 두번째 가설을 생각해낼 수 있다.

Theorem 2: 만약 자원이 종류마다 한 개씩 밖에 없고, 프로세스와 자원이 cycle을 이룬다면, 무조건 deadlock이 발생할 것이고 반대로도 마찬가지일 것이다. 

아래와 같이 그림으로 나타낼 수 있다.

 

 

이제 Deadlock 이 발생하는 필요조건에 대해 아래와 같이 정리해볼 수 있겠다.

아래의 4가지 조건을 동시에 만족할 때 Deadlock은 발생할 수도 있다.

 

① Mutual exclusion 상호배제 : 하나의 자원은 한번에 하나의 프로세스만 사용할 수 있다.

② Hold and wait : 자원을 hold 하면서 다른 자원을 wait 하는 프로세스들 사이에서 발생한다.

③ No preemption : 자원을 hold 하고 있는 프로세스의 자력에 의해서만 자원이 release 될 수 있다.

④ Circular wait : RAG 에 cycle이 존재해야 한다.