操作系统概念(英文)

1、2021/3/101Chapter 7 Deadlocks 2021/3/102An Introduction to Chapter 7 (Two parts)nResource-allocation and Deadlocknconcepts of deadlocksnresource-allocation models (7.1)nnecessary conditions for deadlock (7.2.1)ndescriptions of resource-allocation(7.2.2)nMethodologies of deadlock handling (algorithms

2、)nprinciples (7.3)ndeadlock prevention (7.4)ndeadlock avoidance (7.5)ndeadlock detection-recovery (7.6, 7.7)nExercises!2021/3/103 7.0 Concepts of DeadlocknDefinition na situation or system states in which a set of blocked processes each holding a resource and waiting to acquire a resource held by an

3、other process in the set, and these processes will never proceed.nE.g.1nthere are two tape drivers A and B in the systemnP1 and P2 each hold one tape drive and each needs another one.nsemaphores A and B corresponding to two tape drivers respectively, initialized to 1 P1 P2wait (A);wait(B)wait (B);wa

4、it(A)2021/3/104P1P2ABholdsAwaits for AFig.0.1 Deadlock Concept Concepts of Deadlock (cont.)holdsBwaits for B2021/3/105 E.g.2 Bridge Crossing Concepts of Deadlock (cont.)Fig. 7.0.2 2021/3/106ntraffic only in one direction.neach section of a bridge can be viewed as a resource.nif a deadlock occurs, it

5、 can be resolved if one car backs up (preempt resources and rollback).nseveral cars may have to be backed up if a deadlock occurs.nstarvation is possible.nRefer to Appendix 7.A for more details about formal descriptions of deadlocks Concepts of Deadlock (cont.)2021/3/1077.1 System ModelnSystem model

6、 nresource-allocation modelnFinite number of resources in systems, resource types R1, R2, . . ., Rmnphysical resources, e.g., CPU cycles, memory space, I/O devicesnlogical resources, e.g., files, semaphores, monitorsnEach resource type Ri has Wi instances, a number of competing processes request the

7、 instances of resource types.nEach process utilizes a resource as follows:nrequest ( as a system call, in queue of blocked processes waiting for the resource)nuse nrelease ( as a system call)2021/3/108nIf resources are controlled by semaphores, requesting and releasing resources are conducted by wai

8、t and signal operations.nResources can be classified as nsharable resources, being used by processes concurrentlynnon-sharable resources/critical resources, being used by processes exclusively nas far as process synchronization and deadlock are concerned, non-sharable resources are often referred to

9、7.1 System Model (cont.)2021/3/1097.2 Deadlock Characterization7.2.1 Necessary conditions for deadlocknIf deadlock arises, then the following four conditions hold simultaneouslynmutual exclusionna resource ( or a resource instance) can be used at one time by only one process nhold and wait (or部分分配)n

10、a process holding at least one resource is waiting to acquire additional resources held by other processesnno preemptionna resource can be released only voluntarily by the process holding it, after that process has completed its task.2021/3/1010ncircular waitnthere exists a set P0, P1, , P0 of waiti

11、ng processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, , Pn1 is waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0.7.2.1 Necessary Conditions (cont.)P1P2R2R1 requestholdP3R3holdhold request

12、requestFig. 7.0.3 2021/3/1011n Principles of deadlock handlingn if deadlock occurs then (mutual exclusion) and (hold and wait ) and (no preemption) and (circular wait ) n /* 等价逆否命题： if not (mutual exclusion) or not (hold and wait ) or not (no preemption) or not (circular wait ) then deadlock will no

13、t occur 7.2.1 Necessary Conditions (cont.)2021/3/1012n 通过破坏四个必要条件之一，阻止死锁的发生.n 实际系统中主要采取破坏hold and wait 和circular wait的方法n 涉及到n 死锁的预防n 死锁的避免n 死锁的检测与恢复7.2.1 Necessary Conditions (cont.)2021/3/1013 7.2.2 Resource-allocation graph nA system resource allocation graph is a directed graph and consists of a

14、 set of vertices V and a set of edges EnV is partitioned into two typesn P = P1, P2, , Pn, the set consisting of all the processes in the systemnR = R1, R2, , Rm, the set consisting of all resource types in the system.n E is partitioned into two typesn request edge directed edge P1 Rjnassignment edg

15、e directed edge Rj Pi7.2 Deadlock Characterization (cont.)2021/3/1014nRepresentation of resource-allocation graph Enprocess nresource type with 4 instancesnPi requests instance of RjnPi is holding an instance of RjPiRjPiRj7.2.2 Resource-Allocation Graph (cont.)2021/3/1015E.g.1 n Fig.7.2n no cycle ,

16、no deadlockFig.7.27.2.2 Resource-Allocation Graph (cont.)2021/3/1016*P1 R1 P2 R3 P3 R2P1P2 R3 P3 R2P2E.g.2n F.g.7.3n resource allocation graph with a deadlockn two cycles in the graphF.g.7.37.2.2 Resource-Allocation Graph (cont.)2021/3/1017E.g.3 n Fig.7.4n resource allocation graph with a cycle but

17、no deadlockn resource instance of R2 occupied by P4 is released to P3 after being usedFig.7.47.2.2 Resource-Allocation Graph (cont.)2021/3/1018nConclusions !nif the graph contains no cycles no deadlock in the systemnif graph contains a cycle nif only one instance per resource type, then deadlocknif

18、several instances per resource type, possibility of deadlock.7.2.2 Resource-Allocation Graph (cont.)2021/3/10197.3 Methods for Handling Deadlocks Deadlock can be handled in several ways as follows: nEnsure that the system will never enter a deadlock statendeadlock preventionndeadlock avoidance nAllo

19、w the system to enter a deadlock state and then recover.n deadlock detection and recoverynIgnore the problem and pretend that deadlocks never occur in the system, i.e. OS does not handle deadlock.nuser or other systems are responsible for deadlock handlingnused by most operating systems, including U

20、NIX/Linux (?)2021/3/1020 7.4 Deadlock Prevention7.4.1. The principle nEnsuring that at least one of the necessary conditions cannot hold by constraining the ways resources request can be maden /*通过破坏四个必要条件之一，阻止死锁的发生n/*实际系统中主要采取破坏hold and wait 和circular wait的方法.2021/3/10217.4.2 Methodologies for dead

21、lock prevention on the basis of four necessary conditions1. With respect to Mutual Exclusion n Method: nmutual exclusion constraints can be relaxed for not sharable resources (e.g., read-only files), i.e. permitting several processes to access sharable resources simultaneously. nHowever, mutual excl

22、usion constraint must hold for nonsharable resources (e.g., printers).nConclusions ncannot prevent deadlock by denying the mutual-exclusion condition 7.4 Deadlock Prevention (cont.)2021/3/10222. In view of Hold and Wait nMethod must guarantee that whenever a process requests a resource, it does not

23、hold any other resources.nProtocol 1nthe process can only request and be allocated all required resources before it begins execution /* 预先全部分配所需资源nProtocol 2nthe process is allowed to request resources several times during its lifetimenit must release all the resources that it is currently allocated

24、 before it requests any additional resources, e.g. 2PL in DBS 7.4.2 Methodologies for Deadlock Prevention (cont.)Fig. A concurrent schedule S in DBS under 2PL protocol constraints T1wait(A)wait(B) read (A)read (B)signal (B)write (A)signal (A) T2wait (B)read (B)write (B)signal (B)T1和T2并发访问数据向A和Bgrowi

25、ngphaseshrinkingphase2021/3/1024nE.g. P253. processes and tape driver, disk files and printers.nConclusionsnan applicable methodndemerits: low resource utilization; starvation possible.3. In view of No PreemptionnPrinciplen/*允许进程抢占处于waiting态态的进程所占有的资源nTo ensure No Preemption does not hold, the proto

26、col as follows is usednif P1 is now holding some resources R1 and requests another resource R2, which is now occupied by P2 and cannot be immediately allocated to P1, 7.4.2 Methodologies for Deadlock Prevention (cont.)2021/3/1025 for example, P2 is in the running state and using R2, then refer to Fi

27、g. 7.0.4(a)nP1 turns into the waiting state and R1 held by P1 is released npreempted resources R1 is added to the list of resources for which the process P3 is waiting, so the waiting process P3 may be enabled to runnthe resources-preempted process P1 will be restarted only when it can regain its ol

28、d resources, as well as the new ones that it is requesting 7.4.2 Methodologies for Deadlock Prevention (cont.)P1R1P2R2(a) R1 is released and P1 turns into waiting state, thus the waiting process P3 will be enabled to runP1P2R1P3Fig. 7.0.4 R2waiting request request(b) P1 preempts R1 from the waiting

29、process P22021/3/1027n if P1 requests R1 that is not available, and if R1 is allocated to a waiting process P2 that is waiting for another resource R2, thennP1 preempts R1 from the waiting process P2nrefer to Fig. 7.0.4(b) nConclusion n this method can be applied to resources whose state can be easi

30、ly saved and restored later, such as CPU registers and memory 7.4.2 Methodologies for Deadlock Prevention (cont.)2021/3/1028 4. In view of Circular Wait nMethod to ensure this condition cannot holdnimpose a total ordering of all resource typesnrequire that each process requests resources in an incre

31、asing order of enumeration. /* 有序资源使用法nImplementation nR=R1, R2, R3, Rm, nresource ordering function F: RNne.g. F(tape driver) =1, F(disk driver) =5, F(printer) =12 7.4.2 Methodologies for Deadlock Prevention (cont.)2021/3/1029nProtocol 1nif Pi has requests or holds the instances of Ri, then afterwa

32、rds it can only request resource Rj such that F(Rj) F(Ri) /* 按资源序号递增的顺序请求资源PiRjRiF(Rj) F(Ri) 7.4.2 Methodologies for Deadlock Prevention (cont.)2021/3/1030nProtocol 2nwhenever Pi requests an instances of Rj , it must have released all resources Ri such that F(Ri) F(Rj) nConclusionnin line with these

33、 two protocols, the Circular Wait condition cannot hold and the deadlock is preventednmore commonly used, as the basis of deadlock avoidance and detectionPiRjRiF(Ri) F(Rj)F(Rk) F(Rj)Rk 7.4.2 Methodologies for Deadlock Prevention (cont.)2021/3/10317.5 Deadlock Avoidance7.5.0 PrinciplesnAssuming OS re

34、sources allocator knows some additional a priori information about how resources are to be requested by processesneach process declares the maximum number of resources of each type that it may neednWhen a process requests resources, on the basis of these a priori information, the allocator uses dead

35、lock-avoidance algorithm to examines the resource-allocation statento decide whether the current request can be satisfied or must wait to avoid a possible future deadlock. nto ensure that there can never be a circular-wait condition2021/3/1032nResource-allocation state is defined by the number of av

36、ailable and allocated resources, and the maximum demands of the processes.nne.g. 7.5.1 Safe statenIntuitively, system is in safe state if it can allocate resources to processes and still avoid deadlocknWhen a process requests an available resource, the system must decide if immediate allocation leav

37、es the system in a safe state.7.5 Deadlock Avoidance (cont.)2021/3/1033nDefinition nformally, the system is in the safe state only if there exists a safe sequence of all processes executingnsequence is safe for the current allocation state, if for each Pi, the resources that Pi can still request can

38、 be satisfied by currently available resources plus resources held by all the Pj, with j2021/3/1047ntotal resources=(10 5 7)nNeed is defined to be Max AllocationNeed=MAX- Allocationnapply safety algorithm, for sequence Need: A B C Workstep5. P0 7 4 3 (7 4 5) + Allocat 2 =(10 4 7)step1. P1 1 2 2 (3 3

39、 2) Step4. P2 6 0 0 (7 4 3) + Allocat 4 =(7 4 5)step2. P3 0 1 1 (3 3 2) + Allocat 1=(5 3 2)Step3. P4 4 3 1 (5 3 2) + Allocat 3 =(7 4 3)nIn the current situation, the system is in a safe state since the sequence satisfies safety criteria. Bankers Algorithm Example One (cont.) 2021/3/1048ndecide wheth

40、er or not the P1s request(1, 0, 2) can be grantedn request (1, 0, 2) Need1 = (1, 2, 2)ncheck that Request Available (that is, (1, 0, 2) (3, 3, 2) true), (1 0 2) are allocated to P1, and system enters a new safety state Allocation Need AvailableA B C A B C A B C P0 0 1 0 7 4 3 2 3 0P1 3 0 2 0 2 0 P2

41、3 0 1 6 0 0 P3 2 1 1 0 1 1P4 0 0 2 4 3 1 Bankers Algorithm Example One (cont.) 3 3 2 1 0 21 2 2 1 0 22021/3/1049nexecuting safety algorithm shows that sequence satisfies safety requirement Homework:nCan request for (3, 3, 0) by P4 be granted?nCan request for (0, 2, 0) by P0 be granted?Bankers Algori

42、thm Example One (cont.) 2021/3/1050nFor the system described in the following table n(a) is the system in a safe or unsafe state ? Why ?n(b) if P3 request resource of (0, 1, 0, 0), can resources be allocated to it ? Why ? Bankers Algorithm Example TwoprocessCurrent allocationMaximum allocationResour

43、ce availableR1R2R3R4R1R2R3R4R1R2R3R4P100120012 2 1 0 0P220002750P300346656P423544356P503320652 Bankers Algorithm Example Two (cont.) 2021/3/1052nSolution-(a)nthe system is in a safe state, because there exists a safe process sequence n the Need Matrix (=MAX Allocation) is: Bankers Algorithm Example

44、Two (cont.) R1R2R3R4P10000P20750P36622P42002P503202021/3/1053Bankers Algorithm Example Two (cont.) naccording to safety algorithm, nfirstly, Work:=(2, 1, 0, 0), Finishi:=false i:=1, 2, 3, 4, 5nfor i:=1, Need1=(0, 0, 0, 0) Work, Finish1:=true, and Work:=(2, 1, 1, 2)nfor i:=4, Need4=(2, 0, 0, 2) Work,

45、 Finish4:=true, and Work:=(4, 4, 6, 6)nfor i:=5, Need5=(0, 3, 2, 0) Work, Finish5:=true, and Work:=(4, 7, 9, 8)nfor i:=2, Need2=(0, 7, 5, 0) Work, Finish2:=true, and Work:=(6, 7, 9, 8)nfor i:=3, Need3=(6, 6, 2, 2) Work, Finish3:=true, and Work:=(6, 7, 12, 12)nFinishi=true for i:=1, 2, 3, 4, 5, so th

46、e system is in a safe state.2021/3/1054Bankers Algorithm Example Two (cont.) nSolution-(b)nNo, because if the resources are allocated to P3, then the system will be in a unsafe state.nmatrix Allocation , Need , and Available are as follows:2021/3/1055processCurrent allocationNeedAvailableR1R2R3R4R1R

47、2R3R4R1R2R3R4P1001200002000P220000750P301346522P423542002P503320320Bankers Algorithm Example Two (cont.) 2021/3/1056naccording to safety algorithm, nfirstly, Work:= (2, 0, 0, 0) Finishi:=false i:=1, 2, 3, 4, 5nfor i:=1, Need1=(0, 0, 0, 0) Work, Finish1:=true, and Work:=(2, 0, 1, 2)nfor i:=4, Need4=(

48、2, 0, 0, 2) Work, Finish4:=true, and Work:=(4, 3, 6, 6)nfor i:=5, Need5=(0, 3, 2, 0) Work, Finish5:=true, and Work:=(4, 6, 9, 8)nfor i:=2, Need2=(0, 7, 5, 0) Work is not true; and for i:=3, Need3=(6, 5, 2, 2) Work： /* 已经占有资源，又申请新资源，但资源请求目前无法满足，标记暂时仍为Finishi = false； 需要等到以后某一时刻其他进程结束并归还资源后，再判断本进程的资源请

49、求能否得到满足n/* 检测算法考虑 (2), (3) 类进程7.6.2 Detection for Multiple-instance-Resource Systems (cont.)2021/3/1065nAlgorithm stepsnstep1. Initialize:(a) Work = Available(b) For i = 1, 2, , n, if allocationi 0 then Finishi = false /*占有资源, 涉及死锁*/ else Finishi = true /*排除不在环路中、不占有资源/不 导致死锁 的进程 */nstep2. Find an i

50、ndex i such that both:(a) Finishi = false(b) Requesti Work , if no such i exists, go to step 4/ * Pi 可以立即获得资源并执行 */7.6.2 Detection for Multiple-instance-Resource Systems (cont.)2021/3/1066nstep3. Work = Work + Allocationi Finishi = true go to step 2.nstep4. If Finishi = false, for some i, 1 i n, the

51、n: (1) the system is in deadlock state. (2) moreover, if Finishi = false, then Pi is deadlocked. /*当前状态下，不存在一个可分配process sequence（按此序列为进程分配资源，不会导致死锁） */nAlgorithm requires an order of O (mn2) operations to detect whether the system is in deadlocked state. / *为Pi 分配资源使 之执行 */7.6.2 Detection for Multi

52、ple-instance-Resource Systems (cont.)2021/3/1067nFive processes P0 through P4; three resource types A with 7 instances, B with 2 instances, and C with 6 instances.nSnapshot at time T0: Allocation Request Available A B C A B C A B CP0 0 1 0 0 0 0 0 0 0P1 2 0 0 2 0 2P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0

53、0 2 0 0 2An Example2021/3/1068nThe system is not in a deadlock state, becausenthe sequence and will result in Finishi = true for all i. Or: nP2 requests an additional instance of type C.RequestA B C P0 0 0 0 P1 2 0 2 P2 0 0 1 P3 1 0 0 P4 0 0 2An Example (cont.)2021/3/1069nthen the system is in a dea

54、dlock state, processes P1, P2, P3, and P4. is deadlockedAn Example (cont.) Allocation Request Available A B C A B C A B CP0 0 1 0 0 0 0 0 0 0P1 2 0 0 2 0 2P2 3 0 3 0 0 1 P3 2 1 1 1 0 0 P4 0 0 2 0 0 22021/3/1070作业！nFive processes P0 through P4; three resource types A with 6 instances, B with 3 instan

55、ces, and C with 6 instancesnGiven the snapshot at time T0: Allocation Request Available A B C A B C A B CP0 0 1 0 0 0 0 1 0 1P1 2 0 1 2 0 2P2 1 1 1 0 0 2 P3 2 1 1 1 0 0 P4 0 0 2 0 0 22021/3/1071作业 (续)！nAnswer the following questions on the basis of deadlock-detecting algorithmnis the system in a dea

56、dlock-free state? and why?nif P2 requests two additional instance of type A, is there a deadlock in the system, and why? Allocation Request Available A B C A B C A B CP0 0 1 0 0 0 0 1 0 1P1 2 0 1 2 0 2P2 1 1 1 2 0 2 P3 2 1 1 1 0 0 P4 0 0 2 0 0 22021/3/10727.6.3 When and how often to invoke the detec

57、tion algorithmnDepends on /*何时启动算法*/ (7.6.3)nhow often a deadlock is likely to occur?nhow many processes will need to be rolled back?none for each disjoint cyclenif detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph, and so we would not be able to tell which o

58、f the many deadlocked processes “caused” the deadlockDeadlock Detection and Recovery (cont.)2021/3/1073nWhen deadlock recovery occurs, nhandled by operators, ornrecovery automatically bynprocess terminationnresource preemption Detection When and How often (cont.)2021/3/10747.7.1 Process Termination

59、-break the circular waitnHow to terminate the process in deadlock ?nabort (夭折、撤销) all deadlocked processesnabort one process at a time until the deadlock cycle is eliminated.nIn which order should we choose to abort?npriority of the process.nhow long process has computed, and how much longer to completion.nresou