Khoa học máy tính - Chapter 8: Deadlocks

Chapter 8DeadlocksCopyright © 20081Operating Systems, by Dhananjay Dhamdhere*IntroductionWhat is a Deadlock?Deadlocks in Resource AllocationHandling DeadlocksDeadlock Detection and ResolutionDeadlock PreventionDeadlock AvoidanceCharacterization of Resource Deadlocks by Graph ModelsDeadlock Handling in Practice2Operating Systems, by Dhananjay Dhamdhere*What is a Deadlock?Resource deadlock  primary concern of OSPi, Pj are deadlocked after their second requests Deadlocks can also arise in synchronization and message communication  user concern3Operating Systems, by Dhananjay Dhamdhere*Deadlocks in Resource AllocationOS may contain several resources of a kindResource unit refers to a resource of a specific kindResource class to refers to the collection of all resource units of a kindResource allocation in a system entails three kinds of events:Request for the resourceActual allocation of the resourceRelease of the resourceReleased resource can be allocated to another process4Operating Systems, by Dhananjay Dhamdhere*Deadlocks in Resource Allocation (continued)5Operating Systems, by Dhananjay Dhamdhere*Conditions for a Resource DeadlockAnother condition is also essential for deadlocks:No withdrawal of resource requests: A process blocked on a resource request cannot withdraw it6Operating Systems, by Dhananjay Dhamdhere*Modeling the Resource Allocation State(Resource) allocation state:Information about resources allocated to processes and about pending resource requestsUsed to determine whether a set of processes is deadlockedTwo kinds of models are used to represent the allocation state of a system:A graph modelA matrix model7Resource request and allocation graph (RRAG)Nodes and edges in an RRAGTwo kinds of nodes exist in an RRAGA circle is a processA rectangle is a resource classEach bullet in a rectangle is one resource unitEdges can also be of two kindsAn edge from a resource class to a process is a resource allocationAn edge from a process to a resource class is a pending resource request Operating Systems, by Dhananjay Dhamdhere*8Wait-for graph (WFG)A WFG can be used to depict the resource state of a system in which every resource class contains only one resource unitA Node in the graph is a processAn edge is a wait-for relationship between processesA wait-for edge (Pi, Pj) indicates thatProcess Pj holds the resource unit of a resource classProcess Pi has requested the resource and it has become blocked on itIn essence Pi waits for Pj to release the resourceOperating Systems, by Dhananjay Dhamdhere*9Operating Systems, by Dhananjay Dhamdhere*Graph Models10Paths in WFG and RRAGA path in a graph is a sequence of edges such that the destination node of an edge is the source node of the subsequent edgeConsider an RRAG path P1 – R1 – P2 – R2 Pn-1 – Rn-1 – Pn This path indicates thatProcess Pn has been allocated a resource unit of Rn-1 Process Pn-1 has been allocated a resource unit of Rn-2 and awaits a resource unit of Rn-1, etc.In WFG, the same path would be P1 – P2 – Pn-1 – PnOperating Systems, by Dhananjay Dhamdhere*11Operating Systems, by Dhananjay Dhamdhere*Graph Models (continued)A deadlock cannot exist unless an RRAG, or a WFG, contains a cycleA cycle in an RRAG does not necessarily imply a deadlock if a resource class has multiple resource unitsWhen Pk completes,its tape unit can be allocated to Pj12Operating Systems, by Dhananjay Dhamdhere*Matrix ModelAllocation state represented by two matrices:Allocated_resourcesRequested_resourcesIf system has n processes and r resource classes, each of these matrices is an n × r matrixAuxiliary: Total_resources and Free_resources13Operating Systems, by Dhananjay Dhamdhere*Handling Deadlocks14Operating Systems, by Dhananjay Dhamdhere*Deadlock Detection and ResolutionA blocked process is not currently involved in a deadlock if request on which it is blocked can be satisfied through a sequence of process completion, resource release, and resource allocation eventsIf each resource class in system contains a single resource unit, check for a cycle in RRAG or WFGNot applicable if resource classes have multiple resource unitsWe will use matrix modelApplicable in all situations15Operating Systems, by Dhananjay Dhamdhere*Example: Deadlock DetectionThe allocation state of a system containing 10 units of a resource class R1 and three processes:Process P3 is in the running stateWe simulate its completionAllocate its resources to P2All processes can complete in this mannerNo blocked processes exist when the simulation endsHence no deadlock16Operating Systems, by Dhananjay Dhamdhere*A Deadlock Detection Algorithm17Operating Systems, by Dhananjay Dhamdhere*Example: Operation of a Deadlock Detection Algorithm18Operating Systems, by Dhananjay Dhamdhere*Deadlock ResolutionDeadlock resolution for a set of deadlocked processes D is breaking of deadlock to ensure progress for some processes in DAchieved by aborting one or more processes in DEach aborted process is called a victimChoice of victim made using criteria such as process priority, resources consumed by it, etc.19Operating Systems, by Dhananjay Dhamdhere*Deadlock Prevention20Operating Systems, by Dhananjay Dhamdhere*All Resources TogetherSimplest of all deadlock prevention policiesProcess must ask for all resources it needs in a single requestKernel allocates all of them togetherA blocked process does not hold any resourcesHold-and-wait condition is never satisfiedAttractive policy for small operating systemsHas one practical drawback:Adversely influences resource efficiency21Operating Systems, by Dhananjay Dhamdhere*Resource RankingResource rank associated with each resource classUpon resource request, kernel applies a validity constraint to decide if it should be consideredRank of requested resource must be larger than rank of highest ranked resource allocated to the processResult: absence of circular wait-for relationshipsWorks best when all processes require their resources in the order of increasing resource rankIn worst case, policy may degenerate into the “all resources together” policy of resource allocation22Operating Systems, by Dhananjay Dhamdhere*Deadlock AvoidanceBanker’s algorithmAnalogy: bankers admit loans that collectively exceed the bank’s funds and then release each borrower’s loan in installmentsUses notion of a safe allocation stateWhen system is in such a state, all processes can complete their operation without possibility of a deadlockDeadlock avoidance implemented by taking system from one safe allocation state to another23Operating Systems, by Dhananjay Dhamdhere*Deadlock Avoidance24Operating Systems, by Dhananjay Dhamdhere*Deadlock Avoidance (continued)Outline of the approach:1. When a process makes a request, compute projected allocation state– This would be the state if the request is granted2. If projected allocation state is safe, grant request by updating Allocated_resources and Total_alloc; otherwise, keep request pending – Safety is checked through simulation – A process is assumed to complete only if it can get its maximum requirement of each resource satisfied simultaneously3. When a process releases any resource(s) or completes its operation, examine pending requests and allocate those that would put the system in a new safe allocation state25Operating Systems, by Dhananjay Dhamdhere*Example: Banker’s Algorithm for a Single Resource ClassNow consider the following requests:P1 makes a request for 2 resource unitsP2 makes a request for 2 resource unitsP3 makes a request for 2 resource unitsRequests by P1 and P2 do not put the system in safe allocation states, hence they will not be grantedRequest by P3 will be granted26Operating Systems, by Dhananjay Dhamdhere*27Operating Systems, by Dhananjay Dhamdhere*28Operating Systems, by Dhananjay Dhamdhere*Example: Banker’s Algorithm for Multiple Resource Classes29Operating Systems, by Dhananjay Dhamdhere*30Operating Systems, by Dhananjay Dhamdhere*Characterization of Resource Deadlocks by Graph ModelsA deadlock characterization is a statement of the essential features of a deadlockWe discuss characterization using graph models of allocation state and elements of graph theoryA cycle in a RRAG or WFG is a sufficient condition for a deadlock in some systems, but not in others31Operating Systems, by Dhananjay Dhamdhere*Single-Instance, Single-Request (SISR) SystemsEach resource class contains a single instance of the resource and each request is a single requestA cycle in an RRAG implies a mutual wait-for relationship for a set of processesSince each resource class contains a single resource unitEach blocked process Pi in cycle waits for exactly one other process, say Pk, to release required resource Hence a cycle that involves Pi also involves PkA cycle is thus a necessary and sufficient condition to conclude that a deadlock exists in the system32A knot in RRAG is a necessary and sufficient condition for the existence of a deadlock in an MISR systemOperating Systems, by Dhananjay Dhamdhere*Multiple-Instance, Single-Request (MISR) Systems33Operating Systems, by Dhananjay Dhamdhere*Single-Instance, Multiple-Request (SIMR) SystemsA process making a multiple request has > 1 out-edgeIt remains blocked until each of the requested resources is availableA cycle is a necessary and sufficient condition for a deadlock in an SIMR system34Operating Systems, by Dhananjay Dhamdhere*Multiple-Instance, Multiple-Request (MIMR) SystemsWe must differentiate between process and resource nodes in the RRAG of an MIMR systemAll out-edges of a resource node must be involved in cycles for a deadlock to ariseA process node needs to have only one out-edge involved in a cycleA resource knot incorporates these conditions35Operating Systems, by Dhananjay Dhamdhere*Multiple-Instance, Multiple-Request (MIMR) Systems (continued)A resource knot is a necessary and sufficient condition for the existence of a deadlock in an MIMR system...And, in all classes of systems discussed in this section36Operating Systems, by Dhananjay Dhamdhere*Processes in Deadlock37Operating Systems, by Dhananjay Dhamdhere*Deadlock Handling in PracticeDeadlock detection-and-resolution and deadlock avoidance are unattractive in practice (overhead)OS uses deadlock prevention approach or simply does not care about possibility of deadlocksOSs tend to handle deadlock issues separately for each kind of resourceMemory: Explicit deadlock handling is unnecessaryI/O devices: Resources are not limited (virtual devices)Files: Deadlocks are handled by processes, not OSControl blocks: Resource ranking or all-resources-together38Operating Systems, by Dhananjay Dhamdhere*Deadlock Handling in UnixMost operating systems simply ignore the possibility of deadlocks involving user processesUnix is no exceptionUnix addresses deadlocks due to sharing of kernel data structures by user processesKernel uses resource ranking (deadlock prevention) by requiring processes to set locks on kernel data structures in a standard orderThere are exceptions to this rule; deadlocks can ariseSpecial deadlock handling for buffer cache and file system39Operating Systems, by Dhananjay Dhamdhere*Deadlock Handling in WindowsVista has feature called wait chain traversal (WCT)Assists applications and debuggers in detecting deadlocksA wait chain starts on a thread and is analogous to a path in the RRAGDebugger can investigate cause of a freeze by invoking getthreadwaitchain with the id of a thread to retrieve a chain starting on that thread40Operating Systems, by Dhananjay Dhamdhere*SummaryDeadlock: set of processes wait indefinitely for events because each of the events can be caused only by other processes in the setResource deadlock arises when:Resources are nonshareable and nonpreemptibleHold-and-waitCircular wait existsOS can discover a deadlock by analyzing the allocation state of a systemUse RRAG, WFG or matrix modelDeadlocks can be detected, prevented and avoided41