1) 교착 상태 발생 필요 조건

1. 상호 배제 : 한 번에 한 스레드만이 그 자원을 사용할 수 있다
2. 점유하며 대기 : 최소한 하나의 자원을 점유한 채, 자원을 추가로 필요로 하는 것을 대기해야한다.
3. 비선점 : 사용되는 자원을 중간에 강제로 방출하는 것이 불가능하다.
4. 순환 대기 : 스레드들간 자원을 순환적으로 할당받길 대기한다.

⇒ 위 네 가지 조건을 모두 만족해야 교착 상태가 가능하다.

2) 자원 할당 그래프

• 교착 상태를 자세하게 기술할 수 있는 그래프이다.
• 기본 용어
  • 모든 활성 스레드 집합 : $T$ $= {T_1,T_2….T_i}$
  • 모든 자원 유형 집합 : $R = {R_1, R_2……R_i}$
  • 요청 간선 - 자원을 요청하는 간선 $E$ : $T_i → R_i$
  • 할당 간선 - 자원을 할당하는 간선 $E$ : $R_i → T_i$

• 자원 할당 그래프 예시
  • 집합 T,R 그리고 E
    • $T = {T_1,T_2,T_3}$
    • $R = R_1,R_2,R_3,R_4$
    • $E = T_1 → R_1 ….$
  • 자원의 인스턴스
    • $R_1,R_3$ : 1개
    • $R_2$ : 2 개
    • $R_3$ : 3개
  • 스레드 상태
    • 스레드 $T_1$은 $R_2$의 자원을 할당받아 $R_1$에 자원을 요청 중이다……
• 그래프가 사이클을 포함하지 않으면 교착 상태가 아니지만, 만약 사이클을 포함 한다면 교착 상태일 수 있다!
• 하나의 인스턴스만 갖는 경우 교착상태가 되기 필요 충분 조건이다.
• 두 개 이상의 인스턴스를 갖는 경우 교착 상태가 존재하는 필요 조건이다.

⇒ 자원 할당 그래프에 사이클이 없다면, 시스템은 교착 상태가 아니다

⇒ 자원 할당 그래프에 사이클이 있다면, 시스템은 교착 상태일 수도 아닐수도 있다.