교착 상태의 개념

6장에서 잠금으로 경쟁 조건을 막았더니, 이번에는 프로그램이 아무 오류 메시지 없이 멈추어 버리는 일이 생길 수 있습니다. 작업 완료 로그가 더는 찍히지 않고, CPU 사용률은 거의 0인데 프로세스는 살아 있습니다. 스레드 덤프를 떠 보면 몇몇 스레드가 잠금을 기다린 채 꼼짝하지 않고 있습니다. 이것이 교착 상태(deadlock, 데드락)일 수 있습니다.

경쟁 조건이 실행 순서에 따라 결과가 틀어지는 문제라면, 교착 상태는 스레드나 프로세스, 트랜잭션 같은 작업들이 서로가 쥔 자원을 기다리느라 아무도 진행하지 못하는 문제입니다. 잠금, 세마포어, 조건 변수 같은 동기화 도구도 얻는 순서와 돌려주는 규칙을 잘못 짜면 교착 상태를 만듭니다. 이 글에서는 교착 상태가 무엇이고 언제 생기는지 정리하고, 다음 글들에서 이를 막고, 피하고, 찾아내는 방법을 다룹니다.

서로가 쥔 것을 기다리는 상태

교착 상태는 여러 작업이 각자 자원을 쥔 채 다른 작업이 쥔 자원을 기다려, 그 대기가 스스로 풀리지 않는 상태입니다. 좁은 골목에 양쪽에서 차가 들어와 마주 보고 섰다고 생각해 보세요. 어느 한쪽이 후진하지 않는 한 둘 다 빠져나갈 수 없습니다. 프로그램에서 후진에 해당하는 것은 쥐고 있던 자원을 돌려주는 것인데, 돌려주는 코드가 원하는 자원을 얻은 다음에야 실행되도록 짜여 있다면 아무도 후진할 수 없습니다.

전형적인 모양은 두 스레드가 잠금 두 개를 서로 반대 순서로 얻는 것입니다.

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

static pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

static void *thread_a(void *arg)
{
    (void) arg;
    pthread_mutex_lock(&lock1);
    printf("[A] lock1 획득, lock2를 기다림\n");
    sleep(1);                         /* B가 lock2를 잡을 시간을 준다. 순서를 보장하지는 않는다. */
    pthread_mutex_lock(&lock2);
    printf("[A] 두 잠금 획득\n");
    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

static void *thread_b(void *arg)
{
    (void) arg;
    pthread_mutex_lock(&lock2);
    printf("[B] lock2 획득, lock1을 기다림\n");
    sleep(1);
    pthread_mutex_lock(&lock1);
    printf("[B] 두 잠금 획득\n");
    pthread_mutex_unlock(&lock1);
    pthread_mutex_unlock(&lock2);
    return NULL;
}

int main(void)
{
    pthread_t ta, tb;
    pthread_create(&ta, NULL, thread_a, NULL);
    pthread_create(&tb, NULL, thread_b, NULL);
    pthread_join(ta, NULL);           /* 두 스레드가 멈추면 main도 여기서 영원히 기다린다. */
    pthread_join(tb, NULL);
    return 0;
}

A가 lock1을, B가 lock2를 먼저 얻으면 두 스레드는 두 번째 pthread_mutex_lock에서 멈춥니다. 네 번의 잠금 호출을 시간 순서로 적어 보면 이유가 보입니다. A가 lock1을 얻고, B가 lock2를 얻습니다. A는 lock2를 요청하지만 B가 쥐고 있으므로 기다리고, B는 lock1을 요청하지만 A가 쥐고 있으므로 기다립니다. 각 스레드가 잠금을 돌려주는 unlock은 두 번째 잠금을 얻은 뒤에야 실행되므로, 이 상태에서는 돌려주는 코드까지 갈 수 있는 스레드가 하나도 없습니다.

sleep(1)은 이런 겹침이 일어날 기회를 줄 뿐 보장하지는 않습니다. 스케줄링에 따라 한 스레드가 두 잠금을 모두 얻고 끝낸 뒤 다른 스레드가 시작하면 정상적으로 끝나기도 합니다. 그래서 교착 상태는 가끔만 나타나고, 실행 결과를 몇 번 보는 것으로는 없다고 말할 수 없습니다. 또 멈춘 두 스레드는 잠들어 기다리므로 CPU를 거의 쓰지 않습니다. CPU 사용률이 낮다는 것만으로 교착 상태라고 단정할 수는 없지만, 프로세스가 살아 있는데 아무 일도 하지 않는다면 의심해 볼 만합니다.

다음 Python 코드는 같은 상황을 언제나 재현되도록 만든 것입니다. Barrier로 두 스레드가 모두 첫 잠금을 쥔 뒤에 두 번째 잠금을 요청하게 하고, 영원히 멈추지 않도록 두 번째 잠금은 0.2초까지만 기다립니다.

import threading

def run(opposite):
    lock1, lock2 = threading.Lock(), threading.Lock()
    both_hold_first = threading.Barrier(2)
    both_tried = threading.Barrier(2)
    results = {}

    def worker(name, first, second):
        with first:
            if opposite:
                both_hold_first.wait()           # 둘 다 첫 잠금을 쥔 뒤에 진행한다
            got = second.acquire(timeout=0.2)    # 영원히 멈추지 않도록 시간 제한을 둔다
            results[name] = "두 잠금 획득" if got else "둘째 잠금을 얻지 못함"
            if opposite:
                both_tried.wait()                # 둘 다 시도를 마칠 때까지 첫 잠금을 놓지 않는다
            if got:
                second.release()

    b_order = (lock2, lock1) if opposite else (lock1, lock2)
    threads = [threading.Thread(target=worker, args=("A", lock1, lock2)),
               threading.Thread(target=worker, args=("B", *b_order))]
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    return dict(sorted(results.items()))

print("B가 반대 순서로 잠글 때:", run(opposite=True))
print("B도 같은 순서로 잠글 때:", run(opposite=False))

B가 반대 순서로 잠글 때: {'A': '둘째 잠금을 얻지 못함', 'B': '둘째 잠금을 얻지 못함'}
B도 같은 순서로 잠글 때: {'A': '두 잠금 획득', 'B': '두 잠금 획득'}

두 스레드가 반대 순서로 잠그면 둘 다 두 번째 잠금을 얻지 못합니다. 시간 제한이 없었다면 둘 다 영원히 기다렸을 것입니다. 반면 B도 A와 같이 lock1, lock2 순서로 잠그면, 먼저 lock1을 얻은 스레드가 lock2까지 얻어 일을 마치고, 나머지 스레드가 그 뒤에 두 잠금을 얻으므로 둘 다 끝납니다. 잠그는 순서를 모두 같게 맞추는 것이 교착 상태를 막는 가장 실용적인 방법이며, 그 이유는 다음 글에서 자세히 봅니다.

기다림이 있다고 모두 교착 상태는 아닙니다. 위 상황에서 B가 lock1을 요청하지 않고 lock2만 쓰는 일을 마친 뒤 돌려준다면, A는 B가 돌려줄 때까지 기다렸다가 lock2를 얻습니다. 기다림이 있더라도, 기다리게 만든 쪽이 결국 돌려줄 수 있다면 교착 상태가 아닙니다. 또 교착 상태는 두 스레드 사이에서만 생기는 것도 아닙니다. 재귀 잠금을 지원하지 않는 뮤텍스를 쥔 스레드가 같은 뮤텍스를 다시 잠그면, 스레드 하나가 자기 자신을 기다리며 멈춥니다. Python의 threading.Lock과 POSIX의 PTHREAD_MUTEX_NORMAL 뮤텍스가 그렇습니다. 다만 POSIX의 오류 검사 뮤텍스(PTHREAD_MUTEX_ERRORCHECK)는 멈추는 대신 EDEADLK 오류를 돌려주고, 종류를 정하지 않은 기본 뮤텍스에서는 결과가 정의되어 있지 않습니다(pthread_mutex_lock 명세).

교착 상태, 라이브락, 기아

교착 상태와 비슷해 보이지만 다른 상태가 두 가지 있습니다.

라이브락은 좁은 복도에서 마주친 두 사람이 서로 비켜 주려고 같은 쪽으로 계속 움직이는 모습과 같습니다. 교착 상태를 피하려고 "두 번째 잠금을 못 얻으면 첫 잠금을 놓고 다시 시도한다"는 방식을 쓰면, 두 스레드가 똑같은 박자로 잡고 놓기를 되풀이해 라이브락에 빠질 수 있습니다. 다음 코드는 이를 단순한 모델로 보여 줍니다. 두 작업이 같은 틱에 시도하면 각자 첫 잠금만 쥐고 실패한 뒤 물러나고, 정해진 틱만큼 기다렸다가 다시 시도합니다.

def simulate(backoff, ticks=10):
    """두 작업이 같은 틱에 시도하면 각자 첫 잠금만 쥐고 실패한 뒤 놓는다."""
    next_try = {"A": 0, "B": 0}
    for t in range(ticks):
        trying = [w for w in next_try if next_try[w] == t]
        if len(trying) == 1:
            return f"{t}틱에 {trying[0]}가 혼자 시도해 두 잠금을 얻음"
        for w in trying:
            next_try[w] = t + backoff[w]         # 물러났다가 정해진 틱 뒤에 다시 시도한다
    return f"{ticks}틱 동안 서로 양보만 하고 아무도 끝내지 못함"

print("둘 다 1틱 뒤 재시도:", simulate({"A": 1, "B": 1}))
print("A는 1틱, B는 2틱 뒤 재시도:", simulate({"A": 1, "B": 2}))

둘 다 1틱 뒤 재시도: 10틱 동안 서로 양보만 하고 아무도 끝내지 못함
A는 1틱, B는 2틱 뒤 재시도: 1틱에 A가 혼자 시도해 두 잠금을 얻음

두 작업이 같은 간격으로 물러났다 다시 시도하면 매번 같은 틱에 부딪혀 아무도 끝내지 못합니다. 교착 상태와 달리 두 작업은 계속 움직이고 있으므로, 로그에는 재시도 기록이 끝없이 쌓입니다. 물러나는 간격이 달라지면 박자가 어긋나 한쪽이 혼자 시도하게 되고, 두 잠금을 얻어 끝냅니다. 실제 시스템에서는 간격을 무작위로 정하는 방법(randomized backoff)을 많이 쓰는데, 이것은 부딪힐 가능성을 줄일 뿐 반드시 끝난다고 보장하지는 않습니다. 근본적으로는 잠그는 순서를 통일하거나, 재시도 횟수나 기한을 정해 두는 방법을 함께 씁니다.

기아는 5장에서 본 것처럼 다른 작업은 잘 진행하는데 특정 작업만 계속 밀리는 상태입니다. 기다린 순서대로 처리하거나, 오래 기다린 작업의 우선순위를 올리는 에이징으로 줄입니다. 특정 집단을 늘 앞세우는 규칙은 다른 집단의 기아를 낳을 수 있으므로, 정책 전체를 함께 따져야 합니다.

교착 상태에 필요한 네 가지 조건

1971년 에드워드 코프먼(Edward G. Coffman Jr.) 등은 교착 상태가 생기려면 다음 네 조건이 동시에 성립해야 한다고 정리했습니다. 다시 말해 하나라도 성립하지 않게 만들면 교착 상태는 생기지 않습니다. 다음 글의 예방 기법은 모두 이 가운데 하나를 깨뜨리는 방법입니다.

첫째, 상호 배제(mutual exclusion)입니다. 자원을 한 번에 한 작업만 쓸 수 있어야 합니다. 뮤텍스, 쓰기 잠금, 프린터가 그렇습니다. 읽기 전용 데이터처럼 여럿이 함께 쓸 수 있는 자원은 그 자체로는 기다림을 만들지 않습니다.

둘째, 점유와 대기(hold and wait)입니다. 자원을 하나 이상 쥔 채로 다른 자원을 기다려야 합니다. 앞의 예에서 A는 lock1을 쥔 채 lock2를 기다립니다. 필요한 자원을 한꺼번에 요청하거나, 새 자원을 요청하기 전에 쥔 자원을 모두 돌려준다면 이 조건이 깨집니다.

셋째, 비선점(no preemption)입니다. 이미 할당된 자원을 강제로 빼앗을 수 없어야 합니다. 운영체제가 A의 lock1을 빼앗아 B에게 줄 수 있다면 교착 상태가 풀립니다. 하지만 뮤텍스를 강제로 빼앗으면 임계 영역 안의 데이터가 반쯤 고쳐진 채로 남을 수 있으므로, 일반적으로 허락하지 않습니다.

넷째, 순환 대기(circular wait)입니다. 작업들이 원을 이루며 서로의 자원을 기다려야 합니다. P1이 P2가 쥔 자원을, P2가 P3가 쥔 자원을 기다리고, 마지막 Pn이 다시 P1이 쥔 자원을 기다리는 사슬입니다. 앞의 예에서는 A가 B가 쥔 lock2를, B가 A가 쥔 lock1을 기다리는 원이 생겼습니다.

자원 할당 그래프

누가 무엇을 쥐고 무엇을 기다리는지는 그래프로 그리면 한눈에 보입니다. 1972년 리처드 홀트(Richard C. Holt)가 제안한 자원 할당 그래프(resource allocation graph)는 다음 요소로 이루어집니다.

앞의 예를 그리면, lock1에서 A로 할당 간선이, A에서 lock2로 요청 간선이, lock2에서 B로 할당 간선이, B에서 lock1로 요청 간선이 이어져 닫힌 고리가 생깁니다.

사이클이 있으면 교착 상태인가

그래프에 사이클이 있다는 것과 교착 상태라는 것은 자원의 인스턴스 수에 따라 관계가 달라집니다. 모든 자원 유형의 인스턴스가 하나뿐이라면, 사이클이 있으면 반드시 교착 상태입니다. 사이클 위의 프로세스들은 각자 다음 프로세스가 쥔 유일한 인스턴스를 기다리므로, 아무도 원하는 자원을 얻을 수 없기 때문입니다.

인스턴스가 하나뿐인 자원에서는 자원 노드를 지우고 "누가 누구를 기다리는가"만 남긴 대기 그래프(wait-for graph)를 쓰면 더 간단합니다. 다음 코드는 각 잠금을 누가 쥐고, 각 작업이 어떤 잠금을 기다리는지에서 대기 그래프를 만들고 사이클을 찾습니다.

def find_cycle(holds, waits):
    """holds: 자원 -> 쥔 작업, waits: 작업 -> 기다리는 자원. 자원은 모두 하나씩만 있다."""
    edges = {w: holds[r] for w, r in waits.items() if r in holds}   # 작업 -> 기다리게 만드는 작업
    for start in edges:
        path, node = [start], edges[start]
        while node in edges and node not in path:
            path.append(node)
            node = edges[node]
        if node in path:
            cycle = path[path.index(node):]
            return " -> ".join(cycle + [node])
    return None

holds = {"lock1": "A", "lock2": "B"}
print("A는 lock2, B는 lock1을 기다림:", find_cycle(holds, {"A": "lock2", "B": "lock1"}))
print("A만 lock2를 기다림:", find_cycle(holds, {"A": "lock2"}))

A는 lock2, B는 lock1을 기다림: A -> B -> A
A만 lock2를 기다림: None

두 작업이 서로를 기다리면 A에서 B로, B에서 다시 A로 돌아오는 사이클이 나옵니다. A만 기다리는 경우에는 A에서 B로 가는 간선만 있고 B에서 나가는 간선이 없으므로 사이클이 없고, B가 일을 마치면 A도 진행할 수 있습니다.

자원 유형의 인스턴스가 여러 개라면 사이클이 있어도 교착 상태가 아닐 수 있습니다. 프린터가 두 대 있고, P1과 P2가 한 대씩 쥐고 있으며, P1이 한 대를 더 원한다고 합시다. 그래프에는 P1에서 프린터로 가는 요청 간선과 프린터에서 P1로 가는 할당 간선이 있어 고리가 보입니다. 하지만 P2가 더 원하는 것이 없어 지금 가진 한 대로 일을 마치고 돌려준다면, 남는 프린터가 0대에서 1대가 되어 P1의 요청도 채울 수 있습니다. 자원 노드 하나가 프린터 한 대를 뜻한다고 잘못 읽으면 이 해소 경로를 놓칩니다. 그래서 인스턴스가 여럿일 때는 사이클만 보지 말고, 지금 남은 자원으로 끝낼 수 있는 프로세스가 있는지를 차례로 따져야 합니다.

그래프를 줄여 가며 판단하기

인스턴스가 여럿인 경우에 교착 상태인지 판단하는 방법이 그래프 축소(graph reduction)입니다. 지금 남은 자원으로 요청을 모두 채울 수 있는 프로세스를 찾아, 그 프로세스가 일을 마치고 쥔 자원을 모두 돌려준다고 보고 그 간선들을 지웁니다. 돌려받은 자원으로 다른 프로세스의 요청을 채울 수 있으면 같은 일을 되풀이합니다. 모든 프로세스를 지울 수 있다면 지금은 교착 상태가 아닙니다. 더 지울 수 없는데 프로세스가 남는다면, 남은 프로세스들이 교착 상태에 빠져 있거나 그에 묶여 기다리고 있는 것입니다.

이 판단은 요청을 채워 받은 프로세스가 일을 마치고 자원을 돌려줄 수 있다는 가정 위에 있습니다. 앞으로 더 요청할 최대량까지 고려해 위험한 상태를 미리 피하는 방법은 다음 글의 은행원 알고리즘에서, 이 판단을 표로 계산하는 탐지 알고리즘은 7장 3편에서 다룹니다.

실무에서 만나는 교착 상태

데이터베이스에서는 교착 상태가 아주 흔합니다. 트랜잭션 A가 테이블 X의 행을 잠그고 테이블 Y의 행을 고치려 하는데, 동시에 트랜잭션 B가 테이블 Y의 그 행을 잠그고 테이블 X의 행을 고치려 하면 서로를 기다리게 됩니다. 그래서 대부분의 데이터베이스는 대기 그래프를 만들어 교착 상태를 찾고, 트랜잭션 하나를 골라 되돌려 고리를 끊습니다. MySQL의 InnoDB는 기본적으로 교착 상태 탐지를 켜 두며, SHOW ENGINE INNODB STATUS의 LATEST DETECTED DEADLOCK 부분에서 마지막으로 찾은 교착 상태의 내용을 볼 수 있습니다. InnoDB가 희생자로 고른 트랜잭션을 애플리케이션이 어떻게 다시 시도하는지는 데이터베이스 교재의 격리 수준과 잠금에서 다룹니다. 잠금 대기 시간 초과도 대기를 끊는 수단이지만, 시간이 초과되었다고 해서 그것이 교착 상태였다는 뜻은 아닙니다.

분산 시스템에서도 같은 구조가 나타납니다. 서비스 A가 자원이나 작업 슬롯을 쥔 채 서비스 B의 응답을 기다리고, B가 그 요청을 처리하다가 A에 콜백을 보내 A의 그 자원이 풀리기를 기다리면 여러 서버에 걸친 순환 대기가 됩니다. 호출 방향이 A에서 B로, 다시 A로 간다는 것만으로 교착 상태가 되는 것은 아니고, 각자 상대가 쥔 것을 기다려야 합니다. 한 서버 안에서는 대기 그래프로 찾을 수 있지만, 여러 서버에 흩어진 대기 관계를 모아 판단하기는 매우 어렵습니다. 그래서 분산 시스템에서는 동기적으로 기다리는 구간을 줄이고, 비동기 메시지와 시간 제한을 적극적으로 씁니다.

파일 잠금도 마찬가지입니다. 프로세스 A가 file1에 flock을 걸고 file2를 기다리고, 프로세스 B가 file2에 flock을 걸고 file1을 기다리면 교착 상태가 됩니다. Linux의 flock은 교착 상태를 감지하지 않습니다. fcntl의 레코드 잠금은 커널이 일부 교착 상태를 감지해 EDEADLK 오류를 돌려주기도 하지만, 모든 경우를 감지하지는 못한다고 fcntl_locking(2)에 적혀 있습니다. 결국 잠그는 순서를 정하거나, 기다리지 않는 잠금 시도와 기한을 함께 설계해야 합니다.

멈춘 프로그램 진단하기

교착 상태가 의심되면, 먼저 각 스레드가 어디서 멈추어 있는지 봅니다. Java 스레드 덤프에서 누가 어떤 잠금을 쥐고 무엇을 기다리는지 읽는 방법은 Java 교재의 BLOCKED·WAITING 상태로 스레드 덤프 읽기에서 자세히 다룹니다.

덤프를 얻으면 각 스레드가 쥔 잠금과 기다리는 잠금을 적고, 기다리는 잠금을 누가 쥐고 있는지 이어 봅니다. 인스턴스가 하나뿐인 잠금들 사이에 닫힌 고리가 보이면 교착 상태입니다. 그다음에는 잠그는 순서를 통일하거나, 작업을 안전하게 취소하고 되돌리는 방법, 기다리는 시간에 기한을 두는 방법을 검토합니다. 시간 제한을 두더라도 시간이 초과된 뒤 이미 얻은 자원을 돌려주고, 반쯤 바뀐 상태를 되돌리는 코드가 함께 있어야 합니다.

정리

• 교착 상태는 여러 작업이 각자 자원을 쥔 채 다른 작업이 쥔 자원을 기다려, 대기가 스스로 풀리지 않는 상태입니다. 두 잠금을 반대 순서로 얻는 코드가 전형적인 원인입니다.
• 라이브락은 작업들이 계속 움직이지만 양보만 되풀이해 진척이 없는 상태이고, 기아는 다른 작업은 진행하는데 특정 작업만 계속 밀리는 상태입니다.
• 교착 상태에는 상호 배제, 점유와 대기, 비선점, 순환 대기의 네 조건이 모두 필요하며, 하나라도 깨면 생기지 않습니다.
• 자원 할당 그래프에서 모든 자원의 인스턴스가 하나면 사이클이 곧 교착 상태이고, 인스턴스가 여럿이면 그래프를 줄여 가며 끝낼 수 있는 프로세스가 남았는지 확인해야 합니다.
• 데이터베이스, 분산 시스템, 파일 잠금에서도 같은 구조의 교착 상태가 생기며, 스레드 덤프로 누가 무엇을 쥐고 기다리는지 이어 보는 것이 진단의 출발점입니다.

연습 문제

1. 기다림은 있지만 교착 상태일까

A가 lock1을, B가 lock2를 쥐고 있고, A는 lock2를 기다립니다. B는 lock1을 요청하지 않고, 지금 쥔 lock2만 쓰는 일을 마치면 lock2를 돌려줍니다. 다른 자원 요청이나 예외는 없습니다. A의 기다림은 교착 상태인가요?

2. 프린터 두 대와 두 프로세스

프린터가 두 대 있고, P1과 P2가 한 대씩 쥐고 있어 남은 프린터는 없습니다. 이번에는 P1과 P2 모두 한 대를 더 받아야 일을 마칠 수 있고, 일을 마치기 전에는 쥔 프린터를 돌려주지 않습니다. 교착 상태인지 판단하세요. 본문의 예처럼 P2가 더 원하는 것이 없다면 무엇이 달라지나요?

3. 계좌 이체의 교착 상태

계좌 이체 함수가 출금 계좌의 잠금을 먼저 얻고, 이어서 입금 계좌의 잠금을 얻습니다. 스레드 1은 계좌 X에서 Y로, 스레드 2는 같은 순간 Y에서 X로 이체합니다. 교착 상태가 생길 수 있는지 네 조건으로 설명하고, 코드를 고치는 방법을 제안하세요.

다음 글 데드락 예방과 회피에서는 네 조건을 하나씩 깨뜨려 교착 상태를 막는 방법과, 은행원 알고리즘으로 위험한 상태를 미리 피하는 방법을 살펴봅니다.