中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall 第六讲 死锁及其处理 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall.

Presentation on theme: "中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall 第六讲 死锁及其处理 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall."— Presentation transcript:

1 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn 2013Fall
第六讲 死锁及其处理 中国科学技术大学计算机系 陈香兰 2013Fall

2 内容提要 死锁的定义和产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法 Reading 死锁的预防 死锁的避免 死锁的检测与解除
计算机操作系统，汤子瀛，4.6、4.7、4.8节 Operating System Concepts，7Th edition，ch7

3 内容提要 死锁的定义和产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法 死锁的预防 死锁的避免 死锁的检测与解除

4 死锁的定义 Deadlock 死锁 所谓死锁，是指多个进程因竞争资源而造成的一种僵局（Deadly－Embrace），若无外力作用，这些进程将永远不能再向前推进。

5 产生死锁的原因 归结为两点 竞争资源 进程推进顺序非法 为便于讨论，首先给出资源分配图的概念

6 资源分配图（Resource allocation Graph）
死锁可用资源分配图来描述 资源分配图是由一组结点N和一组边E所组成的一个有向图G=(N, E) N=P∪R P是一组进程结点，P={P1,P2,…,P3} R是一组资源结点，R={R1,R2,…,R3} e={Pi,Rj}，或PiRj，资源请求边 e={Rj,Pi}，或RjPi，资源分配边

7 资源分配图的图形表示 使用小圆卷表示一个进程 使用方框表示一个资源类型 使用一个点表示一个资源实例 请求边由进程指向方框；
分配边必须始于方框中的某个点 Pi Rj Pi Rj

8 资源分配图举例

9 发生死锁的资源分配图

10 一、竞争资源引起死锁 可剥夺和非剥夺性资源 竞争非剥夺资源 可剥夺资源，如CPU，内存 不可剥夺资源，如磁带机，打印机 Example：
System has 2 tape drives P1 and P2 each hold one and each needs another one P1 tape1 tape2 P2

11 竞争临时性资源 临时性资源 vs. 永久性资源 S1、S2、S3是临时资源 P1：Release(S1);Request(S3)
不可能发生死锁 P1 S3 S1 P1：Request(S3);Release(S1) P2：Request(S1);Release(S2) P3：Request(S2);Release(S3) 可能发生死锁 P3 P2 S2

12 二、进程推进顺序不当引起死锁 基于进程的异步特性。 进程推进顺序合法 vs. 非法 举例：P1和P2竞争R1和R2

13 内容提要 死锁的定义和产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法 死锁的预防 死锁的避免 死锁的检测与解除

14 产生死锁的必要条件Necessary Conditions
当下列4个必要条件同时具备时，就会产生死锁 互斥条件（Mutual exclusion） 请求和保持条件（Hold and wait） 不剥夺条件（No Preemptive） 环路等待（Circular wait）

15 1、互斥条件 指进程对所分配到的资源进行排它性使用。 对于这样的资源，不妨标记为R： 在一段时间内R只能有一个进程占有，例如P1
若此时还有其他进程（例如P2）要请求资源R，则P2只能被阻塞，直到P1用完后释放资源R R P1 P2

16 2、请求和保持条件 有一个进程（例如P1）已经获得了至少一个资源，但又提出了新的资源要求，而该资源又已经被其他进程所占有，此时P1被阻塞，但P1对已经获得的其他资源保持不放 被请求的其他资源 已经拥有的资源 P1

17 3、不剥夺条件 对进程已经占有的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放

18 4、环路等待条件 发生死锁时，必然存在一个进程-资源的环形链
即存在进程集合 {P0,P1,P2,…,Pn} 其中，P0正在等待P1占用的资源；P1正在等待P2占用的资源；……；Pn正在等待P0占用的资源

19 发生死锁的资源分配图

20 If graph contains no cycles  no deadlock If graph contains a cycle 
关于环和死锁 If graph contains no cycles  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

21 存在环，但没有发生死锁的资源分配图

22 内容提要 死锁的定义和产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法 死锁的预防 死锁的避免 死锁的检测与解除

23 处理死锁的基本方法 Ensure that the system will never enter a deadlock state
Deadlock prevention，死锁的预防 Breaks at least one of the necessary conditions Deadlock avoidance，死锁的避免 For each request, OS decides whether or not the process should wait Allow the system to enter a deadlock state and then recover Deadlock detect & recover 鸵鸟政策： Ignore the problem and pretend that deadlocks never occur in the system Used by most OS, including UNIX

24 内容提要 死锁的定义和产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法 死锁的预防 死锁的避免 死锁的检测与解除

25 预防死锁的方法 破坏死锁的必要条件 对于互斥条件（Mutual Exclusion） 摒弃“请求和保持”条件 摈弃“不剥夺”条件
Not required for sharable resources; Must hold for non-sharable resources 无法破坏 摒弃“请求和保持”条件 摈弃“不剥夺”条件 摒弃“环路等待”条件

26 摒弃“请求和保持”条件 Must guarantee that whenever a process requests a resource, it does not hold any other resources Require process to 1）request and be allocated all its resources before it begins execution, or 2）allow process to request resources only when the process has none 简单、易于实现、安全 缺点：Low resource utilization; starvation possible.

27 摈弃“不剥夺”条件 No Preemption 有的程序重新运行会出问题、周转时间长、降低吞吐量
If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released. Preempted resources are added to the list of resources for which the process is waiting Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting. 有的程序重新运行会出问题、周转时间长、降低吞吐量

28 摒弃“环路等待”条件 Circular Wait 缺点：
Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration. 无法形成环 申请高序号的进程总能获得资源 缺点： 序号限制了扩展性 强制资源使用的顺序，造成被占用资源闲置 降低了方便性

29 内容提要 死锁的定义和产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法 死锁的预防 死锁的避免 死锁的检测与解除

30 死锁的避免 避免死锁的方法是： 将系统的状态划分为安全状态和不安全状态，通过施加一些较弱的限制条件，使得系统始终都处于安全状态 允许进程动态的申请资源，但在分配资源之前要对系统的安全状态进行判定，若分配操作是安全的，则分配；否则不予分配。

31 安全状态的定义： 所谓安全状态，是指系统能按照某种进程顺序 <P1, P2,…, Pn> 来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺序的完成。 称上面的进程序列为安全序列 对于序列<P1, P2,…, Pn>， if for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j<i. 则该序列是安全的。

32 安全状态和不安全状态举例 System has 12 tape drivers
Current is safe, since <P2, P1, P3> is a safe sequence If P3 requests 1 tape driver, and OS allocate one to it, the system enters an unsafe state Process Max request Allocated Available P1 10 5 3 P2 4 2 P3 9 Process Max request Allocated Available P1 10 5 2 P2 4 P3 9 3

33 安全状态和死锁的关系 If a system is in safe state  no deadlocks. If a system is in unsafe state  possibility of deadlock. Avoidance  ensure that a system will never enter an unsafe state.

34 Safe, unsafe , deadlock state spaces

35 Dijkstra的银行家算法 每类资源有多个资源实例 每个进程必须预先声明它所需要的最多资源数 当一个进程申请申请资源时，可能需要等待
当进程申请到所有资源后，必须在有限的时间内释放这些资源 需要设置若干数据结构来表达资源需求和分配情况

36 银行家算法中的数据结构 令 n = 进程数；m = 资源种类数 Available[0..m-1]: 长度为m的向量，可利用资源向量
Available[j] = k  资源Rj有k个空闲资源 Max[0..n-1][0..m-1]: n×m矩阵，最大请求矩阵. Max[i][j] = k 进程Pi最多将申请k个Rj资源 Allocation[0..n-1][0..m-1]: n×m矩阵，分配矩阵 Allocation[i,j] = k 进程Pi当前已经被分配了k个Rj资源 Need[0..n-1][0..m-1]: n×m矩阵，需求矩阵 Need[i][j] = k 进程Pi可能还需要再分配k个Rj资源 Need [i][j] = Max[i][j] – Allocation [i][j].

37 银行家算法 假设在某时刻， 进程Pi发出请求的资源请求向量为Requesti， 若Request[j]=k，即需要k个Rj类型的资源
针对上述请求 首先判断请求是否合法：比较Requesti与Needi 若Requesti≤Needi，合法，继续；不合法，系统出错 其次判断当前请求是否可能立即得到满足： 比较Requesti与Available Requesti ≤ Available，可能，继续；不可能，等待

38 尝试分配：假定将资源分配给进程Pi 执行安全算法，判定安全状态
暂时更新各个数据结构，Available、Allocationi、Needi Available := Available - Requesti; Allocationi := Allocationi + Requesti; Needi := Needi – Requesti; 执行安全算法，判定安全状态 安全，真正分配； 不安全，不予分配，Pi必须等待，返回原来资源分配状态

39 Safety Algorithm 安全检查算法需要两个工作向量 算法步骤如下： WORK，表示可用资源数，随着算法的进行不断发生变化
FINISH，表示经检查能顺利获得资源并运行完毕的进程 算法步骤如下：

40 Work[0..m-1] & Finish[0..n-1], initialize
Work := Available Finish[i] = false for i = 0,1, …, n-1 Find i such that both Finish [i] = false Need[i]  Work If no such i exists, go to step 4 Work := Work + Allocation[i] Finish[i] := true go to step 2 If Finish [i] = true for all i, then the system is in a safe state, else its an unsafe state.

41 Example of Banker’s Algorithm
P = {P0, P1, …, P4}; R={A(10), B(5), C(7)} Snapshot at time T0: Allocation Max Available A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3

42 Example (Cont.) The content of the matrix. Need is defined to be Max-Allocation. The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria. Need A B C P0 P1 P2 P3 P4 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 MAX A B C 7 5 3 － 9 0 2 2 2 2 4 3 3 Allocation A B C 0 1 0 ＝ 3 0 2 2 1 1 0 0 2

43 Available＝3 3 2 WORK Need Allocation Work＋ Allocation Finish A B C P0
7 4 3 0 1 0 P1 1 2 2 2 0 0 P2 6 0 0 3 0 2 P3 0 1 1 2 1 1 P4 4 3 1 0 0 2 5 3 2 true 3 3 2 5 3 2 7 4 3 true 7 4 3 true 7 4 5 < P1, P3, P4, P2, P0> < P1, P3, P4, P0, P2>

44 Example (Cont.): P1 request (1,0,2)
Check that Request  Available ( (1,0,2)  (3,3,2)  true) 由安全判定算法，sequence <P1, P3, P4, P0, P2> satisfies safety requirement. Can request for (3,3,0) by P4 be granted? Can request for (0,2,0) by P0 be granted? Allocation Need Available A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 1 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 假装分配之后 作业

45 内容提要 死锁的定义和产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法 死锁的预防 死锁的避免 死锁的检测与解除

46 Allow system to enter deadlock state
死锁的检测与解除 Allow system to enter deadlock state The system must provide Detection algorithm Recovery scheme

47 Single Instance of Each Resource Type
The detect algorithm Wait-for graph, a variant of the resource-allocation graph Nodes are processes Pi  Pj if Pi is waiting for Pj Deadlock ≡ wait-for graph contains cycle Periodically invoked to search for a cycle in the graph Complexity O(n2), where n is the number of vertices (processes) in the graph

48 单个资源分配图的化简 从资源分配图化简到等待图 Corresponding wait-for graph
Resource-Allocation Graph Corresponding wait-for graph

49 Available[0..m-1], 可利用资源向量 Available[i] the number of resources of Ri
若资源具有多个资源实例 令m = 资源类型个数; n = 进程个数 Available[0..m-1], 可利用资源向量 Available[i] the number of resources of Ri Allocation[0..n-1][0..m-1], n×m矩阵，分配矩阵 Request [0..n-1][0..m-1], n×m矩阵，请求矩阵 The current request of each process Request [i][j] = k Pi is requesting k more instances of Rj

50 Detection Algorithm：检测算法
Work[0..m-1] & Finish[0..n-1], initialize Work := Available For i = 0,1, …, n, if Allocation[i]  0, then Finish[i] := false; otherwise, Finish[i] := true //请求&保持 Find an index i such that both Finish[i] = false Request[i]  Work //请求可以得到满足 If no such i exists, go to step 4 Work := Work + Allocation[i] Finish[i] := true go to step 2 If for some i, 1  i  n, Finish[i] = false, then the system is in deadlock state. Moreover, if Finish[i] = false, then Pi is deadlocked

51 Complexity O(m x n2)

52 Example of Detection Algorithm
P={P0, …, P4}; R={A(7), B(2), C(6)} Snapshot at time T0: Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true for all i. Allocation Request Available A B C P0 0 1 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 P3 2 1 1 1 0 0 P4 0 0 2

53 Example (Cont.) P2 requests an additional instance of type C
State of system? 可以回收 P0当前拥有的资源, 但无法满足其他进程需求. Deadlock exists, consisting of processes P1, P2, P3, and P4 Allocation Request Available A B C P0 0 1 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 1 P3 2 1 1 1 0 0 P4 0 0 2

54 Detection-Algorithm Usage
什么时候，什么频率调用检测算法 How often a deadlock is likely to occur? How many processes will need to be rolled back? one for each disjoint cycle If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock.

55 Recovery from Deadlock
Process Termination Abort all deadlocked processes Abort one process at a time until the deadlock cycle is eliminated. In which order should we choose to abort? Priority of the process How long process has computed, and how much longer to completion Resources the process has used Resources process needs to complete How many processes will need to be terminated Is process interactive or batch?

56 Recovery from Deadlock
Resource Preemption Selecting a victim Minimize cost Rollback return to some safe state, restart process from that state Starvation Same process may always be picked as victim, include number of rollback in cost factor

57 Combined Approach to Deadlock Handling
Combine the three basic approaches Prevention Avoidance Detection allowing the use of the optimal approach for each of resources in the system Partition resources into hierarchically ordered classes Use most appropriate technique for handling deadlocks within each class

58 作业 什么是死锁？产生死锁的原因是什么？ 死锁产生的必要条件是什么？ 处理死锁的方法有哪些？ Ppt中作业