调度准则和算法评价 调度准则 面向用户 周转时间 响应时间 最后期限 可预测性 >面向系统 吞吐量 处理机利用率 公平 平衡资源 强制优先级 CUIT徐红 设计调度算法时考虑的因素 应与系统的整个设计目标一致。 系统资源的均衡使用 平衡系统和用户要求。 统 大多数系统都根据用户的需要而采用兼 顾某些目标的简单调度算法。 CUIT徐红
6 操 作 系 统 | 调 度 与 死 锁 11 CUIT 徐虹 ¾调度准则和算法评价 ¾调度准则 ¾面向用户 ¾周转时间 ¾响应时间 ¾最后期限 ¾可预测性 ¾面向系统 ¾吞吐量 ¾处理机利用率 ¾公平 ¾平衡资源 ¾强制优先级 操 作 系 统 | 调 度 与 死 锁 12 CUIT 徐虹 ¾设计调度算法时考虑的因素 ¾应与系统的整个设计目标一致。 ¾系统资源的均衡使用。 ¾平衡系统和用户要求。 大多数系统都根据用户的需要而采用兼 顾某些目标的简单调度算法
调度性能的衡量 批处理系统:平均周转时间或平均带权周 转时间 分时或实时系统:平均响应时间 周转时间: 作业i.Ti=Tei-Tbi=Twi+Tsi Te:完成时间Tbi:提交时间 Twi:等待时间Ts:执行时间 有n个作业的作业流,其平均周转时间: T=1hn[1+T2+……Tn] CUIT徐红 带权周转时间 比较某种调度算法对不同作业流的调度性能。 Wi=Ti「si 系平均带权周转时间: W=1/nw1+w2+…+Wn] 一般,总是T或W小的作业被选中,因为这样 死资源利用率较高,用户也满意 响应时间 截止完成时间 CUIT徐红
7 操 作 系 统 | 调 度 与 死 锁 13 CUIT 徐虹 ¾调度性能的衡量 批处理系统：平均周转时间或平均带权周 转时间 分时或实时系统：平均响应时间 ¾周转时间： 作业i. Ti = Tei – Tbi = Twi + Tsi Tei: 完成时间 Tbi:提交时间 Twi：等待时间 Tsi：执行时间 有n个作业的作业流，其平均周转时间： T = 1/n [T1 + T2 + ……+ Tn ] 操 作 系 统 | 调 度 与 死 锁 14 CUIT 徐虹 ¾带权周转时间 比较某种调度算法对不同作业流的调度性能。 Wi=Ti/Tsi 平均带权周转时间： W = 1/n [W1 + w2 + …… + Wn ] 一般，总是T或W小的作业被选中，因为这样 资源利用率较高，用户也满意。 ¾响应时间 ¾截止完成时间
例:假定有四个作业,它们的提交,运行,完成情况如下 作业 Tbi tsi开始完成 操18:002008:0010:002.001.00 系28:300.5010:0010:302.004.00 39:000.10 10:361.616.00 调49:300.2010:3610:481.36.5 锁平均周转时间T=1.725(小时) 15平均带权周转时间W=6875 CUIT徐红 4.2调度算法 作>先来先服务调度算法 统 原理 作业 进程 特点 利于长作业,利于cPU繁忙型的作业。 CUIT徐红
8 操 作 系 统 | 调 度 与 死 锁 15 CUIT 徐虹 例：假定有四个作业，它们的提交，运行，完成情况如下： 作业 Tbi Tsi 开始 完成 Ti Wi 1 8：00 2. 00 8：00 10：00 2. 00 1. 00 2 8：30 0. 50 10：00 10：30 2. 00 4. 00 3 9：00 0. 10 10：30 10：36 1. 6 16. 00 4 9：30 0. 20 10：36 10：48 1. 3 6. 5 平均周转时间 T=1.725(小时) 平均带权周转时间 W=6.875 操 作 系 统 | 调 度 与 死 锁 16 CUIT 徐虹 4．2 调度算法 ¾先来先服务调度算法 ¾原理 ¾ 作业 ¾进程 ¾特点 利于长作业，利于CPU 繁忙型的作业
Process Arrival Time Service Time ABCDE 36452 8 5 inish Time turnaround Time (Tr) 1.17 2.25 2.40 6.00 u氰 最短作业(进程)优先法(SJF) 原理:估计运行时间 优点:SJF能有效地降低作业的平均等待 时间和提高系统吞吐量。 统 缺点: 对长作业不利; 不能保证紧迫性作业或进程会得到及时处理 >不一定能真正做到短作业优先。 CUIT徐红
9 操 作 系 统 | 调 度 与 死 锁 17 CUIT 徐虹 0 5 10 15 20 1 2 3 4 5 操 作 系 统 | 调 度 与 死 锁 18 CUIT 徐虹 ¾最短作业（进程）优先法 （SJF） ¾原理：估计运行时间。 ¾优点：SJF能有效地降低作业的平均等待 时间和提高系统吞吐量。 ¾缺点： ¾对长作业不利； ¾不能保证紧迫性作业或进程会得到及时处理； ¾不一定能真正做到短作业优先
Process Arrival Time Service Time e B 6 E 8 2 inish Time Turnaround Time (Tr) Tr/TS 1.17 280 50 184 Process Arrival Time Service Time us 最短剩余时 2 6 间 E 8 10 R inish Time Turnaround Time (Tr) 1.00
10 操 作 系 统 | 调 度 与 死 锁 19 CUIT 徐虹 0 5 10 15 20 1 2 3 4 5 操 作 系 统 | 调 度 与 死 锁 20 CUIT 徐虹 0 5 10 15 20 1 2 3 4 5 最 短 剩 余 时 间 （ S R T）