데드락 탐지와 복구

예방과 회피를 완벽하게 적용하기 어렵다면, 데드락이 발생하도록 두었다가 탐지(Detection)한 후 복구(Recovery)하는 전략을 쓸 수 있습니다.

예방은 제약이 많고, 회피는 미래 예측이 필요합니다.

정책은 자원을 관리하는 계층마다 다릅니다. 예를 들어 InnoDB는 트랜잭션 락의 데드락을 탐지해 희생 트랜잭션을 롤백하지만, 범용 OS가 모든 사용자 프로그램의 자원 관계를 일괄 복구해 주지는 않습니다.

탐지 알고리즘: 자원 유형별 구분

탐지 알고리즘은 현재 시점에서 데드락이 존재하는지를 판정합니다.

자원 유형의 인스턴스 수에 따라 두 가지 방법이 있습니다.

단일 인스턴스 — 대기 그래프

각 자원 유형의 인스턴스가 하나뿐인 경우에는 대기 그래프(Wait-for Graph)를 사용합니다.

자원 할당 그래프에서 자원 노드를 제거하고, Pi가 Pj가 보유한 자원을 기다린다면 Pi → Pj 간선을 그립니다.

이 절처럼 선점하지 않는 재사용 자원의 현재 대기를 모델링하면, 단일 인스턴스 대기 그래프의 사이클은 데드락을 뜻합니다.

사이클 탐지는 DFS로 $O(V + E)$ 시간에 수행할 수 있습니다.

def detect_cycle(graph):
    """대기 그래프에서 처음 찾은 사이클의 구성원 반환"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    cycle_members = set()

    def dfs(u, path):
        color[u] = GRAY
        path.append(u)
        for v in graph.get(u, []):
            if color[v] == GRAY:
                # 사이클 발견! path에서 v 이후가 사이클
                idx = path.index(v)
                cycle = path[idx:]
                cycle_members.update(cycle)
                return True
            if color[v] == WHITE:
                if dfs(v, path):
                    return True
        path.pop()
        color[u] = BLACK
        return False

    for node in graph:
        if color[node] == WHITE:
            if dfs(node, []):
                return cycle_members
    return cycle_members

# P1→P2→P3→P1 순환, P4는 P2를 기다림
graph = {
    "P1": ["P2"],
    "P2": ["P3"],
    "P3": ["P1"],
    "P4": ["P2"],
}
deadlocked = detect_cycle(graph)
print(f"데드락 프로세스: {deadlocked}")
# 데드락 프로세스: {'P1', 'P2', 'P3'}
# P4는 P2를 기다리지만 사이클의 일부는 아님 (하지만 간접적으로 영향받음)

모든 도착 노드가 graph의 키로 등록된 입력을 가정합니다. 함수는 처음 발견한 사이클에서 종료하며, 집합의 출력 순서는 보장하지 않습니다.

DFS 결과 {'P1','P2','P3'}는 '처음 발견한 사이클의 구성원'입니다. P4는 P2를 기다려 진행이 막힐 수 있지만 그 반환 집합에는 없습니다. 집합에 P4가 없다고 정상 진행 중이라는 뜻으로 읽으면 안 됩니다. 또한 다른 독립 사이클까지 모두 수집하려면 첫 발견에서 즉시 반환하는 이 함수와는 다른 순회가 필요합니다.

독립 확인: 키 순서가 A, B, C, D이고 간선은 A→B, B→A, C→D, D→C입니다. 원 detect_cycle이 반환하는 구성원과 반환하지 못한 독립 사이클은 무엇인가요? 모든 도착 노드는 키에 등록됐다고 가정합니다.

다중 인스턴스 — 은행원 변형

자원 유형의 인스턴스가 여러 개인 경우에는 은행원 알고리즘과 유사한 탐지 알고리즘을 사용합니다.

차이점은 Max 대신 현재 요청 행렬(Request)을 사용한다는 것입니다.

알고리즘은 Available 자원으로 완료 가능한 프로세스를 찾고, 그 프로세스의 자원을 반환받아 다른 프로세스를 완료시킵니다.

이 모형에서 자원을 보유한 채 완료 불가능으로 남은 프로세스를 데드락 집합으로 반환합니다. 처음부터 할당량이 0인 프로세스는 다른 프로세스의 자원을 막지 않으므로 이 반환 집합에서 제외합니다.

def detect_deadlock(available, allocation, request, n_proc, n_res):
    """다중 인스턴스 데드락 탐지 알고리즘"""
    work = available[:]
    finish = [False] * n_proc

    # Allocation이 0인 프로세스는 자원을 보유하지 않으므로 데드락 아님
    for i in range(n_proc):
        if all(allocation[i][j] == 0 for j in range(n_res)):
            finish[i] = True

    changed = True
    while changed:
        changed = False
        for i in range(n_proc):
            if not finish[i]:
                if all(request[i][j] <= work[j] for j in range(n_res)):
                    # 요청 충족 가능 → 완료 후 자원 반환
                    for j in range(n_res):
                        work[j] += allocation[i][j]
                    finish[i] = True
                    changed = True

    deadlocked = [i for i in range(n_proc) if not finish[i]]
    return deadlocked

# 예제
available = [0, 0, 0]
allocation = [
    [0, 1, 0],  # P0
    [2, 0, 0],  # P1
    [3, 0, 3],  # P2
    [2, 1, 1],  # P3
    [0, 0, 2],  # P4
]
request = [
    [0, 0, 0],  # P0: 추가 요청 없음
    [2, 0, 2],  # P1
    [0, 0, 0],  # P2: 추가 요청 없음
    [1, 0, 0],  # P3
    [0, 0, 2],  # P4
]

dl = detect_deadlock(available, allocation, request, 5, 3)
print(f"데드락 프로세스: {dl}")

다음은 주어진 입력을 코드 순서대로 손으로 추적한 결과입니다.

원 입력의 첫 가용량은 [0,0,0]이지만 P0의 현재 Request도 0이므로 완료하여 Allocation=[0,1,0]을 반환할 수 있습니다. P1은 자신의 첫 검사에서 [2,0,2]를 충족하지 못합니다. 그러나 P2의 Request=0이므로 기존 [3,0,3]을 반환해 Work=[3,1,3]이 되고, P3·P4도 완료할 수 있습니다. 두 번째 순회에서 P1까지 완료하므로 원 반환값은 []입니다. 가용량 0, 한 번의 실패한 검사, 최종 교착 집합을 구별하세요.

P3의 단계도 안전성 코드와 같은 반환 계산을 씁니다. Work=[3,1,3]에서 Request=[1,0,0]을 가상으로 주면 [2,1,3]이지만 P3는 기존 [2,1,1]과 추가 [1,0,0]을 함께 반납하므로 [5,2,4]가 됩니다. 식으로는 원 Work+[2,1,1]입니다. 현재 Request를 검사하는 코드에 미래 Need를 대신 넣으면 질문 자체가 회피 문제로 바뀝니다.

독립 확인: 원 입력의 P2 Request만 [1,0,0]으로 바꿉니다. P0 완료 뒤 Work부터 계산하여 반환되는 프로세스 번호를 구하세요. 그 상태에 Allocation=[0,0,0], Request=[1,0,0]인 P5를 추가하면 반환 집합이 어떻게 달라지나요?

언제 탐지를 실행할 것인가

탐지 알고리즘의 실행 시점은 트레이드오프입니다.

• 매 자원 요청마다: 즉시 감지하지만 오버헤드가 큽니다. $O(n^2 \times m)$을 매번 수행.
• 주기적으로: 30초마다, 5분마다 등. CPU 이용률이 임계치 아래로 떨어지면 실행하는 변형도 있습니다.
• 자원 요청이 즉시 충족되지 않을 때: 프로세스가 대기 상태에 들어갈 때만 실행. 합리적인 절충안입니다.

MySQL InnoDB의 데드락 탐지는 기본적으로 활성화되며, 감지한 데드락의 희생 트랜잭션을 롤백합니다. 탐지 대상은 InnoDB가 파악하는 락 관계입니다.

탐지 비용이 큰 환경에서는 비활성화하고 innodb_lock_wait_timeout을 사용할 수 있지만, 기본 시간 초과 처리는 현재 문장만 롤백합니다. 전체 트랜잭션 롤백 여부는 innodb_rollback_on_timeout 설정과 애플리케이션 처리까지 확인해야 합니다.

데드락 복구

데드락을 탐지했으면 복구해야 합니다.

두 가지 주요 방법이 있습니다.

복구할 때는 중단할 작업과 허용할 손실을 함께 정합니다.

프로세스 종료

가장 직접적인 방법입니다.

방법 1 — 전체 종료: 데드락에 관련된 모든 프로세스를 종료합니다.

확실히 해결되지만, 작업 손실이 큽니다.

방법 2 — 하나씩 종료: 프로세스를 하나씩 종료하면서 매번 데드락이 해제되었는지 검사합니다.

어떤 프로세스를 먼저 종료할지는 다음 기준으로 판단합니다.

• 우선순위: 낮은 우선순위의 프로세스부터 종료
• 실행 시간: 적게 실행된 프로세스를 종료 (손실 최소화)
• 보유 자원 수: 많은 자원을 보유한 프로세스를 종료 (효과 극대화)
• 남은 작업량: 완료까지 많은 작업이 남은 프로세스를 종료
• 프로세스 유형: 대화형(interactive)보다 일괄처리(batch)를 우선 종료

프로세스 종료는 파일 쓰기 같은 외부 효과를 자동으로 되돌리지 않습니다. 트랜잭션이 보장하는 변경은 롤백할 수 있지만, 그 밖의 I/O와 이미 확정된 작업까지 함께 복구되는 것은 아닙니다.

자원 선점

데드락에 관련된 프로세스에서 자원을 강제로 빼앗아 다른 프로세스에게 주는 방법입니다.

세 가지 문제를 해결해야 합니다.

1. 희생자 선택(Selecting a victim): 어떤 프로세스에서 어떤 자원을 빼앗을 것인가?

비용이 최소인 프로세스를 선택합니다.

비용 함수에는 우선순위, 실행 시간, 보유 자원 등이 포함됩니다.

2. 롤백(Rollback): 자원을 빼앗긴 프로세스를 이전의 안전한 상태로 되돌려야 합니다.

체크포인트(Checkpoint)를 주기적으로 저장해 두면 롤백 비용을 줄일 수 있습니다.

처음부터 다시 실행하려면 입력 재현과 외부 효과 정리 등 재시작 가능한 설계가 필요합니다. 임의의 뮤텍스를 빼앗거나 프로세스만 재시작한다고 상태가 복원되지는 않습니다.

3. 기아 방지(Starvation Prevention): 같은 프로세스에서 계속 자원을 빼앗으면 그 프로세스는 영원히 완료되지 못합니다.

해결법: 롤백 횟수를 비용 함수에 포함시켜서, 자주 희생된 프로세스의 비용을 높여 다음에는 선택되지 않게 합니다.

타조 알고리즘

타조 알고리즘(Ostrich Algorithm)은 "데드락이 발생하면 무시한다"는 전략입니다.

타조가 위험에 처하면 모래에 머리를 파묻는다는 속담에서 유래했습니다.

이 전략은 탐지·예방 비용과 장애 비용을 비교하는 사고 실험입니다. 발생 빈도가 낮고 수동 복구 비용이 작은 일부 자원에 적용할 수 있지만, 운영체제 전체가 한 정책만 쓰는 것은 아닙니다.

예를 들어 지속적인 5% 성능 비용과 월 1회 5분의 복구를 비교할 수 있습니다. 이는 가정한 수치이며 장애의 데이터 손실, 영향 범위, 중단 허용 시간을 포함해야 판단할 수 있습니다.

실무에서 데드락을 다루는 종합 가이드

실무에서는 단일 전략이 아닌 여러 전략의 조합을 사용합니다.

설계 단계: 예방

• 락 순서 규칙: 팀 전체가 락 획득 순서를 약속하고 문서화합니다. 코드 리뷰에서 순서 위반을 잡습니다.
• 최소 락 원칙: 임계 구역을 최소화합니다. 락을 잡은 상태에서 I/O를 하지 않습니다.
• 단일 락 선호: 가능하면 하나의 커다란 락(coarse-grained locking)을 사용합니다. 성능이 문제가 될 때만 세밀한 락(fine-grained locking)으로 분리합니다.

구현 단계: 방어적 코딩

import threading
import time
import random

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

def safe_worker(name):
    retries = 0
    max_retries = 5
    while retries < max_retries:
        acquired1 = lock1.acquire(timeout=1)
        if acquired1:
            acquired2 = lock2.acquire(timeout=1)
            if acquired2:
                try:
                    print(f"[{name}] 작업 수행")
                    return
                finally:
                    lock2.release()
                    lock1.release()
            else:
                lock1.release()
                wait = random.uniform(0.05, 0.2)
                print(f"[{name}] lock2 타임아웃, {wait:.2f}초 후 재시도")
                time.sleep(wait)  # 랜덤 대기로 충돌 반복 가능성 완화
        else:
            wait = random.uniform(0.05, 0.2)
            print(f"[{name}] lock1 타임아웃, {wait:.2f}초 후 재시도")
            time.sleep(wait)
        retries += 1
    print(f"[{name}] 최대 재시도 초과, 대체 로직 실행")

각 락 대기에 1초 제한을 두고 최대 다섯 번 시도합니다. 랜덤 대기는 충돌 반복을 줄일 수 있지만 성공이나 공정성을 보장하지 않습니다. 함수 정의만으로 스레드를 실행한 것은 아니며, 마지막 경로는 실패 안내만 출력합니다.

타임아웃 예에서 다섯 시도 중 처음 세 번은 lock1, 나머지 두 번은 lock2 획득에 실패했다고 합시다. lock1의 최대 대기는 총 다섯 번, lock2는 총 두 번이므로 지정한 대기 한도 합은 7초입니다. 다섯 랜덤 재시도 대기는 각각 최대 0.2초여서 합은 최대 1초입니다. 이는 요청한 대기·백오프 예산 8초의 계산이며 스레드가 다시 스케줄되는 시간, 함수 내부 실행·출력, 시스템 지연까지 포함한 엄밀한 벽시계 완료 상한은 아닙니다. 실패 분기에서는 그 시도에서 획득했던 락을 반납한 뒤 재시도합니다.

독립 확인: DB 트랜잭션으로 기록을 바꾸는 작업이 중간에 외부 알림을 이미 보낸 뒤 교착 희생자로 롤백됐습니다. DB 기록이 원래 상태로 돌아왔다는 확인만으로 재시도 시 알림 중복도 해결됐다고 볼 수 있나요? 외부 알림은 그 DB 트랜잭션에 참여하지 않는다고 가정합니다.

운영 단계: 감지와 대응

• Java: 스레드 덤프와 ThreadMXBean.findDeadlockedThreads()로 확인합니다. 후자는 플랫폼 스레드의 모니터·소유 가능한 동기화 객체를 대상으로 하며 가상 스레드나 모든 외부 자원 대기를 탐지하지는 않습니다.
• MySQL: innodb_deadlock_detect = ON으로 자동 감지 + 비용 낮은 트랜잭션 롤백. SHOW ENGINE INNODB STATUS\G로 상세 확인.
• Linux: lockdep으로 커널 수준 락 순서 위반 탐지. perf lock으로 락 경합 프로파일링.
• 분산 시스템: 타임아웃과 서킷 브레이커로 대기·실패를 제한할 수 있습니다. 메시지 큐를 사용해도 소비자 사이의 순환 대기와 재처리 조건은 별도로 설계해야 합니다.

다음 장에서는 OS가 관리하는 또 다른 핵심 자원인 메모리를 다루겠습니다.

물리 메모리의 한계를 극복하기 위한 메모리 관리 전략을 살펴봅니다.