대기 그래프 (Wait-for Graph)

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

본질: 대기 그래프(Wait-for Graph)는 교착 상태를 시각화한 원본 '자원 할당 그래프(RAG)'에서 '자원 정점(네모 상자)'을 모두 지워버리고, 오직 "어떤 프로세스가 어떤 프로세스의 완료를 멱살 쥐듯 기다리고 있는가"라는 사람(프로세스) 간의 직접적인 원한 관계(의존성)만 남긴 초경량 압축 위상 지도다.

가치: 불필요한 자원 노드를 삭제하여 탐색 크기를 절반 이하로 줄였기 때문에, 운영체제나 데이터베이스의 탐지 알고리즘이 $O(V+E)$의 쾌속 깊이 우선 탐색(DFS)을 이용해 '죽음의 사이클(원형 고리)' 존재 여부를 훨씬 빠르고 가볍게 스캔해 낼 수 있게 해준다.

융합: 단, 이 가벼운 마법은 오직 "자원이 1개씩(단일 인스턴스)만 존재하는 환경"에서만 성립하며, 다중 인스턴스 환경에서는 누가 누구를 간접적으로 기다리는지 화살표가 왜곡되므로 다중 환경에서는 은행원 변형 스캔(행렬 탐지)으로 융합 및 치환되어 사용된다.

Ⅰ. 개요 및 필요성

자원 할당 그래프(RAG)를 보면, P1 → 프린터(R1), 프린터(R1) → P2 처럼 사람이 사물을 요구하거나 사물이 사람에게 귀속된 복잡한 그림이 그려진다.

하지만 데드락 감시 데몬 입장에선 "프린터 건, 스캐너 건 나발이건 알 바 아니고, 결국 P1이 P2가 나가주길 기다리고 있는 거잖아?" 라는 핵심만 있으면 된다. 따라서 중간에 낀 '사물(자원)' 노드를 생략하고, P1 → P2 라는 다이렉트 화살표로 그림을 단축시켜 버린다. 이것이 바로 **대기 그래프(Wait-for Graph, WFG)**다.

💡 비유: 복잡한 사각관계 막장 드라마 인물 관계도. "철수가 영희의 집문서(자원)를 원하고, 그 집문서는 민수 명의(할당)로 되어 있다"는 긴 문장(RAG)을, 변호사가 쓱 보고 "그냥 철수가 민수(결재권자)를 기다린다(Wait-for)"는 단 한 줄로 칠판에 요약(WFG)해 버리는 것.

┌────────────────────────────────────────────────────────────────┐
│         RAG (자원 할당) → WFG (대기 그래프)의 압축 과정        │
├────────────────────────────────────────────────────────────────┤
│                                                                │
│  [거추장스러운 RAG 도면]                                       │
│  (P1) ───요청───▶ [자원A] ───할당───▶ (P2)                     │
│  (P2) ───요청───▶ [자원B] ───할당───▶ (P3)                     │
│  (P3) ───요청───▶ [자원C] ───할당───▶ (P1)                     │
│                                                                │
│  [▼ 자원 A, B, C 정점(Node) 삭제 및 간선 축약 (WFG)]           │
│  (P1) ───기다림(Wait-for)───▶ (P2)                             │
│   ▲                              │                             │
│   │                              ▼                             │
│   └───────◀ (P3) ◀──────────────┘                              │
│                                                                │
│  ▶ 결과: P1, P2, P3 3명의 노드로만 이루어진 완벽한 삼각형      │
│           (사이클)이 한눈에 파악됨! → [데드락 탐지 발동!]      │
└────────────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 대기 그래프는 중간 마진(자원)을 쏙 빼고, 순수하게 빚진 자와 빚쟁이(프로세스 간)의 목줄 관계만 남겨 탐정(OS)이 한눈에 연속 살인 고리를 파악하게 돕는 압축 지도입니다.

Ⅱ. 아키텍처 및 핵심 원리

DFS 베이스의 Cycle Detection (사이클 탐지)

WFG의 최대 장점은 컴퓨터 과학의 가장 기본이자 극도로 최적화된 자료구조 탐색 트리 알고리즘인 깊이 우선 탐색(DFS)을 그대로 들이부어 쓸 수 있다는 점이다.

그래프 축소 변환: 운영체제는 0.1밀리초 만에 메모리 내 PCB와 Resource Table 락 큐를 순회하며(자원 매핑 축소), 간선 배열 구조체 WFG를 동적으로 메모리에 조립한다.
DFS 스윕 (Sweep): 임의의 노드(프로세스)를 잡고 화살표를 따라 미로를 그린다. (방문한 곳은 visited=true 마킹).
데드락 확정 선고: 만약 내가 화살표를 타고 가다가 이미 visited=true 마킹된 내 등을 다시 찍게 된다면(Back-edge 발견), 이는 부정할 수 없는 닫힌 원(Cycle)이다. 이 순간 즉시 탐지 데몬은 알람을 울리고(Deadlock!), 사이클을 짠 놈들 리스트를 복구 모듈에 넘긴다.

📢 섹션 요약 비유: WFG 축약 지도의 엄청난 파워 덕에, 1만 명의 얽힌 실타래 속에서 누가 원을 그리며 묶여있는지, 눈 감고 손가락만 따라가도(DFS) 순식간에 원형 매듭을 백발백중으로 찾아낼 수 있습니다.

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

비교 대상	자원 할당 그래프 (RAG)	대기 그래프 (Wait-for Graph)
노드(Node)의 종류	프로세스(동그라미) + 자원(네모) [2종]	오직 프로세스(동그라미) [1종]
그래프의 크기	아주 크고 복잡함 (수만 개 메모리 맵)	절반 이하로 다이어트됨 (탐색 속도 2배)
활용 목적	데드락 회피(Avoidance) (예약 간선 활용)	데드락 탐지(Detection) 전용 (사후 스캔용)
다중 자원 적용	적용 불가 (그려도 판별 불가)	아예 사용 불가 (그리면 오류남)

📢 섹션 요약 비유: WFG는 오직 '데드락 사후 색출' 이라는 단일 목적을 위해 RAG의 뼈를 깎아 가볍게 만든 경주용 자동차입니다.

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

실무 시나리오:

RDBMS (PostgreSQL, MySQL 등)의 Lock Manager: 데이터베이스 내부에서 레코드 단위 Row-Lock이 수십만 개씩 터진다. 트랜잭션 하나가 다른 트랜잭션을 수초째 기다릴 때마다 DBMS 백그라운드 스레드는 WFG 해시테이블을 슥 순회한다. $Transaction A \rightarrow Transaction B$ 로 축약된 사이클이 포착되면, "Deadlock Found when trying to get lock" 에러를 뿜으며 Victim을 킬(Kill)한다. 오직 단일 락(Single-instance Lock) 환경인 DB 레코드 제어에서 가장 빛을 발하는 핵심 탐지 무기다.
분산 환경의 분산 대기 그래프 (Distributed WFG): 노드가 여러 대인 블록체인이나 카산드라 같은 분산 원장 DB에서는, WFG 그래프 파편을 들고서 "내 노드엔 A가 B를 기다리는데, 저쪽 노드엔 B가 A를 기다리면?" 엣지 체인을 이어붙여 거대한 글로벌 사이클(Global WFG Cycle)을 탐지해 내는 알고리즘(Chandy-Misra-Haas 등)으로 진화하여 쓰인다.

안티패턴:

다중 자원에 WFG 적용하는 멍청함: 자원이 USB 5개라고 치자. P1이 USB 1개를 점유했고, P2가 "USB 1개 더 줘!" 대기 중이다. 이때 WFG를 어거지로 그려버리면 $P2 \rightarrow P1$ 화살표가 그려져 'P1이 나가야 P2가 산다'고 왜곡된다. 실제론 옆에 남은 4개의 USB를 주면 그만인데 말이다! "WFG는 자원이 단일 1개인 환경이 아니면 절대 그리면 안 되는 독약이다."

📢 섹션 요약 비유: 자원이 여러 개일 때는 굳이 줄 앞에 있는 사람이 안 비켜줘도 옆 계산대 가면 되니까, "누가 누구를 기다린다(WFG)"는 선 자체가 거짓말이 됩니다. WFG는 오직 "계산대가 1개뿐인 외나무다리 병목"에서만 유효한 탐지 지도입니다.

Ⅴ. 기대효과 및 결론

기준	RAG 탐색 시 (원본)	WFG 탐색 전환 시 (압축)
탐색 속도	$O(N+M)$ (무거움)	$O(N)$ 전격 경량화 달성
구조체 복잡도	메모리에 자원/프로세스 구분을 둬야 함	오직 포인터 체인 하나로 해결 (초경량)
교착 증명력	단일 환경에선 어차피 결과가 100% 똑같음

대기 그래프 (Wait-for Graph)는 실시간 운영체제 커널의 탐지 데몬이 자원 검사 부하를 한계점까지 다이어트시키기 위한 컴퓨터 공학의 극강의 추상화(Abstraction) 성과다. 중간에 낀 본질이 아닌 매개체(자원)를 수학적으로 배제함으로써, DFS 그래프 탐색이라는 가장 빠르고 기초적인 컴퓨터 알고리즘만으로 거대한 악당(Deadlock)의 아지트를 손쉽게 급습하는 훌륭한 길잡이로 평가받는다.

📌 관련 개념 맵

개념	관계
자원 할당 그래프 (RAG)	WFG의 어머니. 여기에서 중간 '자원 상자'를 도려내면 WFG가 됨
DFS (Depth First Search)	이 가벼운 WFG 지도 위에서 누가 빙그르르 도는 쳇바퀴에 갇혔나 쫓아다니는 추적견
교착 상태 탐지 (Detection)	WFG가 그려지는 유일한 목적지 (주기적으로 그래프 그려서 쳇바퀴 잡기)
분산 교착 상태 탐지	WFG 지도를 여러 서버가 반쪽씩 나눠 가졌을 때, 서로 통신하며 큰 WFG 사이클을 조립해 내는 거대 탐지망

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

"자원 할당 그래프"는 민수가 딱지 1개를 가졌고 철수가 그걸 뺏으려 기다린다고 물건 그림까지 다 그려놓은 너무너무 복잡한 지도예요.
하지만 "대기 그래프(WFG)"는 쿨하게 딱지 그림은 확 지워버리고, "그냥 철수가 민수를 노려보고 멱살 잡고 있음!" 하고 화살표 딱 하나로만 줄여서 그린 요약 만화랍니다.
물건 그림을 다 뺐더니, 애들끼리 멱살 잡고 둥글게 동그라미(데드락)로 싸우고 있는 모습이 1초 만에 눈에 확 띄어서 선생님(OS)이 잡기 편해진 거죠!