操作系統(tǒng)教學(xué)課件Chapter6Deadlock

1、Modern Operating Systems Chapter 6 - DeadlockZhang YangSpring 2013Content of this lecture6.1 Resources6.2 Deadlock6.3 Ostrich Algorithm6.4 Deadlock Detection & Deadlock Recovery6.5 Deadlock Avoidance6.6 Deadlock Prevention6.7 Other IssuesSummaryResources (1)Deadlocks may occur when Processes are gra

2、nted exclusive access to devices, files, and so forth.We refer to the objects granted as resourcesA resource is anything that can be used by a single process at any instant of time.Resource Types R1, R2, . . ., RmCPU cycles, memory space, I/O devices ,record in a databaseEach resource type Ri has Wi

3、 instances.Resources (2)Resources can be either: Reusable ResourcesUsed by one process at a time and not depleted by that useProcesses obtain resources that they later release for reuse by other processesE.g., CPU, memory, disk space, I/O devices, files, databases, semaphores. Acquire Use ReleaseCon

4、sumable ResourcesCreated (produced) and destroyed (consumed) by a processE.g., messages, buffers of information, interrupts.Create Acquire Use Resource ceases to exist after it has been used, so it is not released. Resources (3)Resources can also be either:Preemptible ResourcesCan be taken away from

5、 a process with no ill effects E.g., CPU, memory No deadlockNon-preemptible ResourcesOne that cannot be taken away from its current owner without causing the computation to fail.Will cause the process to fail if taken away E.g., Tape Drives, CD RecorderDeadlock possibleResources (4)And resources can

6、 be either: Shared among several processes E.g., Read-only filesDedicated exclusively to a single processE.g., Printers Each process utilizes a resource as follows:Request the resourceUse the resourceRelease the resourceMust wait if request is deniedRequesting process may be blockedMay fail with err

7、or codeAssume that when a process is denied a resource request, it is put to sleep.Resources (5)Processes need access to resources in reasonable orderSuppose a process holds resource A (e.g. scanner) and requests resource B (e.g. CD recorder)At same time another process holds B and requests ABoth ar

8、e blocked and remain soDeadlocks occur when Processes are granted exclusive access to devicesUsing Semaphore to Share ResourceProcess P(); A.Down(); B.Down(); use both resource B.Up(); A.Up(); Process Q(); A.Down(); B.Down(); use both resource B.Up(); A.Up(); 423 External Semaphore A(0), B(1);2Exter

9、nal Semaphore A(0), B(0);3External Semaphore A(0), B(1);4External Semaphore A(1), B(1);5516External Semaphore A(1), B(1);11But Deadlock can Happen!Process P(); A.Down(); B.Down(); use both resources B.Up(); A.Up(); Process Q(); B.Down(); A.Down(); use both resources A.Up(); B.Up(); 3211External Sema

10、phore A(1), B(1);1External Semaphore A(0), B(1);2External Semaphore A(0), B(0);3DEADLOCKBridge Crossing ExampleTraffic only in one direction.Each section of a bridge can be viewed as a resource.Deadlock can occur if two cars enter the bridge from opposite sidesIf a deadlock occurs, it can be resolve

11、d if one car backs up (preempt resources and rollback). Several cars may have to be backed up if a deadlock occurs. Starvation is possibleTimid driver hesitates to enter bridgeIntroduction to Deadlocks (1)Formal Definition A set of processes is deadlocked if each process in the set is waiting for an

12、 event that only another process in the set can cause.Assume that processes have only a single threadAssume that there are no interrupts possible to wake up a blocked processUsually the event is release of a currently held resourceThe number of processes and the number and kind of resources possesse

13、d and requested are unimportant.None of the processes can RunRelease resourcesBe awakenedIntroduction to Deadlocks (2)Is deadlock the same as starvation (or indefinitely postponed)? A process is indefinitely postponed if it is delayed repeatedly over a long period of time while the attention of the

14、system is given to other processes. I.e., logically the process may proceed but the system never gives it the CPU. Conditions for DeadlockWhat conditions should exist in order to lead to a deadlock?Group Discussion (2 minutes)Can use real life analogy such as“You take the monitor, I grab the keyboar

15、d”Cars in intersectionFour Conditions for Deadlock (1)Mutual 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 awayThey must be explici

16、tly released by the process holding themCircular wait conditionMust be a circular chain of 2 or more processesEach is waiting for resource held by next member of the chainDeadlock can arise if four conditions hold simultaneously.Four Conditions for Deadlock (2)circular wait condition exampleConditio

17、ns AnalysisDeadlock occurs if and only if the circular wait condition is not resolvable.The circular wait condition is not resolvable when the first 3 policy conditions hold.Therefore, the four conditions taken together constitute the necessary and sufficient conditions for deadlock!Resource-Allocat

18、ion Graph (1)A set of vertices V and a set of edges E.V is partitioned into two types:P = P1, P2, , Pn, the set consisting of all the processes in the system.R = R1, R2, , Rm, the set consisting of all resource types in the system.request edge directed edge P1 Rjassignment edge directed edge Rj PiRe

19、source-Allocation Graph (2)ProcessResource Type with 4 instancesPi requests instance of RjPi is holding an instance of RjPiPiRjRjExample of a Resource Allocation GraphResource Allocation Graph With A DeadlockResource Allocation Graph With A Cycle But No DeadlockBasic FactsIf graph contains no cycles

20、 no deadlock.If graph contains a cycle If only one instance per resource type, then deadlock.If several instances per resource type, possibility of deadlock.Deadlock Modeling (1)Modeled with directed graphsResource R assigned to process AProcess B is requesting/waiting for resource SProcess C and D

21、are in deadlock over resources T and U C-T-D-U-CHow deadlock occurs A B CDeadlock Modeling (2)Deadlock Modeling (3)How deadlock can be avoided (o) (p) (q)Methods for Handling DeadlocksIgnore the problem and pretend that deadlocks never occur in the systemAllow the system to enter a deadlock state an

22、d then recoverDeadlock detection & recoveryEnsure that the system will never enter a deadlock stateDynamic avoidance (careful resource allocation)Prevention (negating one of the four necessary conditions)The Ostrich Algorithm Dont do anything, simply restart the system (stick your head into the sand

23、, pretend there is no problem at all).ConsiderHow often will a deadlock happen?How severe will it be if it does happen?How hard would it be to avoid/prevent/detect?Rational: make the common path faster and more reliableDeadlock prevention, avoidance or detection/recovery algorithms are expensiveIf d

24、eadlock occurs only rarely, it is not worth the overhead to implement any of these algorithms. The ostrich algorithm is both Windows and UNIX approved!Deadlock Detection and RecoveryAllow system to enter deadlock state Run the Deadlock Detection algorithm periodicallyAfter detecting deadlock, run a

25、Recovery algorithmDeadlock Detection (1)Check to see if a deadlock has occurred!Single Resource per TypeCheck for cycles Example (next page)Process A holds R and wants S.Process B holds nothing but wants T.Process C holds nothing but wants S.Process D holds U and wants S and T.Process E holds T and

26、wants V.Process F holds W and wants S.Process G holds V and wants U.Is this system deadlocked, and if so, which processes are involved?Deadlock Detection (2)Note the resource ownership and requestsA cycle can be found within the graph, denoting deadlockSingle Resource per Type (ctd.)Example (ctd.)Fi

27、gure 6-5. (a) A resource graph. (b) A cycle extracted from (a).Deadlock Detection (3)Single Resource per Type (ctd.)Deadlock Detection AlgorithmPeriodically invoke an algorithm that searches for a cycle in the graph.1. For each node N in the graph, perform the following 5 steps with N as the startin

28、g node.2. Initialize L to the empty list, and designate all the arcs as unmarked. (L is the list of nodes)3. Add the current node to the end of the L and check to see if the node now appears in L two times. If it does, the graph contains a cycle (listed in L) and the algorithm terminates.Deadlock De

29、tection (4)Single Resource per Type (ctd.)Deadlock Detection Algorithm (ctd.)4. From the given node, see if there are 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 current node and go to step 3.

30、6. If this node is the initial node, the graph does not contain any cycles and the algorithm terminates. Otherwise, we have now reached a dead end. Remove it and go back to the previous node, make that one the current node, and go to step 3. Deadlock Detection (5)Multiple Resources of Each TypeMatri

31、x-based AlgorithmN processes, P1 to PnThe number of resource classes:m Ei: resources of class i (1 i m)E : the existing resource vectorA : the available resource vectorC : the current allocation matrixR : the request matrixDeadlock Detection (6)Figure 6-6 Data structures needed by deadlock detection

32、 algorithm Cij + Aj = Eji=1nDeadlock Detection (7)Look for an unmark process Pi, for which the i-th row of R is less than or equal to A. (Pi s request can be satisfied )If such a process is found, add the i-th row of C to A, mark the process and go back to step 1. ( When Pi completes, its resources

33、will become available ).If no such process exist, the algorithm terminates. The unmarked process, if any, are deadlock.Deadlock Detection AlgorithmBased on comparing vectors.(A B if and only if Ai Bi for 0 i m)Each process is initially unmarked.Deadlock Detection (8)Figure 6-7 An example for the dea

34、dlock detection algorithmDeadlock Detection (9)How often should the detection algorithm be run?Check every time a resource request is made.Possibly expensive in terms of CPU timeCheck every k minutes, or perhaps only when the CPU utilization has dropped below some threshold.Recovery from Deadlock (1

35、)Recovery through preemptionTake a resource from some other processDepends on nature of the resourceRecovery through rollbackCheckpoint a process periodicallyWrite the processs state (memory image &resource state) to a fileUse this saved state Restart the process if it is found deadlockedRecovery fr

36、om Deadlock (2)Recovery through killing processesCrudest but simplest way to break a deadlockKill one of the processes in the deadlock cycle, then the other processes get its resources. Kill the process not in the deadlock cycle,but hold the resources that some process in the cycle needsKill process

37、 that can be rerun from the beginning with no ill effectsDeadlock Avoidance (1)When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.This technique requires that the system would not allocate resources if deadlock could happenVery

38、 conservative since just because deadlock could happen doesnt mean that deadlock will happenRequires that the system has some additional a priori information available.Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.Dead

39、lock Avoidance (2)Figure 6-8 Two process resource trajectoriesResource TrajectoriesUnsafe safesafesafesafesafeUnrea-chable Safe and Unsafe States (1) System is in safe state if there exists a safe sequence of all processes.Sequence is safe if for each Pi, the resources that Pi can still request can

40、be satisfied by currently available resources + resources held by all the Pj, with ji.If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished.When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate.When Pi termin

41、ates, Pi+1 can obtain its needed resources, and so on.When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.Safe and Unsafe States (2)Figure 6-9 Demonstration that the state in (a) is safe(there exists a safe sequence BCA) (a) (b)

42、 (c) (d) (e)Safe and Unsafe States (3)Figure 6-10 Demonstration that the sate in b is not safe (a) (b) (c) (d) Safe and Unsafe States (4) Unsafe StatesBeing in an unsafe state does not guarantee deadlockAn unsafe state merely means that the OS cannot guarantee deadlock will not happenIn other words,

43、 it is out of the hands of the OSFrom a safe state the system can guarantee that all processes will finish; from an unsafe state, no such guarantee can be given.Basic FactsIf a system is in safe state no deadlocks.If a system is in unsafe state possibility of deadlock.Avoidance Dynamically examines

44、the resource-allocation stateEnsure that a system will never enter an unsafe state. Bankers ProblemSuppose total bank capital is 1000Current cash : 1000- (410+210) = 380 Customerc1c2Max. Need800600Present Loan410210Claim390390Dijkstras Bankers Algorithm (1)DefinitionsEach process has a LOAN, CLAIM,

45、MAXIMUM NEEDLOAN: current number of resources heldMAXIMUM NEED: total number resources needed to completeCLAIM: = (MAXIMUM - LOAN)Dijkstras Bankers Algorithm (2)AssumptionsEstablish a LOAN ceiling (MAXIMUM NEED) for each processMAXIMUM NEED not safe. (If several processes are eligible to be chosen,

46、it does not matter which one is selected.)If such a row exists, the process may finish. Mark that process (row) as terminate and add all of its resources to A.Repeat Steps 1 and 2 until all rows are marked = safe state or not marked = not safe.Bankers Algorithm for Multiple Resources (2)Figure 6-12

47、Example of bankers algorithm with multiple resources C RExampleFigure 6-12 is safe stateSuppose that process B now makes a request for the scanner. Can this request be granted?After giving B one scanner, E wants the last scanner. Can this request be granted?Is Allocation (1 0 2) to P1 Safe?If P1 req

48、uests max resources, can completeProcessAllocMaxNeedAvailableABCABCABCABCP00107537431055P1200322122332P2300902602P3211222011P4002433431And Run Safety Test: Group DiscussionIf P1 requests max resources, can completeProcessAllocMaxNeedAvailableABCABCABCABCP00107537431055P1302322020230P2300902602P32112

49、22011P4002433431Allocate to P1, Then Release P1 Finishes Now P3 can acquire max resources and releaseRelease P3 Finishes Now P4 can acquire max resources and releaseProcessAllocMaxNeedAvailableABCABCABCABCP00107537431055P1000322322743P2300902602P4002433431P3000222222Release - P4 Finishes Now P2 can

50、acquire max resources and releaseRelease - P2 Finishes Now P0 can acquire max resources and releaseSo P1 Allocation (1 0 2) Is SafeThere exists a safe sequence: P1, P3, P4, P2, P0Is allocation (0 2 0) to P0 Safe?Try to Allocate 2 B to P0Run Safety TestNo Processes may get max resources and releaseSo

51、 Unsafe State - Do Not EnterReturn to Safe State and do not allocate resourceP0 Suspended Pending RequestWhen enough resources become available, P0 can awakeResultsP0s request for 2 Bs cannot be granted because that would prevent any other process from completing if they need their maximum claim.Jus

52、t Because Its UnsafeP0 could have been allocated 2 Bs and a deadlock might not have occurred if:P1 say didnt use its maximum resources but finished using the resources it hadIf P1 Doesnt Need MaxThen P1 would have finishedProcessAllocMaxNeedAvailableABCABCABCABCP00307537231055P1000322322512P23009026

53、02P3211222011P4002433431Banker Solution IssuesTrade-off: The bankers algorithm is conservative it reduces parallelism for safety sake Not very practicableProcesses rarely know advance what their maximum resource needs will beThe number of processes is not fixedResources that were thought to be avail

54、able can suddenly vanish(tape drive can break)Deadlock Prevention Restrain the ways request can be made.Mutual ExclusionHold and WaitNo PreemptionCircular WaitAttacking the Mutual Exclusion ConditionSome devices (such as printer) can be spooledOnly the printer daemon uses printer resourceThus deadlo

55、ck for printer eliminatedNot all devices can be spooledNot a general solution, but useful neverthelessPrinciple:Avoid assigning resource when not absolutely necessaryAs few processes as possible actually claim the resourceAttacking the Hold and Wait Condition (1)To ensure that the hold-and-wait cond

56、ition never occurs in the system, we must guarantee that, whenever a process requests a resource, it does not hold any other resources.Approach : Require all processes to request all their resources before starting executionIf everything is available, the process will be allocated whatever it needs

57、and can run to completion.If one or more resources are busy, the process will just wait.ProblemsMay not know required resources at start of runResources will not be used optimally. Still done sometimes in the mainframe worldOf course, if we could do that, we could use the Bankers AlgorithmAttacking

58、the Hold and Wait Condition (2)Alternative ApproachProcess must give up all resources, then request all immediately neededDoesnt work if some resources must be heldMain Disadvantages of Two ApproachesResource utilization may be low, since resources may be allocated but unused for a long period.Starv

59、ation is possible. A process that needs several popular resources may have to wait indefinitely, because at least one of the resources that it needs is always allocated to some other process.Attacking the No Preemption Condition (1)Difficult to achieve in practiceCannot take a printer away from a pr

60、ocess in the middle of printingCannot take a semaphore away from a process arbitrarilyMight be in the middle of updating a shared areaCannot take open streams, pipes and sockets awayProcess would need to be written very carefully, probably using signalsvery undesirable if possible at all Attacking t