14 209 操作系统第13讲：第4章 处理机调度(调度算法).ppt

* * 4.8 第4章补充参考作业 清华大学2005年硕士生入学考试试题 十．设在批处理系统中有四道作业。它们进入系统的时间及运行时间如下： 作业号 进入时刻（h） 运行时间（h） 1?????????????????? ⒏00 ⒉00 2 ⒏50 0.50 3 ⒐00 0.10 4 ⒐50 0.20 设系统每次只选择一个作业装人主机，请分别给出在下列算法中这组作业的运行顺序、平均周转时间和平均带权周转时间FCFS算法、SJF算法（最短者优先） 、HRN算法（最高响应比者优先） （10分） * * 谢谢再见 09/04 * * 操作系统第14讲 第4章 处理机调度 (调度算法) 主讲：闫新庆 2012– 04 * * 4.4 调度算法 一、先来先服务调度算法(FCFS) 1、特点：最简单的调度算法，单独用少，其它方法配合用较多 2、应用范围：作业和进程的调度算法 3、作业调度 （1）选择作业进入内存 （2）为其分配资源 （3）创建进程 （4）将其放入就绪队列 4、 进程调度 （1）从就绪队列中选择一进程进占CPU （2）执行 （3）放弃CPU、终结或阻塞 5、缺陷：有利于长作业或进程 ，不利于短作业或进程 * * 4.4 调度算法 5、?FCFS 分析举例 ? 注1: 权----在按位记数法中，为了确定一个数位的实际值，必须乘上某个 因子，这个数位叫做这个数的权。 注意P90: 周转T、完成T、提交T、带权周转T等概念在公式中的含义。 ●分析结论:P3 执行的时间非常短，但等待时间过长，显然是不合理的。 进程名 同时到达序列 执行T 开始执行T 完成T 等待T P1 1 1 0 1 0 P2 2 100 1 101 1 P3 3 1 101 102 101 p4 4 100 102 202 102 * * 4.4 调度算法 二、短作业或短进程调度算法（SJF） 1.?适应范围：作业或进程 2.?原则：选取最短作业或进程进行执行 3.?优点：当短作业或短进程较多时，系统效率较高 4.?缺陷：对长作业不利，设有考虑优先级 * * 4.4 调度算法 三、时间片轮转算法（RR） 1．只适用于进程调度 ，而不只适用于作业调度 2．原则 ：将CPU的时间划分为一个长长的均等的时间序列片，依序分配给就绪队列中的各进程，选中且被执行的进程因时间到，但未执行完毕，乃将终止执行，将其放入就绪队列之尾。若时间片未用完，发生终结(正常或非正常)或阻塞，调度下一进程。 3．时间片大小确定：若时间片过大，可使每个进程都能在时间片内执行完毕，则该方法就退化为 FCFS算法。若时间片过短，则切换太频繁，系统负荷加大，效率降低： * * 4.4 调度算法 三、时间片轮转算法（RR） 4. 时间片大小确定原则 ●系统对响应时间（执行一条指令所需要的时间） ●队列中的进程数目 ●系统的处理能力（速度） 分时系统必须满足系统对群体进程响应时间T的要求，当并发进程（N）一定时，定义q为时间片，三者之间的关系为：T=N*q,例: 当T=3S，N=100时，则q≈30ms * * ? 4.4 调度算法 四、优先权调度(take precedence) 1．可用于作业、进程和对时间要求不高的实时系统 2．选择优先权最高的作业或进程进占内存或CPU 3．优先权调度算法的类型 ◆非抢占式——择优先数最大的进程或作业进占内存或 CPU，直到执行完毕不中断，交给次高级优先数的进程 ◆ 抢占式——中断当前进程执行，让位于优先数更高的作业或进程进行执行 * * 4.4 调度算法 四、优先权调度（续1) 4．优先权的类型 （1）静态优先权 ●创建进程时确定，在整个运行期间保持不变 ●确定高优先权的依据： ◆根据进程的类型，对换 I/O设备（磁盘） 执行时间短； ◆根据对资源需求量小（如内存） ◆根据用户需求（交费高低） ●开销小，简单易行，但精度不高，适用于要求不高的系统 * * 4.4 调度算法 四、优先权调度（续2) 4．优先权的类型 （续2） （2）动态优先级 对创建进程时所赋予的优先级可以随着进程的推 进而改变，以便获得更好 的调度性能。其依据主 要是根据在就绪队列中进程等待的时间长短来调 整各进程的优先级数 * * 4.4 调度算法 五、最高响应比的优先调度算法(HRN) ●最高响应比优先法（HRN）是对FCFS方式和S