교착 상태 복구 (프로세스 킬)

핵심 인사이트 (3줄 요약)

본질: 교착 상태 복구(Deadlock Recovery)는 시스템이 데드락 예방이나 회피를 포기하고 일단 데드락이 발생하도록 내버려 둔 뒤, 주기적인 탐지(Detection)를 통해 꼬인 매듭을 사후에 강제로 끊어내는(Recovery) 비관적 대처법이다.

해결책 (Process Kill): 가장 확실하고 잔인한 복구 방법은 데드락 사이클(원형 대기)에 얽혀있는 프로세스 중 만만한 놈(Victim) 하나를 골라 강제로 죽여버려(Kill) 쥐고 있던 자원을 뺏는 것이다.

희생자 선정 (Victim Selection): 아무나 죽이면 시스템 피해가 크므로, 연산 진행도가 가장 낮거나, 롤백(Rollback)해야 할 데이터가 가장 적거나, 우선순위가 가장 낮은 프로세스를 희생자로 고르는 경제적이고 전략적인 판단이 요구된다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념:
- 교착 상태 탐지 (Detection): 주기적으로 자원 할당 그래프(RAG)를 순회하며 사이클(데드락)이 발생했는지 찾는 과정.
- 교착 상태 복구 (Recovery): 탐지된 데드락을 풀기 위해, 얽힌 프로세스를 죽이거나 자원을 강제로 뺏어 시스템을 정상화하는 과정.
필요성 (타조 알고리즘의 한계와 데이터베이스의 책임):
- 범용 OS(리눅스, 윈도우)는 데드락이 나도 책임지지 않고 그냥 타조처럼 무시한다.
- 하지만 수천억 원이 오가는 **데이터베이스(Oracle, MySQL)**마저 타조 흉내를 내면? 결제 트랜잭션이 멈춘 상태로 DB가 뻗어버리면 회사가 망한다.
- 해결책: "데드락이 나는 건 어쩔 수 없다. 하지만 났을 때 그대로 멈춰서 다 같이 죽는 것보단, 차라리 제일 덜 중요한 트랜잭션 하나를 쏴 죽여서(Kill) 나머지라도 살려내자!"는 사후 약방문(하지만 확실한) 처방이 도입되었다.
💡 비유:
- 4대의 차가 좁은 사거리에서 꼬리를 물고 완벽하게 엉켰다(데드락 탐지).
- 아무도 안 비켜서 교통이 마비됐다.
- 이때 거대한 견인차(Recovery 모듈)가 와서, 가장 값싸 보이고 견인하기 쉬운 티코 1대(희생자, Victim)를 찝어서 허공으로 번쩍 들어 올린다(Kill & Rollback).
- 길이 뻥 뚫리고 나머지 3대의 차(트랜잭션)는 무사히 자기 길을 간다. 티코 운전자는 화가 나겠지만 나중에 다시 길을 가면 된다(재시도).
발전 과정:
1. 모두 죽이기 (Abort All): 초창기 방식. 꼬인 애들을 다 죽여버림. 복구 비용이 너무 큼.
2. 하나씩 죽이기 (Abort One by One): 하나 죽이고 데드락 풀렸는지 확인. 안 풀렸으면 또 하나 죽임.
3. 자원만 선점하기 (Resource Preemption): 프로세스는 안 죽이고 자원만 뺏어옴. (하지만 뺏긴 프로세스가 망가져서 롤백 관리가 극도로 어려움)
📢 섹션 요약 비유: 암세포(데드락)가 생기는 것을 완벽히 막는 예방약은 없으니, 정기적으로 MRI(탐지)를 찍고 암이 발견되면 가장 살리기 힘든 장기 일부를 칼로 도려내는(Kill) 외과 수술적 접근법입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

데드락 복구를 위한 프로세스 종료 (Process Termination) 기법

탐지기(Detector)가 데드락 사이클을 발견했을 때, 운영체제나 DBMS는 다음 두 가지 극단적인 방법 중 하나를 택한다.

Abort All (교착 상태 프로세스 모두 종료):
- 사이클에 엮인 5개의 프로세스를 동시에 다 죽여버린다.
- 장점: 확실하고 빠르다. 단 1초 만에 데드락이 붕괴된다.
- 단점: 5명이 지금까지 연산했던 수시간 분량의 데이터가 모조리 증발한다. 시스템 피해가 막심하다.
Abort One by One (희생자 하나씩 찌르기):
- 5명 중 제일 만만한 **'희생자(Victim)'**를 1명 고른다.
- 그 1명을 죽여서 자원을 회수한 뒤, 다시 탐지 알고리즘을 돌려 데드락이 풀렸는지 본다.
- 여전히 4명이 데드락 상태라면? 또 다음 타자를 골라 죽인다. 풀릴 때까지 반복한다.
- 장점: 시스템 피해를 최소화할 수 있다. (수술 부위를 최소화)
- 단점: 1명 죽일 때마다 무거운 데드락 탐지(DFS 사이클 찾기)를 다시 돌려야 하므로 오버헤드가 엄청나다.

희생자 선정 알고리즘 (Victim Selection)

"누구를 쏴 죽일 것인가?"는 철저히 비용(Cost) 최소화 원칙을 따른다.

평가 기준	누구를 죽일 것인가? (Victim의 특징)	이유 (비용 최소화)
진행 척도 (Execution Time)	방금 막 시작한 놈	10시간 연산한 놈을 죽이면 너무 아깝다. 1초 된 놈을 죽이는 게 싸다.
자원 사용량 (Resource Held)	가진 자원이 적은 놈	자원을 많이 가진 놈은 그걸 다시 뺏어서 정리(회수)하는 비용이 크다.
남은 시간 (Remaining Time)	앞으로 한참 더 일해야 하는 놈	1초 뒤면 끝날 놈을 죽이는 건 바보짓이다.
우선순위 (Priority)	우선순위가 가장 낮은 놈	일반 유저 쿼리를 죽이지, 시스템 백업 쿼리를 죽일 순 없다.

롤백 (Rollback): 쏴 죽이는 것으로 끝이 아니다. 죽인 프로세스가 만지작거리던 데이터(계좌 잔고 등)를 다시 과거의 깨끗한 상태로 되돌려 놔야(Rollback) 다른 프로세스가 안전하게 쓸 수 있다. DBMS가 거대한 Undo Log를 유지하는 이유가 바로 이 롤백을 위함이다.
📢 섹션 요약 비유: 침몰하는 배(데드락)를 구하기 위해 짐을 바다에 던져야 합니다. 선장(OS)은 황금(오래 실행된 중요 프로세스)을 버리지 않고, 가장 가볍고 다시 구하기 쉬운 밀가루 포대(방금 시작한 작은 프로세스)부터 바다에 던집니다.

Ⅲ. 융합 비교 및 다각도 분석

자원 선점 (Resource Preemption) vs 프로세스 종료 (Process Kill)

프로세스를 아예 죽여버리는 게 너무 잔인해서 나온 대안이 '자원 선점'이다. 하지만 현실은 녹록지 않다.

구분	Process Kill (프로세스 종료)	Resource Preemption (자원만 뺏기)
조치 내용	프로세스의 메모리와 스레드를 완전히 소멸시킴	프로세스는 살려두고 쥐고 있던 락(자원)만 뺏어옴
부작용	데이터 완전 날아감. 처음부터 다시 시작해야 함	자원을 뺏긴 프로세스가 멘붕에 빠짐 (정합성 파괴)
구현 난이도	쉬움 (그냥 `SIGKILL` 날리면 됨)	매우 극악 (안전한 지점까지 Rollback 시켜야 함)
기아 위험	낮음	매우 높음 (매번 뺏기는 놈만 뺏겨 굶어 죽음)

자원만 뺏으면 뺏긴 쪽 코드가 에러를 뿜기 때문에, 결국 그 프로세스를 과거의 체크포인트(안전한 상태)로 되돌리는 무서운 복잡도가 따라붙어 현실에서는 주로 DB 시스템에서만 한정적으로 쓰인다.

과목 융합 관점

데이터베이스 (DB): 데드락 복구의 진짜 주인공은 OS가 아니라 DBMS다. MySQL(InnoDB)은 두 트랜잭션이 데드락 사이클을 만들면, 즉시 이를 감지하고 **"Undo Log의 크기가 더 작은(롤백하기 쉬운) 트랜잭션"**을 희생자(Victim)로 선정하여 강제로 에러(Error 1213: Deadlock found)를 던지며 롤백시켜 버린다.
분산 시스템 (Distributed): MSA 환경에서는 여러 마이크로서비스에 걸친 분산 데드락을 감지하기도, 희생자를 정하기도 불가능에 가깝다. 따라서 "타임아웃(Timeout)"이라는 단순 무식한 칼을 쓴다. API 응답이 3초 이상 안 오면 "이거 데드락인가 보네?" 하고 요청을 끊어버리는(임의의 Kill) 서킷 브레이커(Circuit Breaker)가 이 복구 기법의 클라우드 버전이다.
📢 섹션 요약 비유: 뺏은 빵(자원)을 먹다 뱉게 하는 것(자원 선점)은 매우 더럽고 뒤처리가 힘듭니다. 그래서 운영체제나 DB는 보통 빵을 먹던 사람을 통째로 밖으로 던져버리고(Process Kill), 나중에 새 빵을 주며 처음부터 다시 먹게 하는 깔끔한 방식을 선호합니다.

Ⅳ. 실무 적용 및 기술사적 판단

실무 시나리오

시나리오 — JPA/Spring 환경에서 발생하는 DeadlockLoserDataAccessException 대처: 결제 서버 개발자가 코드를 짰는데, 사용자가 몰리는 피크 타임에 자꾸 저 에러가 나면서 결제가 실패함.
- 원인 분석: DB 락 순서가 꼬여서 MySQL이 데드락을 감지했다. MySQL은 데드락을 풀기 위해 개발자의 트랜잭션 하나를 **희생자(Victim)**로 골라서 죽여(Kill) 버렸다. 그 결과 스프링 앱으로 DeadlockLoser 예외가 날아온 것이다.
- 대응 (기술사적 가이드): 이 에러는 "DB가 너의 코드를 데드락의 범인으로 지목해서 쏴 죽였다"는 사형 선고다. 개발자는 이 에러를 catch 블록으로 잡고 사용자에게 "결제 실패"를 띄우면 안 된다. **반드시 백오프(Backoff)를 두고 @Retryable 등을 이용해 트랜잭션을 다시 처음부터 재시도(Retry)**하게 만들어야, 죽었다 살아난 트랜잭션이 이번엔 락을 쥐고 성공할 수 있다.
시나리오 — 기아 현상 (Starvation)과 희생자 선정의 딜레마: 오라클 DB에서 긴 배치(Batch) 트랜잭션과 수많은 짧은 웹 트랜잭션이 데드락을 일으켰다.
- 원인 분석: DB의 데드락 감지기는 "비용을 최소화"하기 위해 짧은 웹 트랜잭션보다 롤백 비용이 적은 트랜잭션을 희생자로 고른다. 그런데 하필 긴 배치 작업이 매번 데드락 사이클에 껴있어서, 감지기가 매번 똑같은 긴 배치 작업만 희생자(Victim)로 골라 죽여버렸다. 배치 작업은 밤새도록 100번을 죽었다 살아나기를 반복하며 영원히 끝나지 못하는 기아(Starvation)에 빠졌다.
- 아키텍처 적용: 희생자 선정 알고리즘에 반드시 **'롤백 횟수(Number of Rollbacks)'**를 가중치로 넣어야 한다. "아무리 만만한 놈이라도 3번 이상 쏴 죽였으면, 4번째엔 불쌍하니까 살려주고 다른 놈을 죽여라!"라는 에이징(Aging) 철학이 데드락 복구에도 필수적이다.

의사결정 및 튜닝 플로우

  ┌───────────────────────────────────────────────────────────────────┐
  │                 시스템 장애 시 데드락 탐지 및 복구(Recovery) 플로우         │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │   [서버나 DB가 데드락 징후(특정 기능 영구적 응답 지연)를 보일 때]               │
  │                │                                                  │
  │                ▼                                                  │
  │      1. [탐지 주기 설정] 데드락 감지 알고리즘(DFS 사이클 검색)을 돌려야 함     │
  │         - 너무 자주 돌리면? -> CPU 낭비로 시스템 전체가 느려짐.            │
  │         - 너무 가끔 돌리면? -> 데드락에 빠진 채로 오래 방치되어 피해 큼.      │
  │         ★ 타협점: 자원 요청 시마다 검사하지 않고, 10초에 한 번씩만 데몬 구동  │
  │                │                                                  │
  │                ▼                                                  │
  │      2. [사이클 발견 시 1차 대응: Rollback Cost 계산]                  │
  │         - 얽혀있는 프로세스들의 '실행 시간', '가진 자원', '우선순위' 스캔.     │
  │         - 가장 비용이 싼 놈을 희생자(Victim)로 타겟팅.                     │
  │                │                                                  │
  │                ▼                                                  │
  │      3. [2차 대응: Kill & Retry]                                    │
  │         - 희생자에게 `SIGKILL` 또는 `Abort` 신호 전송.                 │
  │         - 남은 애들이 락을 쥐고 살아나는지 확인.                           │
  │         - 죽인 놈이 또 꼬이는 기아를 막기 위해 희생자의 우선순위 일시 부스트.    │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 복구(Recovery)는 실패를 인정한 패배자의 선택이 아니다. 복잡성이 극에 달한 현대 마이크로서비스에서 데드락을 100% 예방하는 것은 오만이다. 최고의 시스템은 꼬이지 않는 시스템이 아니라, **"꼬였을 때 가장 싸고 만만한 놈의 꼬리를 0.1초 만에 잘라내고, 잘린 꼬리가 알아서 다시 자라나게(Retry) 만드는 회복 탄력성(Resilience)"**을 가진 시스템이다.

도입 체크리스트

비등멱성(Non-idempotent) 연산의 롤백 위험: 희생자로 선정되어 킬을 당하면, 시스템은 그 놈이 하던 짓을 롤백(취소)해야 한다. 그런데 그 놈이 외부 API로 결제 승인을 쏴버렸거나 프린터로 종이를 인쇄하고 있었다면? 물리적 세계로 나간 액션은 롤백할 수 없다. 데드락 킬이 예상되는 임계 구역 안에는 롤백이 불가능한 외부 I/O를 절대 넣지 않도록 설계했는가?
📢 섹션 요약 비유: 도마뱀이 포식자(데드락)에게 물렸을 때 살기 위해 스스로 꼬리를 자르고 도망치는 것(Victim Kill)과 같습니다. 꼬리(잘린 트랜잭션)는 아프겠지만 몸통(시스템 전체)은 살아서 도망갈 수 있고, 꼬리는 나중에 다시 자라납니다(Retry).

Ⅴ. 기대효과 및 결론

정량/정성 기대효과

구분	데드락 무시 (타조 알고리즘)	탐지 및 복구 (Detection & Kill)	개선 효과
정성 (시스템 가용성)	꼬인 앱은 영원히 멈춤 (수동 재시작)	스스로 꼬인 매듭을 풀고 자가 치유됨	무인화된(Self-healing) 무중단 서비스 달성
정량 (자원 낭비)	데드락 상태로 메모리/락 무한 점유	수 초 내에 락 강제 회수	데드락으로 인한 OOM 및 커넥션 풀 고갈 방지
정성 (데이터 무결성)	유저가 강제 종료 시 데이터 깨질 위험	DB 레벨의 안전한 Undo 및 Rollback	데이터 정합성 100% 보장

미래 전망

머신러닝 기반 데드락 예측: 주기적인 탐지(Detection) 오버헤드를 없애기 위해, 트랜잭션이 시작될 때 AI 모델이 "이 쿼리 패턴은 3초 뒤에 저 쿼리와 교착 상태를 일으킬 확률이 95%다"라고 런타임에 예측하여, 애초에 락 대기 줄에 섞이지 않고 우회하게 만드는 지능형 락 매니저가 차세대 RDBMS의 핵심 기술로 연구되고 있다.
분산 환경의 락 리스(Lock-less) 아키텍처: 클라우드에서는 프로세스 하나를 킬(Kill)하고 롤백하는 비용이 너무 비싸다. 아예 교착 상태 복구 로직을 만들지 않아도 되도록, 이벤트 소싱(Event Sourcing)과 CQRS, Saga 패턴을 융합하여 서비스 간에 락을 잡지 않고 상태 머신으로만 데이터를 일관성 있게 맞추는 아키텍처가 데드락 복구의 궁극적인 종착지가 되고 있다.

결론

교착 상태 복구(프로세스 킬)는 완벽함을 포기하고 실용성을 택한 컴퓨터 공학의 살벌하지만 가장 현실적인 결단이다. "우리는 꼬임을 막을 수 없다. 하지만 꼬였을 때 칼로 끊어낼 용기는 있다"는 이 비관적이고 과단성 있는 철학 덕분에, 오늘날의 거대한 데이터베이스와 클라우드 인프라가 멈추지 않고 돌아가고 있다. 희생양(Victim)을 골라 피를 묻히고(Kill), 다시 살려내어(Retry) 기아(Starvation)를 막아내는 이 정교한 살생부야말로 시스템 엔지니어가 그릴 수 있는 가장 치열한 복구 아키텍처다.

📢 섹션 요약 비유: 복잡하게 엉킨 고르디우스의 매듭(데드락)을 손으로 하나하나 풀려다 늙어 죽는 대신, 알렉산더 대왕처럼 단칼에 매듭 하나를 베어버려(프로세스 킬) 전체를 한 번에 풀어내는 가장 압도적이고 효율적인 결단력입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
Detection (탐지)	복구를 실행하기 전, 자원 할당 그래프(RAG)에서 사이클을 찾아 데드락을 확진하는 선행 작업
Victim Selection (희생자 선정)	데드락을 부수기 위해 누구를 쏴 죽일지 고르는 작업. 롤백 비용과 우선순위를 철저히 계산해야 함
Rollback (롤백)	희생자로 킬(Kill)당한 프로세스의 더럽혀진 데이터를 과거의 깨끗한 상태로 되돌리는 필수 사후 처리
Starvation (기아)	매번 만만한 놈만 희생자(Victim)로 골라 죽여서, 그 프로세스가 평생 일을 못 끝내는 치명적 부작용
Deadlock Avoidance (회피)	데드락이 터진 뒤에 피를 보는 '복구' 방식이 싫어서, 애초에 은행원처럼 깐깐하게 심사하여 피해 가려는 정반대의 철학

👶 어린이를 위한 3줄 비유 설명

4명의 친구가 좁은 골목에서 서로 비키라고 싸우면서 한 발짝도 못 움직이고 있어요(데드락).
선생님(OS)이 와서 보더니, 이대로 두면 오늘내로 집에 못 갈 것 같았어요. 그래서 4명 중 제일 짐이 가벼운 막내(희생자)를 번쩍 들어서 골목 밖으로 빼버렸어요(프로세스 킬).
막내가 빠지니까 공간이 생겨서 나머지 3명은 무사히 지나갔어요. 밖으로 쫓겨난 막내는 억울하지만 나중에 다시 길을 지나가면 된답니다(재시도)!