中国科学技术大学：《嵌入式操作系统 Embedded Operating Systems》课程教学资源（PPT课件讲稿）第四讲 CPU调度（part II）

内容提要 ◆调度的类型 令调度的队列模型 令调度的准则 令调度的算法 1958 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

内容提要 ❖调度的类型 ❖调度的队列模型 ❖调度的准则 ❖调度的算法

调度算法 ☆FCFS ☆SJF ☆RR ☆ Priority- based 令多级队列(及反馈)调度 令优先级倒转问题及其解决方案 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

调度算法 ❖FCFS ❖SJF ❖RR ❖Priority－based ❖多级队列（及反馈）调度 ❖优先级倒转问题及其解决方案

调度算法 ☆FCFS ☆SJF ☆RR ☆ Priority- based 令多级队列(及反馈)调度 令优先级倒转问题及其解决方案 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

调度算法 ❖FCFS ❖SJF ❖RR ❖Priority－based ❖多级队列（及反馈）调度 ❖优先级倒转问题及其解决方案

先来先服务算法 令先来先服务算法FCFS first come. first served 是一种最简单的调度算法 按照请求处理的时间先后顺序,先来先服务 >通过采用一个FIFO的PCB队列来实现 ◆可用于作业调度、进程调度 前者每次调度时从后备作业队列中,选择一个或者多 个最先进入该队列的作业 >后者每次从就绪队列中,选择一个最先进入该队列的 进程 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

先来先服务算法 ❖先来先服务算法FCFS First Come, First Served 是一种最简单的调度算法 ➢按照请求处理的时间先后顺序，先来先服务 ➢通过采用一个FIFO的PCB队列来实现 ❖可用于作业调度、进程调度 ➢前者每次调度时从后备作业队列中，选择一个或者多 个最先进入该队列的作业 ➢后者每次从就绪队列中，选择一个最先进入该队列的 进程

先来先服务算法举例(1) 进程到达服务开始执完成周转带权周 名时间时间行时间时间时间转时间 A0 B1 1001 1011001 C2 101 102100100 太大了 102 202199 ◆由此可知,FCFS算法比较有利于长作业,而不 利于短作业 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

❖由此可知，FCFS算法比较有利于长作业，而不 利于短作业 先来先服务算法举例（1） 进程 名 到达 时间 服务 时间 开始执 行时间 完成 时间 周转 时间 带权周 转时间 A 0 1 0 1 1 1 B 1 100 1 101 100 1 C 2 1 101 102 100 100 D 3 100 102 202 199 1.99 太大了

先来先服务算法举例(2) Process burst Time 24 令对于进程P1、P2和P3, PPP 3 到达时间均为0 3 令若到达顺序为P1、P2、P3,则按照FCFS调度算法得到 的甘特图为 P1 P2 P3 242730 令则P1、P2、P3的等待时间依次为0、24、27 而平均等待时间为(0+2427)/3=17 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

先来先服务算法举例（2） ❖ 对于进程P1、P2和P3， 到达时间均为0 ❖ 若到达顺序为P1、P2、P3，则按照FCFS调度算法得到 的甘特图为： ❖ 则P1、P2、P3的等待时间依次为0、24、27 ❖ 而平均等待时间为(0+24+27)/3=17 P1 P2 P3 0 24 27 30

令若到达顺序为P2、P3、P1,则按照FCFS调度算 法得到的甘特图为 3 30 1550 >则P1、P2、P3的等待时间依次为6、0、3 而平均等待时间为6+0+3)/3=3 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

❖若到达顺序为P2、P3、P1，则按照FCFS调度算 法得到的甘特图为： ➢则P1、P2、P3的等待时间依次为6、0、3 而平均等待时间为(6+0+3)/3=3

思考: 令定义:CPU繁忙型作业:是指需要大量的CPU时间进行 计算,而很少请求IO的作业。 常见于用于科学计算的作业 ◆定义:IO繁忙型作业:是指CPU进行处理时,又需频繁 地请求O,而每次IO的操作时间却又很短。 >常见于用于事务处理的作业 令请问:当采用FCFS算法时,对这两种作业有何影响? 名词“ convoy effect (即户卫效应)0s:P9,掌握 ☆阅读参考书: Operating System Cor 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

思考： ❖ 定义：CPU繁忙型作业：是指需要大量的CPU时间进行 计算，而很少请求I/O的作业。 ➢ 常见于用于科学计算的作业 ❖ 定义：I/O繁忙型作业：是指CPU进行处理时，又需频繁 地请求I/O，而每次I/O的操作时间却又很短。 ➢ 常见于用于事务处理的作业 ❖ 请问：当采用FCFS算法时，对这两种作业有何影响？ ❖ 阅读参考书：Operating System Concepts，P159页，掌握 名词“convoy effect”（即护卫效应）

调度算法 ☆FCFS ☆SJF ☆RR ☆ Priority- based 令多级队列(及反馈)调度 令优先级倒转问题及其解决方案 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

调度算法 ❖FCFS ❖SJF ❖RR ❖Priority－based ❖多级队列（及反馈）调度 ❖优先级倒转问题及其解决方案

短作业优先调度 ☆使得短作业(进程)能够比长作业(进程)优先 执行 >短作业优先调度( Shortest job first,SJF) ●调度时从后备队列中选择一个或者若干个估计运行时间最短 的作业 短进程优先调度( Shortest process first,SPF) ●调度时,从就绪队列中选择一个估计运行时间最短的进程 ◆两种实现方案:抢占和非抢占 ☆阅读: Operating System Concepts,P160,了解 SJF算法更细致的定义 嵌入式系统实验室 EMBEDDED SYSTEM LABORATORY

短作业优先调度 ❖使得短作业（进程）能够比长作业（进程）优先 执行 ➢短作业优先调度（Shortest Job First，SJF） ⚫调度时从后备队列中选择一个或者若干个估计运行时间最短 的作业 ➢短进程优先调度（Shortest Process First，SPF） ⚫调度时，从就绪队列中选择一个估计运行时间最短的进程 ❖两种实现方案：抢占和非抢占 ❖阅读：Operating System Concepts，P160，了解 SJF算法更细致的定义