第三章 处理机调度与死锁
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
3.2 调度算法
3.3 实时调度
3.4 多处理机系统中的调度
3.5 产生死锁的原因和必要条件
3.6 预防死锁的方法
3.7 死锁的检测与解除
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
3.1.1 高级、中级和低级调度
3.1.2 调度队列模型
3.1.3 选择调度方式和调度算法的若干原则
第三章 处理机调度与死锁
1,高级调度：
? 又称为 作业调度 或 长程调度 。
? 用于决定把后备队列中的 哪些 作业调入内存, 为
它们创建进程, 分配必要的资源, 再将新创建的
进程排在就绪队列上, 准备执行 。
? 在批处理系统中, 大多配有作业调度, 但在分时
和实时系统中, 却往往不配置作业调度 。 作业调
度的运行频率较低, 通常为几分钟一次 。
3.1.1 高级、中级和低级调度 —— 调度的类型
第三章 处理机调度与死锁
执行作业调度时，需要解决：
（ 1） 一次接纳多少作业：即允许多少个作业同时在
内存中运行。
（ 2） 接纳哪些作业：即哪些作业调入内存，取决于
所采用的算法。
比如先来先服务调度算法；或者是短作业优
先调度算法；还有基于作业优先权的调度算法，响
应比高者优先调度算法等。
第三章 处理机调度与死锁
2,低级调度：
? 又称为 进程调度, 短程调度 。
? 用于决定就绪队列中的 哪个 进程能获得处理器,
并将处理机分配给该进程。
? 进程调度程序是操作系统最为核心的部分，进程
调度策略的优劣直接影响到整个系统的性能。
? 三种类型的操作系统中，都必须配置此级调度。
第三章 处理机调度与死锁
有两类低级调度方式：
(1) 非抢占方式
一旦把处理机分配给某个进程后，让该进程一直
执行，直到该进程完成或者发生某事件而阻塞。
引起进程调度的因素：
? 正在执行的进程执行完毕；
? 执行中的进程因为提出 I/O请求而暂停执行；
? 进程通信或同步过程中执行了原语操作。
第三章 处理机调度与死锁
(2) 抢占方式
当一进程正在处理机上执行时，系统可根据某种
原则暂停它的执行，并将已分配给它的处理机重新
分配给另一个进程。
抢占的原则有：
? 优先权原则,就绪的高优先权进程有权抢占低优
先权进程的 CPU。
? 短作业优先原则,就绪的短作业 (进程 )有权抢占
长作业 (进程 )的 CPU。
? 时间片原则,一个时间片用完后，系统重新进行
进程调度。
第三章 处理机调度与死锁
3,中级调度
? 又称 平衡负载调度, 中程调度 。
? 目的是为了提高内存利用率和系统吞吐量。
? 实质是进程的内外存对换功能：将外存中已具
备运行条件的进程换入内存，而将内存中处于阻
塞状态的某些进程换出至外存。
在三种调度中，进程调度的运行频率最高，
作业调度的周期较长，中级调度的运行频率在上
述两者之间。
第三章 处理机调度与死锁
3.1.2 调度队列模型
根据 os中所引入的调度的类型，形成了三种类
型的调度队列模型：
? 仅有进程调度的调度队列模型；
? 具有高级和低级调度的调度队列模型；
? 同时具有三级调度的调度队列模型。
第三章 处理机调度与死锁
1,仅具有进程调度的调度队列模型
就 绪 队 列
阻 塞 队 列
进程调度 CPU 进程完成
等待事件
交互用户
事
件
出
现
时间片完
第三章 处理机调度与死锁
2,具有高级和低级调度的调度队列模型
就 绪 队 列
进程调度 CPU进程完成
等待事件 1
作业
调度
事件 1出现
时间片完
等待事件 2
事件 2出现 ……
等待事件 n
事件 n出现
后 备 队 列
… …
第三章 处理机调度与死锁
3,同时具有三级调度的调度队列模型
就绪队列 进程调度
CPU
就绪，挂起队列中级调度
阻塞，挂起队列
阻塞队列 等待事件
进程完成
时间片完作业调度
交互型作业
后备队列批量作业
挂起
事件出现
事
件
出
现
第三章 处理机调度与死锁
3.1.3 选择调度方式和调度算法的若干原则
1,面向用户的准则
(1) 周转时间短
? 作业周转时间,作业提交计算机到道作业完成为止
的时间间隔。它是作业在系统里的等待时间与运行
时间之和。
? 平均作业周转时间,
? 带权周转时间,W=T /Ts
注意：带权周转时间总大于 1。
? 平均作业带权周转时间：
? 主要用于评价批处理系统。
??
?
??
?? ?
?
i
i
iTnT
1
1
?
?
?
?
?
?? ?
?
n
i Si
i
T
T
n
W
1
1
T:作业的周转时
间,Ts,作业的运
行时间。
第三章 处理机调度与死锁
(2) 响应时间快
从用户通过键盘提交一个请求到系统首次产生
响应之间的时间间隔称 响应时间 。
主要用于评价分时系统 。
(3) 截止时间的保证
任务必须开始执行的最迟时间或必须完成的最
迟时间称 截止时间 。
主要用于评价实时系统。
(4) 优先权准则
在三种 OS中，都可遵循。
第三章 处理机调度与死锁
2,面向系统的准则
(1)系统吞吐量高
吞吐量,单位时间内系统所完成的作业数。
(2) 处理机利用率好
CPU利用率 =CPU有效工作时间 /CPU总的运行时
间
CPU总的运行时间 =CPU有效工作时间 +CPU空
闲等待时间
(3) 各类资源的平衡利用
第三章 处理机调度与死锁
3.2 调度算法
3.2.1 先来先服务和短作业优先调度算法
3.2.2 高优先权优先调度算法
3.2.3 基于时间片轮转调度算法
第三章 处理机调度与死锁
调度算法,
? 根据系统的资源分配策略所规定的资源分配算
法称为 调度算法 。
? 通常将作业或进程归入各种就绪或阻塞队列。
有的算法适用于作业调度，有的算法适用于进
程调度，有的两者都适应。
第三章 处理机调度与死锁
3.2.1 先来先服务和短作业优先调度算法
? 最简单的调度算法。
? 用于作业调度时,按照作业进入系统的先后次序
来挑选作业，先进入系统的作业优先被挑选。
? 用于进程调度时,按照进程就绪的先后次序来调
度进程。
? 算法容易实现，效率不高，只顾及作业等候时间，
没考虑作业要求服务时间的长短，不利于短作业
而优待了长作业。
1,先来先服务调度算法（ FCFS）
第三章 处理机调度与死锁
例,在单道环境下，某批处理显然有四道作业，已
知他们的进入系统的时刻、估计运算时间如下：
作业 进入时刻 (h) 运行时间 (h)
A
B
C
D
0
1
2
3
1
100
1
100
用 FCFS算法计算作业的运行情况、平均周转时间和
平均带权周转时间：
第三章 处理机调度与死锁
作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转
时间
A
B
C
D
0
1
2
3
1
100
1
100
0
1
101
102
1
101
102
202
1
100
100
199
1
1
100
1.99
平均周转时间 T＝ 100（ h）
平均带权周转时间 T’＝ 26.00（ h）
第三章 处理机调度与死锁
2,短作业 (进程 )优先调度算法（ SJF/ SPF）
? 用于作业调度时,SJF调度算法。以进入系统的作
业所要求的 CPU时间为标准，总选取估计计算时间
最短的作业投入运行。
? 用于进程调度时,SPF调度 算法。从就绪队列中选
出估计运行时间最短的进程，将处理机分配给它。
? 算法易于实现，能有效降低作业的平均等待时间。
缺点是, 对长作业不利，有可能导致长作业（进程）
长期不被调度； 未能依据作业的紧迫程度来划分执
行的优先级 ； 难以准确估计作业（进程）的执行时
间，从而影响调度性能。
第三章 处理机调度与死锁
1 3 5 2 4 运行步骤
例：
第三章 处理机调度与死锁
3.2.2 高优先权优先调度算法
? 用于作业调度时,系统将从后备队列中选择若
干个优先权最高的作业装入内存。
? 用于进程调度时,该算法把处理机分配给就绪
队列中优先权最高的进程。
?非抢占式优先权算法
?抢占式优先权调度算法
第三章 处理机调度与死锁
优先权的类型：
? 静态优先权
在创建进程时确定的，且在进程的整个运行期间保
持不变。
静态优先权法简单易行，但随着进程的推进，其优
先权可能与进程的情况不再相符。
? 动态优先权
在创建进程时所确定的优先权，可以随着进程的推
进而改变。
例如,可以规定就绪进程的优先权随着等待时间的
增长以速度 a 增加；正在执行进程的优先权以速度 b
下降，这样便可防止一个长作业长期垄断处理机。
第三章 处理机调度与死锁
3,高响应比优先调度算法（ HRRF）,
? 实际上是一种 动态优先权 调度算法。
? FCFS与 SJF/SPF是片面的调度算法。 FCFS只
考虑作业等候时间而忽视了作业的计算时间，
SJF /SPF只考虑用户估计的作业计算时间而忽视
了作业等待时间。
? HRRF是介乎这两者之间的折衷算法，既考虑
作业等待时间，又考虑作业的运行时间，既照顾
短作业又不使长作业的等待时间过长，改进了调
度性能。但每次调度前，都要进行响应比的计算，
会增加系统开销。
第三章 处理机调度与死锁
要求服务时间
要求服务时间等待时间优先权 +?
优先权的变化规律可描述为：
由于等待时间与服务时间之和, 就是系统对该作
业的响应时间, 故该优先权又相当于响应比 RP。
据此, 又可表示为：
要求服务时间
响应时间
要求服务时间
要求服务时间等待时间R
P ?
+?
第三章 处理机调度与死锁
? 如果等待时间相同，短作业容易得到较高优先权。
? 长作业等待时间足够长后，也将获得足够高的优
先级。
? 如果要求服务时间相同时，作业的优先权决定与
其等待时间，实现的是先来先服务。
第三章 处理机调度与死锁
例如,以下四个作业先后到达系统进入调度：
作业名 到达时间 所需 CPU时间
作业 1 0 20
作业 2 5 15
作业 3 10 5
作业 4 15 10
第三章 处理机调度与死锁
? FCFS调度算法：
平均作业周转时间 T = (20+30+30+35)/4 = 38.75
平均带权作业周转时间 W =
(20/20+30/15+30/5+35/10)/4 = 3.13
? SJF调度算法：
调度顺序为作业 1,3,4,2，
平均作业周转时间 T=(20+15+20+45)/4 =25
平均带权作业周转时间 W =
(20/20+15/5+25/10+45/15)/4 = 2.25
第三章 处理机调度与死锁
? 高响应比调度算法：
1) 开始只有作业 1，被选中执行时间 20；
2) 作业 1执行完毕，响应比依次为 1+15/15,1+10/5、
1+5/10，作业 3被选中，执行时间 5；
3) 作业 3执行完毕，响应比依次为 1+20/15、
1+10/10，作业 2被选中，执行时间 15；
4) 作业 2执行完毕，作业 4被选中，执行时间 10；
平均作业周转时间 T = (20+15+35+35)/4 = 26.25
平均带权作业周转时间 W =
(20/20+15/5+35/15+35/10)/4 = 2.42
第三章 处理机调度与死锁
3.2.3 基于时间片轮转调度算法
? 把 CPU划分成若干时间片,并且按顺序赋给就绪队
列中的每一个进程，进程轮流占有 CPU，当时间
片用完时，即使进程未执行完毕，系统也剥夺该
进程的 CPU，将该进程排在就绪队列末尾。同时
系统选择另一个进程运行。
? 时间片长度的选取非常重要，时间片长度的选择
会直接影响系统开销和响应时间。
1,时间片轮转法（ RR）
第三章 处理机调度与死锁
2,多级反馈队列调度算法（ FB）
? 将就绪队列分为 N级，每个就绪队列分配给不同的
时间片，队列级别越高，时间片越长，级别越小，
时间片越短；
? 新进程进入内存后，放入第一队列末尾，按 FCFS原
则等待调度，如果在一个时间片结束时没完成，将
该进程转入第二队列末尾重新等待调度执行 …… 如
此下去，当一个长作业从第一级队列降到最后一级
队列时，便在该队列中采取时间片轮转方式运行。
第三章 处理机调度与死锁
? 仅当第一队列空闲时，调度程序才调度第二队列
中的进程运行 …… 类推之，仅当第 1～ (i-1)级队
列均空时，才调度第 i 级队列上的进程执行。
? 如果处理机正在为某队列的进程服务，又有新进
程插入到较高优先级的队列中，则新进程将抢占
正在运行进程的处理机。
第三章 处理机调度与死锁
多级反馈队列调度算法
就绪队列 1
就绪队列 2
就绪队列 3
就绪队列 n
S1
S2
S3
至 CPU
至 CPU
至 CPU
至 CPU
(时间片,S1＜ S2＜ S3)
第三章 处理机调度与死锁
多级反馈队列调度算法性能：
较好的性能，能够较好地满足各种类型用户的
需要。
? 终端型作业用户
? 短批处理作业用户
? 长批处理作业用户
第三章 处理机调度与死锁
3.3 实 时 调 度
3.3.1 实现实时调度的基本条件
3.3.2 实时调度算法的分类
3.3.3 常用的两种实时调度算法
第三章 处理机调度与死锁
1,实时调度
根据实时系统的特点，对实时系统中的调度
有特殊的要求，故引入一种新的调度方式 ——
实时调度 。
3.3.1 实现实时调度的基本条件
第三章 处理机调度与死锁
2,实时系统的特点
? 有限等待时间（决定性）
? 有限响应时间
? 用户控制
? 可靠性高
? 系统出错处理能力强
第三章 处理机调度与死锁
3,实现实时调度的基本条件
? 提供必要的信息
如：就绪时间、开始或完成截止时间、处理时
间、资源要求、绝对或相对优先级（硬实时或软
实时）
? 系统处理能力强
? 采用抢占式调度机制
? 具有快速切换机制
对外部中断的快速响应能力、快速的任务分派
能力
第三章 处理机调度与死锁
3.3.2 实时调度算法的分类
? 根据时实任务性质，分为
?硬实时调度算法
?软实时调度算法
? 根据调度方式，分为 （ √ ）
?非抢占式调度算法
?抢占式调度算法
? 根据调度程序调度时间，分为
?静态调度算法
?动态调度算法
? 在多处理机环境下，分为
?集中式调度算法
?分布式调度算法
第三章 处理机调度与死锁
1,非抢占式调度算法
? 非抢占式轮转调度算法
将实时任务排成轮转队列，调度程序每次选择
队列中的第一个任务运行，当任务自我终止或运
行完成后，此时调度程序选择下一个队首任务运
行；未完成的任务被挂在轮转队列的队尾。
用于要求不太严格的实时控制系统。
? 非抢占式优先调度算法
在就绪队列中，优先级高的任务位于队首，当
任务自我终止或运行完成后，调度程序选择下一
个队首任务运行。
用于有一定要求的实时控制系统。
第三章 处理机调度与死锁
2,抢占式调度算法
? 基于时钟中断的抢占式优先权调度算法
当新到来的实时任务的优先级高于当前任务，
则等到时钟中断到来时，调度程序剥夺当前任
务的执行，将处理机分配给新到的高优先权任
务。
用于大多数的实时系统。
? 立即抢占的优先权调度算法
操作系统能快速相应外部时间中断，一旦出
现外部中断，只要当前任务未处于临界区，便
立即剥夺当前任务的执行，将处理机分配给请
求中断的紧迫任务。
用于实时要求比较严格的实时控制系统。
第三章 处理机调度与死锁
(a) 非抢占轮转调度
当前进程 实时进程
实时进程请求调度 实时进程枪占当前进程，并立即执行
(d) 立即抢占的优先权调度
调度时间
进程 1 进程 2
实时进程要求调度
进程 n 实时进程
调度实时进程运行
(b) 非抢占优先权调度
当前进程 实时进程
实时进程请求调度 当前进程运行完成
调度时间
当前进程
实时进程请求调度 时钟中断到来时
调度
时间
(c) 基于时钟中断抢占的优先权抢占调度
调度
时间
实时进程
图 3-6 实时进程调度
响应时间：数秒至数十秒 响应时间：几十毫秒至几毫秒
响应时间：数秒至数百毫秒 响应时间：几百毫秒至几毫秒
第三章 处理机调度与死锁
3.3.3 常用的两种实时调度算法
1,最早截止时间优先算法（即 EDF算法）
根据任务的 开始截止时间 来确定任务的优先级。
该调度算法首先运行队首进程，即开始截止时间
最近的那个进程。
算法即可采用 非抢占调度方式,也可采用 抢占
调度方式 。
第三章 处理机调度与死锁
1 3 4 2
1 2 3 4
开始截止时间
执行任务
任务到达
t
1 3 4 2
例,非抢占调度方式下的 EDF算法。
第三章 处理机调度与死锁
2,最低松弛度优先算法（即 LLF算法）
根据任务的 紧迫程度 （或松弛程度）来确定任
务的优先级。松弛度最低的任务排在就绪队列的
最前面，调度程序总是选择队列中的首任务执行。
算法主要用于 可抢占调度方式 中。
松弛度 =必须完成时间 - 其本身的运行时间 - 当
前时间
第三章 处理机调度与死锁
例,如果系统中有两个周期性的实时任务 A和 B：
任务 A要求每 20ms执行一次，执行时间为 10ms；
任务 B要求每 50ms执行一次，执行时间为 25ms；
任务 A和 B每次的开始截止时间分别为 A1,A2、
A3… 和 B1,B2,B3… 见图。
第三章 处理机调度与死锁
A1(10) A2(30) A3(50) A4(70) A5(90) A6(110) A7(130) A8
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160
t
B1(25) B2(75) B3(125)
0 10 30 40 45 55 70 80 90 100 110 130 140
A1 A2 A3 A4 A5 A6 A7
B1(20) B1(5) B2(15) B2(10) B3(20)
调度情况：
第三章 处理机调度与死锁
3.4 多处理机系统中的调度
3.4.1 多处理机系统的类型
3.4.2 进程分配方式
3.4.3 进程 (线程 )调度方式
第三章 处理机调度与死锁
多处理机系统
? MPS,MultiProcessor System
? 20世纪 70年代出现
? 多处理机系统,是一个具有两个或多个处理机并
能相互进行通信以协同一个大的给定问题求解的
计算机系统。
第三章 处理机调度与死锁
3.4.1 多处理机系统的类型
? 根据多处理器之间耦合的紧密程度，分为
紧密耦合 MPS
松散耦合 MPS
? 根据系统中所用处理器的相同与否，分为
对称多处理器系统 SMPS
非对称多处理器系统
第三章 处理机调度与死锁
3.4.2 进程分配方式
1,对称式多处理系统中的进程分配方式：
? 静态分配方式
每个 CPU设立一个就绪队列，进程从开始执
行到完成，都在同一个 CPU上。
优点,调度算法开销小。
缺点,容易出现处理机忙闲不均。
? 动态分配方式
各个 CPU采用一个公共就绪队列，队首进程每
次分派到当前空闲的 CPU上执行。
优点,消除个处理机忙闲不均的现象。
缺点,对松散耦合系统，会增加调度开销。
第三章 处理机调度与死锁
2,非对称式多处理系统中的进程分配方式
主－从处理机系统。操作系统核心驻留在主机上，
由主处理机执行调度，从机上只是用户程序；主机
管理一个公共就绪队列，并分派进程给从处理机执
行；各个处理机有固定分工，如执行 OS的系统功能，
I/O处理，应用程序。
优点,系统处理较简单。
缺点,存在不可靠性；当主机太忙时，会出现系统
瓶颈。
克服方法,利用多台处理机（而非一台）来管理整
个系统。
第三章 处理机调度与死锁
? 注重整体运行效率（而不是个别处理机的利用
率）。
? 更多样的调度算法。
? 多处理机访问 OS数据结构时的互斥（对于共
享内存系统）。
? 调度单位广泛采用线程。
3,多处理机调度与单处理机调度的区别
第三章 处理机调度与死锁
3.4.3 进程 (线程 )调度方式
? 指在系统中设置一个公用的进程 (或线程 )队列，
所有的处理器在空闲时，都可自己到该队列中取一
进程 (或线程 )来执行。
? 是最简单、最常用的调度方式，采用单处理机环
境下的调度方式。
? 需要对就绪队列的数据结构进行互斥访问控制。
1,自调度 (self-scheduling)方式：
第三章 处理机调度与死锁
? 优点：
?易将单处理机系统的调度机制移植到多处
理机系统。
?避免处理机忙闲不均的现象。
? 缺点：
?瓶颈问题
?低效性
?线程切换频繁
第三章 处理机调度与死锁
? 为了解决自调度方式中线程被频繁切换的问题。
? 是指将一组相互合作的进程或隶属于同一个进程
的一组线程分配到一组处理器上去同时执行。
? 分配处理机时间时，可采用两种方式：
? 面向所有应用程序平均分配处理机时间
? 面向所有线程平均分配处理机时间
2,成组调度 (gang scheduling)方式
第三章 处理机调度与死锁
两种分配处理器时间的方式：
面向所有应用程序
平均分配处理机时间
面向所有线程
平均分配处理机时间
第三章 处理机调度与死锁
优点：
? 对于一组相互合作的线程，成组调度能够提高这
些线程的执行并行度，有利于减少阻塞和加快推
进速度，最终提高系统的吞吐量。
? 每次调度可以完成多个线程的分派，能够减少调
度次数，从而减少调度的开销。
第三章 处理机调度与死锁
? 是指在一个应用程序执行期间，专门为该应用程
序分配一组处理器，每个线程分配一个 CPU。这
组处理器仅供该应用程序专用，直至该应用程序
执行完成。
? 适用于 CPU数量众多的高度并行系统，单个 CPU
利用率已不太重要。
? 线程的总和不应超过系统中的处理机数目。
? 缺点,有线程阻塞时，造成 CPU的闲置
? 优点,线程执行时不需切换，相应的开销可以大
大减小，推进速度更快。
3,专用处理机分配 (dedicated processor assignment)方式
第三章 处理机调度与死锁
以下是线程数对加速比的影响：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2122 23 24
1
2
3
4
5
6
7
加速比
线程数
矩阵相乘
FFT
0
例,具有 16个处理器的系统，运行两个应用程序：
矩阵 相乘、快速傅立叶变换。
第三章 处理机调度与死锁
3.5 产生死锁的原因和必要条件
3.5.1 产生死锁的原因
3.5.2 产生死锁的必要条件
3.5.3 处理死锁的基本方法
第三章 处理机调度与死锁
死锁的定义
所谓死锁，是指多个进程因竞争资源而造成的
一种 僵局,若无外力作用，这些进程都将不能再
向前推进。
注意,如果死锁发生，会浪费大量系统资源，
甚至导致系统崩溃。
第三章 处理机调度与死锁
3.5.1 产生死锁的原因
一个操作系统基本上是一个资源管理者，它负责
分配不同类型的资源给进程使用。
系统中的资源分两类：
? 可剥夺性资源 — 指资源占有进程虽然需要使用该
资源，但另一个进程却能强行把资源从占有者进程
处抢来。
? 不可剥夺性资源 — 指只有占用者进程不再需要使
用该资源而主动释放资源外, 其它进程不得在占有
者进程使用资源过程中强行抢占 。
1,资源
第三章 处理机调度与死锁
资
源
可剥夺,CPU、主存、硬盘，该资源
可为几个进程共同使用。
不可剥夺,打印机、读卡机、磁带驱
动器，该资源为某个进程独享。
第三章 处理机调度与死锁
永久性资源和临时性资源：
? 永久性资源 —— 可顺序重复使用的资源：如打
印机；
? 临时性资源 —— 由一个进程产生, 被另一进程
使用一短暂时间后便无用的资源：如消息, 故
也称之为消耗性资源 。
第三章 处理机调度与死锁
? 竞争资源 （不可剥夺性、临时性）
当系统中供多个进程共享的资源不足时，将引起
进程对资源的竞争而产生死锁。
? 进程推进顺序不合理
进程在运行过程中具有异步性特征，如果它们之
间的请求和释放资源的顺序不当，也同样会导致进
程产生死锁。
2,死锁产生的根本原因
第三章 处理机调度与死锁
(1) 竞争资源产生的死锁：
R
1
R
2
P
1
P
2
进程
资源
进程
资源
第三章 处理机调度与死锁
… … …
生产出一产品；
P（ empty ）
P（ mutex ）
将产品放入缓冲区；
V（ mutex ）
V（ full ）
… … …
(2) 进程推进顺序不合理产生的死锁：
例 1,生产者 — 消费者问题中，若 PV操作使用不当，
把生产者进程两个 P操作次序互换,先执行 P(mutex)，
后执行 P(empty)，则会引起死锁。
… … …
P（ full ）
P（ mutex ）
从缓冲区取出产品；
V（ mutex ）
V（ empty ）
消费该产品；
… … …
生产者 消费者
第三章 处理机调度与死锁
P2Rel(R1)
P2Rel(R2)
P2Req(R1)
P2Req(R2)
P1Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2)
①
②
③
④
D
例 2,（见书 P91）
第三章 处理机调度与死锁
3.5.2 产生死锁的必要条件
四个必要条件：
? 互斥条件,涉及的资源是非共享的 。
? 请求和保持条件,进程在等待一新资源时继续占
有已分配的资源 。
? 不剥夺条件,不能强行剥夺进程拥有的资源 。
? 环路等待条件,存在一种进程的循环链，链中的
每一个进程已获得的资源同时被链中的下一个进
程所请求。
以上四个条件须同时具备。
第三章 处理机调度与死锁
3.5.3 处理死锁的基本方法
(1) 预防死锁：
? 通过设置某些限制条件，去破坏死锁四个必要
条件中的一个或多个，来防止死锁。
? 较易实现，广泛使用，但由于所施加的限制往
往太严格，可能导致系统资源利用率和系统吞吐
量的降低。
第三章 处理机调度与死锁
(2) 避免死锁：
? 不事先采取限制去破坏产生死锁的条件，而是
在资源的动态分配过程中，用某种方法去防止系
统进入不安全状态，从而避免死锁的发生。
? 实现较难，只需要较弱的限制条件，可获得较
高的资源利用率和系统吞吐量。
第三章 处理机调度与死锁
? 事先并不采取任何限制，允许发生死锁，但可
以通过系统的检测机构及时检测出死锁的发生，
并精确确定与死锁有关的进程和资源。
(3) 检测死锁：
第三章 处理机调度与死锁
? 与检测死锁相配套，用于将进程从死锁状态解
脱出来。
? 常用的方法是 撤消或挂起一些进程 。以回收一
些资源，再将它们分配给处于阻塞状态的进程，
使之转为就绪状态。
? 实现难度大，但可获得较好的资源利用率和系
统吞吐量。
(4) 解除死锁：
第三章 处理机调度与死锁
3.6 死锁的预防和避免
3.6.1 预防死锁
3.6.2 避免死锁
3.6.3 利用银行家算法避免死锁
第三章 处理机调度与死锁
1,摒弃“请求和保持”条件
系统要求所有进程在开始运行之前，要一次性
地申请在整个运行过程中所需的全部资源。若系
统有足够资源则完全分配；否则，进程等待。
3.6.1 预防死锁
优点,简单、易于实现且安全。
基本思想,打破产生死锁的四个必要条件中的
一个或几个。
第三章 处理机调度与死锁
缺点：
? 实用性不强,在许多情况下, 一个进程在执行之
前不可能知道它所需要的全部资源 。 这是由于进
程在执行时是动态的, 不可预测的；
? 资源利用率低,无论所分资源何时用到, 一个进
程只有在占有所需的全部资源后才能执行 。 即使
有些资源最后才被该进程用到一次, 但该进程在
生存期间却一直占有它们, 造成长期占着不用的
状况 。 造成极大的资源浪费；
? 延迟进程的运行,因为进程只有获得了其所需的
全部资源才开始运行, 但有些资源可能长期被其
它进程占用, 导致该进程迟迟不能运行 。
第三章 处理机调度与死锁
2,摒弃“不剥夺”条件
一个已拥有资源的进程, 若它再提出新资源要
求而不能立即得到满足时, 它必须释放已经拥有
的所有资源 。 以后需要时再重新申请 。
缺点,实现复杂、要付出很大的代价。原因：
?一个资源在使用一段时间后被释放，可能会造
成前阶段工作的失效；
?反复地申请和释放资源，又会使进程的执行无
限推迟，从而进一步增加系统的开销，降低系
统的吞吐量。
第三章 处理机调度与死锁
3,摒弃“环路等待”条件
系统中的所有资源都有一个确定的唯一号码,
所有分配请求必须以序号上升的次序进行 。
例如,系统中有下列设备：输入机 (1),打印机 (2)，
穿孔机 (3),磁带机 (4),磁盘 (5)。 有一进程要先后
使用输入机, 磁盘, 打印机, 则它申请设备时要
按输入机, 打印机, 磁盘的顺序申请 。
第三章 处理机调度与死锁
优点：
同前两法相比, 其资源利用率和系统吞吐量
有较明显的改善 。
缺点：
?系统中各类资源的编号必须相对稳定, 限制了
新设备类型的增加；
?进程实际需要资源的顺序不一定与资源的编号
一致, 因此仍会造成资源浪费 。
第三章 处理机调度与死锁
在系统运行过程中，对进程发出的每一个系统
能够满足的资源申请进行动态检查，并根据检查
结果决定是否分配资源，若分配后系统可能发生
死锁，则不予分配，否则予以分配。
把系统的状态分为 安全状态 和 不安全状态,只
要能使系统始终都处于安全状态，便可避免死锁
的发生。
3.6.2 避免死锁
第三章 处理机调度与死锁
1,安全状态
如果系统能按某种顺序 （ P1,P2,…,Pn） 为
每个进程分配其所需的资源, 直至所有进程都能
运行完成, 称系统处于 安全状态 。 若不存在这样
一个安全序列称系统处于 不安全状态 。
其中, <P1,P2,…,Pn> 称为 安全序列 。
第三章 处理机调度与死锁
? 并非所有的不安全状态都导致死锁，但当系统
进入不安全状态后，便可能进而进入死锁状态；
? 只要系统处于安全状态，便可避免进入死锁状
态
? 避免死锁的本质在于,当进行资源分配时，如
何避免进入不安全状态。
第三章 处理机调度与死锁
安全状态举例：
有三个进程 p1,p2,p3,有 12台磁带机 。 P1
共要求 10台, P2共要求 4台, P3共要求 9台 。 在
T0时刻, p1,p2,p3分别获得 5,2,2台, 尚有
3台空闲 。
第三章 处理机调度与死锁
进程 最大需求 已分配 还需 可用
p1 10 5 5 3
p2 4 2 2
p3 9 2 7
经分析，在 T0时刻，系统是安全的。因为存在
一个安全序列 p2,p1,p3。见下图。
第三章 处理机调度与死锁
3.6.3 利用银行家算法避免死锁
? 最有代表性的避免死锁算法，由 Dijkstra提出。
第三章 处理机调度与死锁
1,银行家算法中的数据结构
? 可利用资源向量 Available。 它是一个含有 m个元
素的数组，其中每个元素代表一类可利用资源的
数目。
? 最大需求矩阵 Max。 n*m矩阵，表示 n个进程的
每一个对 m类资源的最大需求。
? 分配矩阵 Allocation。 n*m矩阵，表示每个进程分
配的资源数。
? 需求矩阵 Need。 n*m矩阵，表示每个进程还需要
各类资源数。
第三章 处理机调度与死锁
2,银行家算法描述
当进程 pi提出资源申请时，系统执行下列步骤：
(1) 若 Request[i]≤Need[i]，转 (2)；否则错误返回。
(2) 若 Request[i]≤Available，转 (3)；否则进程等待。
(3) 假设系统分配了资源，则有：
Available:=Available-Request[i];
Allocation[i]:=Allocation[i]+Request[i];
Need[i]:=Need[i]-Request[i]
(4) 执行安全性算法，若系统新状态是安全的，则分
配完成；若系统新状态是不安全的，则恢复原状
态，进程等待。
第三章 处理机调度与死锁
3,安全性算法
为进行安全性检查，设置两个向量：
? 工作向量 Work,表示系统可提供给进程继续运行
所需的各类资源数目，含有 m个元素，在执行安
全算法开始时,Work:=Available;
? Finish,表示系统是否有足够的资源分配给进程，
使之运行完成。开始时先做 Finish[i]:=false; 当有
足够资源分配给进程时，再令 Finish[i]:=true。
第三章 处理机调度与死锁
安全性算法步骤：
(1) Work:=Available;
Finish:=false；
(2) 寻找满足下列条件的 i：
a) Finish[i]=false；
b) Need[i]≤Work ；
若找到，转 (3)；若找不到，则转 (4)。
(3) Work:=Work+Allocation[i]；
Finish[i]:=true；
转 (2)。
(4) 若对所有 i, Finish[i]=true，则系统处于安全状
态，否则处于不安全状态。
第三章 处理机调度与死锁4,银行家算法举例
设系统有五个进程和三类资源，每类资源分别有 10、
5,7。在 T0时刻资源分配情况如图：
第三章 处理机调度与死锁(1) T0时刻的安全性检查：
T0时刻可以找到一个安全序列 {p1,p3,p4,p0,p2}。系统是安全的。
第三章 处理机调度与死锁
(2) T0时刻 P1请求资源，请求向量 Request1(1,0,2)。
执行银行家算法：
① Request1(1,0,2)≤Need1(1,2,2)
② Request1(1,0,2)≤Available(3,3,2)
③ 系统先假定可为 P1分配资源, 并修改 Available,
Allocation1和 Need1向量, 由此形成的资源变化情
况如 图一 所示 。
④ 进行安全性检查：如 图二 所示。可以找到一个
安全序列 { p1,p3,p4,p0,p2 }。故系统是安全的，
可以将 P1的请求分配给它 。
第三章 处理机调度与死锁图一：
第三章 处理机调度与死锁图二：
第三章 处理机调度与死锁
(3) P4请求资源，请求向量 Request4(3,3,0)。
执行银行家算法,
① Request4(3,3,0) ≤ Need4(4,3,1);
② Request4(3,3,0) ≤ Available(2,3,0);
所以 P4等待 。 P4的请求不能分配 。
第三章 处理机调度与死锁
(4) P0请求资源,请求向量 Request0(0,2,0)
Request0(0,2,0)，执行银行家算法：
① Request0(0,2,0)≤Need0(7,4,3);
② Request0(0,2,0)≤Available(2,3,0);
③ 系统暂时先假定可为 P0分配资源，并修改 图一 有
关数据，如后图所示。
④ 进行安全性检查,Available{2,1,0}已不能满足任
何进程需要，所以系统进入不安全状态,P0的请
求不能分配。
第三章 处理机调度与死锁
第三章 处理机调度与死锁
3.7 死锁的检测与解除
3.7.1 死锁的检测
3.7.2 死锁的解除
第三章 处理机调度与死锁
死锁检测与解除是指系统设有专门的机构，
当死锁发生时，该机构能够检测到死锁发生的
位置和原因，并能通过外力破坏死锁发生的必
要条件，从而使得并发进程从死锁状态中恢复
出来。
第三章 处理机调度与死锁
允许死锁发生，操作系统不断监视系统进展情
况，判断死锁是否发生。
一旦死锁发生则采取专门的措施，解除死锁并
以最小的代价恢复操作系统运行。
3.7.1 死锁的检测
第三章 处理机调度与死锁
1,资源分配图
用来描述系统资源及资源的申请和分配情况的
有向图。
定义为,二元组 G=（ V,E）
其中：
V：结点集，分为 P(进程集合 ),R(资源集合 )两
部分。即 P={p1,p2,…,pn} ； R={r1,r2,…,rm} 。
E：边的集合，其元素为有序二元组 (pi,rj) 或
(rj,pi) 。
第三章 处理机调度与死锁
资源请求边,e={pi,rj}
进程 ?资源的一条有向边
表示进程 pi申请 rj类资源中的一个资源。
资源分配边,e={rj,pi}
资源 ?进程的一条有向边
表示 rj类中的一个资源已被进程 pi占用。
第三章 处理机调度与死锁
例：
R1 R2
P2 P3 P4
P1 P1
P2
r1 r2
请求 r2
资源请求边
资源分配边
第三章 处理机调度与死锁
(1) 如果资源分配图中无环路，则此时系统没有发
生死锁。
(2) 如果资源分配图中有环路，且每个资源类中仅
有一个资源，则 系统中发生了死锁,此时，环路是
系统发生死锁的充要条件，环路中的进程便为死锁
进程。
(3) 如果资源分配图中有环路，且涉及的资源类中
有多个资源，则环路的存在只是产生死锁的 必要条
件而不是充分条件 。
第三章 处理机调度与死锁
可以利用把 资源分配图加以简化 的方法，来检测
系统是否为死锁状态。简化方法如下：
（ 1） 在资源分配图中，找 — 个进程 pi，其请求边均
能立即得到满足。
（ 2） 若找到这样的 pi，则将与 pi相连的边全部删去，
转（ 1）。否则过程结束。
如果简化后，所有进程都成为孤立结点，则称该
图是 可完全简化 的；否则，称该图是 不可完全简化 。
第三章 处理机调度与死锁
死锁状态的 充分条件 是：当且仅当资源分配图是
不可完全简化的。
2,死锁定理
第三章 处理机调度与死锁例：
P1
P4
R2R1
P2 P3
P1
P4
R2R1
P2 P3
P1
P4
R2R1
P2 P3
P1
P4
R2R1
P2 P3
P1
P4
R2R1
P2 P3
第三章 处理机调度与死锁
3,死锁检测算法 —— 数据结构
? 可利用资源向量 Available：表示 m类资源中的每
个资源的可用数目。
? 请求向量 Request：表示为当前进程对各类资源
的请求数目。
? 分配矩阵 Allocation，表示资源的分配情况。
? 工作向量 Work：表示系统课提供给进程继续执
行的 m类资源数目。
? 进程向量 L：表示当前已不占有资源的各个进程。
第三章 处理机调度与死锁
死锁检测算法 —— 算法描述
Work:=Available;
L:= {Li|Allocationi=0∩Requesti=0}
for all Li L do
begin
for all Requesti≤Work do
begin
Work:=Work+Allocationi;
Li∪ L;
end
end
deadlock:= ? (L={p1,p2,…,p n});
?
第三章 处理机调度与死锁
3.7.2 死锁的解除
? 剥夺资源
强迫从其它进程剥夺足够数量的资源给死锁进程，
直至死锁不存在。
? 撤消进程
终止参与死锁的进程，收回它们占有的资源，从
而解除死锁。又分两种情况：
? 一次性撤消参与死锁的全部进程，剥夺全部资
源。
? 逐步撤消参与死锁的进程，直至有足够的资源
可用。
第三章 处理机调度与死锁
思考题：
设系统有五个进程 A,B,C,D,E共享四类资
源 R1,R2,R3,R4，进程对资源的需求量和目前
分配情况如下表，若系统还剩余资源数分别为
(2,6,2,1)，请按银行家算法回答下列问题：
(1) 目前系统是否出于安全状态？
(2) 现在如果进程 D提出申请 (2,5,0,0)各资源，系统
是否能为他分配资源？
第三章 处理机调度与死锁
进程 已占资源数 最大需求数R1 R2 R3 R4 R1 R2 R3 R4
A 3 6 2 0 5 6 2 0
B 1 0 2 0 1 0 2 0
C 1 0 4 0 5 6 6 0
D 0 0 0 1 5 7 0 1
E 5 3 4 1 5 3 6 2
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
3.2 调度算法
3.3 实时调度
3.4 多处理机系统中的调度
3.5 产生死锁的原因和必要条件
3.6 预防死锁的方法
3.7 死锁的检测与解除
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
3.1.1 高级、中级和低级调度
3.1.2 调度队列模型
3.1.3 选择调度方式和调度算法的若干原则
第三章 处理机调度与死锁
1,高级调度：
? 又称为 作业调度 或 长程调度 。
? 用于决定把后备队列中的 哪些 作业调入内存, 为
它们创建进程, 分配必要的资源, 再将新创建的
进程排在就绪队列上, 准备执行 。
? 在批处理系统中, 大多配有作业调度, 但在分时
和实时系统中, 却往往不配置作业调度 。 作业调
度的运行频率较低, 通常为几分钟一次 。
3.1.1 高级、中级和低级调度 —— 调度的类型
第三章 处理机调度与死锁
执行作业调度时，需要解决：
（ 1） 一次接纳多少作业：即允许多少个作业同时在
内存中运行。
（ 2） 接纳哪些作业：即哪些作业调入内存，取决于
所采用的算法。
比如先来先服务调度算法；或者是短作业优
先调度算法；还有基于作业优先权的调度算法，响
应比高者优先调度算法等。
第三章 处理机调度与死锁
2,低级调度：
? 又称为 进程调度, 短程调度 。
? 用于决定就绪队列中的 哪个 进程能获得处理器,
并将处理机分配给该进程。
? 进程调度程序是操作系统最为核心的部分，进程
调度策略的优劣直接影响到整个系统的性能。
? 三种类型的操作系统中，都必须配置此级调度。
第三章 处理机调度与死锁
有两类低级调度方式：
(1) 非抢占方式
一旦把处理机分配给某个进程后，让该进程一直
执行，直到该进程完成或者发生某事件而阻塞。
引起进程调度的因素：
? 正在执行的进程执行完毕；
? 执行中的进程因为提出 I/O请求而暂停执行；
? 进程通信或同步过程中执行了原语操作。
第三章 处理机调度与死锁
(2) 抢占方式
当一进程正在处理机上执行时，系统可根据某种
原则暂停它的执行，并将已分配给它的处理机重新
分配给另一个进程。
抢占的原则有：
? 优先权原则,就绪的高优先权进程有权抢占低优
先权进程的 CPU。
? 短作业优先原则,就绪的短作业 (进程 )有权抢占
长作业 (进程 )的 CPU。
? 时间片原则,一个时间片用完后，系统重新进行
进程调度。
第三章 处理机调度与死锁
3,中级调度
? 又称 平衡负载调度, 中程调度 。
? 目的是为了提高内存利用率和系统吞吐量。
? 实质是进程的内外存对换功能：将外存中已具
备运行条件的进程换入内存，而将内存中处于阻
塞状态的某些进程换出至外存。
在三种调度中，进程调度的运行频率最高，
作业调度的周期较长，中级调度的运行频率在上
述两者之间。
第三章 处理机调度与死锁
3.1.2 调度队列模型
根据 os中所引入的调度的类型，形成了三种类
型的调度队列模型：
? 仅有进程调度的调度队列模型；
? 具有高级和低级调度的调度队列模型；
? 同时具有三级调度的调度队列模型。
第三章 处理机调度与死锁
1,仅具有进程调度的调度队列模型
就 绪 队 列
阻 塞 队 列
进程调度 CPU 进程完成
等待事件
交互用户
事
件
出
现
时间片完
第三章 处理机调度与死锁
2,具有高级和低级调度的调度队列模型
就 绪 队 列
进程调度 CPU进程完成
等待事件 1
作业
调度
事件 1出现
时间片完
等待事件 2
事件 2出现 ……
等待事件 n
事件 n出现
后 备 队 列
… …
第三章 处理机调度与死锁
3,同时具有三级调度的调度队列模型
就绪队列 进程调度
CPU
就绪，挂起队列中级调度
阻塞，挂起队列
阻塞队列 等待事件
进程完成
时间片完作业调度
交互型作业
后备队列批量作业
挂起
事件出现
事
件
出
现
第三章 处理机调度与死锁
3.1.3 选择调度方式和调度算法的若干原则
1,面向用户的准则
(1) 周转时间短
? 作业周转时间,作业提交计算机到道作业完成为止
的时间间隔。它是作业在系统里的等待时间与运行
时间之和。
? 平均作业周转时间,
? 带权周转时间,W=T /Ts
注意：带权周转时间总大于 1。
? 平均作业带权周转时间：
? 主要用于评价批处理系统。
??
?
??
?? ?
?
i
i
iTnT
1
1
?
?
?
?
?
?? ?
?
n
i Si
i
T
T
n
W
1
1
T:作业的周转时
间,Ts,作业的运
行时间。
第三章 处理机调度与死锁
(2) 响应时间快
从用户通过键盘提交一个请求到系统首次产生
响应之间的时间间隔称 响应时间 。
主要用于评价分时系统 。
(3) 截止时间的保证
任务必须开始执行的最迟时间或必须完成的最
迟时间称 截止时间 。
主要用于评价实时系统。
(4) 优先权准则
在三种 OS中，都可遵循。
第三章 处理机调度与死锁
2,面向系统的准则
(1)系统吞吐量高
吞吐量,单位时间内系统所完成的作业数。
(2) 处理机利用率好
CPU利用率 =CPU有效工作时间 /CPU总的运行时
间
CPU总的运行时间 =CPU有效工作时间 +CPU空
闲等待时间
(3) 各类资源的平衡利用
第三章 处理机调度与死锁
3.2 调度算法
3.2.1 先来先服务和短作业优先调度算法
3.2.2 高优先权优先调度算法
3.2.3 基于时间片轮转调度算法
第三章 处理机调度与死锁
调度算法,
? 根据系统的资源分配策略所规定的资源分配算
法称为 调度算法 。
? 通常将作业或进程归入各种就绪或阻塞队列。
有的算法适用于作业调度，有的算法适用于进
程调度，有的两者都适应。
第三章 处理机调度与死锁
3.2.1 先来先服务和短作业优先调度算法
? 最简单的调度算法。
? 用于作业调度时,按照作业进入系统的先后次序
来挑选作业，先进入系统的作业优先被挑选。
? 用于进程调度时,按照进程就绪的先后次序来调
度进程。
? 算法容易实现，效率不高，只顾及作业等候时间，
没考虑作业要求服务时间的长短，不利于短作业
而优待了长作业。
1,先来先服务调度算法（ FCFS）
第三章 处理机调度与死锁
例,在单道环境下，某批处理显然有四道作业，已
知他们的进入系统的时刻、估计运算时间如下：
作业 进入时刻 (h) 运行时间 (h)
A
B
C
D
0
1
2
3
1
100
1
100
用 FCFS算法计算作业的运行情况、平均周转时间和
平均带权周转时间：
第三章 处理机调度与死锁
作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转
时间
A
B
C
D
0
1
2
3
1
100
1
100
0
1
101
102
1
101
102
202
1
100
100
199
1
1
100
1.99
平均周转时间 T＝ 100（ h）
平均带权周转时间 T’＝ 26.00（ h）
第三章 处理机调度与死锁
2,短作业 (进程 )优先调度算法（ SJF/ SPF）
? 用于作业调度时,SJF调度算法。以进入系统的作
业所要求的 CPU时间为标准，总选取估计计算时间
最短的作业投入运行。
? 用于进程调度时,SPF调度 算法。从就绪队列中选
出估计运行时间最短的进程，将处理机分配给它。
? 算法易于实现，能有效降低作业的平均等待时间。
缺点是, 对长作业不利，有可能导致长作业（进程）
长期不被调度； 未能依据作业的紧迫程度来划分执
行的优先级 ； 难以准确估计作业（进程）的执行时
间，从而影响调度性能。
第三章 处理机调度与死锁
1 3 5 2 4 运行步骤
例：
第三章 处理机调度与死锁
3.2.2 高优先权优先调度算法
? 用于作业调度时,系统将从后备队列中选择若
干个优先权最高的作业装入内存。
? 用于进程调度时,该算法把处理机分配给就绪
队列中优先权最高的进程。
?非抢占式优先权算法
?抢占式优先权调度算法
第三章 处理机调度与死锁
优先权的类型：
? 静态优先权
在创建进程时确定的，且在进程的整个运行期间保
持不变。
静态优先权法简单易行，但随着进程的推进，其优
先权可能与进程的情况不再相符。
? 动态优先权
在创建进程时所确定的优先权，可以随着进程的推
进而改变。
例如,可以规定就绪进程的优先权随着等待时间的
增长以速度 a 增加；正在执行进程的优先权以速度 b
下降，这样便可防止一个长作业长期垄断处理机。
第三章 处理机调度与死锁
3,高响应比优先调度算法（ HRRF）,
? 实际上是一种 动态优先权 调度算法。
? FCFS与 SJF/SPF是片面的调度算法。 FCFS只
考虑作业等候时间而忽视了作业的计算时间，
SJF /SPF只考虑用户估计的作业计算时间而忽视
了作业等待时间。
? HRRF是介乎这两者之间的折衷算法，既考虑
作业等待时间，又考虑作业的运行时间，既照顾
短作业又不使长作业的等待时间过长，改进了调
度性能。但每次调度前，都要进行响应比的计算，
会增加系统开销。
第三章 处理机调度与死锁
要求服务时间
要求服务时间等待时间优先权 +?
优先权的变化规律可描述为：
由于等待时间与服务时间之和, 就是系统对该作
业的响应时间, 故该优先权又相当于响应比 RP。
据此, 又可表示为：
要求服务时间
响应时间
要求服务时间
要求服务时间等待时间R
P ?
+?
第三章 处理机调度与死锁
? 如果等待时间相同，短作业容易得到较高优先权。
? 长作业等待时间足够长后，也将获得足够高的优
先级。
? 如果要求服务时间相同时，作业的优先权决定与
其等待时间，实现的是先来先服务。
第三章 处理机调度与死锁
例如,以下四个作业先后到达系统进入调度：
作业名 到达时间 所需 CPU时间
作业 1 0 20
作业 2 5 15
作业 3 10 5
作业 4 15 10
第三章 处理机调度与死锁
? FCFS调度算法：
平均作业周转时间 T = (20+30+30+35)/4 = 38.75
平均带权作业周转时间 W =
(20/20+30/15+30/5+35/10)/4 = 3.13
? SJF调度算法：
调度顺序为作业 1,3,4,2，
平均作业周转时间 T=(20+15+20+45)/4 =25
平均带权作业周转时间 W =
(20/20+15/5+25/10+45/15)/4 = 2.25
第三章 处理机调度与死锁
? 高响应比调度算法：
1) 开始只有作业 1，被选中执行时间 20；
2) 作业 1执行完毕，响应比依次为 1+15/15,1+10/5、
1+5/10，作业 3被选中，执行时间 5；
3) 作业 3执行完毕，响应比依次为 1+20/15、
1+10/10，作业 2被选中，执行时间 15；
4) 作业 2执行完毕，作业 4被选中，执行时间 10；
平均作业周转时间 T = (20+15+35+35)/4 = 26.25
平均带权作业周转时间 W =
(20/20+15/5+35/15+35/10)/4 = 2.42
第三章 处理机调度与死锁
3.2.3 基于时间片轮转调度算法
? 把 CPU划分成若干时间片,并且按顺序赋给就绪队
列中的每一个进程，进程轮流占有 CPU，当时间
片用完时，即使进程未执行完毕，系统也剥夺该
进程的 CPU，将该进程排在就绪队列末尾。同时
系统选择另一个进程运行。
? 时间片长度的选取非常重要，时间片长度的选择
会直接影响系统开销和响应时间。
1,时间片轮转法（ RR）
第三章 处理机调度与死锁
2,多级反馈队列调度算法（ FB）
? 将就绪队列分为 N级，每个就绪队列分配给不同的
时间片，队列级别越高，时间片越长，级别越小，
时间片越短；
? 新进程进入内存后，放入第一队列末尾，按 FCFS原
则等待调度，如果在一个时间片结束时没完成，将
该进程转入第二队列末尾重新等待调度执行 …… 如
此下去，当一个长作业从第一级队列降到最后一级
队列时，便在该队列中采取时间片轮转方式运行。
第三章 处理机调度与死锁
? 仅当第一队列空闲时，调度程序才调度第二队列
中的进程运行 …… 类推之，仅当第 1～ (i-1)级队
列均空时，才调度第 i 级队列上的进程执行。
? 如果处理机正在为某队列的进程服务，又有新进
程插入到较高优先级的队列中，则新进程将抢占
正在运行进程的处理机。
第三章 处理机调度与死锁
多级反馈队列调度算法
就绪队列 1
就绪队列 2
就绪队列 3
就绪队列 n
S1
S2
S3
至 CPU
至 CPU
至 CPU
至 CPU
(时间片,S1＜ S2＜ S3)
第三章 处理机调度与死锁
多级反馈队列调度算法性能：
较好的性能，能够较好地满足各种类型用户的
需要。
? 终端型作业用户
? 短批处理作业用户
? 长批处理作业用户
第三章 处理机调度与死锁
3.3 实 时 调 度
3.3.1 实现实时调度的基本条件
3.3.2 实时调度算法的分类
3.3.3 常用的两种实时调度算法
第三章 处理机调度与死锁
1,实时调度
根据实时系统的特点，对实时系统中的调度
有特殊的要求，故引入一种新的调度方式 ——
实时调度 。
3.3.1 实现实时调度的基本条件
第三章 处理机调度与死锁
2,实时系统的特点
? 有限等待时间（决定性）
? 有限响应时间
? 用户控制
? 可靠性高
? 系统出错处理能力强
第三章 处理机调度与死锁
3,实现实时调度的基本条件
? 提供必要的信息
如：就绪时间、开始或完成截止时间、处理时
间、资源要求、绝对或相对优先级（硬实时或软
实时）
? 系统处理能力强
? 采用抢占式调度机制
? 具有快速切换机制
对外部中断的快速响应能力、快速的任务分派
能力
第三章 处理机调度与死锁
3.3.2 实时调度算法的分类
? 根据时实任务性质，分为
?硬实时调度算法
?软实时调度算法
? 根据调度方式，分为 （ √ ）
?非抢占式调度算法
?抢占式调度算法
? 根据调度程序调度时间，分为
?静态调度算法
?动态调度算法
? 在多处理机环境下，分为
?集中式调度算法
?分布式调度算法
第三章 处理机调度与死锁
1,非抢占式调度算法
? 非抢占式轮转调度算法
将实时任务排成轮转队列，调度程序每次选择
队列中的第一个任务运行，当任务自我终止或运
行完成后，此时调度程序选择下一个队首任务运
行；未完成的任务被挂在轮转队列的队尾。
用于要求不太严格的实时控制系统。
? 非抢占式优先调度算法
在就绪队列中，优先级高的任务位于队首，当
任务自我终止或运行完成后，调度程序选择下一
个队首任务运行。
用于有一定要求的实时控制系统。
第三章 处理机调度与死锁
2,抢占式调度算法
? 基于时钟中断的抢占式优先权调度算法
当新到来的实时任务的优先级高于当前任务，
则等到时钟中断到来时，调度程序剥夺当前任
务的执行，将处理机分配给新到的高优先权任
务。
用于大多数的实时系统。
? 立即抢占的优先权调度算法
操作系统能快速相应外部时间中断，一旦出
现外部中断，只要当前任务未处于临界区，便
立即剥夺当前任务的执行，将处理机分配给请
求中断的紧迫任务。
用于实时要求比较严格的实时控制系统。
第三章 处理机调度与死锁
(a) 非抢占轮转调度
当前进程 实时进程
实时进程请求调度 实时进程枪占当前进程，并立即执行
(d) 立即抢占的优先权调度
调度时间
进程 1 进程 2
实时进程要求调度
进程 n 实时进程
调度实时进程运行
(b) 非抢占优先权调度
当前进程 实时进程
实时进程请求调度 当前进程运行完成
调度时间
当前进程
实时进程请求调度 时钟中断到来时
调度
时间
(c) 基于时钟中断抢占的优先权抢占调度
调度
时间
实时进程
图 3-6 实时进程调度
响应时间：数秒至数十秒 响应时间：几十毫秒至几毫秒
响应时间：数秒至数百毫秒 响应时间：几百毫秒至几毫秒
第三章 处理机调度与死锁
3.3.3 常用的两种实时调度算法
1,最早截止时间优先算法（即 EDF算法）
根据任务的 开始截止时间 来确定任务的优先级。
该调度算法首先运行队首进程，即开始截止时间
最近的那个进程。
算法即可采用 非抢占调度方式,也可采用 抢占
调度方式 。
第三章 处理机调度与死锁
1 3 4 2
1 2 3 4
开始截止时间
执行任务
任务到达
t
1 3 4 2
例,非抢占调度方式下的 EDF算法。
第三章 处理机调度与死锁
2,最低松弛度优先算法（即 LLF算法）
根据任务的 紧迫程度 （或松弛程度）来确定任
务的优先级。松弛度最低的任务排在就绪队列的
最前面，调度程序总是选择队列中的首任务执行。
算法主要用于 可抢占调度方式 中。
松弛度 =必须完成时间 - 其本身的运行时间 - 当
前时间
第三章 处理机调度与死锁
例,如果系统中有两个周期性的实时任务 A和 B：
任务 A要求每 20ms执行一次，执行时间为 10ms；
任务 B要求每 50ms执行一次，执行时间为 25ms；
任务 A和 B每次的开始截止时间分别为 A1,A2、
A3… 和 B1,B2,B3… 见图。
第三章 处理机调度与死锁
A1(10) A2(30) A3(50) A4(70) A5(90) A6(110) A7(130) A8
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160
t
B1(25) B2(75) B3(125)
0 10 30 40 45 55 70 80 90 100 110 130 140
A1 A2 A3 A4 A5 A6 A7
B1(20) B1(5) B2(15) B2(10) B3(20)
调度情况：
第三章 处理机调度与死锁
3.4 多处理机系统中的调度
3.4.1 多处理机系统的类型
3.4.2 进程分配方式
3.4.3 进程 (线程 )调度方式
第三章 处理机调度与死锁
多处理机系统
? MPS,MultiProcessor System
? 20世纪 70年代出现
? 多处理机系统,是一个具有两个或多个处理机并
能相互进行通信以协同一个大的给定问题求解的
计算机系统。
第三章 处理机调度与死锁
3.4.1 多处理机系统的类型
? 根据多处理器之间耦合的紧密程度，分为
紧密耦合 MPS
松散耦合 MPS
? 根据系统中所用处理器的相同与否，分为
对称多处理器系统 SMPS
非对称多处理器系统
第三章 处理机调度与死锁
3.4.2 进程分配方式
1,对称式多处理系统中的进程分配方式：
? 静态分配方式
每个 CPU设立一个就绪队列，进程从开始执
行到完成，都在同一个 CPU上。
优点,调度算法开销小。
缺点,容易出现处理机忙闲不均。
? 动态分配方式
各个 CPU采用一个公共就绪队列，队首进程每
次分派到当前空闲的 CPU上执行。
优点,消除个处理机忙闲不均的现象。
缺点,对松散耦合系统，会增加调度开销。
第三章 处理机调度与死锁
2,非对称式多处理系统中的进程分配方式
主－从处理机系统。操作系统核心驻留在主机上，
由主处理机执行调度，从机上只是用户程序；主机
管理一个公共就绪队列，并分派进程给从处理机执
行；各个处理机有固定分工，如执行 OS的系统功能，
I/O处理，应用程序。
优点,系统处理较简单。
缺点,存在不可靠性；当主机太忙时，会出现系统
瓶颈。
克服方法,利用多台处理机（而非一台）来管理整
个系统。
第三章 处理机调度与死锁
? 注重整体运行效率（而不是个别处理机的利用
率）。
? 更多样的调度算法。
? 多处理机访问 OS数据结构时的互斥（对于共
享内存系统）。
? 调度单位广泛采用线程。
3,多处理机调度与单处理机调度的区别
第三章 处理机调度与死锁
3.4.3 进程 (线程 )调度方式
? 指在系统中设置一个公用的进程 (或线程 )队列，
所有的处理器在空闲时，都可自己到该队列中取一
进程 (或线程 )来执行。
? 是最简单、最常用的调度方式，采用单处理机环
境下的调度方式。
? 需要对就绪队列的数据结构进行互斥访问控制。
1,自调度 (self-scheduling)方式：
第三章 处理机调度与死锁
? 优点：
?易将单处理机系统的调度机制移植到多处
理机系统。
?避免处理机忙闲不均的现象。
? 缺点：
?瓶颈问题
?低效性
?线程切换频繁
第三章 处理机调度与死锁
? 为了解决自调度方式中线程被频繁切换的问题。
? 是指将一组相互合作的进程或隶属于同一个进程
的一组线程分配到一组处理器上去同时执行。
? 分配处理机时间时，可采用两种方式：
? 面向所有应用程序平均分配处理机时间
? 面向所有线程平均分配处理机时间
2,成组调度 (gang scheduling)方式
第三章 处理机调度与死锁
两种分配处理器时间的方式：
面向所有应用程序
平均分配处理机时间
面向所有线程
平均分配处理机时间
第三章 处理机调度与死锁
优点：
? 对于一组相互合作的线程，成组调度能够提高这
些线程的执行并行度，有利于减少阻塞和加快推
进速度，最终提高系统的吞吐量。
? 每次调度可以完成多个线程的分派，能够减少调
度次数，从而减少调度的开销。
第三章 处理机调度与死锁
? 是指在一个应用程序执行期间，专门为该应用程
序分配一组处理器，每个线程分配一个 CPU。这
组处理器仅供该应用程序专用，直至该应用程序
执行完成。
? 适用于 CPU数量众多的高度并行系统，单个 CPU
利用率已不太重要。
? 线程的总和不应超过系统中的处理机数目。
? 缺点,有线程阻塞时，造成 CPU的闲置
? 优点,线程执行时不需切换，相应的开销可以大
大减小，推进速度更快。
3,专用处理机分配 (dedicated processor assignment)方式
第三章 处理机调度与死锁
以下是线程数对加速比的影响：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2122 23 24
1
2
3
4
5
6
7
加速比
线程数
矩阵相乘
FFT
0
例,具有 16个处理器的系统，运行两个应用程序：
矩阵 相乘、快速傅立叶变换。
第三章 处理机调度与死锁
3.5 产生死锁的原因和必要条件
3.5.1 产生死锁的原因
3.5.2 产生死锁的必要条件
3.5.3 处理死锁的基本方法
第三章 处理机调度与死锁
死锁的定义
所谓死锁，是指多个进程因竞争资源而造成的
一种 僵局,若无外力作用，这些进程都将不能再
向前推进。
注意,如果死锁发生，会浪费大量系统资源，
甚至导致系统崩溃。
第三章 处理机调度与死锁
3.5.1 产生死锁的原因
一个操作系统基本上是一个资源管理者，它负责
分配不同类型的资源给进程使用。
系统中的资源分两类：
? 可剥夺性资源 — 指资源占有进程虽然需要使用该
资源，但另一个进程却能强行把资源从占有者进程
处抢来。
? 不可剥夺性资源 — 指只有占用者进程不再需要使
用该资源而主动释放资源外, 其它进程不得在占有
者进程使用资源过程中强行抢占 。
1,资源
第三章 处理机调度与死锁
资
源
可剥夺,CPU、主存、硬盘，该资源
可为几个进程共同使用。
不可剥夺,打印机、读卡机、磁带驱
动器，该资源为某个进程独享。
第三章 处理机调度与死锁
永久性资源和临时性资源：
? 永久性资源 —— 可顺序重复使用的资源：如打
印机；
? 临时性资源 —— 由一个进程产生, 被另一进程
使用一短暂时间后便无用的资源：如消息, 故
也称之为消耗性资源 。
第三章 处理机调度与死锁
? 竞争资源 （不可剥夺性、临时性）
当系统中供多个进程共享的资源不足时，将引起
进程对资源的竞争而产生死锁。
? 进程推进顺序不合理
进程在运行过程中具有异步性特征，如果它们之
间的请求和释放资源的顺序不当，也同样会导致进
程产生死锁。
2,死锁产生的根本原因
第三章 处理机调度与死锁
(1) 竞争资源产生的死锁：
R
1
R
2
P
1
P
2
进程
资源
进程
资源
第三章 处理机调度与死锁
… … …
生产出一产品；
P（ empty ）
P（ mutex ）
将产品放入缓冲区；
V（ mutex ）
V（ full ）
… … …
(2) 进程推进顺序不合理产生的死锁：
例 1,生产者 — 消费者问题中，若 PV操作使用不当，
把生产者进程两个 P操作次序互换,先执行 P(mutex)，
后执行 P(empty)，则会引起死锁。
… … …
P（ full ）
P（ mutex ）
从缓冲区取出产品；
V（ mutex ）
V（ empty ）
消费该产品；
… … …
生产者 消费者
第三章 处理机调度与死锁
P2Rel(R1)
P2Rel(R2)
P2Req(R1)
P2Req(R2)
P1Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2)
①
②
③
④
D
例 2,（见书 P91）
第三章 处理机调度与死锁
3.5.2 产生死锁的必要条件
四个必要条件：
? 互斥条件,涉及的资源是非共享的 。
? 请求和保持条件,进程在等待一新资源时继续占
有已分配的资源 。
? 不剥夺条件,不能强行剥夺进程拥有的资源 。
? 环路等待条件,存在一种进程的循环链，链中的
每一个进程已获得的资源同时被链中的下一个进
程所请求。
以上四个条件须同时具备。
第三章 处理机调度与死锁
3.5.3 处理死锁的基本方法
(1) 预防死锁：
? 通过设置某些限制条件，去破坏死锁四个必要
条件中的一个或多个，来防止死锁。
? 较易实现，广泛使用，但由于所施加的限制往
往太严格，可能导致系统资源利用率和系统吞吐
量的降低。
第三章 处理机调度与死锁
(2) 避免死锁：
? 不事先采取限制去破坏产生死锁的条件，而是
在资源的动态分配过程中，用某种方法去防止系
统进入不安全状态，从而避免死锁的发生。
? 实现较难，只需要较弱的限制条件，可获得较
高的资源利用率和系统吞吐量。
第三章 处理机调度与死锁
? 事先并不采取任何限制，允许发生死锁，但可
以通过系统的检测机构及时检测出死锁的发生，
并精确确定与死锁有关的进程和资源。
(3) 检测死锁：
第三章 处理机调度与死锁
? 与检测死锁相配套，用于将进程从死锁状态解
脱出来。
? 常用的方法是 撤消或挂起一些进程 。以回收一
些资源，再将它们分配给处于阻塞状态的进程，
使之转为就绪状态。
? 实现难度大，但可获得较好的资源利用率和系
统吞吐量。
(4) 解除死锁：
第三章 处理机调度与死锁
3.6 死锁的预防和避免
3.6.1 预防死锁
3.6.2 避免死锁
3.6.3 利用银行家算法避免死锁
第三章 处理机调度与死锁
1,摒弃“请求和保持”条件
系统要求所有进程在开始运行之前，要一次性
地申请在整个运行过程中所需的全部资源。若系
统有足够资源则完全分配；否则，进程等待。
3.6.1 预防死锁
优点,简单、易于实现且安全。
基本思想,打破产生死锁的四个必要条件中的
一个或几个。
第三章 处理机调度与死锁
缺点：
? 实用性不强,在许多情况下, 一个进程在执行之
前不可能知道它所需要的全部资源 。 这是由于进
程在执行时是动态的, 不可预测的；
? 资源利用率低,无论所分资源何时用到, 一个进
程只有在占有所需的全部资源后才能执行 。 即使
有些资源最后才被该进程用到一次, 但该进程在
生存期间却一直占有它们, 造成长期占着不用的
状况 。 造成极大的资源浪费；
? 延迟进程的运行,因为进程只有获得了其所需的
全部资源才开始运行, 但有些资源可能长期被其
它进程占用, 导致该进程迟迟不能运行 。
第三章 处理机调度与死锁
2,摒弃“不剥夺”条件
一个已拥有资源的进程, 若它再提出新资源要
求而不能立即得到满足时, 它必须释放已经拥有
的所有资源 。 以后需要时再重新申请 。
缺点,实现复杂、要付出很大的代价。原因：
?一个资源在使用一段时间后被释放，可能会造
成前阶段工作的失效；
?反复地申请和释放资源，又会使进程的执行无
限推迟，从而进一步增加系统的开销，降低系
统的吞吐量。
第三章 处理机调度与死锁
3,摒弃“环路等待”条件
系统中的所有资源都有一个确定的唯一号码,
所有分配请求必须以序号上升的次序进行 。
例如,系统中有下列设备：输入机 (1),打印机 (2)，
穿孔机 (3),磁带机 (4),磁盘 (5)。 有一进程要先后
使用输入机, 磁盘, 打印机, 则它申请设备时要
按输入机, 打印机, 磁盘的顺序申请 。
第三章 处理机调度与死锁
优点：
同前两法相比, 其资源利用率和系统吞吐量
有较明显的改善 。
缺点：
?系统中各类资源的编号必须相对稳定, 限制了
新设备类型的增加；
?进程实际需要资源的顺序不一定与资源的编号
一致, 因此仍会造成资源浪费 。
第三章 处理机调度与死锁
在系统运行过程中，对进程发出的每一个系统
能够满足的资源申请进行动态检查，并根据检查
结果决定是否分配资源，若分配后系统可能发生
死锁，则不予分配，否则予以分配。
把系统的状态分为 安全状态 和 不安全状态,只
要能使系统始终都处于安全状态，便可避免死锁
的发生。
3.6.2 避免死锁
第三章 处理机调度与死锁
1,安全状态
如果系统能按某种顺序 （ P1,P2,…,Pn） 为
每个进程分配其所需的资源, 直至所有进程都能
运行完成, 称系统处于 安全状态 。 若不存在这样
一个安全序列称系统处于 不安全状态 。
其中, <P1,P2,…,Pn> 称为 安全序列 。
第三章 处理机调度与死锁
? 并非所有的不安全状态都导致死锁，但当系统
进入不安全状态后，便可能进而进入死锁状态；
? 只要系统处于安全状态，便可避免进入死锁状
态
? 避免死锁的本质在于,当进行资源分配时，如
何避免进入不安全状态。
第三章 处理机调度与死锁
安全状态举例：
有三个进程 p1,p2,p3,有 12台磁带机 。 P1
共要求 10台, P2共要求 4台, P3共要求 9台 。 在
T0时刻, p1,p2,p3分别获得 5,2,2台, 尚有
3台空闲 。
第三章 处理机调度与死锁
进程 最大需求 已分配 还需 可用
p1 10 5 5 3
p2 4 2 2
p3 9 2 7
经分析，在 T0时刻，系统是安全的。因为存在
一个安全序列 p2,p1,p3。见下图。
第三章 处理机调度与死锁
3.6.3 利用银行家算法避免死锁
? 最有代表性的避免死锁算法，由 Dijkstra提出。
第三章 处理机调度与死锁
1,银行家算法中的数据结构
? 可利用资源向量 Available。 它是一个含有 m个元
素的数组，其中每个元素代表一类可利用资源的
数目。
? 最大需求矩阵 Max。 n*m矩阵，表示 n个进程的
每一个对 m类资源的最大需求。
? 分配矩阵 Allocation。 n*m矩阵，表示每个进程分
配的资源数。
? 需求矩阵 Need。 n*m矩阵，表示每个进程还需要
各类资源数。
第三章 处理机调度与死锁
2,银行家算法描述
当进程 pi提出资源申请时，系统执行下列步骤：
(1) 若 Request[i]≤Need[i]，转 (2)；否则错误返回。
(2) 若 Request[i]≤Available，转 (3)；否则进程等待。
(3) 假设系统分配了资源，则有：
Available:=Available-Request[i];
Allocation[i]:=Allocation[i]+Request[i];
Need[i]:=Need[i]-Request[i]
(4) 执行安全性算法，若系统新状态是安全的，则分
配完成；若系统新状态是不安全的，则恢复原状
态，进程等待。
第三章 处理机调度与死锁
3,安全性算法
为进行安全性检查，设置两个向量：
? 工作向量 Work,表示系统可提供给进程继续运行
所需的各类资源数目，含有 m个元素，在执行安
全算法开始时,Work:=Available;
? Finish,表示系统是否有足够的资源分配给进程，
使之运行完成。开始时先做 Finish[i]:=false; 当有
足够资源分配给进程时，再令 Finish[i]:=true。
第三章 处理机调度与死锁
安全性算法步骤：
(1) Work:=Available;
Finish:=false；
(2) 寻找满足下列条件的 i：
a) Finish[i]=false；
b) Need[i]≤Work ；
若找到，转 (3)；若找不到，则转 (4)。
(3) Work:=Work+Allocation[i]；
Finish[i]:=true；
转 (2)。
(4) 若对所有 i, Finish[i]=true，则系统处于安全状
态，否则处于不安全状态。
第三章 处理机调度与死锁4,银行家算法举例
设系统有五个进程和三类资源，每类资源分别有 10、
5,7。在 T0时刻资源分配情况如图：
第三章 处理机调度与死锁(1) T0时刻的安全性检查：
T0时刻可以找到一个安全序列 {p1,p3,p4,p0,p2}。系统是安全的。
第三章 处理机调度与死锁
(2) T0时刻 P1请求资源，请求向量 Request1(1,0,2)。
执行银行家算法：
① Request1(1,0,2)≤Need1(1,2,2)
② Request1(1,0,2)≤Available(3,3,2)
③ 系统先假定可为 P1分配资源, 并修改 Available,
Allocation1和 Need1向量, 由此形成的资源变化情
况如 图一 所示 。
④ 进行安全性检查：如 图二 所示。可以找到一个
安全序列 { p1,p3,p4,p0,p2 }。故系统是安全的，
可以将 P1的请求分配给它 。
第三章 处理机调度与死锁图一：
第三章 处理机调度与死锁图二：
第三章 处理机调度与死锁
(3) P4请求资源，请求向量 Request4(3,3,0)。
执行银行家算法,
① Request4(3,3,0) ≤ Need4(4,3,1);
② Request4(3,3,0) ≤ Available(2,3,0);
所以 P4等待 。 P4的请求不能分配 。
第三章 处理机调度与死锁
(4) P0请求资源,请求向量 Request0(0,2,0)
Request0(0,2,0)，执行银行家算法：
① Request0(0,2,0)≤Need0(7,4,3);
② Request0(0,2,0)≤Available(2,3,0);
③ 系统暂时先假定可为 P0分配资源，并修改 图一 有
关数据，如后图所示。
④ 进行安全性检查,Available{2,1,0}已不能满足任
何进程需要，所以系统进入不安全状态,P0的请
求不能分配。
第三章 处理机调度与死锁
第三章 处理机调度与死锁
3.7 死锁的检测与解除
3.7.1 死锁的检测
3.7.2 死锁的解除
第三章 处理机调度与死锁
死锁检测与解除是指系统设有专门的机构，
当死锁发生时，该机构能够检测到死锁发生的
位置和原因，并能通过外力破坏死锁发生的必
要条件，从而使得并发进程从死锁状态中恢复
出来。
第三章 处理机调度与死锁
允许死锁发生，操作系统不断监视系统进展情
况，判断死锁是否发生。
一旦死锁发生则采取专门的措施，解除死锁并
以最小的代价恢复操作系统运行。
3.7.1 死锁的检测
第三章 处理机调度与死锁
1,资源分配图
用来描述系统资源及资源的申请和分配情况的
有向图。
定义为,二元组 G=（ V,E）
其中：
V：结点集，分为 P(进程集合 ),R(资源集合 )两
部分。即 P={p1,p2,…,pn} ； R={r1,r2,…,rm} 。
E：边的集合，其元素为有序二元组 (pi,rj) 或
(rj,pi) 。
第三章 处理机调度与死锁
资源请求边,e={pi,rj}
进程 ?资源的一条有向边
表示进程 pi申请 rj类资源中的一个资源。
资源分配边,e={rj,pi}
资源 ?进程的一条有向边
表示 rj类中的一个资源已被进程 pi占用。
第三章 处理机调度与死锁
例：
R1 R2
P2 P3 P4
P1 P1
P2
r1 r2
请求 r2
资源请求边
资源分配边
第三章 处理机调度与死锁
(1) 如果资源分配图中无环路，则此时系统没有发
生死锁。
(2) 如果资源分配图中有环路，且每个资源类中仅
有一个资源，则 系统中发生了死锁,此时，环路是
系统发生死锁的充要条件，环路中的进程便为死锁
进程。
(3) 如果资源分配图中有环路，且涉及的资源类中
有多个资源，则环路的存在只是产生死锁的 必要条
件而不是充分条件 。
第三章 处理机调度与死锁
可以利用把 资源分配图加以简化 的方法，来检测
系统是否为死锁状态。简化方法如下：
（ 1） 在资源分配图中，找 — 个进程 pi，其请求边均
能立即得到满足。
（ 2） 若找到这样的 pi，则将与 pi相连的边全部删去，
转（ 1）。否则过程结束。
如果简化后，所有进程都成为孤立结点，则称该
图是 可完全简化 的；否则，称该图是 不可完全简化 。
第三章 处理机调度与死锁
死锁状态的 充分条件 是：当且仅当资源分配图是
不可完全简化的。
2,死锁定理
第三章 处理机调度与死锁例：
P1
P4
R2R1
P2 P3
P1
P4
R2R1
P2 P3
P1
P4
R2R1
P2 P3
P1
P4
R2R1
P2 P3
P1
P4
R2R1
P2 P3
第三章 处理机调度与死锁
3,死锁检测算法 —— 数据结构
? 可利用资源向量 Available：表示 m类资源中的每
个资源的可用数目。
? 请求向量 Request：表示为当前进程对各类资源
的请求数目。
? 分配矩阵 Allocation，表示资源的分配情况。
? 工作向量 Work：表示系统课提供给进程继续执
行的 m类资源数目。
? 进程向量 L：表示当前已不占有资源的各个进程。
第三章 处理机调度与死锁
死锁检测算法 —— 算法描述
Work:=Available;
L:= {Li|Allocationi=0∩Requesti=0}
for all Li L do
begin
for all Requesti≤Work do
begin
Work:=Work+Allocationi;
Li∪ L;
end
end
deadlock:= ? (L={p1,p2,…,p n});
?
第三章 处理机调度与死锁
3.7.2 死锁的解除
? 剥夺资源
强迫从其它进程剥夺足够数量的资源给死锁进程，
直至死锁不存在。
? 撤消进程
终止参与死锁的进程，收回它们占有的资源，从
而解除死锁。又分两种情况：
? 一次性撤消参与死锁的全部进程，剥夺全部资
源。
? 逐步撤消参与死锁的进程，直至有足够的资源
可用。
第三章 处理机调度与死锁
思考题：
设系统有五个进程 A,B,C,D,E共享四类资
源 R1,R2,R3,R4，进程对资源的需求量和目前
分配情况如下表，若系统还剩余资源数分别为
(2,6,2,1)，请按银行家算法回答下列问题：
(1) 目前系统是否出于安全状态？
(2) 现在如果进程 D提出申请 (2,5,0,0)各资源，系统
是否能为他分配资源？
第三章 处理机调度与死锁
进程 已占资源数 最大需求数R1 R2 R3 R4 R1 R2 R3 R4
A 3 6 2 0 5 6 2 0
B 1 0 2 0 1 0 2 0
C 1 0 4 0 5 6 6 0
D 0 0 0 1 5 7 0 1
E 5 3 4 1 5 3 6 2
