[운영체제/OS] 데드락(Deadlock)의 개념과 발생조건

🧐 0. 들어가면서

이전 포스팅까지 동기화(Synchronization) 이슈에 대해 공부했습니다. 동기화 이슈는 단일프로세서나 멀티프로세서 모두 일어날 수 있는 이슈였는데, 유저모드와 커널모드에서 System call의 리소스에 대한 중복 호출이나, Interrupt Handler가 접근하는 리소스가 중복되는 등의 문제로부터 야기될 수 있었습니다.

 

이번 시간부터 공부 할 데드락(Deadlock) 문제는 Multiple Process에서의 교착 상태 문제를 다루는 것입니다. 동기화 이슈와 약간 비슷한 느낌으로 사용할 수 있는 자원은 정해져있는데, 이 자원을 사용하고 싶은 다수의 프로세스가 존재할 때 발생하죠. 

 

---

1. 데드락의 발생 상황

A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.

 

데드락이 발생하는 상황은 위와 같이 정의되어 있는데요. 데드락이 발생하기 위한 정확한 필요조건은 밑에서 다시 살펴보도록 하고, 예시를 들어 데드락에 대한 감을 잡아보겠습니다.

 

만약 시스템에 두 개의 I/O 장치 P1, P2가 있다고 해보겠습니다. 그리고 현재 Process1, Process2는 각각 하나의 I/O 장치를 할당받은 상태이며 다른 프로세스가 가지고 있는 I/O 장치까지 할당받아 작업을 해야만 프로세스가 종료되는 상황입니다.

 

이 상황에서는 두 프로세스 P1, P2가 모두 상대방 프로세스가 종료되고 자원을 반납(Release)해야 원하는 자원을 자신이 사용할 수 있게 되죠.

 

하지만, 이미 자신이 하나의 I/O 장치를 가지고 있게 되면 서로 상대방이 I/O 장치를 반납하기만을 기다렸다가 평생 자기 할 일을 못하는 상황이 되는 것입니다. 

 

바로 이런 상황이 데드락의 발생 상황입니다. 여러 프로세스가 동시에 자원을 할당받고 있으면서 서로 다른 프로세스가 할당받고 있는 자원을 기다리는 상태죠.

 

 

---

2. Resource Allocation Graph

그래프를 바탕으로 데드락에 대한 상황을 이해해보겠습니다. 그래프의 각 Vertex는 프로세스와 자원을 의미하고 Edge는 프로세스가 자원에게 보내는 요청과, 자원이 할당된 정보를 의미합니다.

Resource Allocation Graph

위 그래프에서 좌측의 Visualization Process 는 Memory Frame 자원에 대한 할당을 요청하고, 자신은 Frame Buffer 자원을 할당받고 있습니다.

 

하지만 Memory frame 자원은 PostScript Interpeter라는 프로세스에게 전부 할당되어 있고, 반대로 PostScript Interpreter는  Visualization Process에게 할당된 Frame Buffer라는 자원을 할당받기를 기다리죠.

 

Resource Allocation Graph를 바탕으로 생각해보면 데드락은 언제 발생할까요?

• 만약 그래프에 Cycle이 존재하지 않는다면, Deadlock은 발생하지 않는다.
• Cycle이 있는 그래프는 Deadlock 발생의 필요조건(Necessary condition)이다.
• 만약 어떤 Resource Type에 오직 하나의 instance밖에 없다면, Cycle이 발생하는 순간 데드락이 발생한다.

 

자, 그러면 이제 본격적으로 데드락이 발생하게 되는 상황에 대해 정의해보겠습니다.

---

 

3. Necessary Conditions for a Deadlock

공룡책을 보면 아래와 같은 네 가지 상황이 동시에 발생해야 데드락이 발생한다고 합니다. 역으로 생각해보면, 이 중에 하나라도 성립이 안되면 데드락은 발생하지 않고, 추후에 이게 데드락을 방지하는 방법이 될 수 있다는 뜻이겠죠?

1.  상호배제(Mutual Exclusion): Non-sharable한 resource가 존재해야 한다.
2.  점유대기(Hold and Wait): 프로세스는 Resource를 점유하고 있는 동시에 다른 프로세스가 들고 있는 Resource를 Wait하고 있다.
3.  비선점(No preemption): Resource는 자신을 점유하고있는 프로세스에 의해서만 release될 수 있다.
4.  순환대기(Circular wait): 2번 내용을 포함하고 있는데, 그래프에 Cycle이 있어야 한다는 것이다.

즉, 공유된 자원 속에서 자원을 소유한 상태로 비동기적으로 요청을 할 수 있고, 한 번 소유한 자원은 반납 전까지 뺐을 수 없으며 내가 아닌 다른 프로세스가 자원을 가지고 있다면 데드락이 발생한다는 것입니다. 

 

하지만, 이 조건은 필요조건(Necessary Condition)이지 충분 조건(Sufficient Condition)은 아닙니다. 다시 말해, 위 상황에서 데드락이 발생할 수 있다는 것이지, 항상 데드락이 생긴다는 것은 아니죠. 

 

어떻게 그럴 수 있는지 예시를 들어보겠습니다.

 

아래에서 살펴 볼 코드는 멀티쓰레딩 환경에서 데드락이 발생한 상황을 보여줍니다. 우선 아래와 같이 두 개의 Mutex 자원이 초기화됩니다.

pthread mutex t first mutex;
pthread mutex t second mutex;
pthread mutex init(&first mutex,NULL);
pthread mutex init(&second mutex,NULL);

이 상황에서 Thread(1)은 Mutex1, Mutex2를 차례대로 얻으려 하고, Thread(2)는 Mutex2, Mutex1을 차례대로 얻으려고 한다고 하겠습니다.

 

그러면 Thread(1)이 Mutex1을 할당받고 Thread(2)는 Mutex2를 할당 받아버리는 순간, 데드락이 생길 수 있겠죠. 왜냐하면 서로가 Mutex 하나씩을 들고 있고, 상대방이 들고 있는 Mutex를 할당받아야 종료되기 때문입니다.

/* thread one runs in this function */
void *do work one(void *param)
{
    pthread mutex lock(&first mutex);
    pthread mutex lock(&second mutex);
    /**
    * Do some work
    */
    pthread mutex unlock(&second mutex);
    pthread mutex unlock(&first mutex);
    pthread exit(0);
}
/* thread two runs in this function */
void *do work two(void *param)
{
    pthread mutex lock(&second mutex);
    pthread mutex lock(&first mutex);
    /**
    * Do some work
    */
    pthread mutex unlock(&first mutex);
    pthread mutex unlock(&second mutex);
    pthread exit(0);
}

하지만 위의 예시에서 우리는 데드락이 발생할 수 있다고 했지, 항상 발생한다고는 안했습니다.

 

만약 Thread1이 Thread2가 Mutex2를 할당받기 전에 먼저 두 개의 Mutex를 모두 할당받고 끝나버리면, 다시 두 개의 Mutex는 Release되고, Thread2가 이를 다시 할당받아서 정상적으로 돌아갈 수 있기 때문이죠.

 

뿐만 아니라, 쓰레드가 실행되는 스케줄링 순서 역시 CPU 스케쥴러에 의해 정해지기 때문에 CPU 스케줄러가 적절히 동작한다면 데드락이 꼭 발생할 것이라고 보장하기는 어렵습니다.

 

따라서, 위에서 설명한 것처럼 상호배제, 점유대기, 비선점, 순환대기라는 네 조건은 데드락 발생에 대한 필요조건일 뿐이지, 충분조건이 되는 것은 아닙니다.

 

4. 나가면서

이번 글에서는 데드락(Deadlock)은 무엇이며 어느 상황에서 발생할 수 있는지에 대해 공부해봤는데요. 데드락이 발생하는 상황에 대해 언급했으니, 이제 데드락을 해결할 수 있는 방법에 대해 공부해봐야겠죠?

 

위에서 잠깐 힌트를 드렸던 것처럼 데드락을 방지하고 해결할 수 있는 방법은 데드락을 발생시킬 수 있는 상황과 반대 상황을 조성해주는 것입니다.

 

이와 관련된 내용을 다음 글에서 보도록 하겠습니다.