第四章调度与死锁 不同的0S,处理机管理的策略不同 系>衡量调度策略的指标 周转时间 吞吐率 响应时间 设备利用率 调度算法 死锁的概念和解决方案 CUIT徐红 4.1调度的类型和模型 操>调度类型 高级调度 统 作业的状态及其转换 作业从输入到完成要经历提交,收容, 执行,完成四个阶段。 作业调度(宏观调度或高级调度) CUIT徐红
1 操 作 系 统 | 调 度 与 死 锁 1 CUIT 徐虹 第四章 调度与死锁 ¾不同的OS，处理机管理的策略不同 ¾衡量调度策略的指标 ¾周转时间 ¾吞吐率 ¾响应时间 ¾设备利用率 ¾调度算法 ¾死锁的概念和解决方案 操 作 系 统 | 调 度 与 死 锁 2 CUIT 徐虹 4． 1 调度的类型和模型 ¾调度类型 ¾高级调度 ¾作业的状态及其转换 作业从输入到完成要经历提交，收容， 执行，完成四个阶段。 ¾作业调度 （宏观调度或高级调度）
进程调度{微观调度或低级调度 进程调度程序 记录进程中所有进程的执行情况:状 态,优先级,所用资源情况等。 选择占用处理机的进程。 进行进程上,下文切换,分配处理机 给进程。 CUIT徐红 进程调度的时机 正在执行的进程执行完毕。 运行中的进程提出Wo请求 执行某原语操作。 统 在可剥夺调度方式中,一个具有 更高优先数的进程进入就绪队列。 在分时系统中,分配给该进程的 时间片已用完 CUIT徐红
2 操 作 系 统 | 调 度 与 死 锁 3 CUIT 徐虹 ¾进程调度 (微观调度或低级调度) ¾进程调度程序 ¾记录进程中所有进程的执行情况：状 态，优先级，所用资源情况等。 ¾选择占用处理机的进程。 ¾进行进程上，下文切换，分配处理机 给进程。 操 作 系 统 | 调 度 与 死 锁 4 CUIT 徐虹 ¾进程调度的时机 ¾正在执行的进程执行完毕。 ¾运行中的进程提出I/O 请求。 ¾执行某原语操作。 ¾在可剥夺调度方式中，一个具有 更高优先数的进程进入就绪队列。 ¾在分时系统中，分配给该进程的 时间片已用完
进程调度方式 非剥夺方式 剥夺方式 选择性剥夺调度 为每个进程设置特征位U和Ⅵ Up=1:本进程可剥夺其它进程 up=0:本进程不能剥夺其它进程 Vp=1:可被剥夺 vp=0:不能被剥夺 CUIT徐红 交换调度(中级调度) 按照给定的原则和策略,将处于外存交 换区中的就绪状态或等待状态的进程调入 内存,或把处于内存就绪状态或内存等待 统 状态的进程交换到外存交换区中。 CUIT徐红
3 操 作 系 统 | 调 度 与 死 锁 5 CUIT 徐虹 ¾进程调度方式 ¾非剥夺方式 ¾剥夺方式 ¾选择性剥夺调度 为每个进程设置特征位Up 和 Vp Up=1：本进程可剥夺其它进程 Up=0：本进程不能剥夺其它进程 Vp=1：可被剥夺 Vp=0：不能被剥夺 操 作 系 统 | 调 度 与 死 锁 6 CUIT 徐虹 ¾交换调度 （中级调度） 按照给定的原则和策略，将处于外存交 换区中的就绪状态或等待状态的进程调入 内存，或把处于内存就绪状态或内存等待 状态的进程交换到外存交换区中
调度和进程状态转换 Long-term scheduling Short-term Blocked Medium-term 调度的层次 统 Neelum Term CUIT徐红
4 操 作 系 统 | 调 度 与 死 锁 7 CUIT 徐虹 调度和进程状态转换 操 作 系 统 | 调 度 与 死 锁 8 CUIT 徐虹 调度的 层次
>调度队列模型 进程调度队列模型 作业和进程调度队列模型 三级调度队列模型 CUIT徐红 Loneterm TIme-out Short-term 工 Medlum-term Interactive 统 Medlum-term B locked Queue
5 操 作 系 统 | 调 度 与 死 锁 9 CUIT 徐虹 ¾调度队列模型 ¾进程调度队列模型 ¾作业和进程调度队列模型 ¾三级调度队列模型 操 作 系 统 | 调 度 与 死 锁 10 CUIT 徐虹
调度准则和算法评价 调度准则 面向用户 周转时间 响应时间 最后期限 可预测性 >面向系统 吞吐量 处理机利用率 公平 平衡资源 强制优先级 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）