[信息与通信]ch2-27-29处理器调度.ppt

* 第二章 处理器管理 2.8.2 作业调度和低级调度算法 1先来先服务算法 三个作业同时到达系统并立即进入调度：作业名/所需CPU时间:作业1/28，作业2/9，作业3/3。采用FCFS算法，平均作业周转时间为35。 ? 若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。 若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。 FCFS调度算法的平均作业周转时间与作业提交的顺序有关。 * 第二章 处理器管理 2?最短作业优先算法(1) SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。 算法易于实现，效率不高，主要弱点是忽视了作业等待时间。 会出现饥饿现象。 SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。 实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。 * 第二章 处理器管理 最短作业优先算法(2) 四个作业同时到达系统并进入调度： 作业名/所需CPU时间:作业1/9，作业2 ，作业3/10，作业4/8。 平均作业周转时间T = ，平均带权作业周转时间W= 。 * 第二章 处理器管理 最短作业优先算法(2) 四个作业同时到达系统并进入调度： 作业名/所需CPU时间:作业1/9，作业2 ，作业3/10，作业4/8。 SJF作业调度顺序为作业2、4、1、3， 平均作业周转时间T = 17，平均带权作业周转时间W= 1.98。 如果施行FCFS调度算法，平均作业周转时间T =19，平均带权作业周转时间 W = 2.61。 * 第二章 处理器管理 3最短剩余时间优先算法(1) SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。称最短剩余时间优先算法 此算法不但适用于JOB调度，同样也适用于进程调度。 * 第二章 处理器管理 最短剩余时间优先算法(2) 四个作业其到达系统/所需CPU时间如下：Job1-0/8，Job2-1/4， Job3- 2/ 9，Job4-3/5。 SRTF调度平均等待时间=6.5毫秒。 SJF调度平均等待时间=7.75毫秒。 J1 J2 J4 J1 J3 0 1 5 10 17 26 * 第二章 处理器管理 4响应比最高者优先算法 FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。 HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。 * 第二章 处理器管理 响应比定义 响应比 ＝作业周转时间/作业处理时间 =1+已等待时间/估计运行时间 ?短作业容易得到较高响应比； ?长作业等待时间足够长后，也将获得足够高的响应比； ?饥饿现象不会发生。 * 第二章 处理器管理 几种算法举例 四个作业到达系统时间/所需CPU时间:作业1-0/20，作业2-5/15，作业3-10 /5，作业4- 15/ 10。 SJF调度顺序为 ，平均作业周转时间T= 平均带权作业周转时间W= 。 FCFS调度顺序为 ，平均作业周转时间T= ，平均带权作业周转时间W= 。 HRRF调度顺序为 ， 平均作业周转时间T= ，平均带权作业周转时间W= 。 * 第二章 处理器管理 几种算法举例 四个作业到达系统时间/所需CPU时间:作业1-0/20，作业2-5/15，作业3-10 /5，作业4- 15/ 10。 SJF调度顺序为作业1、3、4、2，平均作业周转时间T=25， 平均带权作业周转时间W=2.25 。 FCFS调度顺序为作业1、 2 、 3 、 4 ，平均作业周转时间T=28.75， 平均带权作业周转时间W=3.125 。 HRRF调度顺序为作业1、3、 2 、 4，平均作业周转时间T=26.25， 平均带权作业周转时间W=2.46 。 * 第二章 处理器管理 5 优先级调度算法(1) 静态优先数法 使用外围设备频繁者优先数大，这样有利于