CS학습2026년 9월 11일

Deadlock: 순환 대기로 인해 영원히 멈춘 프로세스들

데드락(Deadlock)은 둘 이상의 프로세스가 서로 상대방이 점유한 자원을 기다리며 무한히 대기하는 상태를 말한다. 발생하려면 상호 배제, 점유와 대기, 비선점, 순환 대기라는 네 가지 조건이 동시에 성립해야 한다. 자원 할당 그래프와 은행원 알고리즘(Banker's Algorithm) 같은 기법으로 예방, 회피, 탐지, 복구가 가능하다.

송민성7분 읽기

1. 개념

데드락(Deadlock, 교착 상태)은 두 개 이상의 프로세스(또는 스레드)가 각자 자원을 점유한 채 서로 다른 프로세스가 점유한 자원을 요청하면서, 아무도 다음 단계로 진행하지 못하고 무한히 대기하는 상태다.

예를 들어 프로세스 A가 자원 X를 점유하고 자원 Y를 요청하는 동시에, 프로세스 B가 자원 Y를 점유하고 자원 X를 요청하면 둘 다 영원히 대기한다. 이 상황은 타임아웃이나 외부 개입 없이는 자연적으로 해소되지 않는다.

데드락은 기아 상태(Starvation)와 다르다. 기아 상태는 스케줄링 우선순위 문제로 특정 프로세스가 자원을 계속 못 받는 것이고, 데드락은 관련된 프로세스들이 구조적으로 서로를 막고 있어 진행 자체가 불가능한 상태다.

2. 왜 사용하는가

데드락은 "사용하는" 개념이 아니라 반드시 이해하고 대응해야 하는 위험 상태다. 락(Lock), 세마포어(Semaphore), 뮤텍스(Mutex) 같은 동기화 기법으로 여러 프로세스가 공유 자원에 안전하게 접근하도록 만들면, 그 대가로 데드락이 발생할 구조적 여지가 생긴다.

동시성 프로그래밍에서 자원 보호는 필수이지만, 자원을 잘못된 순서로 잠그면 데드락 위험이 생긴다. 따라서 데드락을 이해하는 목적은 회피가 아니라 "언제, 왜 생기는지"를 알고 설계 단계에서 예방하는 데 있다.

3. 동작 원리

데드락은 다음 네 가지 조건이 동시에 성립할 때만 발생한다. 하나라도 깨지면 데드락은 발생하지 않는다.

상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
점유와 대기(Hold and Wait): 프로세스가 자원을 점유한 상태에서 다른 자원을 추가로 요청한다.
비선점(No Preemption): 다른 프로세스가 점유한 자원을 강제로 빼앗을 수 없고, 점유한 프로세스가 스스로 반납해야 한다.
순환 대기(Circular Wait): 프로세스 P1이 P2의 자원을 기다리고, P2가 P3의 자원을 기다리고, ... Pn이 다시 P1의 자원을 기다리는 순환 구조가 형성된다.

이 관계는 자원 할당 그래프(Resource Allocation Graph)로 표현한다. 프로세스 노드와 자원 노드 사이에 "점유(할당)" 간선과 "요청" 간선을 그렸을 때, 그래프에 사이클이 존재하면 데드락 가능성이 있다. 자원 종류당 인스턴스가 하나면 사이클 존재가 곧 데드락이고, 인스턴스가 여러 개면 사이클이 있어도 데드락이 아닐 수 있다.

대응 전략은 크게 네 가지다.

예방(Prevention): 네 조건 중 하나를 아예 성립 불가능하게 설계한다. 예: 모든 자원을 한 번에 요청하게 하거나(점유와 대기 제거), 자원에 전역 순서를 부여해 항상 같은 순서로만 잠그게 한다(순환 대기 제거).
회피(Avoidance): 은행원 알고리즘처럼 자원 요청이 안전 상태(Safe State)를 유지하는지 미리 계산해서, 안전하지 않은 요청은 거부한다.
탐지(Detection): 자원 할당 그래프에서 주기적으로 사이클을 탐지하고, 발견되면 복구 절차를 실행한다.
복구(Recovery): 관련 프로세스 중 하나를 강제 종료하거나 자원을 선점해서 순환을 끊는다.

4. 코드 예제

4.1 데드락이 실제로 발생하는 코드 (Python, threading)

python

import threading
import time

lock_a = threading.Lock()
lock_b = threading.Lock()

def thread_1():
    with lock_a:
        print("thread_1: lock_a 획득")
        time.sleep(0.5)  # thread_2가 lock_b를 잡을 시간을 확보
        print("thread_1: lock_b 대기 중...")
        with lock_b:
            print("thread_1: lock_b 획득")

def thread_2():
    with lock_b:
        print("thread_2: lock_b 획득")
        time.sleep(0.5)
        print("thread_2: lock_a 대기 중...")
        with lock_a:
            print("thread_2: lock_a 획득")

t1 = threading.Thread(target=thread_1)
t2 = threading.Thread(target=thread_2)
t1.start()
t2.start()
t1.join(timeout=3)
t2.join(timeout=3)

if t1.is_alive() or t2.is_alive():
    print("데드락 발생: 두 스레드가 서로의 락을 기다리며 멈춰 있음")

thread_1은 lock_a → lock_b 순서로, thread_2는 lock_b → lock_a 순서로 락을 요청한다. 서로 반대 순서로 자원을 잠그기 때문에 순환 대기가 형성되어 데드락이 발생한다.

4.2 예방: 자원에 전역 순서를 부여해서 순환 대기 제거

python

import threading
import time

lock_a = threading.Lock()
lock_b = threading.Lock()

# 모든 스레드가 "항상 lock_a를 먼저, lock_b를 나중에" 획득하도록 순서 고정
def worker(name):
    with lock_a:
        print(f"{name}: lock_a 획득")
        time.sleep(0.2)
        with lock_b:
            print(f"{name}: lock_b 획득")

t1 = threading.Thread(target=worker, args=("thread_1",))
t2 = threading.Thread(target=worker, args=("thread_2",))
t1.start()
t2.start()
t1.join()
t2.join()
print("정상 종료: 순환 대기 조건이 깨져서 데드락 없음")

두 스레드가 항상 같은 순서(lock_a → lock_b)로 락을 요청하므로 순환 대기가 구조적으로 불가능해진다.

4.3 회피: 은행원 알고리즘의 안전 상태 검사 로직

python

from typing import List

def is_safe_state(
    available: List[int],
    max_demand: List[List[int]],
    allocation: List[List[int]],
) -> bool:
    """
    현재 자원 할당 상태가 안전 상태(Safe State)인지 검사한다.
    available: 자원 종류별 현재 사용 가능한 개수
    max_demand: 프로세스별 최대 자원 요구량
    allocation: 프로세스별 현재 할당된 자원량
    시간복잡도: O(n^2 * m), n=프로세스 수, m=자원 종류 수
    """
    n = len(allocation)
    m = len(available)
    need = [
        [max_demand[i][j] - allocation[i][j] for j in range(m)]
        for i in range(n)
    ]
    work = available[:]
    finished = [False] * n
    safe_sequence = []

    for _ in range(n):
        progressed = False
        for i in range(n):
            if not finished[i] and all(need[i][j] <= work[j] for j in range(m)):
                # 프로세스 i가 요구량을 충족할 수 있으면 자원을 반납받는다고 가정
                for j in range(m):
                    work[j] += allocation[i][j]
                finished[i] = True
                safe_sequence.append(i)
                progressed = True
        if not progressed:
            break

    return all(finished)


# 사용 예: 3개 프로세스, 3종류 자원
available = [3, 3, 2]
max_demand = [
    [7, 5, 3],
    [3, 2, 2],
    [9, 0, 2],
]
allocation = [
    [0, 1, 0],
    [2, 0, 0],
    [3, 0, 2],
]

print("안전 상태 여부:", is_safe_state(available, max_demand, allocation))

5. 시간 복잡도 또는 성능 특성

자원 할당 그래프 사이클 탐지: 그래프 탐색(DFS) 기반으로 정점 V(프로세스+자원)와 간선 E(할당+요청 관계)에 대해 O(V + E)로 사이클 존재 여부를 확인할 수 있다.
은행원 알고리즘(Banker's Algorithm): 안전 상태 검사 1회에 O(n² × m), n은 프로세스 수, m은 자원 종류 수다. 매 자원 요청마다 이 검사를 수행하므로 프로세스와 자원 종류가 많아질수록 오버헤드가 커진다.
타임아웃 기반 탐지: 락 획득 대기 시간에 제한을 두고 초과 시 실패 처리하는 방식은 구현이 단순하지만, 정상적으로 오래 걸리는 작업과 데드락을 구분하지 못해 오탐(false positive)이 발생할 수 있다.

6. 실무 사용 사례

RDBMS 트랜잭션: PostgreSQL, MySQL(InnoDB) 등은 내부적으로 대기 그래프(Wait-for Graph)를 유지하며 주기적으로 사이클을 탐지한다. 데드락이 확인되면 그중 하나의 트랜잭션을 강제로 롤백시켜 에러를 반환한다.

sql

-- PostgreSQL에서 데드락 발생 시 반환되는 에러 예시
-- ERROR:  deadlock detected
-- DETAIL:  Process 1234 waits for ShareLock on transaction 5678; blocked by process 5678.
--          Process 5678 waits for ShareLock on transaction 1234; blocked by process 1234.
-- HINT:  See server log for query details.

분산 락(Distributed Lock): Redis, ZooKeeper 기반 분산 락 시스템에서는 락 획득에 TTL(Time To Live)을 설정해서, 락을 획득한 노드가 죽어도 일정 시간 후 자동 해제되도록 만들어 데드락 위험을 줄인다.
멀티스레드 애플리케이션: 자바의 synchronized 블록이나 Python의 threading.Lock을 중첩해서 사용할 때 락 획득 순서가 어긋나면 실무 코드에서도 흔히 데드락이 발생한다.

7. 주의할 점

락 순서를 항상 고정한다. 여러 자원을 동시에 잠글 때는 코드 전체에서 일관된 순서(예: ID 오름차순)로 획득하도록 컨벤션을 정한다.
락을 쥔 채로 오래 걸리는 작업(I/O, 네트워크 호출)을 하지 않는다. 락 보유 시간이 길수록 다른 프로세스와 충돌할 확률이 높아진다.
타임아웃을 반드시 설정한다. 무한 대기 대신 일정 시간 후 실패하고 재시도하는 구조로 만들면 데드락이 시스템 전체를 마비시키는 것을 막을 수 있다.
DB 트랜잭션에서는 동일한 순서로 로우를 잠그도록 쿼리를 설계한다. 예를 들어 여러 테이블을 UPDATE할 때 항상 같은 순서로 접근하면 대기 그래프에 사이클이 생기지 않는다.
데드락 탐지 로그를 무시하지 않는다. DB나 락 매니저가 데드락을 탐지해서 자동으로 하나를 롤백시켰다면, 근본 원인(락 순서 불일치)을 찾아 코드를 수정해야 재발하지 않는다.

8. 핵심 정리

데드락은 상호 배제, 점유와 대기, 비선점, 순환 대기라는 네 조건이 동시에 성립할 때 발생하며, 이 중 하나만 깨뜨려도 예방할 수 있다. 실무에서 가장 실용적인 방법은 자원에 전역 순서를 부여해 순환 대기를 원천 차단하거나, 락 대기에 타임아웃을 걸어 최악의 경우에도 시스템이 완전히 멈추지 않도록 하는 것이다. 은행원 알고리즘 같은 회피 기법은 이론적으로 안전하지만 자원 요구량을 미리 알아야 한다는 전제 때문에 실무 적용 범위는 제한적이고, 실제로는 DB나 락 매니저의 데드락 탐지·자동 롤백 기능에 의존하는 경우가 많다.