[운영체제] DeadLock과 DeadLock 예방법

 

 

DeadLock이란?

 

 

DeadLock이란 두 개 이상의 프로세스들이 서로의 자원을 요구하며 Block 상태로 무한정 대기하는 것을 말한다.

이러한 현상은 서로가 서로에게 있는 자원을 원하지만 자원이 Release 되지 않았기 때문에 발생한다.

 

 

그림을 보면 DeadLock 발생하는 상황은 각 프로세스가 자원을 가지고 있지만, 상대 프로세스에게 있는 자원을 기다리며 일어난다.

 

 

데드락에 걸릴 수 있는 자원의 종류로는 두 가지가 있다.

 

• Reusable Resources(재사용 가능한 자원)
  • release된 이후에 사용가능하다.
  • 오직 하나의 프로세스에 의해서만 사용된다.
  • 각 프로세스가 하나의 리소스를 가지고 있고, 그와 동시에 다른 리소스를 요청할 때 데드락이 발생한다.
• Consumable Resources
  • 한 번 자원이 프로세스에게 할당되면, 다시는 다른 프로세스에게 할당되지 않는다.
  • 한 번 자원이 사용되면, 없어진다.

 

 

 

Reusable Resources는 하나의 자원을 공유하기 때문에 한정된 자원을 두 프로세스가 모두 요청하지 못하는 상황이 발생한다. 예를 들면, 200 Kbytes의 공간만 메모리에서 사용할 수 있다고 가정해 보자.

 

 

이때, P1에서 80 Kbytes만큼 사용하고 Time slice가 발생하여 P2로 제어권이 넘어갔다. 아직까진 200 - 80 = 120의 공간이 남아있으므로 70 Kbytes를 할당할 수 있다. 하지만 그 이후에 P1와 P2에서 요청을 보내야 하는 자원의 용량은 남은 용량(10 Kbytes) 보다 현저히 크다. 더 이상 두 프로세스는 요청을 보내지 못하는 것이다.

 

 

Consumable Resources는 각 프로세스가 receive 되길 바라는 Block 상태에 있을 때 발생한다. 예를 들어 Signal이나 Interrupts와 같은데, 아래 상황을 보자.

 

 

 

P1에서는 P2로부터 요청을 받기 위해 대기하고 있다. 이때 P2 또한 P1으로부터 요청을 받기 위해 대기한다. 즉, 서로가 서로에게 요청을 보내주길 기다리고 있을 뿐 어느 누구도 요청을 보내지 않는다.

 

 

 

 

 

위 그림은 데드락이 발생하는 것과 발생하지 않는 것과의 차이를 나타낸 그림이다. 데드락이 일어나는 상황 먼저 살펴보자면 P1 프로세스는 Ra라는 자원을 요청함과 동시에 Rb라는 자원을 이미 차지하고 있다. 따라서 현재 상태는 Block이다. P2 프로세스는 Rb 자원을 요청함과 동시에 Ra를 이미 차지하고 있다. 마찬가지로 Block상태이다.

두 프로세스가 모두 Block상태이면서 끝나지 않는다. 데드락 상태인 것이다.

 

 

반대로 일어나지 않는 상황에서는 Ra와 Rb라는 자원이 모두 2개 이상이다. 요청을 했을 때 각 프로세스는 Block 상태로 들어갈 이유가 없어진다. 따라서 데드락 상태가 아니다.

 

 

 

 

 

 

DeadLock이 발생하는 조건?

 

 

데드락은 결국 발생하는 조건이 정해져 있다. 이 중 어느 하나라도 지켜지지 않는다면 데드락은 일어나지 않는다.

 

1. Mutual Exclusion
   • 오직 하나의 프로세스만이 한 번에 하나의 리소스를 사용한다.
2. Hold and Wait
   • 프로세스는 자원을 하나 차지함과 동시에 다른 자원을 요청해야 한다.
3. No preemtion
   • 이미 점유된 자원은 어느 다른 프로세스에 의해 가로채질 수 없다.
4. Circular wait
   • 프로세스가 요청하는 자원은 어느 다른 프로세스가 이미 점유한 것이 되는데, 이러한 구조가 꼬리를 무는 방식으로 구현되어야 한다.

 

다음은 위 조건을 모두 만족시키는 Deadlock의 한 예시이다.

 

 

 

 

 

DeadLock을 어떻게 해결할까?

 

 

데드락을 해결하는 방법은 크게 세 가지다.

 

 

1. 시스템이 절대 데드락 상태에 들어가지 않도록 한다.
2. 데드락 상태로 진입해도 좋으나 그 이후에 복구한다.
3. OS는 아무것도 하지 않고, 사람이 하도록 내버려둔다.
   • 대부분은 이 방식을 사용한다.

 

 

얼핏 보면 1번이나 2번을 사용할 것 같은 데 실상은 그렇지 않다. 왜 그럴까?

1번부터 차근차근 살펴보도록 하자.

 

 

 

 

 

1. 데드락을 예방하기

 

 

데드락을 만족하기 위해서는 앞서 배웠던 4가지 데드락의 조건을 지켜야 했다. 반대로 말하자면 이 4가지 조건을 지키지 않으면 데드락에 걸리지 않는다.

 

 

첫 번째로 Mutual Exclusion을 깨버린다. 하지만 이는 사실상 불가능하다. Mutual Exclusion은 Race Condition을 지켜주기 위해 가장 중요한 개념이기 때문이다.

 

 

두 번째는 Hold and  Wait을 지키지 않는다. 대신 자원을 초기에 모두 갖도록 해야 한다. 그래야 나중에 새로운 자원을 요청하지 않기 때문이다. 하지만 이 방법도 여전히 좋지 않다. 한 프로세스가 초기에 모든 자원을 점유해 버린다면 해당 자원을 사용하는 다른 프로세스 입장에서는 굉장히 비효율적이다.

 

 

세 번째는 No preemption을 지키지 않는다. 다른 프로세스가 자원을 뺏는 걸 가능하게 하는 것이다. 하지만 99퍼센트만큼 완료된 프로세스인데 자원을 뺏겨서 다시 실행해야 한다고 생각해 보자. 사용자 입장에서는 생각만 해도 화날 것이다.

 

 

네 번째는 Circular Wait을 지키지 않는 것인데, 사실상 가장 가능할 법한 얘기다. 꼬리를 무는 방식으로 구성하지 않으면 언젠가는 모든 프로세스가 자원을 사용한다. 다만, 꼬리를 물지 않도록 해야 하기 때문에 하나의 프로세스는 초기에 모든 자원을 가지고 있어야 하는, Hold and Wait을 어겨야만 한다.

이 방식은 문제가 없어 보이나, 초기에 모든 자원 가지고 있는 하나의 프로세스(즉, 꼬리에 해당되는 프로세스)가 가장 먼저 실행되도록 코딩한다면 데드락이 발생한다.

 

 

따라서 데드락을 예방하는 방법은 완벽하지 않으며 현실적으로 불가능하다.

 

 

 

 

Hold and Wait를 지키지 않는 방법

 

 

Dining Philosophers Plomblem에서 Hold and Wait을 지키지 않는 방법으로 데드락을 예방해보자.

 

 

이 문제는 철학자 5명이 원탁 테이블에서 하나의 음식을 놔두고 밥을 먹고 생각하는 과정을 반복한다. 이때 음식을 먹기 위해서 자신과 자신의 오른쪽 사람의 포크를 들어야 한다. 음식을 다 먹은 후에는 포크들을 내려놓고 생각하다가 다시 배고파지면 포크를 든다.

 

 

먼저 데드락이 발생하도록 코드를 짜면 아래와 같다.

 

 

semaphore fork [5] = {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(0 {
    parbegin (philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4));
    ...
}

 

 

언뜻 보면 올바른 코드처럼 보인다. 각 사람이 자신의 포크를 들고 자신의 오른쪽 사람의 포크를 든다.

세마 포어 값이 1면 wait에 들어가 있는 동안 다른 사람은 자신의 포크나 자신의 오른쪽 사람의 포크를 들지 못한다.

그리고 음식을 먹고 포크를 내려놓는 것을 통해 다른 사람들이 음식을 먹도록 한다.

 

 

하지만 여기에는 큰 문제점이 있다. 만약 모든 사람들이 _wait (fork [i])_하는 와중에 Context Switch 한다고 가정해 보자. 각 사람들은 이제 자신의 오른쪽 사람의 포크를 들어야 하나 모두가 자신의 포크를 들고 있어 가져오지 못한다.

모두가 자신의 오른쪽 사람의 포크만 바라본 채 아무도 음식을 먹지 못하는 것이다.

 

 

이 코드를 데드락이 발생하지 않도록 하려면 세마포어를 더 추가해야 한다.

 

semaphore fork [5] = {1};
semaphore room = {4};
int i;
void philosopher (int i) {
    while (true) {
       think(); // 생각하기
       wait (room);
       wait (fork[i]);
       wait (fork[(i+1) mod 5)]);
       eat(); // 먹는다.
       signal(fork[(i+1) mod 5]);
       signal(fork[i]);
       signal (room);
}

void main(0 {
    parbegin (philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4));
    ...
}

 

 

_room_이라는 세마포어가 추가됐다. 4명의 사람이 포크를 들고 있다면 나머지 한 사람은 어느 한 사람이 포크를 내려놓을 때까지 자신의 포크를 집지 못하는 것이다.

따라서, 데드락 상황을 예방할 수 있다.

 

 

 

 

 

2. 데드락이 감지된 이후에 복구하기

 

 

중요한 것은 데드락이 탐지되는 알고리즘이 적용되었냐이다.

복구 자체는 사람이 결정할 일이다. 물론 이러한 복구 프로세스는 관리자의 코드 단에서 구현한다.

 

 

데드락이 발생하고 나서 모든 프로세스를 종료시킨다면, 사실상 데드락은 없어질 것이다.

이러한 방법은 굉장히 비효율적이다. 대신 하나의 프로세스만 종료시키는 방법을 사용한다.

 

 

종료시켜야 하는 프로세스는 그 우선순위는 사람이 정한다. 이는 프로세스 자체의 우선순위를 보고 결정하기도 하며, CPU가 할당된 시간을 따르기도 하는 등 복합적인 요소들로 결정한다.

 

 

 

 

 

 

 

 

3. OS는 아무것도 하지않고, 사람이 하도록 내비두기

 

 

이 방법에는 데드락 탐지 알고리즘을 적용하지 않는다. 사람이 그냥 프로세스가 전부 Block 상태에 걸린 것을 보고 아, 데드락이 걸렸구나 파악하는 것이다.

 

그리고 복구과정 또한 사람이 알아서 판단하여 처리한다.(사실 상 복구 프로세스는 2번과 동일하다.)

 

 

 

 

Banker's Algorithm

 

Banker's Algorithm은 앞서 보았던 데드락 해결 방법 중에 첫 번째에 해당되는 방식에 속한다.

다만 다른 점은 데드락 상황을 피하기 위해서 앞선 4가지 조건을 깨버리는 것이 아니라 미리 계산을 하고 자원을 할당하지 못한다면 CPU 제어권을 다른 프로세스로 넘겨버린다.

 

 

 

 

앞서 보았던, 200 Kbytes를 할당할 수 있는 자원에서 데드락 상황을 피해보자.

 

 

만약 80 KB만큼의 자원을 P1에서 할당하고 P2로 Context Swtich 됐다고 해보자.

그러면 70KB의 할당 여부를 확인하기 위해서 모든 프로세스에서 앞으로 할당해야 할 메모리를 각각 계산한다.

이때 120 - 70 = 50밖에 남지 않으므로, 앞으로 남은 P1와 P2의 자원을 할당하지 못한다.

 

 

따라서 P2에서 70KB를 할당하면 데드락 문제가 발생할 수 있다. 이를 방지하기 위해 70 KB을 할당하지 않고 P1으로 넘어가 60 KB를 처리한 후 자원을 Release 하도록 해야 한다.

 

 

Banker's Algorithm은 굉장히 좋아 보이나 모든 프로세스가 앞으로 사용할 자원을 계산해야 한다. 이는 현실적으로 불가능하고 몇 안 되는 데드락 순간을 위해 매번 자원을 계산해야 하므로 매우 비효율적이다.