[운영체제] Chapter 8. Deadlocks

경희대학교 허선영 교수님의 운영체제 수업을 기반으로 정리한 글입니다.

 

Chapter Objectives

• mutex lock를 사용하는 환경에서 deadlock이 어떻게 발생하는지 설명
• deadlock을 특정짓는 4가지 필요조건을 정의
• resource allocation graph에서 deadlock 상황을 인지
• deadlock을 방지하는 4가지 접근법을 평가
• deadlock을 방지하는 banker's algorithm을 적용
• deadlock detection algorithm을 적용
• deadlock을 복구하는 접근법을 평가

 

Deadlock

multiprogramming 환경에서, multiple threads는 한정된 자원을 두고 경쟁한다. thread가 자원을 요청하고 사용 가능한 자원이 없다면, thread는 waiting state로 전환된다. 때때로, waiting state는 영원히 state가 변하지 않는 경우가 있다. 이런 경우를 Deadlock이라 부른다.

 

• S & Q -> 1로 초기화된 semaphores

 

 

 

• 2 Dining Philosophers

while (true) {
    wait(chopstick[i]);
    wait(chopstick[(i + 1) % 2]);
    
    /* eat for awhile */
    
    signal(chopstick[i]);
    signal(chopstick[(i + 1) % 2]);
    
    /* think for awhile */
}

 

• Operating systems -> 보통 deadlock prevention facilities 제공 X
• deadlock-free program 설계는 programmers의 책임

 

System Model

• System -> resources로 구성
• Resources types R1, R2, .. . . . . . . .  Rm -> m개의 resource types
  • CPU cycles, files, I/O devices, ..
• each R_i -> has W_i instances
• each process가 활용하는 resource
  • request: threaed가 resource를 요청, 즉시 승인되지 못하면 requesting thread는 resource가 사용 가능할 때까지 waiting
  • use: thread가 resource 위에서 작동
  • release: threaed가 resource를 release

 

Deadlock Characterization

1. Necessary Conditions

• 4가지 조건을 동시에 만족하는 경우에 deadlock 발생

1) Mutual exclutsion

• only one threaed at a time can use a resource

2) Hold and wait

• 하나의 thread -> 적어도 하나의 resource 차지하고 있어야 함
• 동시에, 현재 other threaeds에 의해 차지된 additional resources를 기다리는 waiting 상태여야 함

3) No preemption

• resources cannot be preempted
• resource를 소유한 thread에 의해 자발적으로 released

4) Circular wait

• set {T0, T1, .. . . . . . . .  Tn} of waiting threads 

2. Resource-Allocation Graph

• system resource-allocation graph
• A set of vertices V and set of edges E
• V -> 2가지 타입으로 나뉨
  • T = {T1, T2, ..., Tn}, system의 모든 threads
  • R = {R1, R2, ..., Rm}, system의 모든 resource type
• E -> 2가지 타입으로 나뉨
  • Request edge: Ti -> Rj (Ti가 Rj를 요청)
  • Assignment edge: Rj -> Ti (Rj가 Ti에 할당됨 -> Ti is using Rj)
• if graph contains no cycles -> no deadlock
• if graph contains a cycle -> 
  • resource type 하나 당 오직 하나의 instance -> deadlock
  • resource type 하나 당 여러 개의 instances -> deadlock의 가능성

- Resource Allocation Graph Example

• Resources -> Rectangles
  
  • R1, R2, R3, and R4
• Instances -> Dots in a rectangle
  • One instance of R1
  • Two instances of R2
  • One instances of R3
  • Three instances of R4
• Threads -> Circles
  • T1 holds one instance of R2, is waiting for an instance of R1
  • T2 holds one instace of R1, one instance of R2, and is waiting for an instance of R3
  • T3 is holds one instance of R3

3. Methods for Handling Deadlocks

1) system이 절대 deadlock sate에 진입하지 않도록 보장

• Deadlock prevention
• Deadlock avoidance

2) system이 deadlock state에 진입하는 것을 허용 -> recover

3) problem을 무시 & system 내부에서 deadlocks이 발생하지 않는 척

 

Deadlock Prevention

• deadlock 발생 4가지 필요조건을 무효화

1. Mutual exclusion

• sharable resources(ex read-only files) -> mutual exclusion 없이 한 번에 접근 가능
• but, non-sharable resources에서 필수적임

2. Hold and wait

• thread behavior에 제약 -> low resource utilization, starvation

3. No preemption

• 상태 저장 및 복구가 용이한 CPU registers나 database transaction 작업에 적용
• mutex locks and semaphores -> 적용 X

 

Thus, Invalidating the circular wait condition is most common!!

 

4. Circular wait

• 각 resource -> unique number 할당
• Resources 차례대로 요구: R_j는 F(R_j) > F(R_i)일 때 요청받을 수 있음
• F(): resource number
• Example
  • F(first_mutex) = 1
  • F(second_mutex) = 5

void * do_work_one(void * param) {
    pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
    /**
     * Do some work
     */
    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    
    pthread_exit(0);
}

-> 순서를 지키면 circular wait 발생 X

 

Ti가 resource Ri를 waiting & Ri는 T_(i+1)에 의해 소유된 상태 
(Rn은 T0에 의해 소유된 상태)
F(Ri) < F(R_(i+1))이 지켜져야 한다면, F(R0) < F(R1) < ... < F(Rn) < F(R0) -> F(R0) < F(R0)는 불가능하기 때문에, circular wait은 발생하지 않음

 

Deadlock Avoidance

• Deadlock prevention algorithms -> request 방식을 제한하여 dead lock을 방지
  • but, 이런 방법은 기기활용도와 시스템 출력을 저하시킴
• resource 요청 방식에 addtional information을 추가하는 방식
  • 각 request가 가진 정보 -> 현재 사용 가능한 resources, 각 thread에 할당된 resources, 각 thread의 미래 requests & releases
• Simplest and most useful model: 각 thread는 필요한 각 type의 resources의 maximum nuber를 선언
  • the number of available and allocated resources
  • the maximum demands of the processes

1. Safe State

• thread가 available resource를 요청할 때, 시스템은 즉각적 할당이 시스템을 safe state에 남겨두는지 판단해야 함
  • system in safe state -> no deadlocks
  • system in unsafe state -> possibility of deadlock
• system에 safe sequence가 존재 -> safe state
  • <T1, T2, ..., Tn>: Ti가 사용할 수 있는 resources -> currently available resources + Tj에 할당된 resources(j < i)
• 앞의 thread가 release한 resource를 포함한 resources를 다음 thread가 제공받음 -> safe state!!

- Safe state example

• 3개의 Threads T0, T1, and T2
• 12개의 Resources(Three are free)

2. Deadlock Avoidance Algorithms

• Single instance of a resource type
  
  • Use a resource-allocation graph
• Multiple instances of a resource type
  • Use a Banker's Algorithm 

- Resource Allocation Graph Scheme

• Claim edge: Ti ---> Rj, Tj가 언젠가 Rj를 요청할 수 있다는 의미

• Edge Conversion
  
  • Claim to Request: thread가 resource를 요청할 때
  • Request to Assignment: thread에 resource가 할당될 때
  • Assignment to Claim: resource가 thread에 의해 release될 때
• resources는 시스템 내에서 사전에 요구되어야 함
• resource allocation graph 내에서 cycle이 생성되지 않는 경우에만 request가 허용됨

 

Deadlock Detection

• system이 deadlock prevention or deadlock avoidance를 제공하지 않는 경우, 다음을 제공해야 함 
  • Detection algorithm: deadlock이 발생하는지 확인
  • Recovery scheme: deadlock으로부터 회복

1. Single Instance of Each Resource Type

• 모든 resources가 오직 single instance만 가짐
• wait-for graph
  
  • Nodes are threads
  • Ti -> Tj: Ti가 Tj를 waiting
• graph가 cycle을 포함 -> deadlock
• n개의 정점(vertices), cycle을 detection하는 algorithm의 시간복잡도 -> O(N^2)

 

Recovery from Deadlock

1. Process and Thread Termination

• Abort all deadlocked threads
• Abort one process at a time until the deadlock cycle is eliminated -> which order should we choose to abort?
  • threaed의 우선순위
  • completion에 얼마나 오래 걸리는지
  • thread가 사용하는 resources
  • thread를 완수하기 위해 필요로 하는 resources
  • 얼마나 많은 threads가 종료되어야 하는지
  • interactive thread or batch thread

2. Resource Preemption

• Selecting a victim - minimize cost
• Rollback - return to some safe state, restart the thread for that state
• Starvation - same thread may always be picked as victim, include number of rollback in cost factor