PURSUING EXCELLENCE / TOWARD SUCCESS WUCHANG UNIVERSITY OF TECHNOLOGY 武昌理工学院 操作系统原理 第六章 处理机调度 我们毕业啦 其实是答辩的标题地方 主讲人 温 静 院系 信息工程学院

主要内容 1 处理机调度的分类 2 三级调度 3 选择调度算法的准则 批处理系统中的调度算法 4 CONTANTS 5 分时系统中的调度算法

处理机调度的分类 高级（宏观、作业、长程）调度： 将作业从系统外存调入内存 处理机调度 低级（微观、进程、短程）调度： 将CPU分配给处于就绪状态的某个进程，使之执行 中级（交换、对换、中程）调度： 内外存进程的互换

三级调度 执行 提交 后备 完成 就绪 阻塞 静止就绪 静止阻塞 执行 交换 作业调度 对作业调度而言,只要进入内存就称之为执行,事实上没有真正得到CPU. 执行 内存 执行 进程调度 提交 后备 完成 就绪 外存 阻塞 交换 静止就绪 静止阻塞 外存

调度方式 抢占式调度 非抢占式调度 ①正在执行的进程执行完毕，或因发生某事件而不能再继续执行； 抢占原则： ②执行中的进程因提出I/O请求而暂停执行； ③在进程通信或同步过程中执行了某种原语操作，如wait原语、block原语、wakeup原语等 非抢占式调度 抢占原则： ①优先权原则 ②短作业(进程)优先原则 ③时间片原则 抢占式调度

选择调度算法的准则 面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 面向系统的准则 系统吞吐量高 处理机利用率好 各类资源的平衡利用 批处理系统 分时系统 实时系统 平均周转时间： 平均带权周转时间：

先来先服务调度算法（FCFS） 开始+服务 完成-到达 周转/服务 带权周转时间 作业名 到达时间 服务时间 开始时间 完成时间 周转时间 1 8 2 8 10 2 1 2 8.5 0.5 10 10.5 2 4 3 9 0.1 10.5 10.6 1.6 16 4 0.2 10.6 10.8 1.3 9.5 6.5 平均周转时间： t=1/4（2+2+1.6+1.3）=1.725 平均带权周转时间： w=1/4（1+4+16+6.5）=6.875

先来先服务调度算法（FCFS） 优点 缺点 简单 容易实现 只考虑到作业到达系统的先后顺序，即作业的等待时间（等待时间越久代表到达系统越早），而未考虑到作业的服务时间的长短。 简单 容易实现

短作业优先调度算法（SJF） 带权周转时间 作业名 到达时间 服务时间 开始时间 完成时间 周转时间 1 8 2 8 10 2 1 2 8.5 0.5 10.3 10.8 2.3 4.6 3 9 0.1 10 10.1 1.1 11 4 0.2 10.1 10.3 0.8 4 9.5 平均周转时间： t=1/4（2+2.3+1.1+0.8）=1.55 平均带权周转时间： w=1/4（1+4.6+11+4）=5.15

短作业优先调度算法（SJF） 优点 缺点 具有很好的性能，能有效地降低作业的平均等待时间，提高系统吞吐量 对长作业不利； 未考虑作业的紧迫程度，因而不能保证紧迫作业会被及时处理，不能用于实时系统； 不一定能真正做到短作业优先调度。 具有很好的性能，能有效地降低作业的平均等待时间，提高系统吞吐量

最短剩余时间优先调度算法 带权周转时间 作业名 到达时间 服务时间 开始时间 完成时间 周转时间 1 8 2 8 10.8 2.8 1.4 8.5 0.5 8.5 9 0.5 1 3 9 0.1 9 9.1 0.1 1 4 0.2 9.5 9.7 0.2 9.5 1 平均周转时间： t=1/4（2.8+0.5+0.1+0.2）=0.9 平均带权周转时间： w=1/4（1.4+1+1+1）=1.1

最短剩余时间优先调度算法 优点 缺点 也存在短作业优先算法的那些缺点，除此之外，由于是抢占的方式，所以进程之间会发生较频繁的切换，这种切换将会付出很大的系统开销，所以该算法的实现代价较高 与短作业优先调度算法比较起来，最短剩余时间优先调度算法的平均周转时间和平均带权周转时间更短，性能更好

高响应比优先调度算法 响 应 比 响应比=响应时间/服务时间 响应时间=等待时间+服务时间 响应比=等待时间/服务时间+1 （1）该算法优待短作业。 （2）该算法也实现了先来先服务。 （3）该算法不会使得长作业长期等待而不能运行，从而导致饥饿。

高响应比优先调度算法 响应比： 2：（10-8.5+0.5）/0.5=4 3：（10-9+0.1）/0.1=11 带权周转时间 作业名 到达时间 服务时间 开始时间 完成时间 周转时间 1 8 2 8 10 2 1 响应比： 2：（10-8.5+0.5）/0.5=4 3：（10-9+0.1）/0.1=11 4：（10-9.5+0.2）/0.2=3.5 2 8.5 0.5 10.1 10.6 2.1 4.2 3 0.1 10 9 10.1 1.1 11 4 9.5 0.2 10.6 10.8 1.3 6.5 响应比： 2：（10.1-8.5+0.5）/0.5=4.2 4：（10.1-9.5+0.2）/0.2=4 平均周转时间： t=1/4（2+2.1+1.1+1.3）=1.625 平均带权周转时间： w=1/4（1+4.2+11+6.5）=5.675

高响应比优先调度算法 优点 缺点 该算法的不足之处在于，每次进行调度前，都需要计算每个作业的响应比，这会增加系统开销 该算法是介于先来先服务和短作业优先两种算法之间的一种折中算法，既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务

时间片轮转调度算法 主要用于分时系统中的进程调度； 基本思想： 系统将CPU处理时间划分为若干个时间片（记为q）； 将所有就绪进程按照其到达就绪队列的次序进行排 列； 选择队首进程占用CPU运行； 每次只能运行一个时间片。

时间片轮转调度算法 性能主要取决于时间片的大小； 如果时间片设置得太大，算法便退化为先来先 服务调度算法，未能体现轮转的特点； 如果时间片太小，又会发生进程间的频繁切换， 系统开销显著增加； 因此时间片的大小应选择适当。

时间片轮转调度算法 时间片的长短通常由以下因素确定： （1）系统的响应时间。 （2）就绪队列中的进程数目。 （3）系统的处理能力。

时间片轮转调度算法 假设有A、B、C、D、E五个进程，其到达系统的时间分 别为0、1、2、3、4，要求运行时间依次为3、6、4、 5、2，采用时间片轮转调度算法，当时间片大小分 别为1和4时，试计算其平均周转时间和平均带权周 转时间。

时间片轮转调度算法

时间片轮转调度算法

时间片轮转调度算法

时间片轮转调度算法

多级反馈队列调度算法 综合了先来先服务调度算法、抢占式优先级调度 算法和时间片轮转调度算法； 优点： 兼顾了以上各种算法的优点，可以满足各种类型的 进程的需要； 而且不必事先知道各种进程所需的执行时间； 因此是目前公认的一种较好的进程调度算法。

多级反馈队列调度算法 调度过程： 就绪队列1 就绪队列2 就绪队列3 就绪队列n S1 S2 S3 至CPU

本章小结 三级调度 选择算法准则 批处理中的算法 分时系统的算法 处理机调度的分类 作业调度、交换、进程调度 三级调度图 面向用户的准则、 面向系统的准则 FCFS调度算法、SJF调度算法、 最短剩余时间优先调度算法、 高响应比优先调度 批处理中的算法 分时系统的算法 时间片轮转调度算法、 多级反馈队列调度算法

PURSUING EXCELLENCE / TOWARD SUCCESS WUCHANG UNIVERSITY OF TECHNOLOGY 武昌理工学院 Thank you！