교착 상태 탐지 (Deadlock Detection)

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

본질: 교착 상태 탐지 (Deadlock Detection)는 운영체제가 데드락 예방이나 회피를 포기하고 **"자원을 달라는 대로 다 주되, 주기적으로 시스템 상태를 감시하여 꼬여있는 데드락(Cycle)을 사후에 찾아내는 모니터링 기법"**이다.

가치: 런타임에 $O(N^2)$ 이상의 무거운 탐지 알고리즘(Wait-For Graph 탐색 등)을 돌려야 하므로 범용 운영체제(Windows, Linux)에서는 쓰이지 않으나, 데이터 무결성이 생명인 관계형 데이터베이스(RDBMS, Oracle/MySQL)에서는 시스템 정지를 막는 핵심 백그라운드 엔진으로 동작한다.

융합: 탐지 알고리즘 그 자체만으로는 문제를 해결할 수 없으며, 탐지된 데드락 사이클을 끊어내기 위해 특정 트랜잭션을 희생양(Victim)으로 삼아 킬(Kill)하고 되돌리는 '교착 상태 복구(Recovery)' 매커니즘과 반드시 한 몸으로 융합되어야 한다.

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

개념: 시스템이 프로세스들에게 자원을 자유롭게 할당하다가, 특정 주기(예: 1초)나 자원 부족 이벤트가 발생했을 때 현재 시스템에 '순환 대기(Circular Wait)'가 형성되었는지를 수학적 그래프 알고리즘이나 행렬 연산으로 검사하는 사후 대처법이다.
필요성: 데드락 예방(Prevention)은 너무 빡빡해서 자원이 낭비되고, 데드락 회피(Avoidance)는 미래의 최대 요구량을 미리 알아야 한다는 불가능한 전제를 깔고 있다. 그렇다면 차라리 **"일단 자유롭게 돌아가게 놔두자. 그러다 가끔 터지면 그때 수술(복구)하자"**는 현실적인 경제적 타협안이 필요해졌다.
💡 비유: 길거리에 경찰(예방)을 깔아서 무단횡단을 원천 차단하는 대신, 도시에 **'CCTV(탐지 알고리즘)'**를 달아놓고 사람들이 맘대로 다니게 놔두다가, 교통사고(데드락)가 났을 때만 CCTV로 꼬인 차들을 찾아내어 견인차(복구)를 부르는 사후 처리 시스템과 같다.
등장 배경: 시스템의 덩치가 커지고 분산 처리(Distributed Processing)가 도입되면서, 락(Lock)의 꼬임을 사전에 100% 막는 것이 수학적으로나 비용적으로 불가능해졌다. 차라리 자원 이용률을 극대화한 뒤 주기적으로 암세포를 찾아 도려내는 탐지 이론이 데이터베이스 공학을 중심으로 크게 발전했다.

  [교착 상태 처리 3대 전략의 자유도와 오버헤드 비교]

  [ 1. 예방 (Prevention) ]
  - 스탠스: "문제를 아예 만들지 마!"
  - 자유도: 최악 (1차선 직진만 허용) / 오버헤드: 0 (규칙만 지키면 됨)

  [ 2. 회피 (Avoidance - 은행원 알고리즘) ]
  - 스탠스: "사고 날 것 같으면 피해서 가!"
  - 자유도: 중간 / 오버헤드: 극악 (매번 1m 앞을 시뮬레이션함)

  [ 3. 탐지 및 복구 (Detection & Recovery) ] ⭐
  - 스탠스: "맘대로 달려! 사고 나면 구급차 부를게!"
  - 자유도: 최상 (자원 100% 활용) / 오버헤드: 백그라운드로 가끔씩만 발생

[다이어그램 해설] 탐지 기법은 "인간(프로그램)은 자유로울 때 최고의 효율을 낸다"는 철학에 기반한다. 제한 없이 락을 쥐락펴락하게 놔두어 평상시의 처리량(Throughput)을 한계치까지 뽑아낸다. 데드락 검사 오버헤드는 매 요청 시마다가 아니라, 시스템 큐가 막히는 낌새가 보일 때만 가끔 돌리면 되므로 가성비가 훌륭하다.

📢 섹션 요약 비유: 탐지 기법은 건강검진과 같습니다. 평소엔 먹고 싶은 거 맘대로 다 먹으며(자원 자유 할당) 스트레스 없이 살다가, 1년에 한 번 건강검진(탐지)을 받아 용종(데드락)이 발견되면 그 부분만 레이저로 떼어내는(복구) 현대 의학적 접근법입니다.

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

탐지 알고리즘 1: 단일 인스턴스 자원 환경 (대기 그래프)

자원의 종류당 인스턴스가 1개(예: 특정 DB의 특정 Row 1줄)일 때는 복잡한 행렬이 필요 없다. 자원 할당 그래프(RAG)에서 불필요한 사각형(자원)을 빼버리고 원(프로세스)만 남긴 **대기 그래프 (Wait-For Graph, WFG)**를 그려서 사이클만 찾으면 된다.

  ┌──────────────────────────────────────────────────────────────────────────────────┐
  │         자원 할당 그래프(RAG)에서 대기 그래프(WFG)로의 압축 변환                 │
  ├──────────────────────────────────────────────────────────────────────────────────┤
  │                                                                                  │
  │   [ 1. 기존 RAG (복잡함) ]                                                       │
  │   P1 ─(요청)─▶ [자원 A] ◀─(할당)─ P2 ─(요청)─▶ [자원 B] ◀─(할당)─ P1             │
  │                                                                                  │
  │   [ 2. 변환된 WFG (핵심만 남김) ]                                                │
  │   - "어차피 A는 P2가 쥐고 있으니, P1이 A를 원한다는 건 P1이 P2를 기다린다는 뜻!" │
  │                                                                                  │
  │   P1 ──────────▶ P2 ──────────▶ P1 (사이클 확정!)                                │
  │     (P2가 끝날때까지 대기)  (P1이 끝날때까지 대기)                               │
  │                                                                                  │
  │   ✅ 결론: 노드 2개짜리 초간단 DFS/BFS 탐색 알고리즘으로 0.1ms 만에              │
  │           데드락을 찾아낼 수 있다. DB 엔진의 최고 무기다.                        │
  └──────────────────────────────────────────────────────────────────────────────────┘

탐지 알고리즘 2: 다중 인스턴스 자원 환경 (탐지 은행원 알고리즘)

자원이 여러 개(메모리 블록 여러 개, 스레드 풀 등)일 때는 은행원 알고리즘과 비슷하게 행렬을 쓴다. (하지만 미래 예측 행렬인 Max가 필요 없다는 게 핵심 차이다).

Available (현재 남은 자원), Allocation (현재 쥐고 있는 자원), Request (지금 당장 줘! 라고 외치는 자원) 세 가지 행렬만 쓴다.
스케줄러는 남은 자원(Available)으로 Request를 충족시켜 줄 수 있는 만만한 놈(프로세스)을 하나 찾는다.
그놈이 살아서 자기를 끝내면 Allocation에 있던 자원을 다 뱉어서 Available에 더해준다.
이 짓을 반복해서 모든 프로세스가 다 탈출하면 "현재 데드락 아님", 중간에 아무도 못 살리고 멈춰버리면 남은 놈들이 전부 **"데드락에 걸려있음"**으로 판정한다.

📢 섹션 요약 비유: 탐지 알고리즘은 "지금 내 지갑에 있는 돈(Available)으로, 지금 당장 돈 내놓으라고 멱살 잡는 놈(Request)들 중 하나라도 입을 막을 수 있나?"를 검사하는 현실적 빚쟁이 롤플레잉입니다. 미래(Max) 따위는 알 필요 없이, 당장 눈앞의 위기만 시뮬레이션합니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

탐지 주기의 딜레마 (언제 검사할 것인가?)

탐지 알고리즘을 짰다고 해도 "이걸 도대체 얼마나 자주 실행해야 하는가?"라는 딜레마에 부딪힌다. 이 주기가 시스템 성능을 결정한다.

탐지 주기 방식	장점 (안전성)	단점 (오버헤드)
자원 요청 시마다 (매번)	데드락이 터지는 그 1나노초의 찰나에 즉시 찾아내서 피해를 최소화함	1초에 1만 번씩 탐지 알고리즘이 돌아 시스템 CPU 100% 폭파 (현실성 없음)
타이머 기반 (예: 1초마다)	CPU 낭비가 적어 실무에서 가장 흔히 쓰임	1초 동안 꼬인 스레드들이 아무것도 못 하고 1초를 낭비함
CPU 이용률 저하 시	평소엔 안 하다가 CPU가 갑자기 10% 밑으로 떨어질 때(다들 자원 기다리느라 멈췄을 때) 기습적으로 탐지함	가장 합리적인 휴리스틱. 오버헤드 최저.

데드락 탐지(Detection)와 회피(Avoidance)의 본질적 차이

**회피(은행원 알고리즘)**는 Max (미래에 땡깡부릴 최대치)를 미리 알아야 한다. 현실 세계에선 불가능하다.
**탐지(Detection 알고리즘)**는 Request (지금 당장 달라고 아우성치는 양)만 보면 된다. 100% 팩트(Fact) 데이터만 쓰므로 현실 세계(데이터베이스)에서 완벽히 돌아간다.
📢 섹션 요약 비유: 감시 카메라(탐지)를 1초마다 쳐다보고 있으면(매번 탐지) 범죄는 막지만 경비원이 과로사합니다. 그래서 평소엔 냅두다가 센서에 침입 알람이 울리거나 밤 12시가 될 때만 한 번씩 카메라를 돌려보는 것(이용률 저하 시 탐지)이 인건비(CPU 오버헤드)를 아끼는 최적의 경비 시스템입니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

RDBMS(Oracle, InnoDB)의 백그라운드 탐지 데몬 (Deadlock Detector): 데드락 탐지 알고리즘이 현대 컴퓨터 공학에서 유일하게, 그리고 완벽하게 숨 쉬는 곳이 바로 관계형 데이터베이스 엔진 내부다.
- 아키텍처 동작: InnoDB 스토리지 엔진은 내부에 락(Lock) 매니저를 두고 있다. 트랜잭션 A가 B의 행(Row) 락을 기다리게 되면 Wait-For Graph에 엣지를 하나 긋는다.
- 실무 판단: 이 WFG를 그리는 순간, 엔진은 DFS(깊이 우선 탐색)를 백그라운드 스레드에서 초고속으로 돌려 사이클을 찾는다. 만약 A가 B를 기다리는데 B도 A를 기다리는 사이클이 터지면, 1초를 낭비하지 않고 즉시 B(수정한 데이터가 더 적은 놈)를 찾아내 Deadlock found when trying to get lock; try restarting transaction 에러를 뱉으며 트랜잭션을 킬(Kill)하고 강제 롤백시킨다.
분산 시스템(MSA)에서의 분산 탐지(Distributed Detection) 포기: 단일 DB에서는 그래프를 그리기 쉽다. 하지만 마이크로서비스 100개가 얽힌 분산 환경(Kafka, Redis)에서는 이 그래프의 꼭짓점들이 전 세계 서버에 흩어져 있다.
- 절망: A서버의 노드 정보와 B서버의 노드 정보를 합쳐서 글로벌 사이클(Global Cycle)을 찾는 것은 네트워크 지연과 상태 불일치(Inconsistency) 때문에 불가능하다.
- 아키텍트 결단: 분산 아키텍트들은 분산 데드락 탐지를 완전히 포기했다. 대신 그냥 "3초 동안 응답 없으면 타임아웃(Timeout)!"이라는 무식한 룰을 모든 API와 락 획득에 걸어버려, 탐지 알고리즘 없이도 데드락 고리를 부숴버리는 실용주의적 결단을 내렸다.

  ┌─────────────────────────────────────────────────────────────────────────┐
  │     교착 상태 탐지 후 '복구(Recovery)' 시나리오 아키텍처 트리           │
  ├─────────────────────────────────────────────────────────────────────────┤
  │                                                                         │
  │   [시스템이 데드락 사이클(A ─▶ B ─▶ C ─▶ A)을 탐지함!]                  │
  │                │                                                        │
  │                ▼ 희생자(Victim) 선정 및 처형 방식 결정                  │
  │   [ 1. 일망타진 (무식한 복구) ]                                         │
  │     ▶ 방법: A, B, C를 그냥 싹 다 Kill 해버림.                           │
  │     ▶ 결과: 데드락은 한 방에 풀리지만 데이터 3명분 다 날아감 (피해 막심)│
  │                                                                         │
  │   [ 2. 외과 수술 (스마트한 복구) ]                                      │
  │     ▶ 방법: C가 제일 만만하네(Undo 로그가 젤 적음). C만 Kill 하자!      │
  │     ▶ 결과: C가 죽으면서 자원을 뱉어 A와 B는 락을 잡고 무사히 생존함.   │
  │                                                                         │
  │   [ 3. 롤백 (Time Machine) ]                                            │
  │     ▶ 방법: C를 죽이지 않고, C의 상태를 5초 전으로 타임머신 태움.       │
  │     ▶ 결과: 꼬였던 락만 스르륵 풀리고 C도 나중에 다시 재시작 가능.      │
  │            (가장 우아하지만, DB처럼 체크포인트 기능이 있어야만 가능)    │
  └─────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 탐지(Detection)는 절반의 완성일 뿐이다. 데드락을 찾았으면 누군가는 피를 흘려야(Kill or Rollback) 사이클이 깨진다. 운영체제가 범용 프로세스(C 프로그램)의 배를 갈라 죽이면 데이터가 오염되기 때문에 OS는 탐지 알고리즘 자체를 탑재하지 않는다. 오직 완벽한 롤백(Undo) 생태계를 갖춘 데이터베이스만이 탐지 알고리즘을 떳떳하게 쓸 자격을 갖는다.

📢 섹션 요약 비유: 암세포(데드락)를 탐지하는 MRI(탐지 알고리즘) 기계를 샀습니다. 암을 발견했는데 병원에 메스(롤백 기능)가 없으면 환자를 통째로 죽여야(강제 종료) 합니다. 완벽한 수술 장비(Undo Log)가 갖춰진 종합 병원(Database)만이 MRI 장비를 들여놓을 자격이 있습니다. 일반 동네 의원(운영체제)은 그냥 진통제(타이머)만 주는 게 맞습니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

대기 그래프(WFG) 기반의 데드락 탐지 엔진을 데이터베이스나 트랜잭션 관리자에 내장하면, 수만 명의 유저가 동시에 쿼리를 때리며 우연히 자원이 꼬이는 찰나의 순간을 백그라운드에서 조용히 스나이핑(Kill & Retry)하여 전체 시스템의 무중단 스루풋(Zero-Downtime Throughput)을 극한으로 유지할 수 있다.

결론 및 미래 전망

교착 상태 탐지 알고리즘은 1970년대 OS 스케줄러를 위해 고안되었으나, 그 무거운 체급과 희생자 롤백의 한계 때문에 결국 '데이터베이스 엔진'의 전유물로 이주하여 진화의 꽃을 피웠다. 현대 클라우드 마이크로서비스 환경에서는 분산 데드락 탐지의 수학적 한계를 인정하고, 타임아웃(Timeout)과 분산 트레이싱(Distributed Tracing, 예: Jaeger/Zipkin) 툴을 결합하여, 실시간 차단보다는 사후 로그 분석을 통해 "어떤 서비스 간의 의존성이 꼬였는가"를 사후에 리팩토링하는 옵저버빌리티(Observability) 영역으로 그 철학이 승계되고 있다.

📢 섹션 요약 비유: 옛날엔 도둑(데드락)을 잡으려고 집마다 레이저 함정(탐지 알고리즘)을 깔았습니다(비용 폭발). 지금은 그냥 털리게 놔두고, 곳곳에 숨겨둔 CCTV(분산 트레이싱)를 돌려본 뒤 내일 도둑을 잡아 감옥에 넣고 집 구조를 뜯어고치는(리팩토링) 방식이 클라우드 대저택을 관리하는 현실적인 해답입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
순환 대기 (Circular Wait)	탐지 알고리즘(DFS/BFS)이 그래프를 미친 듯이 파고들며 찾아내고자 하는 닫힌 원(Cycle) 형태의 최종 목표물이다.
자원 할당 그래프 (RAG)	교착 상태를 인간과 컴퓨터가 동시에 이해할 수 있게 시각화해 주는 방향성 그래프 자료구조다.
대기 그래프 (Wait-For Graph)	RAG에서 자원(네모)을 지워버리고, "A스레드가 B스레드를 기다린다"로 극압축 시켜 DB 탐지 엔진에 탑재된 초경량 그래프다.
교착 상태 회피 (Avoidance)	탐지(Detection)의 형제로, 탐지가 터진 후에 찾는 거라면 회피는 터지기 전에 엑셀을 돌려보는 사전 검사다.
롤백 (Rollback)	데드락을 탐지한 후 희생자(Victim)를 쏴 죽였을 때, 그놈이 어질러놓은 데이터를 원래대로 되돌리는 복구(Recovery)의 핵심 기술이다.

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

운영체제 선생님이 아이들이 장난감 때문에 싸우지 않게 미리 규칙을 정해주면 너무 피곤하고 깐깐해져서 애들이 놀지를 못해요.
그래서 선생님은 **"일단 맘대로 갖고 놀아!"**라고 풀어주고, 대신 1시간에 한 번씩 교실을 쓱 둘러보며 아이들이 서로 멱살을 잡고 동그랗게 멈춰있는지(데드락) 감시(탐지)해요.
만약 꽉 막혀서 아무도 못 노는 걸 발견하면, 제일 만만한 한 명의 손을 강제로 풀게 해서(복구) 꼬인 실타래를 다시 술술 풀리게 만들어주는 똑똑한 시스템이랍니다!