17. 데드락의 이해: Chapter 8. Deadlocks (Part 1)

8.1 시스템 모델System Model

• 데드락
  • 대기 중인 스레드들이 그들이 요청한 자원들이 다른 스레드들에 의해서 점유되어 있고, 그들도 다 대기 상태에 있기 때문에 결코 다시는 그 상태를 변경할 수 없는 상황
• 시스템은 경쟁하는 스레드들 상이에 분배되어야 할 유한한 수의 자원들로 구성됨
• 이들 자원은 다수의 유형으로 분할되며 이들 각각은 동등한 다수의 인스턴스들로 구성됨
  • ex) CPU 주기, 파일, 입/출력 장치 등
• 만일 한 스레드가 어떤 자원 유형의 한 인스턴스를 요청하면, 동일 유형 자원의 임의의 인스턴스를 할당함으로써 요청이 충족됨
• 스레드는 자원을 사용하기 전에 반드시 요청해야 함
• 스레드는 자원을 사용한 후에는 반드시 방출해야 함
• 스레드는 지정된 테스크를 수행하기 위해 필요한 만큼의 자원을 요청할 수 있음
• 요청된 자원의 수는 시스템에서 사용 가능한 전체 자원의 수를 초과해서는 안됨
• 프로세스는 다음 순서로만 자원을 사용할 수 있음
  • 요청
  • 사용
  • 방춤

 

 

8.2 다중 스레드 응용에서의 교착 상태Deadlock in Multithreaded Applications

• 위 예제에서 thread_one은 (1)first_mutex, (2)second_mutex 순서로 뮤텍스 락을 획득하려고 함
• 동시에 thread_two는 (1)second_mutex, (2)first_mutex 순서로 뮤텍스 락을 획득하려고 함
• thread_one이 first_mutex를 획득하고 thread_two가 second_mutex를 획득하게 되면 데드락이 가능함
• 데드락이 가능하더라도 thread_two가 뮤텍스 락을 획득하려고 시도하기 전에 thread_one이 first_mutex와 second_mutex를 획득하고 방출한다면 데드락이 발생하지 않음

 

 

8.3 교착 상태 특성Deadlock Characterization

필요 조건들Necessary Conditions

• 데드락은 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있음
  1. 상호 배제mutual exclusion
     • 최소한 하나의 자원이 비공유 모드로 점유되어야 함
     • 비공유 모드에서는 한 번에 한 스레드만이 그 자원을 사용할 수 있음
  2. 점유하며 대기hold and wait
     • 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 함
  3. 비선점no preemption
     • 자원을 선점할 수 없어야 함
     • 즉 자원이 강제적으로 방출될 수없고, 점유하고 있는 스레드가 테스크를 종료한 후 그 스레드에 의해 자발적으로 방출될 수 있음
  4. 순환 대기circular wait
     1. 대기하고 있는 스레드들의 집합 {T0, T1, ... , Tn}에 T0는 T1이 점유한 자원을 대기하고, T1은 T2가 점유한 자원을 대기하고, ... , Tn-1은 Tn이 점유한 자원을 대기하며, Tn은 T0가 점유한 자원을 대기해야 함

 

 

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

• 데드락은 시스템 자원 할당 그래프라고 하는 방향 그래프로 더욱 정확하게 기술할 수 있음
• 이 그래프는 정점 V의 집합과 간선 E의 집합으로 구성됨
  • 정점 V의 집합은 두 가지로 구별됨
    • T = {T1, T2, ... , Tn}: 시스템 내의 모든 활성 스레드의 집합
    • R = {R1, R2, ... , Rn}: 시스템 내의 모든 자원 유형의 집합
• 요청 간선 Ti -> Rj
  • 스레드 Ti로부터 자원 유형 Rj로의 방향 간선은 Ti -> Rj로 표현되며 이것은 스레드 Ti가 자원 유형 Rj의 인스턴스를 하나 요청하는 것으로, 현재 이 자원을 기다리는 상태임
• 할당 간선 Rj -> Ti
  • 자원 유형 Rj로부터 스레드 Ti로의 방향 간선은 Rj -> Ti로 표현되며 이것은 자원 유형 Rj의 한 인스턴스가 스레드 Ti에 할당된 것을 의미함

• 예시 1
  • 위 그림은 8.2 프로그램에서의 교착 상황을 보여줌

• 예시 2
  
  • T = {T1, T2, T3}
  • R = {R1, R2, R3, R4}
    • R1의 인스턴스 1개
    • R2의 인스턴스 2개
    • R3의 인스턴스 1개
    • R4의 인스턴스 3개
  • E = {T1, -> R1, T2 -> R3, R1 -> T2, R2 -> T2, R2-> T1, R3 -> T3}
  • 위 그래프는 사이클을 포함하고 있지 않음
  • 만일 그래프가 사이클을 포함하고 있지 않으면 시스템 내에 어느 스레드도 교착 상태가 아니라는 것을 알 수 있음

• 예시 3
  • T = {T1, T2, T3}
  • R = {R1, R2, R3, R4}
    • R1의 인스턴스 1개
    • R2의 인스턴스 2개
    • R3의 인스턴스 1개
    • R4의 인스턴스 3개
  • E = {T1, -> R1, T2 -> R3, R1 -> T2, R2 -> T2, R2-> T1, R3 -> T3, T3 -> T2}
  • 위 그래프에는 두 개의 사이클이 존재
    • T1 -> R1 -> T2 -> R3 -> T3 -> T2 -> T1
    • T2 -> R3 -> T3 -> R2 -> T2
  • 스레드 T1, T2, T3는 교착 상태임

• 예시 3
  • T = {T1, T2, T3, T4}
  • R = {R1, R2}
    • R1의 인스턴스 2개
    • R2의 인스턴스 2개
  • E = {T1, -> R1, R2 -> T1, R1 -> T2, R1 -> T3, R2-> T4, T3 -> R2}
  • 위 그래프에는 한 개의 사이클이 존재
    • T1 -> R1 -> T3 -> R2 -> T1
  • 그러나 교착 상태가 없음
    • T4가 R2의 인스턴스를 방출할 수 있음
    • 이어 R2가 T3에 할당될 수 있고 그 경우 사이클이 없어짐
• 따라서 자원 할당 그래프에 사이클이 없다면 시스템은 교착 상태가 아님
• 반면에 자원 할당 그래프에 사이클이 있다면 교착 상태 일수도 있고 아닐 수도 있음