【思维导图】第三章 处理机调度与死锁-

短作业优先调度算法SJF，是指对短作业或 短进程优先调度的算法。它们可以分别用于作业 调度和进程调度。
FCFS和SJF调度算法的性能
SJF调度算法也存在不容忽视的缺点：
(1) 该算法对长作业不利。
(2) 该算法完全未考虑作业的紧迫程度，因而 不能保证紧迫性作业(进程)会被及时处理。
(3) 由于作业(进程)的长短只是根据用户所提供 的估计执行时间而定的，致使该算法不一定能真 正做到短作业优先调度。
3.1 处理机调度的层次和调度算法目标
一个批处理型作业，从进入系统并驻留在外存的后备 队列上开始，直至作业运行完毕，可能要经历的三 级调度:
高级调度 低级调度 中级调度
3.1.1 处理机调度的层次
1. 高级调度—— (作业调度、长程调度、接纳调度）
• 根据作业控制块中的信息，审查系统能否满足 用户作业的需要，按照某种算法，把外存上处 于后备队列中的哪些作业调入内存，并为他们 创建进程、分配资源，然后将新创建的进程插 入就绪队列，准备执行。
响应比
等待时间 要求服务时间 要求服务时间
响应时间 要求服务时间
(1) 如果作业的等待时间相同，则要求服务的时间愈短， 其优先权愈高，因而该算法有利于短作业。
(2) 当要求服务的时间相同时，作业的优先权决定于其等 待时间，等待时间愈长，其优先权愈高，因而它实现的 是先来先服务。
(3) 对于长作业，作业的优先级可以随等待时间的增加而 提高，当其等待时间足够长时，其优先级便可升到很高， 从而也可获得处理机。
2) 抢占方式(Preemptive Mode)
抢占的原则有： (1) 优先权原则。 (2) 短作业(进程)优先原则。 (3) 时间片原则。
3.3.2 轮转调度算法(RR)

(1) 进程类型。 (2) 进程对资源的需求。 (3) 用户要求。
第三章 处理机调度与死锁
2) 动态优先权
计算机操作系统
动态优先权是指，在创建进程时所赋予的优先权， 是可以随进程的推进或随其等待时间的增加而改变的， 以便获得更好的调度性能。
第三章 处理机调度与死锁
3. 高响应比优先调度算法
计算机操作系统
3.1.3 选择调度方式和调度算法的若干准则
1. 面向用户的准则 (1) 周转时间短。 周转时间的长短是评价批处理系统性能、选择作业调
度方式与算法的重要准则之一
第三章 处理机调度与死锁
(1) 周转时间短。
计算机操作系统
周转时间：从作业提交给系统开始，到作业完成为之 的这段时间间隔（作业周转时间） 作业在外存后备队列上等待（作业）调度的时间 进程在就绪队列上等待进程调度的时间 进程在CPU上执行的时间 进程等待I/O操作完成的时间
第三章 处理机调度与死锁
计算机操作系统
第三章 处理机调度与死锁
ห้องสมุดไป่ตู้算机操作系统
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
3.1.1 高级、中级和低级调度
1. 高级调度(High Scheduling)
又称作业调度、长程调度：决定把外存上处于后备 队列中的哪些作业调入内存，并为之创建进程、分配必 要的资源，然后，再将新创建的进程排在就绪队列中。
优先权的变化规律可描述为：
优先权 等待要时求 间 要服求务服时务间时间
由于等待时间与服务时间之和，就是系统对该作 业的响应时间，故该优先权又相当于响应比RP。据此， 又可表示为：
优先 等 权待 要 时 求 要间 服 求务 服时 务 要 响 间 时 求 应 间 服 时 务 间

分派器
上下文切换
非抢占方式
进程调度方式
优先权原则
抢占方式
短进程优先原则
时间片原则
保存处理机的现场信息
进程调度的任务
按某种算法选取进程
把处理器分配给进程
低级调度（进程调度）
优先级调度算法
优先级调度算法的类型
非抢占式优先级调度算法
等当前进程执行完以后，再执行另一个优先权最 高的进程
这种调度算法主要用于批处理系统中；也可用于 某些对实时性要求不严的实时系统中。
批处理系统的目标
系统吞吐量高
处理机利用率高
分时系统的目标
响应时间快 均衡性
实时系统目标
截止时间的保证 可预测性
高级调度（作业调度）
分时系统无需作业调度，因为需要交互 批处理系统需要作业调度
中级调度（和挂起有关）
进程调度是最基本的调度，任何操作系统都有进 程调度。
处理机调度的层次
排队器
低级调度的三个基本机制
银行家算法中的数据结构
利用银行家算法避免死锁
处理死锁的方法
需求矩阵 N e [ , ]：它表示每个进程尚需的 各类资源数，N e [ , ]= 表示进程 还需要 类资源 个。N e [ , ]=M [ , ] -
A loca i [ , ]
银行家算法
安全性算法
银行家算法之例
矩阵 列表
解题
选择一个没有阻塞的进程
请求和保存条件
不可抢占条件
如果每个资源只有一个实例，则环路等待条件是 死锁存在的充分必要条件
循环等待条件
产生死锁的必要条件
静态方法，在进程执行前采取的措施，通过设置 某些限制条件，去破坏产生死锁的四个条件之 一，防止发生死锁。

m
Ci P N i 1 i
25
m
第三章 处理机调度与死锁
3.3.2 实时调度算法的分类
1、非抢占式调度算法
图 3-8 非抢占式实时进程调度
26
第三章 处理机调度与死锁
2、抢占式调度算法
图 3-8 抢占式实时进程调度
27
第三章 处理机调度与死锁
3.4.3 常用的几种实时调度算法
1、 最早截止时间优先即EDF(Earliest Deadline First)算法
11
第三章 处理机调度与死锁
3.2.2 选择调度方式和调度算法的若成 这段时间间隔。
1 i （2）平均周转时间： T Ti n i 1
W0 T
（3）带权周转时间：作业周转时间T与系统为它提供 的服务时间TS之比：
作业 调度 后 备 队 列
时间片完
进程调度 进程完成
就 绪 队 列
CPU
事件1出现
等待事件1
事件2出现 … 事件n出现 … …
等待事件2 … 等待事件n
图 3-2 具有高、低两级调度的调度队列模型
9
第三章 处理机调度与死锁
3、 同时具有三级调度的调度队列模型
作业调度 后备队列 批量作业 交互型作业 中级调度 时间片完 就绪队列 进程完成
进程名 到达 时间 A 0 B C D E 1 2 3 4 服务 时间 4 3 5 2 4 带权平均 周转时间
22
完成 时间
周转 时间
带权周 转时间
平均周转时间
第三章 处理机调度与死锁
2、多级反馈队列调度算法 就绪队列1 S1 S2 S3 至CPU 至CPU
就绪队列2 就绪队列3

让紧急作业及时得到处理，有时甚至是立即抢占
4/29/2020
14
3调度基本准则
面向系统的原则
系统吞吐量高 ：评价批处理系统性能的重要指标
吞吐量：指在单位时间内系统完成的作业数。
处理器利用率好 ：适用于大中型多用户系统，不适于 单用户或实时系统
一般cpu利用率在40%-90%之间
各类资源的平衡利用 ：适用于大中型多用户系统，不 适于单用户或实时系统
4/29/2020
15
调度算法
先来先服务调度算法（FCFS） 短作业（进程）优先调度算法 （SJF） 优先级调度算法
（高响应比优先调度算法 HRRN）
基于时间片的轮转调度算法(RR)
（多级反馈队列调度算法FB ）
4/29/2020
16
先来先服务调度(FCFS)算法
既可用于作业调度，也可用于进程调度
优点：既照顾了短进程，又考虑了进程到达的先后 次序，也不会使长进程长期得不到服务，因此是一 个比较全面考虑的算法
缺点：但每次进行调度时，都需要对各个进程计算 响应比。所以系统开销很大，比较复杂。 适于批处理系统
4/29/2020
28
4/29/2020
29
最高响应比优先作业算法计算结果
1+7/5 1+8/5 1+6/1
4/29/2020
17
先来先服务调度(FCFS)算法
既可用于作业调度，也可用于进程调度
优点:实现简单
缺点:没考虑进程的优先级
特点:利于长作业（进程）和CPU繁忙型的作业 （进程），而不利于短作业（进程）和I/O繁忙型 作业（进程）。
CPU繁忙型的作业：需要大量的CPU时间进行计 算，而很少请求I/O。（科学计算）

第三章 处理机调度与死锁
3. 高响应比优先调度算法（HRRF） ：
▪ 实际上是一种动态优先权调度算法。
▪ FCFS与SJF/SPF是片面的调度算法。FCFS只 考虑作业等候时间而忽视了作业的计算时间， SJF /SPF只考虑用户估计的作业计算时间而忽视 了作业等待时间。
▪ HRRF是介乎这两者之间的折衷算法，既考虑 作业等待时间，又考虑作业的运行时间，既照顾 短作业又不使长作业的等待时间过长，改进了调 度性能。但每次调度前，都要进行响应比的计算， 会增加系统开销。
一旦把处理机分配给某个进程后，让该进程一直 执行，直到该进程完成或者发生某事件而阻塞。 引起进程调度的因素： ▪ 正在执行的进程执行完毕； ▪ 执行中的进程因为提出I/O请求而暂停执行； ▪ 进程通信或同步过程中执行了原语操作。
第三章 处理机调度与死锁
(2) 抢占方式
当一进程正在处理机上执行时，系统可根据某种 原则暂停它的执行，并将已分配给它的处理机重新 分配给另一个进程。
在三种调度中，进程调度的运行频率最高， 作业调度的周期较长，中级调度的运行频率在上 述两者之间。
第三章 处理机调度与死锁
3.1.2 调度队列模型
根据os中所引入的调度的类型，形成了三种类 型的调度队列模型： ▪ 仅有进程调度的调度队列模型； ▪ 具有高级和低级调度的调度队列模型； ▪ 同时具有三级调度的调度队列模型。
A0
1
0
1
1
1
B1 C2
100
1
101 100
1
1
101 102 100 100
D3
100
102
202 199
1.99
平均周转时间T＝100（h） 平均带权周转时间T’＝26.00（h）

阜阳师范学院计算机与信息学院
15
3.2 调度算法
3.2.1 FCFS与SJF/SPF调度算法 3.2.2 高优先权优先调度算法 3.2.3 基于时间片的轮转调度算法
01.12.2020
阜阳师范学院计算机与信息学院
16
3.2.1 FCFS与SJF/SPF调度算法
1. 先来先服务调度算 process
中级调度
作业调度
退出
3.1.2 调度队列模型
1. 仅有进程调度的调度队列模型 2. 具有高级和低级调度的调度队列模型 3. 同时具有三级调度的调度队列模型
01.12.2020
阜阳师范学院计算机与信息学院
11
1. 仅有进程调度的调度队列模型
在分时系统中就绪进程组织成FIFO队 列形式，按时间片轮转方式运行。
20
2. 短作业（进程）优先调度算法
作业情 况
调度算法
FCFS
SJF
作业名 到达时间 服务时间 完成时间 周转时间 带权周转时间 完成时间 周转时间 带权周转时间
AB 01 43
47 46 12 49 48 1 2.67
CD E 23 4 52 4 12 14 18 10 11 14 2 5.5 3.5 18 6 13 16 3 9 3.2 1.5 2.25
01.12.2020
阜阳师范学院计算机与信息学院
4
1. 高级调度
又称为作业调度、宏观调度或长 程调度。用于决定把后备队列中的哪 些作业调入内存，为他们分配必要的 资源，并创建进程。
批处理系统 ： 需要作业调度 分时系统 ： 不需作业调度 实时系统 ： 不需作业调度
01.12.2020
阜阳师范学院计算机与信息学院

它按一定的算法将外存中已具备运 行条件的进程换入内存，而将内存中处 于阻塞状态的某些进程换出至外存。
18.08.2020
阜阳师范学院计算机与信息学院
10
运行
就绪
调
度
阻塞
的
ቤተ መጻሕፍቲ ባይዱ
进程调度
层
次
挂起阻塞
创建
挂起就绪
中级调度
作业调度
退出
3.1.2 调度队列模型
1. 仅有进程调度的调度队列模型 2. 具有高级和低级调度的调度队列模型 3. 同时具有三级调度的调度队列模型
第3章 处理机调度与死锁
3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 产生死锁的原因和必要条件 3.5 预防死锁的方法 3.6 死锁的检测与解除
18.08.2020
1
第一部分
整体概述
THE FIRST PART OF THE OVERALL OVERVIEW, PLEASE SUMMARIZE THE CONTENT
3.1 处理机调度的基本概念
3.1.1 高级调度、中级调度、低级调度 3.1.2 调度队列模型 3.1.3 选择调度方式和调度算法的若干准则
18.08.2020
阜阳师范学院计算机与信息学院
3
18.08.2020
阜阳师范学院计算机与信息学院
4
3.1.1 高级、中级和低级调度
经历下述三级调度:
批处理系统 ： 需要作业调度 分时系统 ： 不需作业调度 实时系统 ： 不需作业调度
18.08.2020
阜阳师范学院计算机与信息学院
6
1. 高级调度
执行作业调度时，必须作出两个决定： 接纳多少作业——每次接纳多少作业进