자원 할당 그래프 (Resource-Allocation Graph)

핵심 개념

자원 할당 그래프는 스레드와 자원 간의 요청/할당 관계를 시각화한 방향 그래프입니다. 그래프의 사이클 존재 여부로 교착 상태 가능성을 체계적으로 분석할 수 있습니다.

동작 원리

정점 집합 V = T(스레드 집합) ∪ R(자원 타입 집합)으로 구성됩니다.

• 요청 간선 (Request Edge): Ti → Rj = 스레드 Ti가 자원 Rj를 요청 중
• 할당 간선 (Assignment Edge): Rj → Ti = 자원 Rj의 인스턴스가 Ti에 할당됨
• 표기: 스레드는 원(○), 자원 타입은 사각형(□), 인스턴스는 사각형 내 점(•)

사이클과 교착 상태 관계

자원 인스턴스	사이클 존재 시
각 타입당 1개	사이클 = 교착 상태 (필요충분조건)
각 타입당 여러 개	사이클 = 교착 상태 가능 (필요조건)

사이클이 없으면 교착 상태 없음. 사이클이 있어도 인스턴스가 여럿이면 교착 아닐 수 있습니다.

예시

  R1        R2
  [•]      [•]
   ↑   ↘    ↑
   │    ↘   │
  T1 ←────  T2

T1: R2 보유, R1 요청
T2: R1 보유, R2 요청
→ 사이클 존재 → 각 자원 1개씩이므로 교착 상태

사이클이 있지만 교착이 아닌 경우:

T1 → R1 → T3 → R2 → T1 (사이클)
그러나 T4가 R2를 해제하면 T3가 진행 → 사이클 해소

관련 개념

• [[교착 상태 필요조건 (Necessary Conditions)]]
• [[은행원 알고리즘 (Banker’s Algorithm)]]