第3章 处理机调度和死锁精品PPT课件
- 格式：ppt
- 大小：1.22 MB
- 文档页数：88
下载文档原格式
合集下载
第三章处理机调度和死锁PPT资料179页
进程调度的时机
进程调度的时机与引起进程调度的原因以及进程调度的方式有关。 引起进程调度的原因 （1）正在执行的进程执行完毕。 （2）执行中的进程提出I/O请求后被阻塞。 （3）执行某种原语操作，比如wait(s)，block原语，wakeup原语。 （4）分时系统中，由于分配给该进程的时间片已经用完。 （5）执行中进程自己调用阻塞原语将自己阻塞起来。 （6）执行完系统程序后返回用户进程时，可看作系统进程执行完毕， 从而可以调度选择一个新的用户进程执行。 以上是在不可剥夺方式下的引起进程调度的原因，在CPU执行方式 是可剥夺时，还有一个原因。 （7）一个比正在运行进程的优先数更高的进程进入就绪队列，从而引 起调度。 在以上所列的几种原因之一发生的情况下，OS进行进程调度。
1、低级调度功能： （1）保存处理器的现场信息。 （2）按某种算法选取进程。 （3）把处理器分配给进程。
2、进程调度中的三个基本机制
排队器： 分派器(分派程序)：
用来将CPU的控制交给由进程调度所选择的 进程。其功能包括：
（1）切换上下文 （2）切换到用户模式 （3）跳转到用户程序的合适位置以重新启动 这个程序。 上下文切换机制 第一对上下文切换：保存当前进程的上下文， 装入分派程序的上下文。 第二对上下文切换：移出分派程序的上下文， 装入新选进程的上下文。
2、面向系统的准则 （1）系统吞吐量高。 （2）处理机利用率好。 （3）各类资源的平衡利用。
§3.3 调度算法
在OS中调度的实质是一种资源分配， 因而调度算法是指：根据系统的资源分配策 略所规定的资源分配算法。
3.3.1先来先服务和短作业优先调度算法
既可用于进程调度， 也可用于作业调度
1、先来先服务调度算法(FCFS)
《处理机调度与死锁》课件
04
死锁的检测与恢复
死锁的检测
资源分配图法
通过构建资源分配图，分析是否存在环路，以判断系统是否发生死锁。
银行家算法
模拟银行家对资源分配的策略，通过检查请求资源是否会导致不安全状态来判断 系统是否发生死锁。
死锁的恢复
资源剥夺法
剥夺已经分配给某个进程的资源，打破 死锁状态，使其中一个进程能够继续执 行。
详细描述
响应时间包括进程从提交到开始执行 的时间以及执行完成的时间。响应时 间的计算公式为：响应时间 = 开始执 行时间 - 提交时间。
周转时间
总结词
周转时间是指从进程到达系统到完成 所经过的时间。
详细描述
周转时间包括进程在等待队列中的等 待时间和在处理机上的执行时间。周 转时间的计算公式为：周转时间 = 完 成时间 - 到达时间。
处理机调度与死锁
目录
• 处理机调度算法 • 死锁 • 处理机调度的性能指标 • 死锁的检测与恢复
01
处理机调度算法
先来先服务（FCFS）
总结词
按照作业到达的先后顺序进行调度，优先处理最先到达的作 业。
详细描述
FCFS算法是一种最简单的调度算法，它不考虑作业的紧迫程 度和所需执行时间，只按照作业到达的顺序进行调度。当一 个作业到达时，系统将其加入到等待队列中，并按照到达顺 序依次处理等待队列中的作业。
避免死锁
通过破坏产生死锁的四个必要条件之一来防止死锁的产生。例如，通过预先分配策略，即 进程在开始执行前就申请所有需要的资源，如果不能获得所有资源则不启动该进程。
避免饥饿
通过设置优先级、时间片轮转等机制，保证所有进程都有机会获得资源，避免某些进程永 久等待。
检测与恢复
操作系统 chapter3 处理机调度与死锁PPT课件
阻 塞， 挂 起队 列 事
件 出
挂起
现
阻 塞队 列
等 待事 件
图 3-3 具有三级调度时的调度队列模型
3.3 调 度 算 法
3.3.1 先来先服务和短作业(进程)优先调度算法
1. 先来先服务调度算法
图 3-4 FCFS和SJF调度算法的性能
就 绪 队 列1 就 绪 队 列2 就 绪 队 列3 就 绪 队 列n
② 执行中的进程因提出I/O请求而暂停执行； ③ 在进程通信或同步过程中执行了某种原语操作，如P 操作(wait操作)、Block原语、Wakeup原语等。 优点：实现简单、系统开销小。
缺点：难以满足紧急任务的要求——立即执行，实时系统中 不宜采用这种调度方式。
2、抢占方式(Preemptive Mode) 抢占的原则有： • 优先权原则。 (2) 短作业(进程)优先原则。 (3) 时间片原则。 优点：防止长进程长时间占用处理机，适合实时任务 缺点：系统开销大
第三章 处理机调度与死锁
3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
1、非抢占方式(Non-preemptive Mode) 引起进程调度的因素可归结为这样几个：
① 正在执行的进程执行完毕，或因发生某事件而不能再 继续执行；
4. 具有快速切换机制
该机制应具有如下两方面的能力：
(1) 对外部中断的快速响应能力。为使在紧迫的外部 事件请求中断时系统能及时响应，要求系统具有快速硬件 中断机构，还应使禁止中断的时间间隔尽量短，以免耽误 时机(其它紧迫任务)。
(2) 快速的任务分派能力。在完成任务调度后，便应 进行任务切换。为了提高分派程序进行任务切换时的速度， 应使系统中的每个运行功能单位适当的小，以减少任务切 换的时间开销。
第三章 处理机调度与死锁PPT课件
第三章 处理机调度与死锁
3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
1
第一部分
整体概述
THE FIRST PART OF THE OVERALL OVERVIEW, PLEASE SUMMARIZE THE CONTENT
✓ 当一个进程运行完毕，或由于某种错误而终止运行 ✓ 当一个进程在运行中处于等待状态（等待I/O） ✓ 在进程通信中，执行中的进程执行了某种原语操作
（P操作，阻塞原语，唤醒原语） ✓ 分时系统中时间片到 ✓ 当有一个优先级更高的进程就绪
1) 非抢占方式(Non-preemptive Mode)
2) 抢占方式(Preemptive Mode)
2
3.1 处理机调度的层次
处理机三级调度
1.高级调度――作业调度
在批处理系统中，作业是先驻留在外存的输入井上 的，因此需要有作业调度。然而在分时系统中，通过键 盘输入的命令和数据直接进入内存，无需作业调度。 2.低级调度――进程调度
进程调度决定就绪队列中哪个进程将获得处理机， 然后由分派程序执行把处理机分配给该进程的操作。进 程调度是最基本的调度，任何操作系统都有进程调度。 3.中级调度——对换
作业 调度 后备队列
时间片完 就绪队列
进程调度 进程完成 CPU
事件1出现
等待事件1
事件2出现
等待事件2
… … … …
事件n出现
等待事件 n
具有高、低两级调度的调度队列模型
15
3.同时具有三级调度的调度队列模型
作业调度
时间片完
3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
1
第一部分
整体概述
THE FIRST PART OF THE OVERALL OVERVIEW, PLEASE SUMMARIZE THE CONTENT
✓ 当一个进程运行完毕，或由于某种错误而终止运行 ✓ 当一个进程在运行中处于等待状态（等待I/O） ✓ 在进程通信中，执行中的进程执行了某种原语操作
（P操作，阻塞原语，唤醒原语） ✓ 分时系统中时间片到 ✓ 当有一个优先级更高的进程就绪
1) 非抢占方式(Non-preemptive Mode)
2) 抢占方式(Preemptive Mode)
2
3.1 处理机调度的层次
处理机三级调度
1.高级调度――作业调度
在批处理系统中，作业是先驻留在外存的输入井上 的，因此需要有作业调度。然而在分时系统中，通过键 盘输入的命令和数据直接进入内存，无需作业调度。 2.低级调度――进程调度
进程调度决定就绪队列中哪个进程将获得处理机， 然后由分派程序执行把处理机分配给该进程的操作。进 程调度是最基本的调度，任何操作系统都有进程调度。 3.中级调度——对换
作业 调度 后备队列
时间片完 就绪队列
进程调度 进程完成 CPU
事件1出现
等待事件1
事件2出现
等待事件2
… … … …
事件n出现
等待事件 n
具有高、低两级调度的调度队列模型
15
3.同时具有三级调度的调度队列模型
作业调度
时间片完
《处理机调度与死锁》PPT课件
当这些进程重又具备运行条件且内存又稍有空闲时，由 中级调度来决定把外存上的那些又具备运行条件的就绪进程 重新调入内存，并修改其状态为就绪状态，挂在就绪队列上 等待进程调度。
中级调度实际上就是存储器管理中的对换功能。
整理ppt15Fra bibliotek第三章 处理机调度与死锁
在上述三种调度中，
• 进程调度的运行频率最高，在分时系统中通常是10～100 ms便进行一次进程调度，因此把它称为短程调度。为避免进 程调度占用太多的CPU时间，进程调度算法不宜太复杂。
（2） 分派器(分派程序)。
（3）上下文切换机制。当对处理机进行切换时，会发生
两对上下文切换操作。在第一对上下文切换时，操作系统将
保存当前进程的上下文，而装入分派程序的上下文，以便分
派程序运行；在第二对上下文切换时，将移出分派程序，而
把新选进程的CPU现场信息装入到处理机的各个相应寄存器
中。
应当指出，上下文切换将花去不少的处理机时间，即使是现代计算
3.1.3 中级调度(Intermediate Level Scheduling) 又称中程调度(Medium-Term Scheduling)。 引入中级调度的主要目的是为了提高内存利用率和系统 吞吐量。
使那些暂时不能运行的进程不再占用宝贵的内存资源， 而将它们调至外存上去等待，把此时的进程状态称为就绪驻 外存状态或挂起状态。
作业调度或长程调度（LongTerm Scheduling）
1．作业和作业步
(1) 作业(Job)。作业不仅包含了通常的程序和数据，而且 还应配有一份作业说明书，系统根据该说明书来对程序的运 行进行控制。
在批处理系统中，是以作业为基本单位从外存调入内存的。
整理ppt
计算机操作系统第三章处理机调度与死锁 ppt课件
2决定接纳哪些作业
选用何种调度算法：先来先服务、 短作业优先、基于作业优先级、响 应比高者优先。
PPT课件
6
注意
批处理系统中，作业是首先进入外存， 然后经由作业调度分批进入内存；
分时系统及实时系统中，由于对响应 时间有要求，因此用户输入的命令和数据 等是直接进入内存的，无须配置作业调度 机制。
PPT课件
PPT课件
14
同时具有三级调度的调度队列模型
作业 调度
后备队列
中级 调度
时间片完 就绪队列 就绪、挂起队列
进程调度
进程完成
CPU
挂起
事件出现
事件发生
阻塞、挂起队列 阻塞队列
挂起 等待事件
具有高、低、中三级调度的调度队列模型
PPT课件
15
选择调度方式和调度算法的若干准则
• 面向用户的准则
– 周转时间短（批处理） – 响应时间快（分时） – 截止时间保证（实时） – 优先权准则（all）
4
2 作业控制块
多道批处理系统中，为每个作业配备一个作业 控制块（JCB），它是作业在系统中存在的标志。
作业运行期间，系Biblioteka 按照JCB中的信息对作业进行 控制。
JCB中保存了系统对作业进行管理和调度所需 的全部信息。例如：作业标识、用户名称、用户帐 户、作业类型、作业状态、调度信息、资源需求、 进入系统时间、开始处理时间、作业完成时间、作 业退出时间、资源使用情况等。
第三章 处理机调度与死锁
要解决的三个问题：
WHAT：按什么原则分配CPU？ —进程调度算法
WHEN：何时分配CPU？ —进程调度的时机
HOW： 如何分配CPU？ —CPU调度过程（进程的上下文切换）
处理机调度与死锁ppt课件
第三章 处置机调度与死锁
3.1 处置机调度的层次 3.2 调度队列模型和调度准那么 3.3 调度算法 3.4 实时调度 3.5 产生死锁的缘由和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
第三章 处理机调度与死锁
处置机调度与死锁(Scheduling and Deadlock )
教学目的： 在多道程序系统中，一个作业从提交到执行完
第三章 处理机调度与死锁
2) 抢占方式(Preemptive Mode)
这种调度方式允许调度程序根据某种原那么去暂停某个 正在执行的进程，将已分配给该进程的处置机重新分配给另 一进程。抢占方式的优点是，可以防止一个出息程长时间占 用途置机，能为大多数进程提供更公平的效力，特别是能满 足对呼应时间有着较严厉要求的实时义务的需求。但抢占方 式比非抢占方式调度所需付出的开销较大。抢占调度方式是 基于一定原那么的，主要有如下几条：
第三章 处理机调度与死锁
2．进程调度中的三个根本机制
为了实现进程调度，应具有如下三个根本机制：
(1) 排队器。为了提高进程调度的效率，应事先将系统 中一切的就绪进程按照一定的方式排成一个或多个队列，以 便调度程序能最快地找到它。
(2) 分派器(分派程序)。分派器把由进程调度程序所选 定的进程，从就绪队列中取出该进程，然后进展上下文切换， 将处置机分配给它。
成，要阅历多级调度，调度的好坏要影响系统的运 转性能，因此调度是多道系统的关键。为了改善系 统资源的利用率和提高系统处置才干，多道程序系 统中采用多个进程的并发执行，但它也能够发生死 锁的危险，研讨死锁的缘由和产生条件，采用预防 死锁、防止死锁、检测死锁和解除死锁等多种方法 防止死锁是多道程序系统重要的研讨课题。
第三章 处理机调度与死锁
3.1 处置机调度的层次 3.2 调度队列模型和调度准那么 3.3 调度算法 3.4 实时调度 3.5 产生死锁的缘由和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
第三章 处理机调度与死锁
处置机调度与死锁(Scheduling and Deadlock )
教学目的： 在多道程序系统中，一个作业从提交到执行完
第三章 处理机调度与死锁
2) 抢占方式(Preemptive Mode)
这种调度方式允许调度程序根据某种原那么去暂停某个 正在执行的进程，将已分配给该进程的处置机重新分配给另 一进程。抢占方式的优点是，可以防止一个出息程长时间占 用途置机，能为大多数进程提供更公平的效力，特别是能满 足对呼应时间有着较严厉要求的实时义务的需求。但抢占方 式比非抢占方式调度所需付出的开销较大。抢占调度方式是 基于一定原那么的，主要有如下几条：
第三章 处理机调度与死锁
2．进程调度中的三个根本机制
为了实现进程调度，应具有如下三个根本机制：
(1) 排队器。为了提高进程调度的效率，应事先将系统 中一切的就绪进程按照一定的方式排成一个或多个队列，以 便调度程序能最快地找到它。
(2) 分派器(分派程序)。分派器把由进程调度程序所选 定的进程，从就绪队列中取出该进程，然后进展上下文切换， 将处置机分配给它。
成，要阅历多级调度，调度的好坏要影响系统的运 转性能，因此调度是多道系统的关键。为了改善系 统资源的利用率和提高系统处置才干，多道程序系 统中采用多个进程的并发执行，但它也能够发生死 锁的危险，研讨死锁的缘由和产生条件，采用预防 死锁、防止死锁、检测死锁和解除死锁等多种方法 防止死锁是多道程序系统重要的研讨课题。
第三章 处理机调度与死锁
第三章 处理机调度与死锁.ppt
第三章 处理机调度与死锁
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 t
A (a) q＝ 1
B
A B
A
A
B
C
C
C
C
D
D
E
E
E
E
(b) q＝ 4
第三章 处理机调度与死锁
作业 情况
时间片
RR q=1
RR q=4
进程名 到达时间
A
B
C
0
1
2
服务时间
4
3
4
完成时间
15 12 16
第三章 处理机调度与死锁 3.1 处理机调度的层次和调度算法的目标 3.1.2 处理机算法的目标
①作业平均周转时间（T）
n
T＝（ Ti ）× 1
i =1
n
②带权平均周转时间（W）
n
W＝（
Ti ）×
1
i = 1 ri
n
n为作业数目， 第i个作业的周转时 间 Ti ＝ Ei– Si Ei：作业完成时间 Si：作业提交时间
2 进程调度机制 (1)排队器 (2)分派器 (3)上下文切换机制
3.3 进程调度
第三章 处理机调度与死锁
3 调度方式 (1)非抢占式
＊引发进程调度的事件——执行完毕、进程阻塞、执行原语 ＊特点——实现简单、开销小、不能立即执行
（2）抢占式
＊基本原则—优先权原则、短作业（进程）优先、时间片原则 ＊特点—开销大、公平、响应及时
第三章 处理机调度与死锁
3.3 进程调度 3.3.2 轮转调度算法（RR）
1 轮转法的基本原理
按FCFS将就绪进程排成一个就绪队列，进程按时间片轮 流使用CPU。
第三章处理机调度与死锁-PPT精品
(1) 进程类型。 (2) 进程对资源的需求。 (3) 用户要求。
第三章 处理机调度与死锁
2) 动态优先权
计算机操作系统
动态优先权是指，在创建进程时所赋予的优先权， 是可以随进程的推进或随其等待时间的增加而改变的， 以便获得更好的调度性能。
第三章 处理机调度与死锁
3. 高响应比优先调度算法
计算机操作系统
3.1.3 选择调度方式和调度算法的若干准则
1. 面向用户的准则 (1) 周转时间短。 周转时间的长短是评价批处理系统性能、选择作业调
度方式与算法的重要准则之一
第三章 处理机调度与死锁
(1) 周转时间短。
计算机操作系统
周转时间：从作业提交给系统开始，到作业完成为之 的这段时间间隔（作业周转时间） 作业在外存后备队列上等待（作业）调度的时间 进程在就绪队列上等待进程调度的时间 进程在CPU上执行的时间 进程等待I/O操作完成的时间
第三章 处理机调度与死锁
计算机操作系统
第三章 处理机调度与死锁
ห้องสมุดไป่ตู้算机操作系统
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
3.1.1 高级、中级和低级调度
1. 高级调度(High Scheduling)
又称作业调度、长程调度：决定把外存上处于后备 队列中的哪些作业调入内存，并为之创建进程、分配必 要的资源，然后，再将新创建的进程排在就绪队列中。
优先权的变化规律可描述为：
优先权 等待要时求 间 要服求务服时务间时间
由于等待时间与服务时间之和，就是系统对该作 业的响应时间，故该优先权又相当于响应比RP。据此， 又可表示为：
优先 等 权待 要 时 求 要间 服 求务 服时 务 要 响 间 时 求 应 间 服 时 务 间
第3章处理机调度与死锁132页PPT
作为系统管理者希望作业平均周转时间最短，有利于大多数
用户 可把平均周转时间描述为：T
1 n
n
Ti i1
作业的周转时间T与系统为它提供服务的时间TS之比，即
W=T/TS，称为带权周转时间，而平均带权周转时间则可表
示为:
W
1 n
n i1
Ti TSi
2020/5/8
12
3调度基本准则
目的
是为了进一步提高主存的利用率和系统的吞吐量。管理 进程在内外存间的交换，从存储器资源管理的角度来看， 把进程的部分或全部换出到外存上，可为当前运行进程 的执行提供所需内存空间。
2020/5/8
4
三种调度中，进程调度运行频率最高，在分 时系统中通常是10~100ms便进行一次进程 调度，因而进程调度算法不能太复杂。 作业调度往往是发生在一个（批）作业运行 完毕，退出系统，而需要重新调入一个（批） 作业进入时，帮作业调度的周期较长，大约 几分钟一次。 中级调度的运行频率，介于上述两种调度之 间
2020/5/8
3
中级调度
系统将那些暂时不能运行的进程从主存调到外存（仍然 保持进程状态）上的特定区域，这些在外存存放的进程 所处的状态称为就绪驻外状态或挂起状态。当这些进程 的运行条件具备，且主存又有空闲时，在中级调度的控 制下，再将处于外存上的那些重新具备运行条件的就绪 驻外进程调入主存，并将其状态修改为就绪状态，放入 就绪队列，等待进程调度。
① 就绪队列的形式：在批处理系统中，最常用的是最高优 先权调度算法，相应的最常用的就绪队列形式是优先权 队列。（仅有进程调度的模型就绪队列采用FIFO队列形 式）
② 设置多个阻塞队列。
2020/5/8
8
调度队列模型
操作系统第3章
给其抢它占进原程则，有决：不允许某进程抢占已 经分配优出先去权的原处则理；机。 优点：短实作现业简优单先，原系则统；开销小。 缺点：时难间于片满原足则紧。急任务的要求。
3.1 处理机调度的基本概念
3. 中级调度
挂起和激活，存储器管理中的对换功能。
主要目的： 为了提高内存的利用率和系统的吞吐量。
三种调度相比较：
● 高级调度的相关概念
作业：用户一次请求计算机系统为其完成任务所做工作 的总和。它通常包括程序、数据和作业说明书，系统根 据说明书对程序进行控制。 作业步：指每个作业在运行期间，都必须经过若干个相 对独立，又相互关联的顺序加工步骤，其中的每一个加 工步骤称为作业步。一个典型的作业可分成三个作业 步：① “编译”作业步，② “连结装配”作业步，③ “运行”作业步 作业状态：作业状态分为后备、运行和完成三种状态。 作业控制块（Job Control Block，JCB）
调度方式
3.1.3 选择调度方式和调度算法的若干准则 2. 面向系统的准则吞吐量：单位时间内系统所
完成的作业数
（1）系统吞吐量高
调度方式和算法对处理机的
（2）处理机利用率好 利用率起着十分重要的作用
（3）各类资源的均衡利 用
对于单用户微机或某些实 时系统，该准则并不重要
3.2 调度算法
3.2.1 先来先服务调度算法
进程插入到就决定： ●接纳多少个作业——取决于多道程序度 ●接纳哪些作业——取决于调度算法
▲内存中同时运行的 作业数目太多，会影 响系统的服务质量。 如，周转时间长。
▲内存中同时运行的 作业数目太少，会导 致系统资源利用率和 系统吞吐量低。
3.1.1 高级、中级和低级调度
算，而很少请求I/O。如，科学计算
3.1 处理机调度的基本概念
3. 中级调度
挂起和激活，存储器管理中的对换功能。
主要目的： 为了提高内存的利用率和系统的吞吐量。
三种调度相比较：
● 高级调度的相关概念
作业：用户一次请求计算机系统为其完成任务所做工作 的总和。它通常包括程序、数据和作业说明书，系统根 据说明书对程序进行控制。 作业步：指每个作业在运行期间，都必须经过若干个相 对独立，又相互关联的顺序加工步骤，其中的每一个加 工步骤称为作业步。一个典型的作业可分成三个作业 步：① “编译”作业步，② “连结装配”作业步，③ “运行”作业步 作业状态：作业状态分为后备、运行和完成三种状态。 作业控制块（Job Control Block，JCB）
调度方式
3.1.3 选择调度方式和调度算法的若干准则 2. 面向系统的准则吞吐量：单位时间内系统所
完成的作业数
（1）系统吞吐量高
调度方式和算法对处理机的
（2）处理机利用率好 利用率起着十分重要的作用
（3）各类资源的均衡利 用
对于单用户微机或某些实 时系统，该准则并不重要
3.2 调度算法
3.2.1 先来先服务调度算法
进程插入到就决定： ●接纳多少个作业——取决于多道程序度 ●接纳哪些作业——取决于调度算法
▲内存中同时运行的 作业数目太多，会影 响系统的服务质量。 如，周转时间长。
▲内存中同时运行的 作业数目太少，会导 致系统资源利用率和 系统吞吐量低。
3.1.1 高级、中级和低级调度
算，而很少请求I/O。如，科学计算
3处理机调度与死锁-PPT资料112页
进程调度
进程完成
CPU
事件1出现
等待事件1
事件2出现
等待事件2
… … … …
事件n出现
等待事件n
具有高、低两级调度的调度队列模型
第三章 处理机调度与死锁
图 3-2 示出了具有高、低两级调度的调度队列模型。 该模型与上一模型的主要区别在于如下两个方面。
(1) 就绪队列的形式。 (2) 设置多个阻塞队列。
(2) 当要求服务的时间相同时，作业的优先权决定于 其等待时间，等待时间愈长，其优先权愈高，因而它实 现的是先来先服务。
(3) 对于长作业，作业的优先级可以随等待时间的增 加而提高，当其等待时间足够长时，其优先级便可升到 很高， 从而也可获得处理机。
第三章 处理机调度与死锁
作业1 作业2 作业3 作业5 作业4 0 3 9 13 15 20
第三章 处理机调度与死锁
3.1.2 调度队列模型
1. 仅有进程调度的调度队列模型
交互用户
事 件 出 现
时间片完 就绪 队列 阻塞 队 列
进程调度
进程完成
CPU
等待事件
仅具有进程调度的调度队列模型
第三章 处理机调度与死锁
2. 具有高级和低级调度的调度队列模型
作业 调度
后 备队 列
时间片完 就绪 队 列
第三章 处理机调度与死锁
3.3 调 度 算 法
• 先进先服务调度算法 • 短作业优先调度算法 • 高优先权优先调度算法 • 最高响应比优先 • 时间片轮转调度算法 • 最短剩余时间优先调度算法 • 均衡法 • 多级反馈队列调度算法
第三章 处理机调度与死锁
3.3.1先来先服务调度算法
其原则按照作业到达系统或进程进入就绪队 列先后次序来选择。 FIFO是一种非抢占算法。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
时间片完 就绪队列
阻塞队列
进程调度 进程完成
CPU
等待事件
2020/11/29
阜阳师范学院计算机与信息学院
12
2. 具有高级和低级调度的调度队列模型
作业调度
后备队列
时间片完 就绪队列
进程调度 进程完成
CPU
事件1出现 事件2出现 事件n出现
2020/11/29
等待事件1 等待事件2 等待事件n
阜阳师范学院计算机与信息学院
2020/11/29
阜阳师范学院计算机与信息学院
4
1. 高级调度
又称为作业调度、宏观调度或长程 调度。用于决定把后备队列中的哪些作 业调入内存，为他们分配必要的资源， 并创建进程。
批处理系统 ： 需要作业调度 分时系统 ： 不需作业调度 实时系统 ： 不需作业调度
2020/11/29
阜阳师范学院计算机与信息学院
Run time 27 3 5
0
2020/11/29
P1
P2 P3
27 30 35
阜阳师范学院计算机与信息学院
17
FCFS（First Come First Serve)
FCFS实例 下表列出了A、B、C、D四个作业分别到达系 统的时间、要求服务的时间、开始执行的时间 及各自的完成时间，计算出各自的周转时间和 带权周转时间。阜阳师范学Fra bibliotek计算机与信息学院
8
3. 中级调度
中级调度又称为交换调度或中程调 度。
它按一定的算法将外存中已具备运行 条件的进程换入内存，而将内存中处于 阻塞状态的某些进程换出至外存。
2020/11/29
阜阳师范学院计算机与信息学院
9
运行
就绪
调
度
阻塞
的
层
进程调度
次
挂起阻塞
创建
挂起就绪
中级调度
作业调度
2020/11/29
阜阳师范学院计算机与信息学院
2
2020/11/29
阜阳师范学院计算机与信息学院
3
3.1.1 高级、中级和低级调度
经历下述三级调度:
1、高级调度（High Scheduling） 2、中级调度（Intermediate-Level
Scheduling） 3、低级调度（Low Level Scheduling）
1 100 100 199
1 1 100 1.99
19
FCFS（First Come First Serve)
FCFS的特点:
FCFS调度算法有利于CPU繁忙型的作业， 而不利于I/O繁忙型的作业（进程）
比较有利于长作业，而不利于短作业
2020/11/29
阜阳师范学院计算机与信息学院
20
2. 短作业（进程）优先调度算法
13
3. 同时具有三级调度的调度队列模型
作业调度
批量作业 后备队列
交互型作业
时间片完
就绪 队 列
进程调度
进程完 CPU 成
中级调度 就绪、挂起队列
事件出现 中级调度
阻 塞、挂 起 队 列
挂起 事件出现 挂起
2020/11/29
阻塞队列
等待事件
阜阳师范学院计算机与信息学院
14
3.1.3 选择调度方式和调度算法的若干准则
退出
3.1.2 调度队列模型
1. 仅有进程调度的调度队列模型 2. 具有高级和低级调度的调度队列模型 3. 同时具有三级调度的调度队列模型
2020/11/29
阜阳师范学院计算机与信息学院
11
1. 仅有进程调度的调度队列模型
在分时系统中就绪进程组织成FIFO队列 形式，按时间片轮转方式运行。
交互用户 事 件 出 现
2020/11/29
作业情 况
调度算法
作业名 到达时间 服务时间
完成时间
FCFS 周转时间
带权周转时间
完成时间
SJF 周转时间
带权周转时间
A B C D E 平均
01 2 3 4
43 5 2 4
4 7 12 14 18 4 6 10 11 14 9 1 2 2 5.5 3.5 2.8 4 9 18 6 13 4 8 16 3 9 8 1 2.67 3.2 1.5 2.25 2.1
2020/11/29
阜阳师范学院计算机与信息学院
18
FCFS（First Come First Serve)
作业名 到达时 服务时 开始执 完成时 周转时 带权周
间
间
行时间 间
间
转时间
A
0
B
1
C
2
D
3
2020/11/29
1
0
1
100
1
101
1
101
102
100
102
202
阜阳师范学院计算机与信息学院
3.2.1 FCFS与SJF/SPF调度算法 3.2.2 高优先权优先调度算法 3.2.3 基于时间片的轮转调度算法
2020/11/29
阜阳师范学院计算机与信息学院
16
3.2.1 FCFS与SJF/SPF调度算法
1. 先来先服务调度算 法(FCFS)
按进程申请CPU（就 绪）的次序
process P1 P2 P3
5
1. 高级调度
执行作业调度时，必须作出两个决定： 接纳多少作业——每次接纳多少作业进入
内存，取决于多道程序度，即允许多少个 作业同时在内存中运行。 接纳哪些作业——应接纳哪些作业从外存 调入内存，取决于所采用的调度算法。
2020/11/29
阜阳师范学院计算机与信息学院
6
2. 低级调度
通常也称为进程调度、微观调度或短程 调度。进程调度是最基本的一种调度，在三种 OS中都有。用于决定就绪队列中哪个进程应 先获得处理机，并将处理机分配给选中的进程。
第3章 处理机调度与死锁
3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 产生死锁的原因和必要条件 3.5 预防死锁的方法 3.6 死锁的检测与解除
2020/11/29
阜阳师范学院计算机与信息学院
1
3.1 处理机调度的基本概念
3.1.1 高级调度、中级调度、低级调度 3.1.2 调度队列模型 3.1.3 选择调度方式和调度算法的若干准则
面向用户的准则
✓ 周转时间短 • 平均周转时间T • 平均带权周转时间（W= T(周 转)/Ts(CPU执行))
✓ 响应时间快 ✓ 截止时间的保证 ✓ 优先权准则
面向系统的准则
✓ 系统吞吐量高 ✓ 处理机利用率好 ✓ 各类资源的平衡利用
2020/11/29
阜阳师范学院计算机与信息学院
15
3.2 调度算法
为实现进程调度，应具有如下三个基本机制：
✓ 排队器
✓ 分派器
✓ 上下文切换
2020/11/29
阜阳师范学院计算机与信息学院
7
2. 低级调度
进程调度可采用下述两种调度方式： 非抢占方式 抢占方式 抢占的原则有： （1）优先权原则 （2）短作业（进程）优先原则 （3）时间片原则
2020/11/29