[운영체제] 10. deadlock

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

 

Deadlock

Deadlock(교착 상태)란 Semaphore에서도 나왔듯이 스레드들이 서로 대기하며 모두 일을 못하는 상태를 말한다.

위같은 코드에서( L1과 L2는 공유 자원), thread 1의 mutex_lock(L1)인 채로 context switch가 발생하여 thread 2가 lock(L2)을 잡으면 스레드가 서로를 wait하며 context switch가 영구히 발생하게 된다.

 

Deadlock은 아래 4가지 특징을 동시에 가질 때 발생한다. 하나라도 해결하면 발생하지 않는다.

- Mutual exclusion : 공유 자원에 접근할 때 여러 스레드가 동시에 접근하려는 것

- Hold and wait : 자원을 할당받은 상태에서 sleep(wait) 하는 것

- No preemption : 스레드의 자원을 강제로 제거할 수 없는 것

- Circular wait : 각 스레드가 요구하는 공유 자원이 서로 참조하며 물려있는 상태

 

Methods for Handling Deadlocks

 

- Deadlock Prevention(static): 위 4가지 특징을 동시에 만족하지 않도록 하는 것이다. 시스템 성능이 안좋아지는 단점이 있다.

- Deadlock Avoidance(dynamic): 자원 할당 상태에 대한 사전 정보를 바탕으로 deadlock의 가능성이 있는 자원 요구를 허락하지 않는 방식이다.

- Deadlock Detection & recovery: Deadlock을 감지하고 발생한 deadlock을 회복시키는 방식이다.

데이터베이스 등에서 사용되는 방식으로, 제일 비용이 적은 스레드를 죽이고 시스템을 다시 시작한다. 매일 새벽에 있는 10여분간의 은행 점검시간이 이러한 작업들을 포함하기도 한다.

- ignore the problem and pretend that deadlocks never occur: 시스템에서 deadlock이 발생하지 않는 것으로 취급한다. Windows, Linux 등 대부분의 OS에서 이 방법을 사용하며, 인위적으로 재시작한다.

 

Deadlock Prevention

deadlock 4가지 특징 중 하나를 억제하는 방법으로, 대부분 프로그래머에 의해 이루어진다.

 

1. Circular wait 예방 - lock을 획득할 때 모든 스레드에 동일한 규칙을 적용하여 해결할 수 있다.

Thread 1, 2가 서로 참조하는 관계(=L1, L2의 순서가 반대)가 아닌, 모두

// thread 1
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);

// thread 2
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);

로 이루어져 있다면 deadlock이 발생하지 않을 것이다.

 

2. Hold and wait 예방 - 모든 lock을 한번에 획득하도록(=원자성) 보장하여 해결할 수 있다. 이는 기존 lock보다 더 큰 lock(아래 코드에선 prevention)을 잡으면 해결된다.

//thread 1
pthread_mutex_lock(prevention);
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);

pthread_mutex_unlock(L2);
pthread_mutex_unlock(L1);
pthread_mutex_unlock(prevention);

//thread 2
pthread_mutex_lock(prevention);
pthread_mutex_lock(L2);
pthread_mutex_lock(L1);

pthread_mutex_unlock(L1);
pthread_mutex_unlock(L2);
pthread_mutex_unlock(prevention);

이 방법은 두가지 문제점이 있다. 1.프로세스를 호출할 때 사전에 어떤 lock을 보유하는지 알고 더 큰 lock을 잡아야 한다. 2. 프로세스가 모든 필요한 리소스를 얻을때까지 기다려야 하므로 병렬성 측면에서 자원 효율이 떨어진다는 점이 있다.

 

3. No preemption 예방 -  스레드가 lock을 획득하면 해제하기 전까지 다른 스레드는 해당 lock을 얻지 못한다.

pthread_mutex_trylock() 인터페이스는 lock을 획득할 수 있는지 확인할 수 있다.

 0을 return하면 lock을 획득할 수 있고, -1이면 실패했으니 나중에 다시 시도하라는 뜻이다. 이를 사용하면 trylock()을 한 뒤 실패하면 가지고 있던 lock을 해제하는 방식으로 deadlock을 피할 수 있다.

pthread_mutex_lock(L1);
    if (pthread_mutex_trylock(L2) == -1) {
        pthread_mutex_unlock(L1); //release
        goto top;
    }
...

하지만 이는 livelock이라는 새로운 문제를 발생시킨다. livelock은 스레드가 계속해서 상태를 변경하지만, 서로 lock을 해제하고 다시 요청하는 것을 반복하여 프로세스 진전이 없는 상태를 뜻한다. 이것은 loop에 랜덤 딜레이를 주는 방식으로 해결할 수 있다. 또한 trylock() 방식은 비용적 문제가 있다. trylock()으로 다른 lock을 얻지 못했을 때, goto top을 실행하므로 그때까지의 연산 비용이 낭비되고, 메모리 할당 및 해제에 따른 오버헤드가 발생한다. 메모리 해제를 명시하지 않으면 메모리 누수가 발생할 수도 있다. 

 

4. Mutual exclusion 예방 - 상호 배제를 고려하지 않음으로써 deadlock을 피할 수 있다. 이 말은 즉, critical section에 대해 lock을 명시적으로 설정하는 것이 아니라 Compare-And-Swap같은 atomic한 hardware instruction을 사용하여 해결하라는 의미다. lock이 필요없고 deadlock도 방지하지만 이는 제한적인 작업만 가능하며, starvation의 위험이 있다.

 

Deadlock Avoidance

 

Deadlock avoidance는 어떤 스레드가 어떤 공유자원을 사용하는지 알고 있어야 한다. 같은 공유자원을 사용하는 스레드를 한 CPU에 순차적으로 넣어주면 deadlock이 발생하지 않는다.

이렇게 스케줄링하면 스레드가 어떤 공유자원을 사용하냐에 따라 특정 경우 한 CPU에 스레드가 몰릴 수 있는데, 이렇게 된다면 load balancing 관점에서 좋지 않다. 이 방식은 범용적으로 사용되는 deadlock 솔루션은 아니다.

 

Deadlock Detection & recovery

 

deadlock이 경우에 따라 발생할 수 있지만, 이를 탐지하고 recover하는 방식이다.

컴퓨터가 deadlock을 1년에 한번 발생시킨다면 컴퓨터를 재부팅하는게 더 효율적이다.