ch2-2.5-2.9处理器调度.ppt

调度机制逻辑功能程序模块组成 队列管理程序： 进程/线程 状态变化时，它会被排入不同队列。 上下文切换程序： 负责进程/线程 上下文切换。 分派程序： 从就绪队列中选择下个运行的进程/线程 。 2 低级调度的基本类型 第一类称剥夺式： 两种处理器剥夺原则， (1)是高优先级进程/线程可剥夺低优先级进程/线程， (2)是当运行进程/线程时间片用完后被剥夺。 第二类称非剥夺式： 2.8.2 作业调度和低级调度算法先来先服务算法 先来先服务是按照作业进入系统后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选进入主存。 算法容易实现，效率不高，不利于I/O频繁的进程 FCFS调度算法的平均作业周转时间与作业提交的顺序有关。 例子： 三个作业同时到达系统并立即进入调度：作业名/所需CPU时间:作业1/28，作业2/9，作业3/3。采用FCFS算法，平均作业周转时间为35。 平均作业周转时间 T=(28 + 37 + 40) / 3 =35 ? 若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。 平均作业周转时间 T=(9 + 37 + 40) / 3 =29 若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。 平均作业周转时间 T=(3+ 12 + 40) / 3 =18 2?最短作业优先算法(1) SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。 算法易于实现，效率不高，主要弱点是忽视了作业等待时间。会出现饥饿现象。 SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。 实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。 最短作业优先算法(2) 四个作业同时到达系统并进入调度： 作业名/所需CPU时间:作业1/9，作业2/4 ，作业3/10，作业4/8。 SJF作业调度顺序为作业2、4、1、3， 平均作业周转时间T = (4 + 12 + 21＋31) / 4=17， 平均带权作业周转时间W= (4/4 + 12/8 + 21/9 + 31/10) =1.98。 如果施行FCFS调度算法， 平均作业周转时间T =(9 + 13 + 23 + 31) / 4 = 19， 平均带权作业周转时间W = (9/9 + 13/4 + 23/10 + 31/8) =2.61。 最短下一个CPU时用优先算法(1) 计算进程/线程下一个CPU周期长度 τn+1=αtn+(1-α)τn tn是进程/线程最近一个CPU周期长度，是最近信息； τn是估算的第n个CPU周期值，是历史信息； 最短下一个CPU时用优先算法(2) 实际值(t i) 6 4 6 13 13 13 估算值(τi) 10 8 6 6 5 9 11 12 条件：α=0.5 3最短剩余时间优先算法(1) SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。称最短剩余时间优先算法 此算法不但适用于JOB调度，同样也适用于进程调度。 最短剩余时间优先算法(2) 四个作业其到达系统/所需CPU时间如下： Job1-0/8，Job2-1/4，Job3-2/ 9，Job4-3/5。 SRTF调度平均等待时间=((10-1)+(1-1)+(17-2)+(5-3))/4 =6.5毫秒。 SRTF调度平均周转时间= ((17-0)+(5-1)+(26-2)+(10-3))/4 = ?毫秒 SJF调度平均等待时间=7.75毫秒。 SJF调度平均周转时间=14.25毫秒。 J1 J2 J4 J1 J3 0 1 5 10 17 26 4响应比最高者优先算法 FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。 HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。 响应比定义 响应比 ＝1+已等待时间/估计运行时间 ?短作业容易得到较高响应比， ?长作业等待时间足够长后，也将获得足够高的响应比， ?饥饿现象不会发生。 HRRF算法举