Bài giảng Nguyên lý hệ điều hành - Chapter 3: DeadLocks

DeadlocksChapter 3 3.1. Resource 3.2. Introduction to deadlocks 3.3. The ostrich algorithm 3.4. Deadlock detection and recovery 3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues 1ResourcesExamples of computer resourcesprinterstape drivestablesProcesses need access to resources in reasonable orderSuppose a process holds resource A and requests resource Bat same time another process holds B and requests Aboth are blocked and remain so2Resources (1)Deadlocks occur when processes are granted exclusive access to deviceswe refer to these devices generally as resourcesPreemptable resourcescan be taken away from a process with no ill effectsNonpreemptable resourceswill cause the process to fail if taken away3Resources (2)Sequence of events required to use a resourcerequest the resourceuse the resourcerelease the resource Must wait if request is deniedrequesting process may be blockedmay fail with error code4Introduction to DeadlocksFormal definition :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 causeUsually the event is release of a currently held resourceNone of the processes can runrelease resourcesbe awakened5Four Conditions for DeadlockMutual exclusion conditioneach resource assigned to 1 process or is availableHold and wait conditionprocess holding resources can request additionalNo preemption conditionpreviously granted resources cannot forcibly taken awayCircular wait conditionmust be a circular chain of 2 or more processeseach is waiting for resource held by next member of the chain6Deadlock Modeling (2)Modeled with directed graphsresource R assigned to process Aprocess B is requesting/waiting for resource Sprocess C and D are in deadlock over resources T and U7Deadlock Modeling (3)Strategies for dealing with Deadlocksjust ignore the problem altogetherdetection and recoverydynamic avoidance careful resource allocationprevention negating one of the four necessary conditions8How deadlock occursA B CDeadlock Modeling (4)9Deadlock Modeling (5)How deadlock can be avoided(o) (p) (q)10The Ostrich AlgorithmPretend there is no problemReasonable if deadlocks occur very rarely cost of prevention is highUNIX and Windows takes this approachIt is a trade off between conveniencecorrectness11Detection with One Resource of Each Type (1)Note the resource ownership and requestsA cycle can be found within the graph, denoting deadlock12Detection with One Resource of Each Type (2)Data structures needed by deadlock detection algorithm13Detection with One Resource of Each Type (3)An example for the deadlock detection algorithm14Recovery from Deadlock (1)Recovery through preemptiontake a resource from some other processdepends on nature of the resourceRecovery through rollbackcheckpoint a process periodicallyuse this saved state restart the process if it is found deadlocked15Recovery from Deadlock (2)Recovery through killing processescrudest but simplest way to break a deadlockkill one of the processes in the deadlock cyclethe other processes get its resources choose process that can be rerun from the beginning16Deadlock AvoidanceResource TrajectoriesTwo process resource trajectories17Safe and Unsafe States (1)Demonstration that the state in (a) is safe(a) (b) (c) (d) (e)18Safe and Unsafe States (2)Demonstration that the sate in b is not safe(a) (b) (c) (d) 19The Banker's Algorithm for a Single ResourceThree resource allocation statessafesafeunsafe(a) (b) (c)20Banker's Algorithm for Multiple ResourcesExample of banker's algorithm with multiple resources21Deadlock PreventionAttacking the Mutual Exclusion ConditionSome devices (such as printer) can be spooledonly the printer daemon uses printer resourcethus deadlock for printer eliminatedNot all devices can be spooledPrinciple:avoid assigning resource when not absolutely necessaryas few processes as possible actually claim the resource22Attacking the Hold and Wait ConditionRequire processes to request resources before startinga process never has to wait for what it needsProblemsmay not know required resources at start of runalso ties up resources other processes could be usingVariation: process must give up all resourcesthen request all immediately needed23Attacking the No Preemption ConditionThis is not a viable optionConsider a process given the printerhalfway through its jobnow forcibly take away printer!!?? 24Attacking the Circular Wait Condition (1)Normally ordered resourcesA resource graph(a) (b)25Attacking the Circular Wait Condition (1)Summary of approaches to deadlock prevention26Other IssuesTwo-Phase LockingPhase Oneprocess tries to lock all records it needs, one at a timeif needed record found locked, start over(no real work done in phase one)If phase one succeeds, it starts second phase, performing updatesreleasing locks Note similarity to requesting all resources at onceAlgorithm works where programmer can arrange program can be stopped, restarted27Nonresource DeadlocksPossible for two processes to deadlockeach is waiting for the other to do some taskCan happen with semaphoreseach process required to do a down() on two semaphores (mutex and another)if done in wrong order, deadlock results28StarvationAlgorithm to allocate a resource may be to give to shortest job firstWorks great for multiple short jobs in a systemMay cause long job to be postponed indefinitelyeven though not blockedSolution:First-come, first-serve policy29