生产围棋的工人不小心把相等数量的黑子和白子混
在一块，该系统由两个并发执行的进程组成，系统
功能如下,
（ 1）进程 A专门拣黑子，进程 B专门拣白子；
（ 2）每个进程每次只拣一个子，当一个进程在拣
子时不允许另一个进程去拣子
（ 3）当一个进程拣一个子后，必让另一个进程拣
一个子
试用同步原语管理进程，使其能正确实现上述功能。
（假定系统启动时先让进程 A拣子）
P111 5.19
若将读者离开与读者进入分别看成一个进程,
试用同步原语描述进程间关系。
读者进入进程 读者离开进程
进入 注销
登记 离开
一条小河上有一座独木桥，现河东河西都
有人要过桥，同一方向的可连续过桥；某
方向有人过桥时另一方向的人须等待。如
果把每个过桥者看作一个进程，为保证安
全，用信号量协调他们之间的关系。
第七章 死锁 (Deadlock)
1、死锁问题的提出
2、死锁的必要条件
3、死锁的预防
4、死锁的避免和银行家算法
5、死锁的检测
6、死锁的恢复
7.1 死锁问题的提出
死锁是指计算机系统和进程所处的一种状态。
常定义为：在系统中的一组进程，由于竞争
系统资源或由于彼此通信而永远阻塞，我们
称这些进程处于死锁状态。
死锁的现象
A进程 B进程
wait(s1) wait(s2)
wait(s2) wait(s1)
signal(s2) signal(s1)
signal(s1) signal(s2)
死锁的原因
资源不足，竞争资源
进程推进路径不当
申请不同类型资源产生死锁
P1,
…
申请打印机
申请扫描仪
使用
释放打印机
释放扫描仪
…
P2,
…
申请扫描仪
申请打印机
使用
释放打印机
释放扫描仪
…
申请同类资源产生死锁 （如内存）
设有资源 R,R有 m个分配单位，由 n个
进程 P1,P2,…,Pn（ n > m） 共享。假
设每个进程对 R的申请和释放符合下
列原则,
* 一次只能申请一个单位
* 满足总申请后才能使用
* 使用完后一次性释放
m=2,n=3
资源分配不当导致死锁产生
7.2 死锁的必要条件
? 资源的分类
? 死锁的必要条件
一、资源的分类
? 可抢占资源、不可抢占资源
? 共享资源、独享资源
? 可再次使用的永久资源、消耗性的临时资源
二、死锁的必要条件
? 互斥条件,一个资源每次只能给一个进程使用
? 不可抢占条件,资源申请者不能强行从资源占有者手中
夺取资源，资源只能由占有者自愿释放
? 部分分配条件,一个进程在申请新资源的同时保持对原
有资源的占有
? 循环等待条件,存在一个进程等待队列
{P1,P2,…,Pn},
其中 P1等待 P2占有的资源,P2等待 P3占有
的资源,…, Pn等待 P1占有的资源，形成
一个进程等待环路
7.3 死锁的预防
? 在系统设计时确定资源分配算法，保证
不发生死锁。具体的做法是破坏产生死
锁的四个必要条件之一
? 预防死锁是一种较可取 的方法，但资源
的利用率较低。
1、破坏互斥条件
? 互斥是正确使用非共享资源的唯一手段。
? 故不能通过取消互斥来预防死锁。
2、破坏不可抢占条件
适用于状态容易保护，稍后又容易恢复的
资源。如 CPU,内存。
3、破坏部分分配条件
? 采用预先静态分配法：每个进程执行前，
一次分配其所有资源
? 允许进程仅当自己未占有资源时才申请
资源。
4、破坏循环等待条件
? 有序资源分配
为使“循环等待”条件不满足，我们把所有
资源按类型进行排队，并赋予不同的编号。
申请 按序号递增次序进行
每个进程 释放 按序号递减次序进行
优点：较前几种，改善资源的利用率。
缺点：进程实际需求和资源顺序不一致
会造成资源浪费。
例如,1,2,3,…, 10
P1,
申请 1
申请 3
申请 9
…
P2,
申请 1
申请 2
申请 5
…
P3 …… P10
7.4 死锁的避免和银行家算法
? 死锁避免
? 安全状态和不安全状态
? 银行家算法数据结构
? 银行家算法
一、死锁避免定义
在系统运行过程中，对进程发出的每一个
系统能够满足的资源申请进行动态检查,
并根据检查结果决定是否分配资源，若分
配后系统可能发生死锁，则不予分配，否
则予以分配
例 单资源的银行家算法
假定某银行家有一笔资金可供一批顾客借用,
并假定,
? 每个顾客预知他的最大借款总额，且不超过银行
家拥有的可用资金总和。
? 每次借款以一万元为单位。
? 每当顾客提出借口请求，银行家可立即给予，或
让顾客等一段时间。
? 只有当顾客达到他的预定最大借款额时，他才在
有限时间依次归还。
?安全状态：如果在某时刻，银行有
可能使它当时的所有的顾客在以后
有限时间内完成全部成交，则此刻
的状态是安全。
?不安全状态：永远不具有成交的可
能，则为不安全。
C 2
P 4（ 4）
Q 2（ 1）
R 2（ 7）
C,现金 总额,P,Q,R,顾客
C 4
P 4（ 4）
R 2（ 7）
C 8
R 2（ 7） C 10
安全状态
C 1
P 4（ 4）
Q 2（ 1）
R 3（ 6）
C 3
P 4（ 4）
R 3（ 6）
不安全状态
二、安全状态和不安全状态
? 安全状态,指系统能按某种进程顺序如
<P1,P2··PN> 为每个进程分配资源直至
最大需求。
? 不安全状态,在系统中不存在这样的序
列。
三、银行家算法数据结构
? Available,一个长度为 m的 向量，表示每类资源的
可用数目。 如果 Available[j]=k,表明 Rj类资源有 k
个。
? Max,一个 m× n矩阵，定义每个进程的最大资源需
求数，如果 Max[i,j]=k,表示进程 i需要 Rj类资源有 k
个。
? Allocation,一个 m× n矩阵，定义当前分配给每个
进程每类资源的数目。如果 Allocation [i,j]=k,则表
示进程 I获得,Rj类资源有 k个
? Need,一个 m× n矩阵，表示每个进程还需多少资
源。 如果 Need[i,j]=k,表示进程 I还需要 Rj类资源
有 k个。 表示进程 I需要 Rj类资源有 k个
四、银行家算法
设,Requesti是 进程 Pi的 请求向量
当 Pi发出 资源请求后，系统按如下步骤进行检查,
1、如果 Requesti ?Needi 则 go to 2,否则认为出错。
2、如果 Requesti ? Available 则 go to 3,否则表示无
足够资源,Pi等待。
3、系统 进行试探分配，并求该相应数据结构数据
Available,= Available- Requesti
Allocationi,= Allocationi+ Requesti
Needi,= Needi-Requesti
4、系统 执行安全性算法：安全，把资源分配给 Pi，
否则,Pi等待。
安全性算法
1、设 Work 和 Finish是长度分别为 m,n的向量
初始值 Work,=Available, Finishi,= False（ 所有）
2,从进程集合中找到一个能满足下列条件的进程
a,Finishi= False
b,Needi ? Work 如找到 go to 3, 否则 go to 4
3,当进程 Pi 获得资源后，顺利执行，直至完成，并释
放分配给它的资源。 Work,= Work+ Allocationi
Finishi,= True go to 2
4、如果所有进程的 Finishi= True 则表示系统安全，否则
为不安全。
例 1
假定系统中五个进程 {P0··P4}和三种资源
{A,B,C},资源数量分别为 10,5,7，在
T0时刻的资源分配情况如下表。
Max Allocation Need Available
P0 7,5,3 0,1,0 7,4,3 3,3,2
P1 3,2,2 2,0,0 1,2,2
P2 9,0,2 3,0,2 6,0,0
P3 2,2,2 2,1,1 0,1,1
P4 4,3,3 0,0,2 4,3,1
1,T0时刻安全性
Work Need Allocation Work+ Allocation Finish
P1 3 3 2 1 2 2 2 0 0 5 3 2 T
P3 5 3 2 0 1 1 2 1 1 7 4 3 T
P4 7 4 3 4 3 1 0 0 2 7 4 5 T
P2 7 4 5 6 0 0 3 0 2 10 4 7 T
P0 10 4 7 7 4 3 0 1 0 10 5 7 T
T0状态是安全
2,P1请求资源
P1 请求向量 Request1（ 1,0,2）
系统按银行家算法进行检查,
? Request1（ 1,0,2） ?Need1（ 1,2,2）
? Request1（ 1,0,2） ?Available（ 3,3,2）
? 系统先假定为 P1分配资源，并求该数据结构的值
Available = Available- Request1=（ 2,3,0）
Allocation1 = Allocation1+Request1=（ 3,0,2）
Need1 = Need1-Request1,=（ 0,2,0）
? 系统调用安全性算法，检查其安全性
Work Need Allocation Work+ Allocation Finish
P1 2 3 0 0 2 0 3 0 2 5 3 2 T
P3 5 3 2 0 1 1 2 1 1 7 4 3 T
P4 7 4 3 4 3 1 0 0 2 7 4 5 T
P0 7 4 5 7 4 3 0 1 0 7 5 5 T
P2 7 5 5 6 0 0 3 0 2 10 5 7 T
状态是安全,P1的请求能满足
3,P4 请求资源
P4 请求向量 Request4（ 3,3,0）
系统按银行家算法进行检查,
? Request4（ 3,3,0） ?Need4（ 4,3,1）
? Request4（ 3,3,0） ?Available（ 2,3,0）
让 P4等待。
4,P0请求资源
P0请求向量 Request0（ 0,2,0）
系统按银行家算法进行检查,
? Request0（ 0,2,0） ?Need0（ 7,4,3）
? Request0（ 0,2,0） ?Available（ 2,3,0）
? 系统先假定为 P0分配资源，并求该数据结构的值
Available,= Available- Request0=（ 2,1,0）
Allocation0,= Allocation0+Request0=（ 0,3,0）
Need0,= Need0-Request0,=（ 7,2,3）
? 系统调用安全性算法，检查结果为不安全
银行家算法的优缺点
? 本算法要求被分配每类资源数量是固定
不变。
? 本算法要求用户数固定不变。
? 本算法保证所有用户的要求在有限时间
内得到，实时较差。
? 本算法要求用户事先说明他的最大资源
要求，这对用户较难。
7.5 死锁的检测与恢复
? 死锁检测的概念
? 资源分配图
? 资源分配图的化简
? 死锁检测中数据结构
? 检测死锁的算法
? 死锁的恢复
一、死锁检测
允许死锁发生。操作系统不断监视
系统进展情况，判断死锁是否发生。
一旦死锁发生则采取专门的措施，
解除死锁并以最小的代价恢复操作
系统运行
二、资源分配图
用有向图描述进程的死锁
资源分配图表示法
资源类 （资源的不同类型）用方框表示
资源实例 （存在于每个资源中的若干同种
资源）用方框中的黑圆点表示
进程 用圆圈中加进程名表示
分配边,资源实例 ?进程的一条有向边
申请边,进程 ?资源类的一条有向边
有环有死锁
有环无死锁
死锁定理
如果资源分配图中没有环路，则系
统中没有死锁；如果图中存在环路
则系统中可能存在死锁
如果每个资源类中只包含一个资源
实例，则环路是死锁存在的充分必
要条件
三、资源分配图化简
如果一个进程所需的资源都满足，则对该
进程结点化简。
化简的方法：移走所有分配边和申请边。
如果图中所有的进程结点均可化简成为孤
立的结点，则该状态是安全的，否则是不
安全的。
四、死锁检测中数据结构
? 可利用资源 Available,它表示 m类资源中每类资源
可用数目。
? 请求矩阵 Request, 一个 m× n矩阵，用以表示进
程当前对各类资源的请求数目。
? 分配矩阵 Allocation,一个 m× n矩阵，用以表示某
一时刻的资源的分配情况。
? 工作向量 Work,表示系统 可 提供的各类资源的数
目。
? 进程向量 L,记录当前已不占用资源的各进程。
五、检测死锁的算法
? 把 某时刻 t的可用资源向量 Available赋予 Work
? 把不占用资源的进程向量 记入表 L。
? 从进程集合中找到一个 Requesti ?Work的进程，做如下
处理,
1.将其资源分配图化简 Work,= Work+ Allocationi
2.将它记入 L表中
? 若不能把所有进程都记入 L表，则状态 S资源分配图不
可完全化简，该系统发生死锁。
六、死锁的恢复
? 强制性撤消死锁的进程并剥夺资源
撤消的次序,
– 使用最少处理器时间的进程
– 使用最少输出工作量的进程
– 具有最多剩余时间的进程
– 分得最少资源的进程
– 最小优先级的进程
? 挂起和解除挂起
作业 1,
假定一个处理机上执行的作业如下,
作业 提交时间 短暂时间段长度 优先数
1 0 7 3
2 1 4 1
3 2 2 6
4 3 1 4
5 3 5 2
且规定优先数大优先级别高 。
试分别用先来先服务, 时间片 （ 时间片为 2）, 短作业优先,
优先级调度算法 （ 非抢占, 可抢占 ） 调度这些作业, 并计算它
们的平均周转时间 。
作业 2,
设有三个作业, 它们到达系统的时间和计
算时间如下,
J1,8,00到达 计算时间 2个小时
J2,8,30到达 计算时间 1个小时
J3,9,30到达 计算时间 0.5小时
系统采用响应比高者优先调度, 在 9,30开
始调度时, 试写出作业调度次序 。
在一块，该系统由两个并发执行的进程组成，系统
功能如下,
（ 1）进程 A专门拣黑子，进程 B专门拣白子；
（ 2）每个进程每次只拣一个子，当一个进程在拣
子时不允许另一个进程去拣子
（ 3）当一个进程拣一个子后，必让另一个进程拣
一个子
试用同步原语管理进程，使其能正确实现上述功能。
（假定系统启动时先让进程 A拣子）
P111 5.19
若将读者离开与读者进入分别看成一个进程,
试用同步原语描述进程间关系。
读者进入进程 读者离开进程
进入 注销
登记 离开
一条小河上有一座独木桥，现河东河西都
有人要过桥，同一方向的可连续过桥；某
方向有人过桥时另一方向的人须等待。如
果把每个过桥者看作一个进程，为保证安
全，用信号量协调他们之间的关系。
第七章 死锁 (Deadlock)
1、死锁问题的提出
2、死锁的必要条件
3、死锁的预防
4、死锁的避免和银行家算法
5、死锁的检测
6、死锁的恢复
7.1 死锁问题的提出
死锁是指计算机系统和进程所处的一种状态。
常定义为：在系统中的一组进程，由于竞争
系统资源或由于彼此通信而永远阻塞，我们
称这些进程处于死锁状态。
死锁的现象
A进程 B进程
wait(s1) wait(s2)
wait(s2) wait(s1)
signal(s2) signal(s1)
signal(s1) signal(s2)
死锁的原因
资源不足，竞争资源
进程推进路径不当
申请不同类型资源产生死锁
P1,
…
申请打印机
申请扫描仪
使用
释放打印机
释放扫描仪
…
P2,
…
申请扫描仪
申请打印机
使用
释放打印机
释放扫描仪
…
申请同类资源产生死锁 （如内存）
设有资源 R,R有 m个分配单位，由 n个
进程 P1,P2,…,Pn（ n > m） 共享。假
设每个进程对 R的申请和释放符合下
列原则,
* 一次只能申请一个单位
* 满足总申请后才能使用
* 使用完后一次性释放
m=2,n=3
资源分配不当导致死锁产生
7.2 死锁的必要条件
? 资源的分类
? 死锁的必要条件
一、资源的分类
? 可抢占资源、不可抢占资源
? 共享资源、独享资源
? 可再次使用的永久资源、消耗性的临时资源
二、死锁的必要条件
? 互斥条件,一个资源每次只能给一个进程使用
? 不可抢占条件,资源申请者不能强行从资源占有者手中
夺取资源，资源只能由占有者自愿释放
? 部分分配条件,一个进程在申请新资源的同时保持对原
有资源的占有
? 循环等待条件,存在一个进程等待队列
{P1,P2,…,Pn},
其中 P1等待 P2占有的资源,P2等待 P3占有
的资源,…, Pn等待 P1占有的资源，形成
一个进程等待环路
7.3 死锁的预防
? 在系统设计时确定资源分配算法，保证
不发生死锁。具体的做法是破坏产生死
锁的四个必要条件之一
? 预防死锁是一种较可取 的方法，但资源
的利用率较低。
1、破坏互斥条件
? 互斥是正确使用非共享资源的唯一手段。
? 故不能通过取消互斥来预防死锁。
2、破坏不可抢占条件
适用于状态容易保护，稍后又容易恢复的
资源。如 CPU,内存。
3、破坏部分分配条件
? 采用预先静态分配法：每个进程执行前，
一次分配其所有资源
? 允许进程仅当自己未占有资源时才申请
资源。
4、破坏循环等待条件
? 有序资源分配
为使“循环等待”条件不满足，我们把所有
资源按类型进行排队，并赋予不同的编号。
申请 按序号递增次序进行
每个进程 释放 按序号递减次序进行
优点：较前几种，改善资源的利用率。
缺点：进程实际需求和资源顺序不一致
会造成资源浪费。
例如,1,2,3,…, 10
P1,
申请 1
申请 3
申请 9
…
P2,
申请 1
申请 2
申请 5
…
P3 …… P10
7.4 死锁的避免和银行家算法
? 死锁避免
? 安全状态和不安全状态
? 银行家算法数据结构
? 银行家算法
一、死锁避免定义
在系统运行过程中，对进程发出的每一个
系统能够满足的资源申请进行动态检查,
并根据检查结果决定是否分配资源，若分
配后系统可能发生死锁，则不予分配，否
则予以分配
例 单资源的银行家算法
假定某银行家有一笔资金可供一批顾客借用,
并假定,
? 每个顾客预知他的最大借款总额，且不超过银行
家拥有的可用资金总和。
? 每次借款以一万元为单位。
? 每当顾客提出借口请求，银行家可立即给予，或
让顾客等一段时间。
? 只有当顾客达到他的预定最大借款额时，他才在
有限时间依次归还。
?安全状态：如果在某时刻，银行有
可能使它当时的所有的顾客在以后
有限时间内完成全部成交，则此刻
的状态是安全。
?不安全状态：永远不具有成交的可
能，则为不安全。
C 2
P 4（ 4）
Q 2（ 1）
R 2（ 7）
C,现金 总额,P,Q,R,顾客
C 4
P 4（ 4）
R 2（ 7）
C 8
R 2（ 7） C 10
安全状态
C 1
P 4（ 4）
Q 2（ 1）
R 3（ 6）
C 3
P 4（ 4）
R 3（ 6）
不安全状态
二、安全状态和不安全状态
? 安全状态,指系统能按某种进程顺序如
<P1,P2··PN> 为每个进程分配资源直至
最大需求。
? 不安全状态,在系统中不存在这样的序
列。
三、银行家算法数据结构
? Available,一个长度为 m的 向量，表示每类资源的
可用数目。 如果 Available[j]=k,表明 Rj类资源有 k
个。
? Max,一个 m× n矩阵，定义每个进程的最大资源需
求数，如果 Max[i,j]=k,表示进程 i需要 Rj类资源有 k
个。
? Allocation,一个 m× n矩阵，定义当前分配给每个
进程每类资源的数目。如果 Allocation [i,j]=k,则表
示进程 I获得,Rj类资源有 k个
? Need,一个 m× n矩阵，表示每个进程还需多少资
源。 如果 Need[i,j]=k,表示进程 I还需要 Rj类资源
有 k个。 表示进程 I需要 Rj类资源有 k个
四、银行家算法
设,Requesti是 进程 Pi的 请求向量
当 Pi发出 资源请求后，系统按如下步骤进行检查,
1、如果 Requesti ?Needi 则 go to 2,否则认为出错。
2、如果 Requesti ? Available 则 go to 3,否则表示无
足够资源,Pi等待。
3、系统 进行试探分配，并求该相应数据结构数据
Available,= Available- Requesti
Allocationi,= Allocationi+ Requesti
Needi,= Needi-Requesti
4、系统 执行安全性算法：安全，把资源分配给 Pi，
否则,Pi等待。
安全性算法
1、设 Work 和 Finish是长度分别为 m,n的向量
初始值 Work,=Available, Finishi,= False（ 所有）
2,从进程集合中找到一个能满足下列条件的进程
a,Finishi= False
b,Needi ? Work 如找到 go to 3, 否则 go to 4
3,当进程 Pi 获得资源后，顺利执行，直至完成，并释
放分配给它的资源。 Work,= Work+ Allocationi
Finishi,= True go to 2
4、如果所有进程的 Finishi= True 则表示系统安全，否则
为不安全。
例 1
假定系统中五个进程 {P0··P4}和三种资源
{A,B,C},资源数量分别为 10,5,7，在
T0时刻的资源分配情况如下表。
Max Allocation Need Available
P0 7,5,3 0,1,0 7,4,3 3,3,2
P1 3,2,2 2,0,0 1,2,2
P2 9,0,2 3,0,2 6,0,0
P3 2,2,2 2,1,1 0,1,1
P4 4,3,3 0,0,2 4,3,1
1,T0时刻安全性
Work Need Allocation Work+ Allocation Finish
P1 3 3 2 1 2 2 2 0 0 5 3 2 T
P3 5 3 2 0 1 1 2 1 1 7 4 3 T
P4 7 4 3 4 3 1 0 0 2 7 4 5 T
P2 7 4 5 6 0 0 3 0 2 10 4 7 T
P0 10 4 7 7 4 3 0 1 0 10 5 7 T
T0状态是安全
2,P1请求资源
P1 请求向量 Request1（ 1,0,2）
系统按银行家算法进行检查,
? Request1（ 1,0,2） ?Need1（ 1,2,2）
? Request1（ 1,0,2） ?Available（ 3,3,2）
? 系统先假定为 P1分配资源，并求该数据结构的值
Available = Available- Request1=（ 2,3,0）
Allocation1 = Allocation1+Request1=（ 3,0,2）
Need1 = Need1-Request1,=（ 0,2,0）
? 系统调用安全性算法，检查其安全性
Work Need Allocation Work+ Allocation Finish
P1 2 3 0 0 2 0 3 0 2 5 3 2 T
P3 5 3 2 0 1 1 2 1 1 7 4 3 T
P4 7 4 3 4 3 1 0 0 2 7 4 5 T
P0 7 4 5 7 4 3 0 1 0 7 5 5 T
P2 7 5 5 6 0 0 3 0 2 10 5 7 T
状态是安全,P1的请求能满足
3,P4 请求资源
P4 请求向量 Request4（ 3,3,0）
系统按银行家算法进行检查,
? Request4（ 3,3,0） ?Need4（ 4,3,1）
? Request4（ 3,3,0） ?Available（ 2,3,0）
让 P4等待。
4,P0请求资源
P0请求向量 Request0（ 0,2,0）
系统按银行家算法进行检查,
? Request0（ 0,2,0） ?Need0（ 7,4,3）
? Request0（ 0,2,0） ?Available（ 2,3,0）
? 系统先假定为 P0分配资源，并求该数据结构的值
Available,= Available- Request0=（ 2,1,0）
Allocation0,= Allocation0+Request0=（ 0,3,0）
Need0,= Need0-Request0,=（ 7,2,3）
? 系统调用安全性算法，检查结果为不安全
银行家算法的优缺点
? 本算法要求被分配每类资源数量是固定
不变。
? 本算法要求用户数固定不变。
? 本算法保证所有用户的要求在有限时间
内得到，实时较差。
? 本算法要求用户事先说明他的最大资源
要求，这对用户较难。
7.5 死锁的检测与恢复
? 死锁检测的概念
? 资源分配图
? 资源分配图的化简
? 死锁检测中数据结构
? 检测死锁的算法
? 死锁的恢复
一、死锁检测
允许死锁发生。操作系统不断监视
系统进展情况，判断死锁是否发生。
一旦死锁发生则采取专门的措施，
解除死锁并以最小的代价恢复操作
系统运行
二、资源分配图
用有向图描述进程的死锁
资源分配图表示法
资源类 （资源的不同类型）用方框表示
资源实例 （存在于每个资源中的若干同种
资源）用方框中的黑圆点表示
进程 用圆圈中加进程名表示
分配边,资源实例 ?进程的一条有向边
申请边,进程 ?资源类的一条有向边
有环有死锁
有环无死锁
死锁定理
如果资源分配图中没有环路，则系
统中没有死锁；如果图中存在环路
则系统中可能存在死锁
如果每个资源类中只包含一个资源
实例，则环路是死锁存在的充分必
要条件
三、资源分配图化简
如果一个进程所需的资源都满足，则对该
进程结点化简。
化简的方法：移走所有分配边和申请边。
如果图中所有的进程结点均可化简成为孤
立的结点，则该状态是安全的，否则是不
安全的。
四、死锁检测中数据结构
? 可利用资源 Available,它表示 m类资源中每类资源
可用数目。
? 请求矩阵 Request, 一个 m× n矩阵，用以表示进
程当前对各类资源的请求数目。
? 分配矩阵 Allocation,一个 m× n矩阵，用以表示某
一时刻的资源的分配情况。
? 工作向量 Work,表示系统 可 提供的各类资源的数
目。
? 进程向量 L,记录当前已不占用资源的各进程。
五、检测死锁的算法
? 把 某时刻 t的可用资源向量 Available赋予 Work
? 把不占用资源的进程向量 记入表 L。
? 从进程集合中找到一个 Requesti ?Work的进程，做如下
处理,
1.将其资源分配图化简 Work,= Work+ Allocationi
2.将它记入 L表中
? 若不能把所有进程都记入 L表，则状态 S资源分配图不
可完全化简，该系统发生死锁。
六、死锁的恢复
? 强制性撤消死锁的进程并剥夺资源
撤消的次序,
– 使用最少处理器时间的进程
– 使用最少输出工作量的进程
– 具有最多剩余时间的进程
– 分得最少资源的进程
– 最小优先级的进程
? 挂起和解除挂起
作业 1,
假定一个处理机上执行的作业如下,
作业 提交时间 短暂时间段长度 优先数
1 0 7 3
2 1 4 1
3 2 2 6
4 3 1 4
5 3 5 2
且规定优先数大优先级别高 。
试分别用先来先服务, 时间片 （ 时间片为 2）, 短作业优先,
优先级调度算法 （ 非抢占, 可抢占 ） 调度这些作业, 并计算它
们的平均周转时间 。
作业 2,
设有三个作业, 它们到达系统的时间和计
算时间如下,
J1,8,00到达 计算时间 2个小时
J2,8,30到达 计算时间 1个小时
J3,9,30到达 计算时间 0.5小时
系统采用响应比高者优先调度, 在 9,30开
始调度时, 试写出作业调度次序 。
