[Operating System] Concurrency Bugs

위의 표에서 보듯이 많은 어플리케이션들에서 발생하는 버그는 주로 concurrency와 관련이 있다. 이 포스팅에서는 여러 concurrency 버그 중에서 데드락(Deadlock)에 대해서 다룬다.

 

 

Deadlock이란?

 

데드락은 두 개 이상의 쓰레드가 있을 때 서로 상대방이 끝나기만을 기다려서 어떤 것도 진행되지 못하는 상황을 의미한다.

복잡하고 큰 시스템에서는 모듈들 간에 dependency를 파악하기가 상당히 까다롭기 때문에 데드락에 대처하기가 어렵다. 또한 많은 모듈들이 캡슐화 되어 있어서 모듈 내부에서 어떤 식으로 lock을 잡고 놓는지 파악하는 것도 어려운 일이다.

 

 

Deadlock이 발생하는 조건

데드락이 발생했다는 건 다음 4가지 조건이 모두 만족 되었다는 의미이다. 이는 다시 말해서 다음 4가지 조건 중에 하나라도 만족하지 않으면 데드락이 발생하지 않는다. 따라서 우리는 아래 조건들 중 최소 한 개는 만족되지 않도록 프로그래밍을 해야만 한다.

 

조건	설명
Mutual Exclusion	각 쓰레드들은 공유 자원에 접근할 때 상호 배제를 필요로 한다.
Hold-and-Wait	쓰레드들은 자신이 필요로 하는 자원이 생길 때까지 CPU 자원을 붙잡고 놓지 않는다.
No Preemption	어떤 쓰레드가 CPU 자원을 놓지 않고 붙잡고 있을 때, 다른 쓰레드에서 강제적으로 이를 뺐어갈 수 없다.
Circular Wait	두 개 이상의 쓰레드들 사이에서 서로가 서로의 종료를 기다리면서 자신이 필요로 하는 자원이 free해지길 기다린다.

 

 

1. Circular Wait 해결

위의 그림은 쓰레드 1은 Lock A를 잡은 상태에서 Lock B가 release 되길 기다리고, 쓰레드 2는 Lock B를 잡은 상태에서 Lock A가 release 되길 기다리고 있다. 이런 상황에선 두 쓰레드 모두 진행이 될 수가 없다.

 

이런 상황을 해결하려면 항상 lock을 일정한 순서로 잡아야 한다. 즉 쓰레드 1에서 lock(A) => lock(B) 순서로 lock을 잡았다면, 쓰레드 2에서도 lock(A) => lock(B) 순서대로 lock을 잡아야한다. 그렇게 해야만 아래의 그림과 같이 circular dependency가 사라진다.

 

 

하지만 복잡한 프로그램 속에서 lock의 순서를 일관적으로 유지하는 것은 프로그래머에게 쉬운 일이 아니다. 따라서 OS 차원에서 가상 주소 순서대로 lock을 잡아야만 하도록 강제하는 방법도 있다.

 

 

2. Hold-and-Wait 해결

어떤 쓰레드에서 lock A, lock B, lock C를 필요로 할 때, lock A와 lock B를 잡은 상태에서 lock C를 기다리는 상황을 생각해보자. Lock C가 free해질 때까지 lock A, B를 놓지 않고 붙잡고 있기 때문에 lock A, B를 필요로 하는 다른 쓰레드들이 진행을 할 수 없다.

 

문제를 해결하기 위한 간단한 방법은 모든 lock을 atomic하게 한번에 얻고, 한 번에 release 하는 것이다. 아래의 예시 코드를 보면 metalock(lock을 위한 lock)을 통해 여러 개의 lock을 atomic하게 잡고 있다. Release도 마찬가지로 metalock을 통해 atomic하게 한 번에 release한다.

 

lock(&meta);
lock(&L1);
lock(&L2);
...
unlock(&meta);

/*** Critical Section ***/

lock(&meta);
...
unlock(&L2);
unlock(&L1);
unlock(&meta);

 

이런 방법은 상호배제를 필요로 하는 critical section의 granularity를 증가시켜서 프로그램의 병렬성을 크게 저하시킨다는 문제가 있다. 따라서 가능하면 데드락의 4가지 조건 중 다른 조건을 resolve하는 편이 더 현명하다.

 

 

3. No Preemption 해결

어떤 쓰레드가 lock $M$을 계속 붙잡고 있을 때 $M$을 필요로 하는 다른 쓰레드에서 강제적으로 $M$을 뺐어 올 수 없는 상황을 의미한다. 이 조건을 resolve 하기 위한 간단한 방법은 trylock을 사용하는 것이다. 일반적인 mutex_lock은 lock을 잡으려고 시도를 했다가 다른 쓰레드에서 이미 lock을 잡은 상태면 release 될 때까지 기다린다. 하지만 trylock은 lock을 잡으려고 시도를 했는데 다른 쓰레드가 사용 중이면 그냥 -1을 리턴하고 다음 명령으로 넘어간다. 따라서 trylock을 쓰면 deadlock이 걸릴 수가 없다. 단, 기다리는 매커니즘을 구현하기 위해서 while loop과 함께 사용해야한다.

 

trylock을 사용하면 데드락 문제는 해결 가능하지만, 실질적인 progress는 이루어지지 않고 lock을 잡으려고 시도하는 코드만 반복적으로 실행하는 livelock 문제가 생긴다. 이를 해결하기 위해서는 exponential backoff로 delay를 주면서 trylock을 하도록 해야한다.

 

 

4. Mutual Exclusion

동시성 프로그래밍에서 상호배제는 무조건 있어야 하기 때문에 상호배제를 없애는 건 말이 안 된다. 그렇다면 상호배제를 resolve 하여 데드락을 방지하는 건 불가능 한가? 그렇지 않다!

 

Pthread_mutex_lock과 같은 경우 lock을 잡지 못하면 lock을 잡을 수 있을 때까지 기다린다. 하지만 HW 레벨에서 구현된 atomic instruction을 사용하면 기다리지 않고도 상호배제의 효과를 거둘 수 있다.

 

Lock 관련 포스팅에서도 다룬 Test-And-Set, Compare-And-Swap과 같은 ISA에 정의된 명령을 사용하면 lock을 사용하지 않고 상호배제가 가능하다. 다음 예시를 살펴보자.

 

void insert(int value) {
    node_t *n = malloc(sizeof(node_t);
    assert(n != NULL);
    n->value = value;
    lock(listlock);
    n->next = head;
    head = n;
    unlock(listlock);
}

 

 위의 코드는 쓰레드 간에 공유되는 list 자료구조에 대해 상호배제를 제공하기 위해 lock을 사용하고 있다. 이를 Compare-And-Swap 명령을 사용해서 wait-free하게 구현한다면 다음과 같다.

 

void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n->value = value;
    do {
        n->next = head;
    } while (CompareAndSwap(&head, n->next, n);
}

 

CAS를 사용한 위의 코드에선 lock을 잡고서 기다리지 않기 때문에 절대로 deadlock이 발생하지 않는다.

 

 

추가) 스케줄링을 통한 데드락 해결

만약 스케줄러가 각 함수에서 어떤 lock을 acquire / release 하는지 파악하고 있다면 데드락이 생기지 않도록 스케줄링을 할 수 있다.

예를 들어, 2개의 CPU가 존재하고 총 4개의 쓰레드가 있다고 하자. 4개의 쓰레드는 L1 또는 L2 lock을 acquire 하고자 하는 상황이다.

 

 

 만약 위의 table 대로 각 쓰레드가 lock을 잡으려고 하는 프로그램이 있다면 똑똑한 스케줄러는 아래와 같이 CPU에게 쓰레드를 할당할 것이다.

 

 

T1와 T2는 동일하게 L1과 L2를 모두 acquire하려 하기 때문에 데드락의 가능성이 있다. 따라서 이들은 같은 CPU run queue에 넣어서 sequential하게 수행되도록 한다. 한편, T3와 T4는 T1, T2와 병렬적으로 실행되어도 데드락의 가능성이 없기 때문에 CPU 1에서 돌아가도록 하면 된다.