操作系统 ppt6.ppt

Concurrency:Deadlock(死锁)and Starvation(饥饿)Chapter 616.1 Principles of Deadlock6.1 Principles of Deadlock6.2 Deadlock Prevention6.3 Deadlock Avoidance6.4 Deadlock Detection 6.5 An Integrated Deadlock Strategy6.6 Dining Philosophers Problem6.7 Summary2DeadlockPermanent blocking of a set of processes that either compete for system resources or communicate with each otherNo efficient solutionInvolve conflicting(冲突)needs for resources by two or more processes3456Resources Categories(资源的分类)Reusable Resources(可重用资源)Consumable Resources(可消费资源)76.1 Principles of Deadlock6.1.1 Reusable Resources6.1.2 Consumable Resources6.1.3 Resource Allocation Graphs6.1.4 The Conditions for Deadlock8Reusable Resources(可重用资源)Used by only one process at a time and not depleted(耗尽)by that useProcesses obtain resources that they later release for reuse by other processesProcessors,I/O channels,main and secondary memory,devices,and data structures such as files,databases,and semaphoresDeadlock occurs if each process holds one resource and requests the other9Example of DeadlockInterleaves the execution:p0 p1 q0 q1 p2 q210Another Example of DeadlockSpace is available for allocation of 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;116.1 Principles of Deadlock6.1.1 Reusable Resources6.1.2 Consumable Resources6.1.3 Resource Allocation Graphs6.1.4 The Conditions for Deadlock12Consumable Resources(可消费资源)Created(produced)and destroyed(consumed)Interrupts,signals,messages,and information in I/O buffersDeadlock may occur if a receive message is blockingMay take a rare combination of events to cause deadlock(很少的事件组合也可能导致死锁)13Example of DeadlockDeadlock occurs if receive is blockingP1.Receive(P2);Send(P2,M1);P2.Receive(P1);Send(P1,M2);146.1 Principles of Deadlock6.1.1 Reusable Resources6.1.2 Consumable Resources6.1.3 Resource Allocation Graphs6.1.4 The Conditions for Deadlock15Resource Allocation Graphs(资源分配图)Directed graph(有向图)that depicts(表述)a state of the system of resources and processes16Resource Allocation Graphs176.1 Principles of Deadlock6.1.1 Reusable Resources6.1.2 Consumable Resources6.1.3 Resource Allocation Graphs6.1.4 The Conditions for Deadlock18Conditions for Deadlock(死锁的条件)Mutual exclusion(互斥)Only one process may use a resource at a timeHold-and-wait(占有且等待)A process may hold allocated resources while awaiting assignment of othersNo preemption(非抢占)No resource can be forcibly removed form a process holding it19Conditions for DeadlockCircular wait(循环等待)A closed chain of processes exists,such that each process holds at least one resource needed by the next process in the chain20Possibility of DeadlockMutual ExclusionHold and wait No preemption21Existence of DeadlockMutual ExclusionHold and waitNo preemptionCircular wait22Agenda6.1 Principles of Deadlock6.2 Deadlock Prevention6.3 Deadlock Avoidance6.4 Deadlock Detection 6.5 An Integrated Deadlock Strategy6.6 Dining Philosophers Problem6.7 Summary23Deadlock Prevention(死锁预防)Mutual ExclusionMust be supported by the operating systemHold and WaitRequire a process request all of its required resources at one time24Deadlock PreventionNo PreemptionProcess must release resource and request againOperating system may preempt a process to require it releases its resourcesCircular WaitDefine a linear ordering of resource types25Agenda6.1 Principles of Deadlock6.2 Deadlock Prevention6.3 Deadlock Avoidance6.4 Deadlock Detection 6.5 An Integrated Deadlock Strategy6.6 Dining Philosophers Problem6.7 Summary26Deadlock Avoidance(死锁避免)A decision is made dynamically whether the current resource allocation request will,if granted,potentially lead to a deadlockRequires knowledge of future process request27Two Approaches to Deadlock AvoidanceDo not start a process if its demands might lead to deadlock(如果一个进程的请求会导致死锁，则不启动此进程，资源启动拒绝)Do not grant an incremental resource request to a process if this allocation might lead to deadlock(如果一个进程增加资源的请求会导致死锁，则不容许此分配，资源分配拒绝)28Resource Allocation DenialReferred to as the bankers algorithmState of the system(系统状态)is the current allocation of resources to processSafe state(安全状态)is where there is at least one sequence that does not result in deadlockUnsafe state(不安全状态)is a state that is not safe29Determination of a Safe StateInitial State30Determination of a Safe StateP2 Runs to Completion31Determination of a Safe StateP1 Runs to Completion32Determination of a Safe StateP3 Runs to Completion33Determination of an Unsafe StateP1 request for one additional unit each of R1 and R334Determination of an Unsafe State35Deadlock Avoidance Logic(死锁避免逻辑)36Deadlock Avoidance Logic37Restrictions of Deadlock AvoidanceMaximum resource requirement must be stated in advanceProcesses under consideration must be independent;no synchronization requirementsThere must be a fixed number of resources to allocateNo process may exit while holding resources38Agenda6.1 Principles of Deadlock6.2 Deadlock Prevention6.3 Deadlock Avoidance6.4 Deadlock Detection 6.5 An Integrated Deadlock Strategy6.6 Dining Philosophers Problem6.7 Summary39Deadlock DetectionReference P.273 of the textbook for deadlock detection algorithm40Strategies Once Deadlock DetectedAbort all deadlocked processesBack up each deadlocked process to some previously defined checkpoint,and restart all processOriginal deadlock may occurSuccessively abort deadlocked processes until deadlock no longer existsSuccessively preempt resources until deadlock no longer exists41Selection Criteria Deadlocked ProcessesLeast amount of processor time consumed so farLeast number of lines of output produced so farMost estimated time remainingLeast total resources allocated so farLowest priority42Strengths and Weaknesses of the Strategies43Agenda6.1 Principles of Deadlock6.2 Deadlock Prevention6.3 Deadlock Avoidance6.4 Deadlock Detection 6.5 An Integrated Deadlock Strategy6.6 Dining Philosophers Problem6.7 Summary44An Integrated Deadlock Strategy(一种综合死锁策略)Group resources into a number of different resource classesUse the linear ordering strategy defined previously for the prevention of circular wait to prevent deadlocks between resource classesWithin a resource class,use the algorithm that is most appropriate for that class45Agenda6.1 Principles of Deadlock6.2 Deadlock Prevention6.3 Deadlock Avoidance6.4 Deadlock Detection 6.5 An Integrated Deadlock Strategy6.6 Dining Philosophers Problem6.7 Summary46Dining Philosophers Problem(哲学家就餐问题)47Dining Philosophers Problem(incorrect)48Dining Philosophers Problem49Dining Philosophers Problem50Agenda6.1 Principles of Deadlock6.2 Deadlock Prevention6.3 Deadlock Avoidance6.4 Deadlock Detection 6.5 An Integrated Deadlock Strategy6.6 Dining Philosophers Problem6.7 Summary51HomeworkReview Questions:6.26.3Problems:6.46.552