교착 상태의 개념

동기화를 열심히 구현해서 경쟁 조건은 해결했는데, 이번에는 프로그램이 아예 멈춰버리는 상황이 발생할 수 있습니다.

에러 메시지 없이 작업 완료 로그가 멈추고, 관련 스레드가 잠금 대기에 머무를 수 있습니다.

이때 스레드 덤프의 보유 자원과 대기 관계를 확인해야 교착 상태(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;
}

A가 lock1을, B가 lock2를 먼저 획득한 경우에는 두 스레드가 두 번째 잠금 호출에서 기다립니다. sleep(1)은 이런 겹침의 기회를 주지만 보장하지 않으므로, 스케줄링에 따라 한 스레드가 두 락을 먼저 얻고 정상 종료할 수도 있습니다. 출력 순서와 데드락 발생을 고정된 실행 결과로 보지 마세요.

이 예시는 pthread 호출의 성공을 전제하고 오류 처리를 생략합니다. 블로킹 대기 중인 두 스레드는 CPU를 거의 사용하지 않을 수 있지만, 프로세스 전체의 CPU 수치만으로 교착 여부를 판정할 수는 없습니다.

데드락 vs 라이브락 vs 기아

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

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

위 Python 코드는 두 worker 함수를 정의하며 스레드를 시작하지는 않습니다. 동시에 실행하더라도 스케줄링에 따라 작업이 끝날 수 있어, 영구적인 라이브락을 재현한다고 보장할 수 없습니다.

라이브락은 재시도 로그가 계속 나와도 완료가 없는지 확인해야 합니다. 랜덤 백오프는 재시도 시점을 분산하는 방법이지만 공정성이나 종료를 보장하지는 않습니다. 락 획득 순서를 통일하거나 재시도 횟수·기한을 정하는 방법도 함께 검토합니다.

기아는 FIFO 대기나 우선순위 노화처럼 공정성을 다루는 정책으로 줄일 수 있습니다. 특정 집단을 항상 우선하는 규칙은 다른 집단의 기아를 만들 수 있으므로 정책 전체를 확인합니다.

데드락 발생의 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은 결국 프린터를 얻을 수 있습니다.

이때 P1 → R1 → P1 사이클이 있어도 P2의 반환으로 요청을 충족할 수 있으므로 데드락은 아닙니다.

그래프 축소 알고리즘

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

1. 요청을 즉시 만족시킬 수 있는 프로세스를 찾습니다.
2. 해당 프로세스의 모든 간선(요청+할당)을 제거합니다.
3. 반환된 자원으로 다른 프로세스의 요청을 만족시킬 수 있으면 반복합니다.
4. 모든 요청을 해소할 수 있으면 현재 요청 상태는 데드락이 아닙니다. 더 축소할 수 없으면 남은 보유·대기 집합을 조사합니다. 순환을 구성하는 프로세스와 그 뒤에서 영향을 받아 기다리는 프로세스를 구분합니다.

이 절차는 요청을 충족한 프로세스가 작업을 마치고 보유 자원을 반환할 수 있다는 가정에 따른 분석입니다. 미래에 할 최대 요청까지 다루는 안전 상태 검사는 다음 절의 회피 알고리즘에서 다룹니다.

자원 할당 그래프를 읽을 때는 사이클이 있는가와 각 자원이 단일 인스턴스인가를 분리해서 봐야 합니다.

단일 인스턴스 자원의 사이클은 곧 데드락이지만, 다중 인스턴스 자원에서는 그래프 축소로 실제 완료 가능한 프로세스가 남아 있는지 확인해야 합니다.

실무에서 만나는 데드락

데이터베이스 교착 상태

데이터베이스에서 데드락은 매우 흔합니다.

트랜잭션 A가 테이블 X의 행을 잠그고 테이블 Y의 행을 업데이트하려 합니다.

동시에 트랜잭션 B가 테이블 Y의 행을 잠그고 테이블 X의 행을 업데이트하려 합니다.

DBMS마다 대기 그래프 탐색과 희생 트랜잭션 선택 정책이 다릅니다. 락 대기 타임아웃은 대기를 제한하는 수단이며, 시간 초과 자체가 데드락을 증명하지는 않습니다.

MySQL의 InnoDB는 기본적으로 데드락 감지를 활성화하며, SHOW ENGINE INNODB STATUS로 최근 데드락 정보를 확인할 수 있습니다.

분산 시스템 교착 상태

서비스 A가 자원이나 작업 슬롯을 보유한 채 B의 응답을 기다리고, B의 콜백도 A의 그 자원 해제를 기다리면 분산된 순환 대기가 생길 수 있습니다. HTTP 호출 방향이 A → B → A라는 사실만으로는 교착을 뜻하지 않습니다.

단일 노드 안에서는 대기 그래프로 감지 가능하지만, 여러 노드에 걸친 분산 데드락은 감지가 매우 어렵습니다.

따라서 분산 시스템에서는 비동기 메시지 큐나 타임아웃을 적극 활용하여 동기 대기를 최소화합니다.

파일 시스템 데드락

프로세스 A가 file1의 flock을 잡고 file2를 기다리고, 프로세스 B가 file2의 flock을 잡고 file1을 기다리는 패턴입니다.

Linux의 flock은 데드락을 감지하지 않습니다. 잠금 방식마다 감지 기능이 다르므로 모든 파일 잠금에 일반화하지 말고, 이 경우에는 비차단 획득·대기 기한·락 순서 규칙을 설계합니다.

디버깅 도구

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

• Linux: gdb로 attach 후 각 스레드의 backtrace 확인. pstack <pid>로 모든 스레드 스택 덤프.
• Java: jstack <pid> 또는 kill -3 <pid>로 스레드 덤프. 지원되는 잠금·스레드 범위에서 JVM이 교착을 감지하면 관련 진단이 포함될 수 있습니다. 모든 대기나 가상 스레드 교착을 자동 검출한다는 뜻은 아닙니다.
• Python: faulthandler.dump_traceback_later(timeout)로 일정 시간 후 자동으로 트레이스백 출력.
• MySQL: SHOW ENGINE INNODB STATUS\G 의 LATEST DETECTED DEADLOCK 섹션.

덤프에서 각 스레드의 보유 락과 대기 락을 기록하고 소유자를 연결합니다. 단일 인스턴스 락의 닫힌 대기 고리가 확인되면 락 순서 통일, 안전한 작업 취소·롤백, 대기 기한 등을 검토합니다. 타임아웃을 추가해도 이미 획득한 자원과 중간 상태를 올바르게 정리해야 합니다.

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