Hệ điều hành - Chapter 6: Concurrency: deadlock and starvation

Chapter 6Concurrency: Deadlock and StarvationPrincipals of DeadlockDeadlock PreventionDeadlock AvoidanceDeadlock DetectionDining Philosophers ProblemDeadlockA set of processes is deadlocked when each process in the set is blocked awaiting an event that can only be triggered by another blocked process in the setTypically involves processes competing for the same set of resourcesThe event is typically the freeing up of some requested resourcesNo efficient solutionPotential Deadlock I need quad A and BI need quad B and CI need quad C and DI need quad D and AThe necessary resources are available for any of the cars to proceedActual DeadlockHALT until B is freeHALT until C is freeHALT until D is freeHALT until A is freeTwo Processes P and QConsider two processes P and Q in a uniprocessor system.Each needs exclusive access to a resource A and B for a period of time.Joint Progress Diagram of DeadlockDeadlock is only inevitable if the joint progress of the two processes creates a path that enters the fatal region.Alternative logicWhether or not deadlock occurs depends on both the dynamics of the execution and on the details of the application.Suppose that P does not need both resources at the same time.Diagram of alternative logicDeadlock cannot occurResource CategoriesTwo general categories of resources:Reusablecan be safely used by only one process at a time and is not depleted by that use.examples: processors, main and secondary memory, devices, and data structures such as files, databases, and semaphoresConsumablecan be created (produced) and destroyed (consumed)examples: interrupts, signals, messages, and information in I/O buffersReusable Resources ExampleConsider two processes that compete for exclusive access to a disk file D and a tape drive T.Reusable Resources ExampleDeadlock occurs if each process holds one resource and requests the other.Example:If the multiprogramming system interleaves the execution of the two processes as followsp0 p1 q0 q1 p2 q2Reusable Resources Example 2:Memory RequestSpace is available for allocation is 200Kbytes and the following sequence of events occurDeadlock occurs if both processes progress to their second requestP1. . .. . .Request 80 Kbytes;Request 60 Kbytes;P2. . .. . .Request 70 Kbytes;Request 80 Kbytes;Consumable Resources Example Consider a pair of processes, in which each process attempts to receive a message from the other process and then send a message to the other process.Deadlock may occur if the Receive is blocking (i.e., the receiving process is blocked until the message is received).Resource Allocation GraphsDirected graph that depicts a state of the system of resources and processesan instance of a resourceConditions for possible DeadlockMutual exclusionOnly one process may use a resource at a timeHold-and-waitA process may hold allocated resources while awaiting assignment of othersNo pre-emptionNo resource can be forcibly removed from a process holding itActual Deadlock Requires Given that the first 3 conditions exist, a sequence of events may occur that lead to the following fourth condition:Circular waitA closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chainResource Allocation Graphs of deadlockResource Allocation Graphs(the traffic deadlock shown in slide 4)Dealing with DeadlockThree general approaches exist for dealing with deadlock.Prevent deadlockby adopting a policy that eliminates one of the conditionsAvoid deadlockby making the appropriate dynamic choices based on the current state of resource allocation Detect Deadlockby checking whether conditions 1 through 4 hold and take action to recoverRoadmapPrincipals of DeadlockDeadlock PreventionDeadlock AvoidanceDeadlock DetectionDining Philosophers ProblemDeadlock Prevention StrategyDesign a system in such a way that the possibility of deadlock is excluded.Two main methodsIndirect: prevent the occurrence of one of the three necessary conditions Direct: prevent circular waitsDeadlock Prevention Conditions 1 & 2Mutual ExclusionCannot be disallowed and must be supported by the OSHold and WaitRequire a process request all of its required resources at one time Inefficient and may be impracticalDeadlock PreventionCondition 3No PreemptionIf a process is denied a further request, it must release its resource and request again.OS may preempt a process to require it releases its resources to another process.Practical only for resources whose state can be easily saved and restored later, e.g., processor.Deadlock PreventionCondition 4Circular WaitDefine a linear ordering of resource types.If a process has been allocated resources of type R, then it may subsequently request only those resources of types following R in the ordering. Inefficient, slowing down processes and denying resource access unnecessarilyRoadmapPrincipals of DeadlockDeadlock PreventionDeadlock AvoidanceDeadlock DetectionDining Philosophers ProblemDeadlock AvoidanceA decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock. Allows more concurrency than prevention. Requires knowledge of future process requests.Two Approaches to Deadlock AvoidanceProcess Initiation DenialDo not start a process if its demands might lead to deadlock.Resource Allocation DenialDo not grant an incremental resource request to a process if this allocation might lead to deadlock.Process Initiation DenialA process is only started if the maximum claim of all current processes plus those of the new process can be met. Not optimal, Assumes the worst: that all processes will make their maximum claims together.Resource Allocation DenialReferred to as the banker’s algorithmConsider a system with fixed number of resourcesState of the system is the current allocation of resources to process.Safe state is where there is at least one sequence that does not result in deadlock, i.e., all processes can be run to completion.Unsafe state is a state that is not safe.Determination of Safe StateExampleA system consists of four processes and three resources. Is this a safe state?requirement of process i for resource jcurrent allocation to process i of resource jtotal amount of each resourcetotal amount of each resource not allocatedProcess iA process i can run to completion if it meets the following condition:Cij - Aij ≤ Vj, for all jThis is not possible for P1, which has only 1 unit of R1 and requires 2 more units of R1, 2 units of R2, and 2 units of R3. If we assign one unit of R3 to process P2, Then P2 has its maximum required resources allocated and can run to completion and return resources to ‘available’ pool.After P2 runs to completionCan any of the remaining processes can be completed?After P1 completesP3 CompletesThus, the state defined originally is a safe state.Deadlock AvoidanceWhen a process makes a request for a set of resources, assume that the request is granted, update the system state accordingly, Then determine if the result is a safe state. if so, grant the request and, if not, block the process until it is safe to grant the request.Determination of an Unsafe StateSuppose that P1 makes the request for one additional unit each of R1 and R3.Is this safe?Deadlock Avoidance Logicrequest[*] is a vector defining the resources requested by process iDeadlock Avoidance LogicDeadlock Avoidance AdvantagesIt is less restrictive than deadlock prevention. It is not necessary to preempt and rollback processes, as in deadlock detection (to be discussed). Deadlock Avoidance RestrictionsMaximum resource requirement must be stated in advance.Processes under consideration must be independent and with no synchronization requirements.There must be a fixed number of resources to allocate.No process may exit while holding resources.RoadmapPrincipals of DeadlockDeadlock PreventionDeadlock AvoidanceDeadlock DetectionDining Philosophers ProblemDeadlock DetectionDeadlock prevention strategies are very conservative.Limit access to resources and impose restrictions on processes.Deadlock detection strategies do the opposite.Resource requests are granted whenever possible.Regularly check for deadlock (circular wait)A Common Detection AlgorithmIdea: Find and mark a process whose resource requests can be satisfied with the available resources.Assume that those resources are granted and that the process runs to completion and releases all its resources.Look for another process to satisfyA deadlock exists if and only if there are unmarked processes at the end.A Common Detection AlgorithmUse a Allocation matrix and Available vector as in the Banker’s algorithm.Also use a request matrix Qwhere Qij indicates that an amount of resource j is requested by process iInitially, ‘un-mark’ all processes.Detection Algorithm1. Mark each process that has a row in the Allocation matrix of all zeros.2. Initialize a temporary vector W to equal the Available vector.3. Find an index i such that process i is currently unmarked and the ith row of Q is less than or equal to W.i.e. Qik ≤ Wk for 1 ≤ k ≤ m. If no such row is found, terminateDetection Algorithm cont.4. If such a row is found,mark process i and add the corresponding row of the allocation matrix to W.i.e. set Wk = Wk + Aik, for 1 ≤ k ≤ mReturn to step 3.A deadlock exists if and only if there are unmarked processes at the end.Each unmarked process is deadlocked.Deadlock DetectionW = (0 0 0 0 1)W = W + (0 0 0 1 0) = (0 0 0 1 1)P1 and P2 are deadlockedRecovery Strategies Once Deadlock DetectedAbort all deadlocked processes.Back up each deadlocked process to some previously defined checkpoint, and restart all processes.Risk of deadlock recurringSuccessively abort deadlocked processes until deadlock no longer exists.Successively preempt resources until deadlock no longer exists.Advantages and DisadvantagesRoadmapPrincipals of DeadlockDeadlock PreventionDeadlock AvoidanceDeadlock DetectionDining Philosophers ProblemDining Philosophers Problem: ScenarioThe life of a philosopher consists of thinking and eating spaghetti. A philosopher requires two forks to eat spaghetti.A philosopher wishing to eat goes to his assigned place at the table and, using the two forks on either side of the plate, takes and eats some spaghetti.The ProblemDevise a ritual (algorithm) that will allow the philosophers to eat.No two philosophers can use the same fork at the same time (mutual exclusion)No philosopher must starve to death (avoid deadlock and starvation literally!)This is a representative problem to illustrate basic problems in deadlock and starvation.A first solution using semaphoresEach philosopher picks up first the fork on the left and then the fork on the right.After eating, the two forks are replaced on the table. What will happen if all of the philosophers are hungry at the same time?Avoiding deadlockAn attendant only allows four philosophers at a time into the dining room.This solution is free of deadlock and starvation.