데드락이 걸릴 수 있는 간단한 시나리오로는, 여러 쓰레드가 병렬적으로 실행되고있을때 쓰레드마다 락을 얻으려는 순서가 서로 바뀌어있는 경우이다.

예를 들어 쓰레드1이 L1에 해당하는 락을 얻은 상태로 L2 락을 얻으려고 하는 상황이다.

그러나 쓰레드2는 쓰레드1이 L2 락을 요청하기 전에 이미 자신이 실행하면서 L2를 잡아놓은 상태로 L1 락을 얻으려고 하는 것이다.

결국 두 쓰레드가 서로 L1과 L2 락을 점유한 상태로 상대의 락을 얻으려고 대기하게 되는데, 이러면 둘 다 빠져나올 수 없는 암울한 상황에 놓이고 이것이 데드락이다.

이렇게 데드락이 발생하기 위한 아래의 4가지 조건들을 다 만족해야만 데드락이 걸린다(걸릴 수 있는 가능성이 생긴다).

• Mutual exclusion : 쓰레드가 락 등을 사용함으로써 특정한 자원에 대한 exclusive 한 제어를 가짐

• Hold and wait : 락을 여러개 사용해야할 때, 어떤 락 하나를 잡아놓은 상태로 다른 락을 잡을때까지 대기하는 상황

• No preemption : 한번 자원을 얻으면 자기 일이 끝날때까지 뺏기지 않는 상태로, 쓰레드가 락을 점유한 이후에는 락을 스스로 풀기 전까지는 놓지 않음

• Circular wait : 각 쓰레드들이 요청하는 자원(락)에 대해 순환이 발생

다시 말해 4가지 조건들 중 하나라도 만족하지 않으면 데드락은 발생하지 않는다는 뜻이 되기 때문에, 데드락을 prevent 하기 위한 방법들이 있다.

Hold and wait

L1을 얻고 L2를 얻는 행위 자체를 아토믹하게 만들어버리면, 중간에 다른 쓰레드가 L2를 가져가지 못한다.

따라서 L1과 L2 락을 얻는 부분에, 아래처럼 앞뒤로 다른 락을 하나 걸어서 L1과 L2를 한번에 같이 가져갈 수 있도록 만들어준다.

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

먼저 prevention 으로 락을 걸어놓은 뒤 두개의 락을 가져가기 때문에, 다른 쓰레드에서 L2를 중간에 가져가려고 하더라도 prevention 락에 의해 막히게 된다.

락이 실제로 필요한 시점에 가져가는 것이 아니라, 필요한 모든 락을 한번에 잡아놓고 수행하기 떄문에 병행성이 저하되는 문제점이 있다.

No Preemption

쓰레드가 한번 락을 얻으면, 자신의 작업이 끝날때까지 락을 뺏기지 않는 상황을 바꿔보는 방식으로, trylock 이라는 함수를 활용할 수 있다.

일반적으로 락은 얻지 못하면 쓰레드가 block 돼서 슬립상태로 넘어가지만, trylock은 락의 상태를 보고, 내가 얻지 못하겠다 싶으면 에러를 발생시켜서 예외 처리를 가능하게 해준다.

따라서 락을 얻지 못하면 기존에 잡아놨던 L1을 풀어준 뒤 처음부터(L1을 잡는 부분부터) 다시 시도하는 것이다.

top:
    pthread_mutex_lock(L1);
    if(pthread_mutex_trylock(L2) != 0)
    {
        pthre_mutex_unlock(L1);
        goto top;
    }

L1을 얻은 뒤 trylock 으로 L2를 얻을 수 있다면 그대로 크리티컬섹션에 진입하지만, L2를 얻지 못하면 L1 을 unlock한 뒤 top 으로 돌아가 재시도한다.

이 경우 데드락은 걸리지 않지만, 최악의 경우 쓰레드가 무한 반복에 빠지는 live lock 이 걸릴 수 있다.

Circular wait

만약에 자원(락)들에 대해, 전체적으로 순서를 매긴 뒤 모든 쓰레드가 락을 얻을 때 그 순서를 지켜야 한다고 만들어버릴 경우 순환 문제에서 벗어날 수 있다.

이를 global ordering(total ordering) 이라고도 하는데, 사실 전체 시스템에서 이를 구현하는 것이 쉽지는 않다.

리눅스에서는 메모리 매핑하는 부분에서 partial ordering으로 서로 다른 그룹으로 묶인 락들에 대한 순서를 매겨놓았다.

혹은 락의 메모리 주소를 기반으로 순서를 지정할 수 있는데, 어떤 함수가 여러개의 락을 파라미터로 받는 경우, 서로 다른 쓰레드들 간에 해당 함수를 호출하는 과정에서 락의 순서를 다르게 넘겨줄 수 있다.

쓰레드 1은 func(L1, L2) 와 같이 호출하는 반면 쓰레드 2는 func(L2, L1) 과 같이 호출하는 경우, func 함수 안에서 락을 획득할 때는 이를 구별하지 못하기 때문이다.

이런 경우 아래와 같이 메모리 주소를 비교함으로써 그 순서를 지정해준다.

if(L1 > L2)
{
    pthread_mutex_lock(L1);
    pthread_mutex_lock(L2);
}
else
{
    pthread_mutex_lock(L2);
    pthread_mutex_lock(L1);
}

항상 락의 주소가 큰 것을 먼저 획득하게 함으로써 데드락 상황을 방지할 수 있다.