Applied Operating System Concepts Chap 8 Deadlocks 死锁 编写：李培峰 Applied Operating System Concepts

Applied Operating System Concepts 内容 System Model（系统模型） Deadlock Characterization（死锁特征） Methods for Handling Deadlocks（处理死锁的方法） Deadlock Prevention（预防死锁） Deadlock Avoidance（死锁避免） Deadlock Detection （死锁检测） Recovery from Deadlock （死锁恢复） Combined Approach to Deadlock Handling（综合处理方法） Summary（总结） Applied Operating System Concepts

The Deadlock Problem（死锁问题） A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. （一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源） Example （例如） System has 2 tape drives.（系统有两个磁带设备） P1 and P2 each hold one tape drive and each needs another one.（进程P1和P2各占有一个磁带设备并且实际需要两个磁带） Example semaphores A and B, initialized to 1（信号量A，B初始化为1） P1 P2 wait (A); wait(B) wait (B); wait(A) Applied Operating System Concepts

Bridge Crossing Example（过桥的例子） Traffic only in one direction.（只有一个方向） Each section of a bridge can be viewed as a resource. （桥的每一个部分都可以看成资源） If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). （如果死锁发生，它可以由一辆车返回而解决，抢占资源并回退） Several cars may have to be backed upif a deadlock occurs. （如果死锁发生，可能很多车都不得不返回） Starvation is possible.（有可能产生饥饿） Applied Operating System Concepts

Applied Operating System Concepts System Model（系统模型） Resource types （资源类型）R1, R2, . . ., Rm CPU cycles, memory space, I/O devices （CPU周期，内存空间，I/O设备） Each resource type Ri has Wi instances. （每一种资源Ri有Wi 种实例） Each process utilizes a resource as follows （每一个进程如下的利用资源） request （申请） use （使用） Release（释放） Applied Operating System Concepts

Deadlock Characterization（死锁的特性） Deadlock can arise if four conditions hold simultaneously. （四个条件同时出现，死锁将会发生） Mutual exclusion: only one process at a time can use a resource.（互斥：一次只有一个进程可以使用一个资源） Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes. （占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源） No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task. （不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放） Circular wait: there exists a set {P0, P1, …, P0} of waiting 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, …, Pn–1 is waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0.（循环等待：等待资源的进程之间存在环） Applied Operating System Concepts

Resource-Allocation Graph（资源分配图） A set of vertices V and a set of edges E.（一个顶点的集合V和边的集合E） V is partitioned into two types:（V被分为两个部分） P = {P1, P2, …, Pn}, the set consisting of all the processes in the system.（P：含有系统中全部的进程） R = {R1, R2, …, Rm}, the set consisting of all resource types in the system.（R：含有系统中全部的资源） request edge – directed edge P1  Rj（请求边：直接P1  Rj ） assignment edge – directed edge Rj  Pi（分配边：P1  Rj ） Applied Operating System Concepts

Resource-Allocation Graph (Cont.) 资源分配图续 Process进程 Resource Type with 4 instances有四个实例的资源类型 Pi requests instance of Rj （ Pi 请求一个Rj的实例） Pi is holding an instance of Rj（ Pi 持有一个Rj的实例） Pi Rj Pi Rj Applied Operating System Concepts

Example of a Resource Allocation Graph 资源分配图的例子 Applied Operating System Concepts

Resource Allocation Graph With A Deadlock 有死锁的资源分配图 Applied Operating System Concepts

Resource Allocation Graph With A Cycle But No Deadlock 有环但没有死锁的资源分配图 Applied Operating System Concepts

Applied Operating System Concepts Basic Facts（基本事实） 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. （如果一种资源类型有多个实例，可能死锁） Applied Operating System Concepts

Methods for Handling Deadlocks 处理死锁的方法 Ensure that the system will never enter a deadlock state. （确保系统永远不会进入死锁状态） Allow the system to enter a deadlock state and then recover. （允许系统进入死锁状态，然后恢复系统） Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.（忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX） Applied Operating System Concepts

Deadlock Prevention（ 死锁的预防） Restrain the ways request can be made.（抑制死锁发生的必要条件） Mutual Exclusion – not required for sharable resources; must hold for nonsharable resources. （互斥：共享资源不是必须的，必须保持非共享资源） Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources. （占有并等待：必须保证进程申请资源的时候没有占有其他资源） Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none. （要求进程在执行前一次申请全部的资源，只有没有占有资源时才可以分配资源） Low resource utilization; starvation possible. （利用率低，可能出现饥饿） Applied Operating System Concepts

Deadlock Prevention (Cont.) 死锁的预防（续） 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. （进程在重新得到旧的资源的时候可以重新开始） Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.（循环等待：将所有的资源类型放入资源列表中，并且要求进程按照资源表申请资源） Applied Operating System Concepts

Deadlock Avoidance（死锁避免） Requires 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.（一个简单而有效的模型要求每一个进程声明它所需要的资源的最大数） The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.（死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况） Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.（资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量） Applied Operating System Concepts

Applied Operating System Concepts Safe State（安全状态） When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state. （当进程申请一个有效的资源的时候，系统必须确定分配后是安全的） System is in safe state if there exists a safe sequence of all processes. （系统处于安全态，如果存在一个安全序列） Sequence <P1, P2, …, Pn> is safe 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. （进程序列是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数） If Pi resource needs are not immediately available, then Pi can wait until all Pi-1have finished. 如果 Pi 需要的资源不能马上获得，那么Pi 等待直到所有的Pj（j<I）结束。 When Pi-1 is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate. 当Pi-1 结束后， Pi获得所需的资源，执行、返回资源、结束。 When Pi terminates, Pi+1 can obtain its needed resources, and so on. 当Pi结束后， Pi+1获得所需的资源执行，依此类推。 Applied Operating System Concepts

Applied Operating System Concepts Basic Facts（基本事实） 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. （避免：确保系统永远不会进入死锁状态） Applied Operating System Concepts

Safe, unsafe , deadlock state spaces 安全、不安全、死锁状态空间 Applied Operating System Concepts

Applied Operating System Concepts 思考 为什么系统处于不安全状态，但不一定发生死锁？ Applied Operating System Concepts

Banker’s Algorithm（银行家算法） Multiple instances.（多个实例） Each process must a priori claim maximum use. （每一个进程必须事先声明使用的最大量） When a process requests a resource it may have to wait. （当一个进程请求资源，它可能要等待） When a process gets all its resources it must return them in a finite amount of time. （当一个进程得到所有的资源，它必须在有限的时间释放它们） Applied Operating System Concepts

Data Structures for the Banker’s Algorithm 银行家算法的数据结构 Let n = number of processes, and m = number of resources types. N为进程的数目，M为资源类型的数目 Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available. （如果available[j]=k,那么资源Rj有k个实例有效） Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj. （如果Max[I,j]=k,那么进程Pi可以最多请求资源Rj的k个实例） Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj. （如果Allocation[I,j]=k,那么进程Pj当前分配了k个资源Rj的实例） Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task. （如果Need[I,j]=k,那么进程Pj还需要k个资源Rj的实例） Need [i,j] = Max[i,j] – Allocation [i,j]. Applied Operating System Concepts

Safety Algorithm（安全算法） 1. Let Work and Finish be vectors of length m and n, respectively. Initialize（让Work和Finish作为长度为m和n的向量） Work := Available Finish [i] = false for i - 1,3, …, n. 2. Find such i that both: （找到i） (a) Finish [i] = false (b) Needi  Work If no such i exists, go to step 4. 3. Work := Work + Allocationi Finish[i] := true go to step 2. 4. If Finish [i] = true for all i, then the system is in a safe state. Applied Operating System Concepts

Resource-Request Algorithm for Process Pi 进程Pi的资源请求 Requesti = request vector for process Pi. If Requesti [m] = k then process Pi wants k instances of resource type Rjm 1. If Requesti  Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim. 2. If Requesti  Available, go to step 3. Otherwise Pi must wait, since resources are not available. 3. Pretend to allocate requested resources to Pi by modifying the state as follows: Available := Available - Requesti; Allocationi := Allocationi + Requesti; Needi := Needi – Requesti;; If safe  the resources are allocated to Pi. If unsafe  Pi must wait, and the old resource-allocation state is restored Applied Operating System Concepts

Example of Banker’s Algorithm 银行家算法的例子 5 processes P0 through P4; 3 resource types A (10 instances), B (5instances, and C (7 instances).（5个进程P0到P4:3个资源类型A(10个实例），B（5个实例），C（7个实例）） Snapshot at time T0:（时刻Tn的片段） Allocation Max Available A B C A B C 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 Applied Operating System Concepts

Applied Operating System Concepts Example (Cont.)（例子续） The content of the matrix. Need is defined to be Max – Allocation. （矩阵的内容。需要被定义为最大值） Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria. （系统在安全的状态因为序列P1,P3,P4,P2,P0满足了安全的标准） Applied Operating System Concepts

Example (Cont.): P1 request (1,0,2) 例子续 Check that Request  Available (that is, (1,0,2)  (3,3,2)  true. (检查请求小于有效（就是说，(1,0,2) (3,3,2)为真） Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Executing safety algorithm shows that sequence <P1, P3, P4, P0, P2> satisfies safety requirement. （执行安全算法表明序列p1,p3,p4,p0,p2满足要求） 补充作业： Can request for (3,3,0) by P4 be granted?（p4的(3,3,0)可以通过？） Can request for (0,2,0) by P0 be granted?（pn的(0,2,0)可以通过？） Applied Operating System Concepts

Applied Operating System Concepts 思考 为什么银行家算法是保守的？ Applied Operating System Concepts

Deadlock Detection（死锁检测） Allow system to enter deadlock state （允许进入死锁状态） Detection algorithm（检测死锁） Recovery scheme（恢复策略） Applied Operating System Concepts

Single Instance of Each Resource Type 每一种资源类型只有一个实例 Maintain wait-for graph（维护等待图） Nodes are processes.（节点是进程） Pi  Pj if Pi is waiting for Pj. （ Pi  Pj表明Pi在等待Pj. ） Periodically invoke an algorithm that searches for acycle in the graph.（定期调用算法来检查是否有环） An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.（一个检查图中是否有环的算法需要n2的操作来进行，n为图中的节点数） Applied Operating System Concepts

Resource-Allocation Graph And Wait-for Graph 资源分配图和等待图 Corresponding wait-for graph Applied Operating System Concepts

Several Instances of a Resource Type 一个资源类型的多个实例 Available: A vector of length m indicates the number of available resources of each type. （可用：一个向量的长度m代表每一种资源类型有效的数目） Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process. （分配：一个n x m 的矩阵定义了当前分配的每一种资源类型的实例数目） Request: An n x m matrix indicates the current request of each process. If Request [ij] = k, then process Pi is requesting k more instances of resource type. Rj. （请求：一个n x m 的矩阵使命了当前的进程请求。如果Request[ij]=k,那么进程Pi请求k个资源Rj的实例） Applied Operating System Concepts

Detection Algorithm(检测算法） 1. Let Work and Finish be vectors of length m and n, respectively Initialize(让Work和Finish作为长度为m和n的向量） (a) Work := Available (b) For i = 1,2, …, n, if Allocationi  0, then Finish[i] := false;otherwise, Finish[i] := true. 2. Find an index i such that both（找到下标i） (a) Finish[i] = false (b) Requesti  Work If no such i exists, go to step 4. （如果没有这样的i存在，转4） Applied Operating System Concepts

Detection Algorithm (Cont.) 3. Work := Work + Allocationi Finish[i] := true go to step 2. 4. If Finish[i] = false, for some i, 1  i  n, then the system is in deadlock state. Moreover, if Finish[i] = false, then Pi is deadlocked. Algorithm requires an order of m x n2 operations to detect whether the system is in deadlocked state. 算法需要m x n2 的操作来判断是否系统处于死锁状态 Applied Operating System Concepts

Example of Detection Algorithm 检测算法的例子 Five processes P0 through P4; three resource types A (7 instances), B (2 instances), and C (6 instances). （五个进程pn到p4,三个资源类型A（7个实例），B（2个实例）,C（6个实例） Snapshot at time T0（时刻Tn的状态） Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true for all i. Applied Operating System Concepts

Applied Operating System Concepts Example (Cont.)（例子续） P2 requests an additional instance of type C.（P2请求C的实例） Request A B C P0 0 0 0 P1 2 0 1 P2 0 0 1 P3 1 0 0 P4 0 0 2 State of system?（系统的状态） Can reclaim resources held by process P0, but insufficient resources to fulfill other processes; requests. （可以归还Pn所有的资源，但是资源不够完成其他进程的请求） Deadlock exists, consisting of processes P1, P2, P3, and P4. （死锁存在，包括进程P1,P2,P3和P4) Applied Operating System Concepts

Detection-Algorithm Usage 检测算法的应用 When, and how often, to invoke depends on: （何时，如何频度的调用取决于） 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. （如果检测算法被随意的调用，可能图中存在很多的环以至于我们无法判断是哪一个进程引起了死锁的发生） Applied Operating System Concepts

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? （进程是交互的还是批处理） Applied Operating System Concepts

Recovery from Deadlock: Resource Preemption 从死锁中恢复：资源优先级 Selecting a victim – minimize cost. （选择一个：最小化代价） Rollback – return to some safe state, restart process fro that state. （回退：返回到安全的状态，然后重新开始进程） Starvation – same process may always be picked as victim, include number of rollback in cost factor. （饥饿：同样进程的可能总是被选中） Applied Operating System Concepts

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.（对每一类使用适当的技术来处理死锁） Applied Operating System Concepts

Applied Operating System Concepts Summary总结 Deadlock is a problem that can only arise in a system with multiple active asynchronous processes. It is important that the students learn the three basic approaches to deadlock: prevention, avoidance, and detection (although the terms prevention and avoidance are easy to confuse). It can be useful to pose a deadlock problem in human terms and ask why human systems never deadlock. Can the students transfer this understanding of human systems to computer systems? Projects can involve simulation: create a list of jobs consisting of requests and releases of resources (single type or multiple types). Ask the students to allocate the resources to prevent deadlock. This basically involves programming the Banker’s Algorithm. The survey paper by Coffman, Elphick, and Shoshani [1971] is good supplemental reading, but you might also consider having the students go back to the papers by Havender [1968], Habermann [1969], and Holt [1971a]. The last two were published in CACM and so should be readily available. Applied Operating System Concepts

Applied Operating System Concepts 作业 P248 8.3 8.4 P249 8.9 Applied Operating System Concepts