index.md (2759B)
1 +++ 2 title = 'Deadlocks' 3 +++ 4 # Deadlocks 5 6 A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. 7 8 Starvation: nobody gets resources? 9 Livelock: many instructions executed but no progress 10 11 Conditions: 12 13 - Mutual exclusion: each resource is assigned to at most one process 14 - Hold & wait: processes can request resource when holding another one 15 - No preemption: resources are not preemptable, i.e. can’t be taken away from a process 16 - Circular wait: chain of at least two processes must be waiting for a resource held by next process in the chain 17 18  19 20 Handling: 21 22 - ignore the problem — no action taken 23 - deadlock detection — detect and perform recovery 24 - deadlock prevention — prevent any of deadlock conditions 25 - deadlock avoidance — allocate resources to avoid deadlocks 26 27 ## Ignore the problem 28 become an ostrich and imagine the problem doesn’t exist. 29 30 assumes deadlocks are rare, the cost of handling them is high, and their effects are ok. 31 32 in practice, only last resort. 33 34 ## Deadlock detection 35 can be used when simple & efficient detection mechanisms are available. 36 37 detection 38 39 - check for cycles in the resource allocation graph 40 - track progress, time out if necessary 41 - detect explicitly if e.g. OOM 42 43 recovery 44 45 - force preemption 46 - checkpoint-rollback 47 - kill the offending processes 48 49 in practice, solution of choice when adequate detection/recovery mechanisms are available 50 51 ## Deadlock prevention 52 mutual exclusion: 53 54 - spool everything 55 - but this usually shifts problem somewhere else 56 57 hold & wait 58 59 - request all resources initially 60 - but this has poor parallelism and resource utilisation 61 62 no preemption: 63 64 - take resources away 65 - but not applicable in a lot of cases 66 67 circular wait: 68 69 - order resources numerically 70 - but it’s hard to consistently enforce in practice 71 72 in practice, adopted in particular domains (e.g. two-phase locking in transaction processing systems) 73 74 ## Deadlock avoidance 75 single resource: Banker’s algorithm (Dijkstra) 76 77 - customers (processes) request credits (resources) 78 - banker (OS) only satisfies requests resulting in safe states 79 - a state is safe if there exists a sequence of other states that allows all customers to complete 80 - max credit demands are known in advance 81 82 multiple resources: 83 84 - generalised safe state detection: 85 86  87 88 - select row R whose unmet resource needs N are all <= A 89 - mark R as terminated and add its resources to A vector 90 - repeat until completion (safe) or deadlock (unsafe) 91 92 in practice, rarely an option (hard to determine resource needs in advance)