교착 상태의 개념

동기화를 열심히 구현해서 경쟁 조건은 해결했는데, 이번에는 프로그램이 아예 멈춰버리는 상황이 발생할 수 있습니다. 에러 메시지도 없고, CPU 사용률도 0%에 가깝고, 로그도 더 이상 찍히지 않습니다. 스레드 덤프를 떠야 원인이 보이는 이 침묵의 장애가 바로 교착 상태(Deadlock)입니다.

경쟁 조건은 너무 빠르게 진행되어 생기는 문제라면, 데드락은 아무것도 진행되지 않아서 생기는 문제입니다. 6장에서 다룬 동기화 도구들을 잘못 조합하면 반드시 마주치게 됩니다.

데드락의 정의

교착 상태란 두 개 이상의 프로세스 또는 스레드가 서로가 보유한 자원을 기다리면서 영원히 진행되지 못하는 상태입니다.

가장 직관적인 예가 좁은 골목길의 교착입니다. 양쪽에서 차가 들어오면 양쪽 모두 빠져나갈 수 없습니다. 어느 한 쪽이 후진하지 않는 한 영원히 막힙니다. 프로그래밍에서 후진은 보유한 자원을 반납하는 것인데, 반납 로직이 없으면 영원히 굳어 있게 됩니다.

코드에서 데드락의 전형적인 패턴을 보겠습니다.

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

pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void *thread_a(void *arg) {
    printf("[A] lock1 획득 시도\n");
    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;
}

void *thread_b(void *arg) {
    printf("[B] lock2 획득 시도\n");
    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() {
    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;
}

이 프로그램을 실행하면 출력은 lock1 획득 성공. lock2 대기... 와 lock2 획득 성공. lock1 대기... 까지만 나오고 멈춥니다. 에러도, 예외도, 세그폴트도 없습니다. 프로세스는 살아 있지만 아무것도 하지 않습니다. CPU 사용률은 0%입니다. 이것이 디버깅하기 가장 어려운 이유입니다 — 증상이 아무 일도 일어나지 않는 것이기 때문입니다.

데드락 vs 라이브락 vs 기아

유사하지만 다른 세 가지 상태를 구분해야 합니다.

• 데드락(Deadlock): 서로를 기다리며 완전히 멈춤. CPU 사용률 0%.
• 라이브락(Livelock): 서로 양보하며 계속 바쁘지만 진전이 없음. CPU 사용률은 높지만 유용한 작업은 없음. 예: 복도에서 마주친 두 사람이 같은 방향으로 계속 피하는 상황.
• 기아(Starvation): 특정 프로세스가 자원을 영원히 할당받지 못함. 다른 프로세스들은 정상 동작. 예: 우선순위가 낮은 프로세스가 항상 밀리기.

import threading
import time

lock1 = threading.Lock()
lock2 = threading.Lock()

def worker_a():
    while True:
        lock1.acquire()
        if not lock2.acquire(timeout=0.01):
            lock1.release()  # 양보
            print("[A] lock2 실패, 양보")
            time.sleep(0.01)
            continue
        print("[A] 작업 완료")
        lock2.release()
        lock1.release()
        break

def worker_b():
    while True:
        lock2.acquire()
        if not lock1.acquire(timeout=0.01):
            lock2.release()  # 양보
            print("[B] lock1 실패, 양보")
            time.sleep(0.01)
            continue
        print("[B] 작업 완료")
        lock1.release()
        lock2.release()
        break

라이브락은 데드락보다 찾기 어렵습니다. 프로세스가 살아있고 바쁘게 보이기 때문입니다. 해결법은 양보 전 랜덤 대기를 넣는 것입니다(이더넷의 지수 백오프 알고리즘과 동일한 원리).

데드락 발생의 4가지 필요조건

1971년 Coffman 등이 정리한 4가지 조건입니다. 교착 상태가 발생하려면 다음 네 가지 조건이 동시에 충족되어야 합니다. 하나라도 깨뜨리면 데드락은 발생하지 않습니다.

1. 상호 배제 (Mutual Exclusion)

자원은 한 번에 하나의 프로세스만 사용할 수 있습니다. 뮤텍스, 프린터, 쓰기 락 등이 여기에 해당합니다. 읽기 전용 파일처럼 여러 프로세스가 동시에 접근할 수 있는 공유 자원에서는 데드락이 발생하지 않습니다.

2. 점유와 대기 (Hold and Wait)

자원을 하나 이상 보유한 채로 다른 자원을 기다립니다. 위 코드에서 thread_a는 lock1을 보유한 상태에서 lock2를 기다립니다. 만약 모든 자원을 한 번에 요청하거나, 새 자원을 요청하기 전에 보유한 자원을 전부 반납한다면 이 조건이 깨집니다.

3. 비선점 (No Preemption)

이미 할당된 자원을 강제로 빼앗을 수 없습니다. thread_a가 보유한 lock1을 OS가 강제로 빼앗아 thread_b에게 줄 수 있다면 데드락은 해소됩니다. 하지만 뮤텍스를 강제로 빼앗으면 임계 구역의 데이터 일관성이 깨질 수 있어서 일반적으로 허용하지 않습니다.

4. 순환 대기 (Circular Wait)

프로세스들이 원형으로 서로의 자원을 기다립니다. P1 → P2 → P3 → ... → Pn → P1 형태의 대기 사슬이 형성됩니다. 위 코드에서는 A → (lock2, B가 보유) → B → (lock1, A가 보유) → A로 순환합니다.

위 데드락 코드에서 네 조건 확인:

자원 할당 그래프

데드락을 시각적으로 분석하는 도구가 자원 할당 그래프(Resource Allocation Graph, RAG)입니다. 1972년 Holt가 제안했습니다.

• 프로세스 노드: 원(○)으로 표현. P1, P2, ...
• 자원 노드: 사각형(□)으로 표현. 사각형 안의 점 개수가 인스턴스 수.
• 요청 간선(Request Edge): Pi → Rj (프로세스 Pi가 자원 Rj를 요청 중)
• 할당 간선(Assignment Edge): Rj → Pi (자원 Rj의 인스턴스 하나가 프로세스 Pi에 할당됨)

사이클과 데드락의 관계

그래프에 사이클(Cycle)이 존재하면 교착 상태의 가능성이 있습니다.

각 자원 유형의 인스턴스가 1개: 사이클이 있으면 반드시 데드락입니다. 증명: 사이클 상의 각 프로세스가 다음 프로세스가 보유한 유일한 인스턴스를 기다리므로, 누구도 자원을 얻을 수 없습니다.

자원 유형의 인스턴스가 여러 개: 사이클이 있어도 데드락이 아닐 수 있습니다. 예: 프린터 2대(R1), P1이 프린터 1대를 보유하고 다른 1대를 기다립니다. P2가 나머지 1대를 보유하지만 P2가 다른 자원을 기다리지 않고 곧 프린터를 반납한다면, P1은 결국 프린터를 얻을 수 있습니다. 사이클이 있지만 데드락은 아닙니다.

그래프 축소 알고리즘

자원 할당 그래프에서 데드락 여부를 판정하는 방법:

1. 요청을 즉시 만족시킬 수 있는 프로세스를 찾습니다.
2. 해당 프로세스의 모든 간선(요청+할당)을 제거합니다.
3. 반환된 자원으로 다른 프로세스의 요청을 만족시킬 수 있으면 반복합니다.
4. 모든 간선이 제거되면 데드락이 아닙니다. 간선이 남으면 남은 프로세스들이 데드락입니다.

실무에서 만나는 데드락

데이터베이스 교착 상태

데이터베이스에서 데드락은 매우 흔합니다. 트랜잭션 A가 테이블 X의 행을 잠그고 테이블 Y의 행을 업데이트하려 합니다. 동시에 트랜잭션 B가 테이블 Y의 행을 잠그고 테이블 X의 행을 업데이트하려 합니다.

대부분의 DBMS는 대기 그래프 탐색 또는 타임아웃으로 데드락을 자동 감지하고, 비용이 적은 트랜잭션을 롤백합니다. MySQL의 InnoDB는 기본적으로 즉시 감지하며, SHOW ENGINE INNODB STATUS로 최근 데드락 정보를 확인할 수 있습니다.

분산 시스템 교착 상태

마이크로서비스 환경에서 서비스 A가 서비스 B에 동기 HTTP 호출을 하며 대기하고, 서비스 B가 동시에 서비스 A에 콜백을 하며 대기하면 분산 데드락이 발생합니다. 단일 노드 안에서는 대기 그래프로 감지 가능하지만, 여러 노드에 걸친 분산 데드락은 감지가 매우 어렵습니다. 따라서 분산 시스템에서는 비동기 메시지 큐나 타임아웃을 적극 활용하여 동기 대기를 최소화합니다.

파일 시스템 데드락

프로세스 A가 file1의 flock을 잡고 file2를 기다리고, 프로세스 B가 file2의 flock을 잡고 file1을 기다리는 패턴입니다. 파일 잠금은 OS가 데드락을 자동 감지하지 않으므로, 개발자가 직접 타임아웃이나 락 순서 규칙을 적용해야 합니다.

디버깅 도구

데드락이 의심될 때 사용할 수 있는 진단 도구들:

• Linux: gdb로 attach 후 각 스레드의 backtrace 확인. pstack <pid>로 모든 스레드 스택 덤프.
• Java: jstack <pid> 또는 kill -3 <pid>로 스레드 덤프. JVM이 Found one Java-level deadlock 메시지를 자동 출력.
• Python: faulthandler.dump_traceback_later(timeout)로 일정 시간 후 자동으로 트레이스백 출력.
• MySQL: SHOW ENGINE INNODB STATUS\G 의 LATEST DETECTED DEADLOCK 섹션.

다음 절에서는 데드락을 예방하고 회피하는 전략을 알아보겠습니다.