Deadlocks.html (4864B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.6 (457297)"/><meta name="altitude" content="-1.222272038459778"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-12-13 12:59:03 +0000"/><meta name="latitude" content="52.33297299596081"/><meta name="longitude" content="4.864358938126112"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-12-19 00:29:52 +0000"/><title>Deadlocks</title></head><body><div><span style="font-weight: bold;">Deadlocks</span></div><div>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.</div><div><br/></div><div>Starvation: nobody gets resources?</div><div>Livelock: many instructions executed but no progress</div><div><br/></div><div>Conditions:</div><ul><li><div>Mutual exclusion: each resource is assigned to at most one process</div></li><li><div>Hold & wait: processes can request resource when holding another one</div></li><li><div>No preemption: resources are not preemptable, i.e. can’t be taken away from a process</div></li><li><div>Circular wait: chain of at least two processes must be waiting for a resource held by next process in the chain</div></li></ul><div><br/></div><div><img src="Deadlocks.resources/screenshot_1.png" height="371" width="651"/><img src="Deadlocks.resources/screenshot_2.png" height="437" width="531"/><br/></div><div><br/></div><div>Handling:</div><ul><li><div>ignore the problem — no action taken</div></li><li><div>deadlock detection — detect and perform recovery</div></li><li><div>deadlock prevention — prevent any of deadlock conditions</div></li><li><div>deadlock avoidance — allocate resources to avoid deadlocks</div></li></ul><div><br/></div><div><span style="font-weight: bold;">Ignore the problem</span></div><div>become an ostrich and imagine the problem doesn’t exist.</div><div>assumes deadlocks are rare, the cost of handling them is high, and their effects are ok.</div><div>in practice, only last resort.</div><div><br/></div><div><span style="font-weight: bold;">Deadlock detection</span></div><div>can be used when simple & efficient detection mechanisms are available.</div><div><br/></div><div>detection</div><ul><li><div>check for cycles in the resource allocation graph</div></li><li><div>track progress, time out if necessary</div></li><li><div>detect explicitly if e.g. OOM</div></li></ul><div><br/></div><div>recovery</div><ul><li><div>force preemption</div></li><li><div>checkpoint-rollback</div></li><li><div>kill the offending processes</div></li></ul><div><br/></div><div>in practice, solution of choice when adequate detection/recovery mechanisms are available</div><div><br/></div><div><span style="font-weight: bold;">Deadlock prevention</span></div><div>mutual exclusion:</div><ul><li><div>spool everything</div></li><li><div>but this usually shifts problem somewhere else</div></li></ul><div>hold & wait</div><ul><li><div>request all resources initially</div></li><li><div>but this has poor parallelism and resource utilisation</div></li></ul><div>no preemption:</div><ul><li><div>take resources away</div></li><li><div>but not applicable in a lot of cases</div></li></ul><div>circular wait:</div><ul><li><div>order resources numerically</div></li><li><div>but it’s hard to consistently enforce in practice</div></li></ul><div><br/></div><div>in practice, adopted in particular domains (e.g. two-phase locking in transaction processing systems)</div><div><br/></div><div><span style="font-weight: bold;">Deadlock avoidance</span></div><div>single resource: Banker’s algorithm (Dijkstra)</div><ul><li><div>customers (processes) request credits (resources)</div></li><li><div>banker (OS) only satisfies requests resulting in safe states</div></li><li><div>a state is safe if there exists a sequence of other states that allows all customers to complete</div></li><li><div>max credit demands are known in advance</div></li></ul><div><br/></div><div>multiple resources:</div><ul><li><div>generalised safe state detection:</div></li></ul><div style="margin-left: 40px;"><img src="Deadlocks.resources/screenshot.png" height="251" width="556"/><br/></div><ul><ul><li><div>select row R whose unmet resource needs N are all <= A</div></li><li><div>mark R as terminated and add its resources to A vector</div></li><li><div>repeat until completion (safe) or deadlock (unsafe)</div></li></ul></ul><div><br/></div><div>in practice, rarely an option (hard to determine resource needs in advance)</div></body></html>