데드락 탐지와 복구
예방과 회피를 완벽하게 적용하기 어렵다면, 데드락이 발생하도록 두었다가 탐지(Detection)한 후 복구(Recovery)하는 전략을 쓸 수 있습니다. 예방은 제약이 많고, 회피는 미래 예측이 필요합니다. 현실의 많은 시스템(Linux, Windows, 대부분의 DBMS)은 사실상 이 탐지 후 복구 접근법이나, 아예 무시하는 전략을 택합니다.
탐지 알고리즘: 자원 유형별 구분
탐지 알고리즘은 현재 시점에서 데드락이 존재하는가?를 판정합니다. 자원 유형의 인스턴스 수에 따라 두 가지 방법이 있습니다.
단일 인스턴스 — 대기 그래프
각 자원 유형의 인스턴스가 하나뿐인 경우에는 대기 그래프(Wait-for Graph)를 사용합니다. 자원 할당 그래프에서 자원 노드를 제거하고, Pi가 Pj가 보유한 자원을 기다린다면 Pi → Pj 간선을 그립니다.
이 그래프에 사이클이 있으면 데드락입니다. 사이클 탐지는 DFS로 에 수행할 수 있습니다.
def detect_cycle(graph):
"""대기 그래프에서 사이클 탐지 (DFS 기반)"""
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:
dfs(node, [])
return cycle_members
# P1→P2→P3→P1 순환, P4는 독립
graph = {
"P1": ["P2"],
"P2": ["P3"],
"P3": ["P1"],
"P4": ["P2"],
}
deadlocked = detect_cycle(graph)
print(f"데드락 프로세스: {deadlocked}")
# 데드락 프로세스: {'P1', 'P2', 'P3'}
# P4는 P2를 기다리지만 사이클의 일부는 아님 (하지만 간접적으로 영향받음)다중 인스턴스 — 은행원 변형
자원 유형의 인스턴스가 여러 개인 경우에는 은행원 알고리즘과 유사한 탐지 알고리즘을 사용합니다. 차이점은 Max 대신 현재 요청 행렬(Request)을 사용한다는 것입니다.
알고리즘은 Available 자원으로 완료 가능한 프로세스를 찾고, 그 프로세스의 자원을 반환받아 다른 프로세스를 완료시킵니다. 이 과정을 반복한 후에도 완료되지 못한 프로세스가 남아있으면 그들이 데드락에 빠진 것입니다.
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}")언제 탐지를 실행할 것인가
탐지 알고리즘의 실행 시점은 트레이드오프입니다.
- 매 자원 요청마다: 즉시 감지하지만 오버헤드가 큽니다. 을 매번 수행.
- 주기적으로: 30초마다, 5분마다 등. CPU 이용률이 임계치 아래로 떨어지면 실행하는 변형도 있습니다.
- 자원 요청이 즉시 충족되지 않을 때: 프로세스가 대기 상태에 들어갈 때만 실행. 합리적인 절충안입니다.
MySQL InnoDB는 매 트랜잭션 대기마다 대기 그래프를 검사합니다(innodb_deadlock_detect = ON, 기본값). 대규모 시스템에서 이 오버헤드가 문제가 되면 innodb_deadlock_detect = OFF로 끄고 innodb_lock_wait_timeout(기본 50초)에 의존합니다.
데드락 복구
데드락을 탐지했으면 복구해야 합니다. 두 가지 주요 방법이 있습니다.
프로세스 종료
가장 직접적인 방법입니다.
방법 1 — 전체 종료: 데드락에 관련된 모든 프로세스를 종료합니다. 확실히 해결되지만, 작업 손실이 큽니다.
방법 2 — 하나씩 종료: 프로세스를 하나씩 종료하면서 매번 데드락이 해제되었는지 검사합니다. 어떤 프로세스를 먼저 종료할지는 다음 기준으로 판단합니다.
- 우선순위: 낮은 우선순위의 프로세스부터 종료
- 실행 시간: 적게 실행된 프로세스를 종료 (손실 최소화)
- 보유 자원 수: 많은 자원을 보유한 프로세스를 종료 (효과 극대화)
- 남은 작업량: 완료까지 멀리 남은 프로세스를 종료
- 프로세스 유형: 대화형(interactive)보다 일괄처리(batch)를 우선 종료
프로세스 종료의 문제: 파일을 쓰는 중간에 종료하면 데이터가 손상됩니다. 트랜잭션 중간에 종료하면 부분 업데이트가 남습니다. 따라서 트랜잭션 지원 시스템에서는 롤백으로 깔끔하게 복구할 수 있지만, 일반 프로세스에서는 손상 위험이 있습니다.
자원 선점
데드락에 관련된 프로세스에서 자원을 강제로 빼앗아 다른 프로세스에게 주는 방법입니다.
세 가지 문제를 해결해야 합니다.
1. 희생자 선택(Selecting a victim): 어떤 프로세스에서 어떤 자원을 빼앗을 것인가? 비용이 최소인 프로세스를 선택합니다. 비용 함수에는 우선순위, 실행 시간, 보유 자원 등이 포함됩니다.
2. 롤백(Rollback): 자원을 빼앗긴 프로세스를 이전의 안전한 상태로 되돌려야 합니다. 체크포인트(Checkpoint)를 주기적으로 저장해두면 롤백 비용을 줄일 수 있습니다. 가장 간단한 방법은 프로세스를 완전히 재시작하는 것(Total Rollback)입니다.
3. 기아 방지(Starvation Prevention): 같은 프로세스에서 계속 자원을 빼앗으면 그 프로세스는 영원히 완료되지 못합니다. 해결법: 롤백 횟수를 비용 함수에 포함시켜서, 자주 희생된 프로세스의 비용을 높여 다음에는 선택되지 않게 합니다.
타조 알고리즘
타조 알고리즘(Ostrich Algorithm)은 "데드락이 발생하면 무시한다"는 전략입니다. 타조가 위험하면 모래에 머리를 파묻는다는 속담에서 유래했습니다.
농담처럼 들리지만, 실제로 대부분의 범용 운영체제(Linux, Windows, macOS)가 이 전략을 기본으로 사용합니다. 이유는 경제적입니다.
- 데드락은 매우 드물게 발생합니다.
- 예방/회피의 지속적 오버헤드가 가끔 발생하는 데드락의 비용보다 클 수 있습니다.
- 사용자가 프로그램을 재시작하면 해결됩니다.
수학적으로 보면: 데드락 예방의 성능 저하가 5%이고 24시간 내내 적용된다면, 하루에 1.2시간의 CPU 시간 손실입니다. 데드락이 한 달에 한 번 발생하고 복구에 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}] 최대 재시도 초과, 대체 로직 실행")타임아웃, 재시도 상한, 랜덤 대기를 조합하면 데드락과 라이브락을 모두 방지할 수 있습니다.
운영 단계: 감지와 대응
- Java:
jstack <pid>로 스레드 덤프. JVM이 Found one Java-level deadlock 자동 출력.ThreadMXBean.findDeadlockedThreads()를 모니터링 스레드에서 주기적 호출. - MySQL:
innodb_deadlock_detect = ON으로 자동 감지 + 비용 낮은 트랜잭션 롤백.SHOW ENGINE INNODB STATUS\G로 상세 확인. - Linux:
lockdep으로 커널 수준 락 순서 위반 탐지.perf lock으로 락 경합 프로파일링. - 분산 시스템: 타임아웃 + 서킷 브레이커 패턴. 분산 데드락 감지가 어려우므로 아예 동기 호출을 피하고 비동기 메시지 큐 사용.
| 전략 | 적용 시점 | 오버헤드 | 제약 |
|---|---|---|---|
| 예방 (순서 규칙) | 설계/구현 | 낮음 | 전역 순서 관리 |
| 회피 (은행원) | 런타임 | 높음 | Max 사전 고지 |
| 탐지+복구 | 런타임 | 중간 | 복구 비용 |
| 타조 (무시) | 운영 | 없음 | 수동 복구 |
다음 장에서는 OS가 관리하는 또 다른 핵심 자원인 메모리를 다루겠습니다. 물리 메모리의 한계를 극복하기 위한 메모리 관리 전략을 살펴봅니다.