교착 상태 (Deadlocks)

1. 교착 상태 특성

(1) 필요조건

(i) 상호 배제 (mutual exclusion)

• 최소한 하나의 자원이 비공유 모드로 점유되어야 한다.
• 비공유 모드에서는 한 번에 한 스레드만이 그 자원을 사용할 수 있다.
  • mutex lock, semaphore 사용 시 비공유 모드

(ii) 점유하며 대기 (hold-and-wait)

• 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.
• Example)
  • A thread : mutex 1 점유, mutex 2 대기
  • B thread : mutex 1 대기, mutex 2 점유

(iii) 비선점 (no preemption)

• 자원들을 선점할 수 없어야 한다.
• 자원이 강제적으로 방출될 수 없고, 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 자발적으로만 방출될 수 있다.

(iv) 순환 대기 (circular wait)

• 대기하고 있는 스레드의 집합 {T0, T1, T2, ..., Tn}에서 T0는 T1이 점유한 자원을 대기하고, T1은 T2가 점유한 자원을 대기하고,..., Tn-1은 Tn이 점유한 자원을 대기하며, Tn은 T0가 점유한 자원을 대기한다.
• 자원 할당 그래프에서 사이클이 있어야 한다.

 

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

• 요청 간선 (Request edge)
• 할당 간선 (assignment edge)
• Resource Type with instances

(i) Example1

• P = {P1, P2, P3}
• R = {R1, R2, R3, R4}
  • R2 resource type은 2개의 instances를 가지고 있다.
• E = {P1->R1, P2->R3, R1->P2, R2->P2, R2->P1, R3->P3}
• 순환 대기 없음 -> 사이클이 없다.
• 교착상태 X

(ii) Example2

• 사이클이 존재한다는 것은 Deadlock 발생 가능성이 존재한다는 것이다.

• 왼쪽 그래프
  • Cycle O, Deadlock O
• 오른쪽 그래프
  • Cycle O, Deadlock X
  • P3가 R2를 P1에게 받지 않아도 된다. (P4 종료 후 R2를 얻을 수 있다.)