Silberschatz,Galvin,and Gagne?19998.1Applied Operating System Concepts
Module 8,Deadlocks（ 死锁）
System Model（ 系统模型）
Deadlock Characterization（死锁特征）
Methods for Handling Deadlocks（处理死锁的方法）
Deadlock Prevention（预防死锁）
Deadlock Avoidance（死锁避免）
Deadlock Detection （死锁检测）
Recovery from Deadlock （死锁恢复）
Combined Approach to Deadlock Handling（综合处理方法）
Silberschatz,Galvin,and Gagne?19998.2Applied 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）
P0 P1
wait (A); wait(B)
wait (B); wait(A)
Silberschatz,Galvin,and Gagne?19998.3Applied 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.（有可能产生饥饿）
Silberschatz,Galvin,and Gagne?19998.4Applied 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（释放）
Silberschatz,Galvin,and Gagne?19998.5Applied Operating System Concepts
Deadlock Characterization（死锁的特性）
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,…,P 0} 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,…,P n–1 is waiting
for a resource that is held by Pn,and P0 is waiting for a resource
that is held by P0.（循环等待：等待资源的进程之间存在环）
Deadlock can arise if four conditions hold simultaneously.
（四个条件同时出现，死锁将会发生）
Silberschatz,Galvin,and Gagne?19998.6Applied Operating System Concepts
Resource-Allocation Graph（资源分配图）
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 ）
A set of vertices V and a set of edges E.（一个顶点的集合 V和边的集合 E）
Silberschatz,Galvin,and Gagne?19998.7Applied 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
Pi
Rj
Rj
Silberschatz,Galvin,and Gagne?19998.8Applied Operating System Concepts
Example of a Resource Allocation Graph
资源分配图的例子
Silberschatz,Galvin,and Gagne?19998.9Applied Operating System Concepts
Resource Allocation Graph With A Deadlock
有死锁的资源分配图
Silberschatz,Galvin,and Gagne?19998.10Applied Operating System Concepts
Resource Allocation Graph With A Cycle But No Deadlock
有环但没有死锁的资源分配图
Silberschatz,Galvin,and Gagne?19998.11Applied 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.
（如果一种资源类型有多个实例，可能死锁）
Silberschatz,Galvin,and Gagne?19998.12Applied 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）
Silberschatz,Galvin,and Gagne?19998.13Applied Operating System Concepts
Deadlock Prevention（ 死锁的预防）
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.
（利用率低，可能出现饥饿）
Restrain the ways request can be made.（抑制死锁发生的必要条件）
Silberschatz,Galvin,and Gagne?19998.14Applied 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.（循环等待：将所有的资源类型放入资源列表中，并且要求进程按照资源表申请资源）
Silberschatz,Galvin,and Gagne?19998.15Applied Operating System Concepts
Deadlock Avoidance（死锁避免）
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.（资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量）
Requires that the system has some additional a priori information
available.（需要系统有一些额外的信息）
Silberschatz,Galvin,and Gagne?19998.16Applied 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 Pj have finished.
– When Pj is finished,Pi can obtain needed resources,execute,
return allocated resources,and terminate,
– When Pi terminates,Pi+1 can obtain its needed resources,and
so on,
Silberschatz,Galvin,and Gagne?19998.17Applied 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,
（避免：确保系统永远不会进入死锁状态）
Silberschatz,Galvin,and Gagne?19998.18Applied Operating System Concepts
Safe,unsafe,deadlock state spaces
安全、不安全、死锁状态空间
Silberschatz,Galvin,and Gagne?19998.19Applied Operating System Concepts
Resource-Allocation Graph Algorithm
资源分配图算法
Claim edge Pi? Rj indicated that process Pj may request
resource Rj; represented by a dashed line.
(边 Pi? Rj代表进程 Pi申请资源 Ri，表示为虚线）
Claim edge converts to request edge when a process
requests a resource.（一个进程申请资源的时候连一个边）
When a resource is released by a process,assignment edge
reconverts to a claim edge.（当资源被释放的时候，取消边）
Resources must be claimed a priori in the system.
（系统中的资源必须被声明为一个 priori）
Silberschatz,Galvin,and Gagne?19998.20Applied Operating System Concepts
Resource-Allocation Graph For Deadlock Avoidance
死锁避免的资源分配图
Silberschatz,Galvin,and Gagne?19998.21Applied Operating System Concepts
Unsafe State In A Resource-Allocation Graph
不安全的状态图
Silberschatz,Galvin,and Gagne?19998.22Applied 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.
（当一个进程得到所有的资源，它必须在有限的时间释放它们）
Silberschatz,Galvin,and Gagne?19998.23Applied Operating System Concepts
Data Structures for the Banker’s Algorithm
银行家算法的数据结构
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].
Let n = number of processes,and m = number of resources types,
N为进程的数目,M为资源类型的数目
Silberschatz,Galvin,and Gagne?19998.24Applied 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 and i such 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.
Silberschatz,Galvin,and Gagne?19998.25Applied Operating System Concepts
Resource-Request Algorithm for Process Pi
进程 Pi的资源请求
Requesti = request vector for process Pi,If Requesti [j] = k then
process Pi wants k instances of resource type Rj.
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
Silberschatz,Galvin,and Gagne?19998.26Applied 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
Silberschatz,Galvin,and Gagne?19998.27Applied 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满足了安全的标准）
Silberschatz,Galvin,and Gagne?19998.28Applied 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 1 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,pn,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)可以通过？）
Silberschatz,Galvin,and Gagne?19998.29Applied Operating System Concepts
Deadlock Detection（ 死锁检测）
Allow system to enter deadlock state （允许进入死锁状态）
Detection algorithm（检测死锁）
Recovery scheme（恢复策略）
Silberschatz,Galvin,and Gagne?19998.30Applied 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为图中的节点数）
Silberschatz,Galvin,and Gagne?19998.31Applied Operating System Concepts
Resource-Allocation Graph And Wait-for Graph
资源分配图和等待图
Resource-Allocation Graph Corresponding wait-for graph
Silberschatz,Galvin,and Gagne?19998.32Applied 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的实例）
Silberschatz,Galvin,and Gagne?19998.33Applied 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）
Silberschatz,Galvin,and Gagne?19998.34Applied 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 的操作来判断是否系统处于死锁状态
Silberschatz,Galvin,and Gagne?19998.35Applied 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,
Silberschatz,Galvin,and Gagne?19998.36Applied 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)
Silberschatz,Galvin,and Gagne?19998.37Applied 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.
（如果检测算法被随意的调用，可能图中存在很多的环以至于我们无法判断是哪一个进程引起了死锁的发生）
Silberschatz,Galvin,and Gagne?19998.38Applied 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?
（进程是交互的还是批处理）
Silberschatz,Galvin,and Gagne?19998.39Applied 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.
（饥饿：同样进程的可能总是被选中）
Silberschatz,Galvin,and Gagne?19998.40Applied 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.（对每一类使用适当的技术来处理死锁）
Module 8,Deadlocks（ 死锁）
System Model（ 系统模型）
Deadlock Characterization（死锁特征）
Methods for Handling Deadlocks（处理死锁的方法）
Deadlock Prevention（预防死锁）
Deadlock Avoidance（死锁避免）
Deadlock Detection （死锁检测）
Recovery from Deadlock （死锁恢复）
Combined Approach to Deadlock Handling（综合处理方法）
Silberschatz,Galvin,and Gagne?19998.2Applied 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）
P0 P1
wait (A); wait(B)
wait (B); wait(A)
Silberschatz,Galvin,and Gagne?19998.3Applied 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.（有可能产生饥饿）
Silberschatz,Galvin,and Gagne?19998.4Applied 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（释放）
Silberschatz,Galvin,and Gagne?19998.5Applied Operating System Concepts
Deadlock Characterization（死锁的特性）
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,…,P 0} 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,…,P n–1 is waiting
for a resource that is held by Pn,and P0 is waiting for a resource
that is held by P0.（循环等待：等待资源的进程之间存在环）
Deadlock can arise if four conditions hold simultaneously.
（四个条件同时出现，死锁将会发生）
Silberschatz,Galvin,and Gagne?19998.6Applied Operating System Concepts
Resource-Allocation Graph（资源分配图）
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 ）
A set of vertices V and a set of edges E.（一个顶点的集合 V和边的集合 E）
Silberschatz,Galvin,and Gagne?19998.7Applied 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
Pi
Rj
Rj
Silberschatz,Galvin,and Gagne?19998.8Applied Operating System Concepts
Example of a Resource Allocation Graph
资源分配图的例子
Silberschatz,Galvin,and Gagne?19998.9Applied Operating System Concepts
Resource Allocation Graph With A Deadlock
有死锁的资源分配图
Silberschatz,Galvin,and Gagne?19998.10Applied Operating System Concepts
Resource Allocation Graph With A Cycle But No Deadlock
有环但没有死锁的资源分配图
Silberschatz,Galvin,and Gagne?19998.11Applied 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.
（如果一种资源类型有多个实例，可能死锁）
Silberschatz,Galvin,and Gagne?19998.12Applied 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）
Silberschatz,Galvin,and Gagne?19998.13Applied Operating System Concepts
Deadlock Prevention（ 死锁的预防）
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.
（利用率低，可能出现饥饿）
Restrain the ways request can be made.（抑制死锁发生的必要条件）
Silberschatz,Galvin,and Gagne?19998.14Applied 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.（循环等待：将所有的资源类型放入资源列表中，并且要求进程按照资源表申请资源）
Silberschatz,Galvin,and Gagne?19998.15Applied Operating System Concepts
Deadlock Avoidance（死锁避免）
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.（资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量）
Requires that the system has some additional a priori information
available.（需要系统有一些额外的信息）
Silberschatz,Galvin,and Gagne?19998.16Applied 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 Pj have finished.
– When Pj is finished,Pi can obtain needed resources,execute,
return allocated resources,and terminate,
– When Pi terminates,Pi+1 can obtain its needed resources,and
so on,
Silberschatz,Galvin,and Gagne?19998.17Applied 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,
（避免：确保系统永远不会进入死锁状态）
Silberschatz,Galvin,and Gagne?19998.18Applied Operating System Concepts
Safe,unsafe,deadlock state spaces
安全、不安全、死锁状态空间
Silberschatz,Galvin,and Gagne?19998.19Applied Operating System Concepts
Resource-Allocation Graph Algorithm
资源分配图算法
Claim edge Pi? Rj indicated that process Pj may request
resource Rj; represented by a dashed line.
(边 Pi? Rj代表进程 Pi申请资源 Ri，表示为虚线）
Claim edge converts to request edge when a process
requests a resource.（一个进程申请资源的时候连一个边）
When a resource is released by a process,assignment edge
reconverts to a claim edge.（当资源被释放的时候，取消边）
Resources must be claimed a priori in the system.
（系统中的资源必须被声明为一个 priori）
Silberschatz,Galvin,and Gagne?19998.20Applied Operating System Concepts
Resource-Allocation Graph For Deadlock Avoidance
死锁避免的资源分配图
Silberschatz,Galvin,and Gagne?19998.21Applied Operating System Concepts
Unsafe State In A Resource-Allocation Graph
不安全的状态图
Silberschatz,Galvin,and Gagne?19998.22Applied 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.
（当一个进程得到所有的资源，它必须在有限的时间释放它们）
Silberschatz,Galvin,and Gagne?19998.23Applied Operating System Concepts
Data Structures for the Banker’s Algorithm
银行家算法的数据结构
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].
Let n = number of processes,and m = number of resources types,
N为进程的数目,M为资源类型的数目
Silberschatz,Galvin,and Gagne?19998.24Applied 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 and i such 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.
Silberschatz,Galvin,and Gagne?19998.25Applied Operating System Concepts
Resource-Request Algorithm for Process Pi
进程 Pi的资源请求
Requesti = request vector for process Pi,If Requesti [j] = k then
process Pi wants k instances of resource type Rj.
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
Silberschatz,Galvin,and Gagne?19998.26Applied 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
Silberschatz,Galvin,and Gagne?19998.27Applied 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满足了安全的标准）
Silberschatz,Galvin,and Gagne?19998.28Applied 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 1 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,pn,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)可以通过？）
Silberschatz,Galvin,and Gagne?19998.29Applied Operating System Concepts
Deadlock Detection（ 死锁检测）
Allow system to enter deadlock state （允许进入死锁状态）
Detection algorithm（检测死锁）
Recovery scheme（恢复策略）
Silberschatz,Galvin,and Gagne?19998.30Applied 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为图中的节点数）
Silberschatz,Galvin,and Gagne?19998.31Applied Operating System Concepts
Resource-Allocation Graph And Wait-for Graph
资源分配图和等待图
Resource-Allocation Graph Corresponding wait-for graph
Silberschatz,Galvin,and Gagne?19998.32Applied 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的实例）
Silberschatz,Galvin,and Gagne?19998.33Applied 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）
Silberschatz,Galvin,and Gagne?19998.34Applied 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 的操作来判断是否系统处于死锁状态
Silberschatz,Galvin,and Gagne?19998.35Applied 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,
Silberschatz,Galvin,and Gagne?19998.36Applied 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)
Silberschatz,Galvin,and Gagne?19998.37Applied 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.
（如果检测算法被随意的调用，可能图中存在很多的环以至于我们无法判断是哪一个进程引起了死锁的发生）
Silberschatz,Galvin,and Gagne?19998.38Applied 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?
（进程是交互的还是批处理）
Silberschatz,Galvin,and Gagne?19998.39Applied 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.
（饥饿：同样进程的可能总是被选中）
Silberschatz,Galvin,and Gagne?19998.40Applied 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.（对每一类使用适当的技术来处理死锁）
