교착 상태(Deadlock) — 발생 조건 4가지와 해결법

두 스레드가 서로가 가진 락을 기다리면서 영원히 멈추는 상황, 데드락. 발생 조건은 4가지인데, 하나라도 깨면 데드락은 없습니다.

이 글에서는 4가지 조건부터 실제로 마주치는 DB 데드락, Java 멀티스레드 데드락까지 해결 전략과 함께 정리합니다.

데드락이란

두 개 이상의 프로세스(또는 스레드)가 서로가 가진 자원을 기다리면서 무한히 대기 하는 상태입니다.

스레드 A: 자원 1을 잡고, 자원 2를 기다림
스레드 B: 자원 2를 잡고, 자원 1을 기다림

→ 서로 영원히 기다림 = 데드락

// 데드락 발생 예시
Object lock1 = new Object();
Object lock2 = new Object();

// 스레드 A
synchronized (lock1) {
    Thread.sleep(100);
    synchronized (lock2) {  // lock2를 기다림
        // ...
    }
}

// 스레드 B
synchronized (lock2) {
    Thread.sleep(100);
    synchronized (lock1) {  // lock1을 기다림
        // ...
    }
}

발생 조건 4가지 (Coffman Conditions)

네 가지가 동시에 성립해야 데드락이 발생합니다. 하나라도 깨면 데드락은 없습니다.

1. 상호 배제 (Mutual Exclusion)

자원을 동시에 여러 프로세스가 사용할 수 없습니다. 프린터를 두 프로세스가 동시에 쓸 수 없는 것처럼요.

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

자원을 하나 잡고 있으면서, 다른 자원을 추가로 요청하며 기다립니다.

3. 비선점 (No Preemption)

다른 프로세스가 가진 자원을 강제로 빼앗을 수 없습니다.

4. 순환 대기 (Circular Wait)

프로세스들이 원형으로 서로의 자원을 기다립니다.

P1 → P2 → P3 → P1 (순환!)

해결 전략

1. 예방 (Prevention)

4가지 조건 중 하나를 원천적으로 막습니다.

상호 배제 제거 — 실질적으로 불가능한 경우가 많음. 읽기 전용 자원에만 적용 가능.

점유와 대기 제거 — 필요한 자원을 한꺼번에 요청 하거나, 자원을 요청하기 전에 현재 가진 것을 전부 반납.

단점: 자원 이용률이 떨어짐 (안 쓰는 자원도 미리 잡아놓으니까)

비선점 제거 — 자원을 기다려야 하면, 현재 가진 자원을 반납하고 나중에 다시 요청.

단점: 일부 자원(프린터 출력 중)에는 적용 불가

순환 대기 제거 — 자원에 번호를 매기고, 오름차순으로만 요청. 이게 실제로 가장 실용적입니다.

// 순환 대기 방지: 항상 lock1 → lock2 순서로 잠금
synchronized (lock1) {
    synchronized (lock2) {
        // ...
    }
}

2. 회피 (Avoidance)

자원을 할당할 때 데드락이 발생할 가능성이 있으면 할당하지 않음.

대표적인 알고리즘이 은행원 알고리즘 (Banker's Algorithm) 입니다.

시스템이 "안전 상태(safe state)"인지 확인하고,
안전 상태가 유지될 때만 자원을 할당합니다.

안전 상태: 모든 프로세스가 순서대로 완료될 수 있는 상태
불안전 상태: 데드락이 발생할 수도 있는 상태 (반드시 발생하는 건 아님)

실제로는 사전에 최대 자원 요구량을 알아야 해서 적용하기 어렵습니다.

3. 탐지 (Detection)

데드락을 허용하되, 주기적으로 발생 여부를 확인 합니다.

• 자원 할당 그래프 (Resource Allocation Graph) 에서 순환을 탐지
• 순환이 있으면 데드락

4. 회복 (Recovery)

데드락이 탐지되면 해결합니다.

• 프로세스 종료 — 데드락에 관련된 프로세스를 하나씩(또는 전부) 종료
• 자원 선점 — 특정 프로세스의 자원을 강제로 빼앗아서 다른 프로세스에 할당
• 롤백 — 체크포인트로 되돌리기

데드락

DB 데드락

가장 흔하게 마주치는 데드락입니다.

-- 트랜잭션 A
UPDATE accounts SET balance = balance - 100 WHERE id = 1;  -- row 1 잠금
UPDATE accounts SET balance = balance + 100 WHERE id = 2;  -- row 2 기다림

-- 트랜잭션 B (동시 실행)
UPDATE accounts SET balance = balance - 50 WHERE id = 2;   -- row 2 잠금
UPDATE accounts SET balance = balance + 50 WHERE id = 1;   -- row 1 기다림

-- → 데드락!

MySQL의 InnoDB는 데드락을 자동 탐지 하고, 관련 트랜잭션 중 하나를 롤백 합니다. 근데 롤백된 쪽 애플리케이션에서 적절히 재시도해야 합니다.

방지법: 항상 같은 순서로 row를 잠금 (id 오름차순으로 UPDATE).

Java 멀티스레드 데드락

// 이런 코드를 작성하지 마세요
public void transfer(Account from, Account to, int amount) {
    synchronized (from) {
        synchronized (to) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

// 동시에 실행되면:
// 스레드1: transfer(A, B, 100)  → A 잠금 → B 기다림
// 스레드2: transfer(B, A, 50)   → B 잠금 → A 기다림

방지법: 계좌 ID 기준으로 항상 같은 순서로 잠금.

public void transfer(Account from, Account to, int amount) {
    Account first = from.id < to.id ? from : to;
    Account second = from.id < to.id ? to : from;

    synchronized (first) {
        synchronized (second) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

관련 개념

라이브락 (Livelock)

데드락처럼 진행이 안 되지만, 프로세스가 블로킹되진 않고 계속 상태를 바꾸면서 서로 양보하는 상태입니다.

좁은 복도에서 두 사람이 마주쳤는데, 동시에 왼쪽으로 비키고, 동시에 오른쪽으로 비키고... 끝없이 반복하는 상황입니다.

기아 상태(Starvation) vs 데드락

• 데드락: 관련된 모든 프로세스가 영원히 대기
• 기아: 특정 프로세스만 계속 자원을 못 얻음 (다른 프로세스는 정상 동작)

우선순위 기반 스케줄링에서 낮은 우선순위의 프로세스가 계속 CPU를 못 받는 게 기아입니다. 에이징(aging) 으로 해결합니다 — 대기 시간이 길어지면 우선순위를 올려주는 방식.

데드락 디버깅

• Java: jstack <pid>로 스레드 덤프 → BLOCKED 상태인 스레드와 대기 중인 모니터 확인
• DB: MySQL의 SHOW ENGINE INNODB STATUS에서 LATEST DETECTED DEADLOCK 섹션 확인
• 로그에 데드락 감지 시점, 관련 트랜잭션, 롤백된 트랜잭션이 기록됨

파생되는 개념들

• 뮤텍스와 세마포어 — 동기화 도구의 차이
• 모니터(Monitor) — Java의 synchronized가 사용하는 구조
• 트랜잭션 격리 수준 — DB 데드락과 관련된 동시성 제어
• Java의 Lock 인터페이스 — synchronized보다 유연한 잠금
• CAS (Compare-And-Swap) — 락 없는(lock-free) 동시성