《现代操作系统 Chapter 6.ppt》由会员分享，可在线阅读，更多相关《现代操作系统 Chapter 6.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 6 DeadlockContents6.1 Resources6.2 Introduction to deadlocks6.3 The ostrich algorithm6.4 Deadlock detection and recovery6.5 deadlock avoidance6.6 deadlock prevention26.1 ResourcesvResources(资源资源)：需要排他性使用的：需要排他性使用的对象。资源可以是硬件设备或是一组信息对象。资源可以是硬件设备或是一组信息（一个排他使用的表格、数据库中的一条（一个排他使用的表格、数据库中的一条记录等）。记录
2、等）。v某些类型的资源会有若干个相同的实例。某些类型的资源会有若干个相同的实例。36.1.1 Preemptable and Nonpreemptable ResourcesvPreemptable Resource(可抢占资源可抢占资源):it can be taken away from the process owning it with no ill effects.Example:Memory,CPU,vNonpreemptable Resource(不可抢占资源不可抢占资源):it cannot be taken away from its current owner withou
3、t causing the computation to fail.vDeadlocks involve nonpreemptable resources.4Preemptable and Nonpreemptable ResourcesvSequence of events required to use a resource:Request the resource.Use the resource.Release the resource.vAssume:when a process is denied a resource request,it is put to sleep.56.1
4、.2 Resource Acquisition(获取获取)vOne way of allowing user management of resources is to associate a semaphore with each resource.Figure 6-1.Using a semaphore to protect resources.(a)One resource.(b)Two resources.6Resource AcquisitionvConsider a situation with two processes,A and B,and two resources.Fig
5、ure 6-2.(a)Deadlock-free code.7Figure 6-2.(b)Code with a potential deadlock.Resource Acquisition86.2 Introduction To DeadlocksvDeadlock can be defined formally as follows: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 caus
6、e.在一个进程集合中，若每个进程都在等在一个进程集合中，若每个进程都在等待某些事件（指：释放资源）的发生，而这待某些事件（指：释放资源）的发生，而这些事件又必须由这个进程集合中的其它进程些事件又必须由这个进程集合中的其它进程来产生，则该进程集合处于死锁状态。来产生，则该进程集合处于死锁状态。96.2.1 Conditions for Resource DeadlocksvMutual exclusion condition(互斥条件互斥条件).Each resource is either currently assigned to exactly one process or is avai
7、lable.vHold and wait condition(占有与等待条件占有与等待条件).Process currently holding resources that were granted earlier can request new resources.vNo preemption condition(不可抢占条件不可抢占条件).Resources previously granted cannot be forcibly taken away from a process.They must be explicitly released by the process hold
8、ing them.vCircular wait condition(环路等待条件环路等待条件).There must be a circular chain of two or more processes,each of which is waiting for a resource held by the next member of the chain.10Conditions for Resource DeadlocksAll four of these conditions must be present for a resource deadlock to occur.If one
9、 of them is absent,no resource deadlock is possible.116.2.2 Deadlock Modeling vHow can these four conditions be modeled using directed graphs(有向图有向图)?vTwo kinds of nodes:Process:shown as circlesResources:shown as squaresvTwo kinds of directed arcs:A directed arc from a resource to a process means th
10、at the resource has previously been requested by,granted to,and is currently held by that process.A directed arc from a process to a resource means that the process is currently blocked waiting for that resource.12Deadlock ModelingFigure 6-3.Resource allocation graphs.(a)Holding a resource.(b)Reques
11、ting a resource.(c)Deadlock.13Deadlock ModelingDeadlock!14Deadlock ModelingvStrategies for dealing with deadlocks:Just ignore the problem.Detection and recovery(检测与恢复检测与恢复).Let deadlocks occur,detect them,take action.Dynamic avoidance(避免避免)by careful resource allocation.Prevention(防止防止),by structura
12、lly negating one of the four required conditions.156.3 The Ostrich(鸵鸟鸵鸟)AlgorithmThe simplest approach is the ostrich algorithm:stick your head in the sand and pretend there is no problem at all.166.4 Deadlock Detection and RecoveryWhen this technique is used,the system does not attempt to prevent d
13、eadlocks from occurring.Instead,it lets them occur,tries to detect when this happens,and then takes some action to recover after the fact.176.4.1 Deadlock Detection with One Resource of Each TypevThe simplest case:only one resource of each type exists.vFor such a system,we can construct a resource g
14、raph.If this graph contains one or more cycles,a deadlock exists.Any process that is part of a cycle is deadlocked.If no cycles exist,the system is not deadlocked.18Deadlock Detection with One Resource of Each Type(2)Example:Figure 6-5.(a)A resource graph.(b)A cycle extracted from(a).19Deadlock Dete
15、ction with One Resource of Each Type(3)Algorithm for detecting deadlock:1.For each node,N in the graph,perform the following five steps with N as the starting node.2.Initialize L to the empty list,designate all arcs as unmarked.3.Add current node to end of L,check to see if node now appears in L two
16、 times.If it does,graph contains a cycle(listed in L),algorithm terminates.20Deadlock Detection with One Resource of Each Type(4)4.From given node,see if any unmarked outgoing arcs.If so,go to step 5;if not,go to step 6.5.Pick an unmarked outgoing arc at random and mark it.Then follow it to the new
17、current node and go to step 3.6.If this is initial node,graph does not contain any cycles,algorithm terminates.Otherwise,dead end.Remove it,go back to previous node,make that one current node,go to step 3.216.4.2 Deadlock Detection with Multiple Resources of Each TypevWe now present a matrix-based a
18、lgorithm for detecting deadlock among n processes,P1 through Pn.vAssume that:E:the existing resource vector.it gives the total number of instances of each resource in existence.A:the available resource vector.Ai gives the number of instances of resource i that are currently available.22Deadlock Dete
19、ction with Multiple Resources of Each Type(2)C:the current allocation matrix.The i-th row of C tells how many instances of each resource class Pi currently holds.R:the request matrix.23Deadlock Detection with Multiple Resources of Each Type(3)vDeadlock detection algorithm:1.Look for an unmarked proc
20、ess,Pi,for which the i-th row of R is less than or equal to A.2.If such a process is found,add the i-th row of C to A,mark the process,and go back to step 1.3.If no such process exists,the algorithm terminates.vWhen the algorithm finishes,all the unmarked processes are deadlocked.24Deadlock Detectio
21、n with Multiple Resources of Each Type(4)vExample:256.4.3 Recovery from Deadlock1.Recovery through preemptionIn some cases it may be possible to temporarily take a resource away from its current owner and give it to another process.2.Recovery through rollback(回滚回滚)The system designers and machine op
22、erators can arrange to have processes checkpointed periodically.Checkpointing a process means that its state is written to a file so that it can be restarted later.26Recovery from DeadlockWhen a deadlock is detected,it is easy to see which resources are needed.To do the recovery,a process that owns
23、a needed resource is rolled back to a point in time before it acquired that resource by starting one of its earlier checkpoints.3.Recovery through killing processesThe crudest way to break a deadlock is to kill one or more processes.One possibility is to kill a process in the cycle.A process not in
24、the cycle can be chosen as the victim in order to release its resources.276.5 Deadlock AvoidancevIn the discussion of deadlock detection,we assumed that when a process asks for resources,it asks for them all at once.However,in most systems,resources are requested one at a time.The system must be abl
25、e to decide whether granting a resource is safe or not and only make the allocation when it is safe.vIs there an algorithm that can always avoid deadlock by making the right choice all the time?286.5.1 Resource Trajectories(轨轨迹图迹图)vThe main algorithms for doing deadlock avoidance are based on the co
26、ncept of safe sates(安全状态安全状态).29Resource Trajectories进程进程Q释放释放A释放释放B申请申请A申请申请B 申请申请A 申请申请B 释放释放A 释放释放B 进程进程P(2)(1)(4)(5)(6)(3)306.5.2 Safe and Unsafe StatesvA state is said to be safe if there is some scheduling order in which every process can run to completion even if all of them suddenly request
27、their maximum number of resources immediately.vUnsafe statevDifference:From a safe state the system can guarantee that all processes will finish;From an unsafe state,no such guarantee can be given.31Safe and Unsafe StatesFigure 6-9.Demonstration that the state in(a)is safe.Figure 6-10.Demonstration
28、that the state in(b)is not safe.326.5.3 The Bankers Algorithm for a Single ResourcevThe bankers algorithm(银行家算法银行家算法)Figure 6-11.Three resource allocation states:(a)Safe.(b)Safe.(c)Unsafe.33The Bankers Algorithm for a Single ResourcevThe bankers algorithm considers each request as it occurs,and sees
29、 if granting it leads to a safe state.If it does,the request is granted;otherwise,it is postponed until later.vTo see if a state is safe,the banker checks to see if he has enough resources to satisfy some customer.34Figure 6-12.The bankers algorithm with multiple resources.6.5.4 The Bankers Algorith
30、m for Multiple Resources35The Bankers Algorithm for Multiple ResourcesAlgorithm for checking to see if a state is safe:1.Look for a row,R,whose unmet resource needs all A.If no such row exists,system will eventually deadlock since no process can run to completion.2.Assume process of row chosen reque
31、sts all resources it needs and finishes.Mark process as terminated,add all its resources to the A vector.3.Repeat steps 1 and 2 until either all processes marked terminated(initial state was safe)or no process left whose resource needs can be met(there is a deadlock).366.6 Deadlock PreventionvAttack
32、ing the mutual exclusion conditionvAttacking the hold and wait conditionvAttacking the no preemption conditionvAttacking the circular wait conditionTanenbaum,Modern Operating Systems 3 e,(c)2008 Prentice-Hall,Inc.All rights reserved.0-13-6006639376.6.1 Attacking the mutual exclusion conditionv互斥条件是由
33、设备的固有特性所决定的，不互斥条件是由设备的固有特性所决定的，不仅不能改变，还应加以保证。仅不能改变，还应加以保证。vBy spooling(假脱机假脱机)printer output,several processes can generate output at the same time.In this model,the only process that actually requests the physical printer is the printer daemon(守护进程守护进程).Since daemon never requests any other resourc
34、es,we can eliminate deadlock for the printer.386.6.2 Attacking the hold and wait conditionvIf we can prevent processes that hold resources from waiting for more resources,we can eliminate deadlocks.vMethod 1:require all processes to request all their resources before starting execution.vThe problem
35、of method 1?Many processes do not know how many resources they will need until they have started running.Resources will not be used optimally.39Attacking the hold and wait conditionvMethod 2:require a process requesting a resource to first temporarily release all the resources it currently holds.The
36、n it tries to get everything it need all at once.406.6.3 Attacking the no preemption conditionvIf a process has been assigned the printer and is in the middle of printing its output,forcibly taking away the printer because a needed plotter is not available is tricky at best and impossible at worst.v
37、Some(not all)resources can be virtualized to avoid this situation.416.6.4 Attacking the Circular Wait ConditionvProviding a global numbering of all the resources,for example:vThe rule is:processes can request resources whenever they want to,but all requests must be made in numerical order(数字数字顺序序).4
38、2Attacking the Circular Wait ConditionAt every instant,one of the assigned resources will be highest.The process holding that resource will never ask for a resource already assigned.It will either finish,or at worst,request even higher numbered resources,all of which are available.Eventually,it will
39、 finish and free its resources.At this point,some other process will hold the highest resource and can also finish.In short,there exists a scenario in which all processes finish,so no deadlock is present.43Attacking the Circular Wait ConditionvA small variation of this algorithm:drop the requirement that resources be acquired in strictly increasing sequence;insist that no process request a resource lower than what it is already holding.44Summary of approaches to deadlock prevention45