第4章处理器调度

第四章处理机调度4.1处理机调度的层次4.2作业调度4.3低级调度4.4实时调度算法

14.1处理机调度的层次高级调度中级调度低级调度2高级调度•作业调度、长程调度•高级调度的任务•批处理操作系统中的高级调度3高级调度

分时操作系统中，高级调度任务：1）是否接受一个终端用户的连接；2）一个程序能否被计算机系统接纳并构成进程；3）一个新建态的进程是否能够加入就绪进程队列。4中级调度平衡负载调度，中程调度。决定主存储器中所能容纳的进程数，这些进程将允许参与竞争处理器资源。中级调度根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换。5中级调度中级调度决定那些进程被允许参与竞争处理器资源，使用的方法是通过把一些进程换出主存，使之进入“挂起”状态，不参与进程调度，起到平滑和调整系统负荷的作用。6低级调度进程调度、短程调度。主要功能是按照某种原则决定就绪队列中的哪个进程或内核级线程能获得处理器,并将处理机出让给它进行工作。短程调度程序是操作系统最为核心的部分，短程调度策略的优劣直接影响到整个系统的性能。7低级调度

有两类低级调度方式：第一类称剥夺方式：高优先级剥夺原则时间片剥夺原则第二类称非剥夺方式：

8处理器调度的层次

中级调度新建态挂起就绪态挂起等待态高级调度低级调度运行态就绪态等待态终止态9处理器调度与进程状态转换高级调度中级调度低级调度运行就绪终止新建挂起就绪中级调度挂起等待等待高级调度高级调度中级调度10处理器的调度模型

中级调度处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度11选择调度算法的原则(1)1、资源利用率

CPU利用率=CPU有效工作时间/CPU总的运行时间，CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间。12选择调度算法的原则(2)

2、周转时间•批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。•这是批处理系统衡量调度性能的一个重要指标。3、吞吐率单位时间内处理的作业数。

13

选择调度算法的原则(3)4、响应时间•交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。•使交互式用户的响应时间尽可能短，或尽快处理实时任务。•这是分时系统和实时系统衡量调度性能的一个重要指标。14选择调度算法的原则(4)

5、公平性确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。15

作业周转时间如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：ti=tf-ts

实际上，它是作业在系统里的等待时间与运行时间之和。16平均作业周转时间为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。

平均作业周转时间T=(Σti)/n17作业带权周转时间和平均

作业带权周转时间如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti/tk为该作业的带权周转时间。ti是等待时间与运行时间之和，故带权周转时间总大于1。

平均作业带权周转时间W=(Σwi)/n18衡量调度算法的调度性能用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们呈现的调度性能；用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算法时，它们呈现的调度性能。194.2批处理作业的管理与调度作业生命周期状态输入状态：此时作业的信息正在从输入设备上预输入。后备状态：此时作业预输入结束但尚未被选中执行。执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行。完成状态：作业已经运行结束，正在等待缓输出。20多道批处理的处理机调度包括作业调度和进程调度两个层次处于后备状态的作业在系统资源满足的前提下可以被作业调度选中进入内存计算。而只有处于执行状态的作业才真正构成进程获得计算的机会。21多道批处理的处理机调度包括作业调度和进程调度两个层次作业调度选中一个作业且把它装入主存储器时就为该作业创建一个用户进程。这些进程将在进程调度的控制下占有处理器运行。为了充分利用处理器，可以把多个作业同时装入主存储器，这样就会同时有多个用户进程，这些进程都要竞争处理器。22多道批处理的处理机调度包括作业调度和进程调度两个层次进入计算机系统的作业只有经过两级调度后才能占用处理器。第一级是作业调度，使作业进入主存储器；第二级是处理器调度，使作业进程占用处理器。作业调度与处理器调度的配合能实现多道作业的同时执行。23作业调度与进程调度的关系

执行状态运行就绪等待输入状态后备状态完成状态进程调度中级调度缓输出作业调度预输入完成24作业调度算法

1

先来先服务算法(1)按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。

25先来先服务算法(2)例如，三个作业依次到达系统并立即进入调度：作业名所需CPU时间作业128作业29作业3326先来先服务算法(3)采用FCFS算法，三个作业的周转时间分别为：28、37和40，因此，平均作业周转时间T=(28+37+40)/3=3527算法特点：算法容易实现，效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业。28•若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。FCFS调度算法的平均作业周转时间与作业提交的顺序有关。292

最短作业优先算法(1)SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。30最短作业优先算法(2)

例如，四个作业依次到达系统并立即进入调度：作业名所需CPU时间作业19作业24作业310作业48假设系统中没有其他作业，现实施SJF调度算法31最短作业优先算法(3)SJF的作业调度顺序为作业2、4、1、3，平均作业周转时间T=(4+12+21+31)/4=17平均带权作业周转时间W=(4/4+12/8+21/9+31/10)/4=1.98如果对它们施行FCFS调度算法，平均作业周转时间T=(9+13+23+31)/4=19平均带权作业周转时间W=(9/9+13/4+23/10+31/8)/4=2.5132最短作业优先算法特点算法易于实现，效率不高，主要弱点是忽视了作业等待时间。会出现饥饿现象。SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。33SJF算法进一步讨论SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业,此算法不但适用于JOB调度，同样也适用于进程调度。34SJF算法进一步讨论——抢占式一个例子,假如四个就绪作业其到达系统和所需CPU时间如下：作业名到达系统时间CPU时间(毫秒)---------------------------------------Job108Job214Job329Job435

35SJF算法进一步讨论

J1J2J4J1J301510172636SJF算法进一步讨论Job1从0开始执行，就绪队列仅一个作业。Job2在时间1到达，Job1剩余时间（7毫秒）大于JOB2所需时间（4毫秒），Job1被剥夺，Job2被调度执行。平均等待时间是（（10-1）+（1-1）+（17-2）+（5-3））/4=26/4=6.5毫秒。采用非抢占式SJF调度，那么，平均等待时间是7.75毫秒。373

响应比最高者优先(HRRF)算法FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时间，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。HRRF是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。38

响应比定义

作业进入系统后的等待时间与估计运行时间之比称作响应比，现定义；响应比＝1+已等待时间/估计运行时间

39HRRF算法举例(1)

例如，以下四个作业先后到达系统进入调度：作业名到达时间所需CPU时间作业10 20作业25 15作业3105作业415 1040HRRF算法举例(2)假设实施SJFSJF的作业调度顺序为作业1、3、4、2，平均作业周转时间T=(20+15+20+45)/4=25平均带权作业周转时间W=(20/20+15/5+25/10+45/15)/4=2.2541HRRF算法举例(3)假设实施FCFS如果对它们施行FCFS调度算法，平均作业周转时间T=(20+30+30+35)/4=38.75平均带权作业周转时间W=(20/20+30/15+30/5+35/10)/4=3.1342

HRRF算法举例(4)

对作业流执行HRRF调度算法•开始只有作业1，被选中执行时间20；•作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被选中，执行时间5；•作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15；•作业2执行完毕，作业4被选中，执行时间10；平均作业周转时间T=(20+15+35+35)/4=26.25平均带权作业周转时间W=(20/20+15/5+35/15+35/10)/4=2.4243HRRF算法特点短作业容易得到较高响应比，长作业等待时间足够长后，也将获得足够高的响应比，饥饿现象不会发生。444

优先数法(1)这种算法是根据确定的优先数来选取作业，每次总是选择优先数高的作业。

45优先数法(2)

规定用户作业优先数的方法：一种是由用户自己提出作业的优先数。另一种是由系统综合考虑有关因素来确定用户作业的优先数。464.3低级调度

1低级调度的功能2低级调度算法3实时调度

474.3.1低级调度的功能低级调度负责动态地把处理器分配给进程或内核级线程。操作系统中实现低级调度的程序称为进程(线程)调度程序，或分派程序(Dispatcher)。进程调度算法多数适用于线程调度。48何时发生CPU调度呢?

有四种情况都会发生CPU调度:当一个进程从运行态切换成等待态时;当一个进程从运行态切换成就绪态时;当一个进程从等待态切换成就绪态时;当一个进程中止时。49

低级调度的主要功能•记住进程的状态。•决定某个进程什么时候获得处理器，以及占用多长时间。•把处理器分配给进程。•收回处理器。50低级调度基本方式

非抢占式抢占式

514.3.2低级调度算法1

先来先服务算法按照进程进入就绪队列的先后次序分配处理器。先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行直到结束或阻塞。算法容易实现，效率不高，不利于I/O频繁的进程。522

时间片轮转调度算法(1)

时间片调度做法是：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。53时间片轮转调度算法(2)轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备。轮转策略与间隔时钟54时间片轮转调度算法(3)

时间片取选(1)

轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大，这个开销与时间片的大小很有关系。55时间片轮转调度算法(4)

时间片取选(2)时间片取值太小，多数进程不能在一个时间片内运行完毕，切换就会频繁，开销显著增大，从系统效率来看，时间片取大一点好。时间片取值较大，随就绪队列里进程数目增加，轮转一次的总时间增大，对进程的响应速度放慢了。为满足响应时间要求，要么限制就绪队列中进程数量，要么采用动态时间片法，根据负载状况，及时调整时间片的大小。56时间片轮转调度算法(5)

时间片取选(3)时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。573

优先权调度(1)

静态优先数法使用外围设备频繁者优先数大，这样有利于提高效率；重要算题程序的进程优先数大，这样有利于用户；进入计算机时间长的进程优先数大，这样有利于缩短作业完成的时间；交互式用户的进程优先数大，这样有利于终端用户的响应时间等等,

58优先权调度(2)

动态优先数法基本原则：①根据进程占有CPU时间多少来决定,当进程占有CPU时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越低，反之,进程获得调度的可能性越大;②根据进程等待CPU时间多少来决定,当进程在就绪队列中等待时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越高，反之,进程获得调度的可能性越小。59UNIX(早期版本)动态优先数计算公式

p-pri=min{127,(p-cpu/16+PUSER+p-nice)}p-pri为进程优先数p-nice用户调节参数PUSER为常数p-cpu反映进程使用处理机的程度60UNIX动态优先数调度效果

(1)如果一个进程连续占用处理机较长时间，那么，它的p-cpu值就增大，计算出的p-pri也增大，于是优先权下降。(2)如果一个进程长时间未被调用到或者虽频繁调度到，但每次占用的时间都小于200ms，那么，p-cpu就较小甚至为0，从而，计算出的p-pri也较小，于是优先权上升。61UNIX系统计算优先数的时机一是对所有优先数大于100的进程，系统每秒钟重新计算一次它的优先数；二是每次系统调用命令处理完毕之时，就重新对现进程的优先数进行计算。624

多级反馈队列调度

又称反馈循环队列或多队列策略。主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。634.4实时调度

实时操作系统的特性实时系统是那些时间因素非常关键的系统。实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。64硬实时系统和软实时系统实时系统通常分为硬实