[운영체제] Deadlock 처리

오늘은 앞선 글에서 다룬 Deadlock에 대해서 OS는 어떻게 처리하는지 알아봅시다.

 

 

Deadlock을 처리하는 방법

Deadlock을 처리하는 방법에는 3가지가 있습니다.

1. Deadlock이 발생되지 않도록 예방하는 방법
2. Deadlock이 발생되었다면 이를 감지하고 해결하는 방법
3. Deadlock이 발생되어도 아무것도 하지 않는 방법

 

 

Deadlock 예방하기

우리는 이전 글에서 Deadlock이 발생하는 조건에 대해서 알아봤습니다. 

Mutual Exclusion, Hold-and-Wait, No Preemption, Circular wait. 이 네가지 조건을 모두 만족해야 Deadlock이 발생했었죠.

 

그렇다면 우리는 이 네 가지 조건 중 하나만 성립하지 않게 한다면 Deadlock이 발생되는 것을 막을 수 있습니다.

 

 

하나씩 성질들을 성립되지 않게 하는 방법을 확인해봅시다.

 

1. Mutual Exclusion

 

Mutual Exclusion을 적용시키지 않는다는 말은, 컴퓨팅 자원을 혼자 쓰는 것이 아닌 여러 프로세스가 같이 사용하도록 하자는 뜻입니다.

 

이 방법은 굉장히 위험합니다. 가령 예를 들어서 설명해보겠습니다.

회사에 프린트기가 하나 있습니다. 만약 우리가 어떤 프린트 명령을 내리게 했는데, 다른 회사원이 프린트를 또 하나 걸게 되면 한 장에 여러 내용이 담길 수 있게 될 수도 있습니다.

 

따라서 우리는 Mutual Exclusion을 적용시켜야하므로 이 성질은 성립되지 않으면 안됩니다. (성립되어야만 합니다.)

 

 

2. Hold-and-wait

 

프로세스가 자원을 가지고 있으면서 다른 자원을 요청하는 경우가 Hold-and-wait이었죠. 이 성질을 break해봅시다. 그러기 위해서는 프로세스를 실행함에 있어 시작부터 끝까지 필요한 모든 자원을 프로세스 시작과정에서 한번에 배정받아 사용하는 방법이 있겠습니다.

 

물론 이 방법이 해결책이 될 수 있습니다. 하지만 효율적이지 못합니다. 만약 어떤 프로세스가 30분의 어떠한 처리 과정을 진행한 후에 프린트를 해야하는 작업을 해야한다고 가정해봅시다. 그렇게 되면 프린트는 30분동안 아무것도 하지 못하고 있다가 그제서야 프린트를 하게 되므로 30분동안 아무 작업도 하지 않는 것이 비효율적입니다.

 

따라서 이러한 방법도 권장되지 않습니다.

 

 

3. No Preemption

이 성질을 break한다는 것. 어떤 프로세스든 자신이 컴퓨팅 자원을 필요로 할 때 사용 여부와 상관없이 뺏어온다는 것을 의미합니다. 이렇게 된다면 사용자가 프로세스의 관계를 파악하기 어렵고, 프로그램이 잘 진행되다가 block되는 등의 단점이 있습니다.

 

예를 들어 30분동안 진행되어야하는 프로세스 A가 29분 30초까지 진행되고 이제 30초만 기다리면 되는데, A가 사용중인 컴퓨팅 자원을 B 프로세스가 필요로하여 빼앗게 된다면 A는 B가 모두 사용할 때까지 block되게 됩니다.

 

따라서 이러한 방법도 사용하지 않습니다.

 

 

4. Circular wait

Hold-and-wait를 일부적으로만 허용하자는 말을 의미합니다. 지난 글에서 참조한 그림으로 다시 설명해보겠습니다.

 

이러한 경우가 Deadlock이 발생하는 경우였는데 만약 여기서 P4가 Ra라는 컴퓨팅 자원을 요청하지 않는다면 Deadlock이 발생되지 않습니다. 각 프로세스가 갖고 있는 자원보다 높은 자원만 요청하도록 설계하면 Deadlock을 예방할 수 있습니다.

 

만약 이렇게 된다면 P4는 애초에 시작할 때 Ra라는 컴퓨팅 자원을 갖고있게 설계하면 Deadlock이 발생하지 않을 수 있겠죠. 하지만 이 방법은 위와 같은 단순한 구조에서는 직관적으로 해결책이 보이지만, 이보다 더욱 복잡한 관계에서는 해결책이 보이지 않을 수 있습니다.

 

프로그램의 설계 시점부터 Deadlock을 신경써서 설계해야하는 등의 어려움이 존재합니다. 이러한 불편함때문에 우리는 4번 성질 또한 break하지 않습니다.

 

 

 

만약 이렇게 된다면 우리는 Deadlock을 예방하기란 이론상 불가능하게 되었습니다. 그렇다면 2번 방법이었던 Deadlock이 발생했을 때, 이를 탐지하고 해결하는 방법에 대해서 알아봅시다.

 

 

Deadlock 탐지하고 해결하기

Deadlock이 만약 발생했다면 어떻게 해결하면 될까요??

아마 가장 단순한 방법은 모든 프로세스를 죽이고 재실행시키는 방법일 것입니다. 왜냐하면 Deadlock은 일련의 과정에서 우연한 타이밍에 발생하기 때문이죠.

 

또는 프로세스를 하나씩 천천히 죽여보면서 Deadlock이 해결되는지를 확인하는 방법도 있겠습니다.

 

 

 하지만 문제는 Deadlock을 탐지하는 것입니다. Deadlock의 발생 주기는 실생활에서 많으면 2주에 한번 꼴로 발생합니다. 컴퓨터가 Deadlock을 확인하는 방법은 알려져있지만 이를 매순간 확인하여 Deadlock의 여부를 체크하는 것은 비효율적입니다. 마치 Overhead처럼 말이죠.

 

2주에 한번꼴로 나타나는 사태를 위해서 우리 컴퓨터가 느리게 작동하는 것은 그닥 좋지 못한 해답인셈이죠. 따라서 사실 Deadlock을 탐지하는 방법도 사용하지 않습니다.

 

 

아무 것도 하지 않기

말그대로 아무것도 하지 않는 것입니다. 사용자가 Deadlock을 감지하고 알아서 해결하게 책임을 전가하는 것입니다.

이 방식은 실제 윈도우나 리눅스에서 사용하는 방식이며 가장 효율적입니다.

 

 

 

---

Dining Philosophers Problem

Deadlock에 대한 유명한 문제가 있어 소개해볼까 합니다.

 

 

원탁에 앉아서 철학자들은 식사와 사색 중 하나를 할 수 있습니다. 원탁의 가운데에는 스파게티가 있으며, 철학자들은 아래와 같은 순서로 식사를 합니다.

 

1. 자신 포크가 탁자 위에 놓여져있다면 그것을 집어 든다. 만약 그렇지 않다면 탁자 위에 포크가 놓여질 때까지 사색을 한다.

2. 오른쪽 포크가 탁자 위에 놓여져있다면 그것을 집어 든다. 만약 그렇지 않다면 탁자 위에 포크가 놓여질 때까지 사색을 한다.

3. 양 손에 포크를 집었으므로 식사를 한다.

4. 식사를 마치면 오른쪽에 포크 하나를 내려 놓는다.

5. 나머지 하나도 자신의 앞에 내려놓는다.

6. 1번으로 돌아간다.

 

 

위 과정으로 진행됩니다. 웨이터는 음식을 철학자들에게 서빙한 후에, 오랜 시간이 지났음에도 기척이 없어 다시 확인해보았더니 모든 철학자가 굶어죽었습니다.

 

어떻게 된 걸까요?? 이것이 Deadlock을 아주 잘 설명하는 예시가 됩니다.

 

아마 이 일화를 통해서 우리가 (초보마냥) 프로그램을 짠다면 아래와 같이 짤 것입니다.

 

semaphore fork[5] = {1}; //포크가 5개가 있고 모두 semaphre의 값이 1입니다.
int i;

void philosopher(int i){
	while(true){
    	think();
        wait(fork[i]); // 내 포크를 든다.
        wait(fork[(i+1) mod 5]); // 오른쪽 포크를 든다.
        eat(); // 먹는다.
        signal(fork[(i+1) mod 5]); // 오른쪽에 포크를 둔다.
        signal(fork[i]); // 내 앞에 포크를 둔다.
    }
}

void main(){
	parbegin(philosopher[0], philosopher[1], ... );
}

 

이런 식으로 만약 프로그램을 짰다면 최악의 경우 모든 철학자들이 자신의 앞에 있는 포크를 들고, 오른쪽 포크가 빌 때까지 기다리는 상황이 발생하게 됩니다.

 

즉, Deadlock이 발생한 것이죠. 이를 해결하기 위해 어떻게 해야할까요??

 

여기서는 room이라는 semaphore를 하나 둡니다. 이 semaphore는 식사를 할 수 있는 최대 인원을 의미하고, 이를 4로 세팅합니다.

즉, 동시에 식사를 할 수 있는 사람을 4명으로 제한하는 거죠. 이렇게 되면 Deadlock 문제를 해결할 수 있습니다.

 

semaphore fork[5] = {1}; //포크가 5개가 있고 모두 semaphre의 값이 1입니다.
semaphre room = {4];
int i;

void philosopher(int i){
	while(true){
    	think();
        wait(fork[i]); // 내 포크를 든다.
        wait(fork[(i+1) mod 5]); // 오른쪽 포크를 든다.
        eat(); // 먹는다.
        signal(fork[(i+1) mod 5]); // 오른쪽에 포크를 둔다.
        signal(fork[i]); // 내 앞에 포크를 둔다.
    }
}

void main(){
	parbegin(philosopher[0], philosopher[1], ... );
}

 

 

이러한 방식으로 우리는 semaphore를 해결할 수 있습니다. 하지만 앞서 말했다시피, 이러한 단순한 문제가 아닌 복잡한 문제에서는 해결하기 어려우므로 결국 Deadlock에 대한 아무처리를 하지 않는 것이 대중적이라고 합니다.

 

---

이렇게 Deadlock에 대해서 어떻게 처리해야하는 지를 배워봤습니다. 감사합니다.