ch2.5处理器调度2.6批处理的管理与调度2.7低级调度

2.5处理机调度

2.5.1处理机调度的层次2.5.3高级调度2.5.3中级调度2.5.4低级调度2.5.5选择调度算法的原则

2.5.1处理机调度的层次

高级调度(1)•作业调度、长程调度•高级调度的任务•批处理操作系统中的高级调度高级调度(2)分时操作系统中，高级调度任务：1）是否接受一个终端用户的连接；2）一个程序能否被计算机系统接纳并构成进程；3）一个新建态的进程是否能够加入就绪进程队列。中级调度(1)平衡负载调度，中程调度。决定主存储器中所能容纳的进程数，这些进程将允许参与竞争处理器资源。中级调度根据存储资源量和进程的当前状态来决定辅存和主存中进程的对换。中级调度(2)中级调度决定那些进程被允许参与竞争处理器资源，使用的方法是通过把一些进程换出主存，使之进入“挂起”状态，不参与进程调度，起到平滑和调整系统负荷的作用。低级调度(1)

进程调度、短程调度。主要功能是按照某种原则决定就绪队列中的哪个进程或内核级线程能获得处理器,并将处理机出让给它进行工作。短程调度程序是操作系统最为核心的部分，短程调度策略的优劣直接影响到整个系统的性能。低级调度(2)

有两类低级调度方式：第一类称剥夺方式：

高优先级剥夺原则时间片剥夺原则第二类称非剥夺方式：

处理器调度的层次

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

高级调度中级调度低级调度运行态就绪态终止态新建态挂起就绪态中级调度挂起等待态等待态高级调度高级调度中级调度处理器的调度模型

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

l

资源利用率

CPU利用率=CPU有效工作时间/CPU总的运行时间，

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

2

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

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

选择调度算法的原则(4)

4吞吐率单位时间内处理的作业数。

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

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

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

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

作业带权周转时间如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti/tk为该作业的带权周转时间。ti是等待时间与运行时间之和，故带权周转时间总大于1。平均作业带权周转时间W=(Σwi)/n衡量调度算法的调度性能用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们呈现的调度性能；用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算法时，它们呈现的调度性能。这两个数值均2.6批处理作业的管理与调度

2.6.1作业和进程的关系2.6.2批处理作业的管理2.6.3批处理作业的调度2.6.4作业调度算法2.6.1作业和进程的关系(1)

•作业(JOB)，•作业步(JobStep)，•作业组织，•作业的提交、收容、执行和完成。作业和进程的关系(2)

作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。2.6.2批处理作业的管理

批处理作业的脱机控制方式，作业控制语言，作业说明书，批处理作业的输入，调度、执行和撤离。

作业控制块(1)多道批处理操作系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块（JCB）。JCB通常是在批作业进入系统时，由Spooling系统建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。作业控制块(2)

JCB的主要内容包括：

(1)作业情况(用户名、作业名、语言名),(2)资源需求(估计CPU运行时间、最迟截止期、主存量、设备类型/台数、文件数和数据量、函数库/实用程序等),(3)资源使用情况(进入系统时间、开始运行时间、己运行时间),作业控制(优先数、控制方式、操作顺序、出错处理等)。作业生命周期状态输入状态：此时作业的信息正在从输入设备上预输入。后备状态：此时作业预输入结束但尚未被选中执行。执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行。完成状态：作业已经运行结束，正在等待缓输出。2.6.3批处理作业的调度(1)处于后备状态的作业在系统资源满足的前提下可以被作业调度选中进入内存计算。而只有处于执行状态的作业才真正构成进程获得计算的机会。批处理作业的调度(2)作业调度选中一个作业且把它装入主存储器时就为该作业创建一个用户进程。这些进程将在进程调度的控制下占有处理器运行。为了充分利用处理器，可以把多个作业同时装入主存储器，这样就会同时有多个用户进程，这些进程都要竞争处理器。批处理作业的调度(3)进入计算机系统的作业只有经过两级调度后才能占用处理器。第一级是作业调度，使作业进入主存储器；第二级是处理器调度，使作业进程占用处理器。作业调度与处理器调度的配合能实现多道作业的同时执行。作业调度与进程调度的关系

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

1

先来先服务算法(1)按照作业进入系统的先后次序来挑选作业，先进入系统的作业优先被挑选。算法容易实现，效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短，不利于短作业而优待了长作业。

先来先服务算法(2)

例如，三个作业同时到达系统并立即进入调度：作业名所需CPU时间作业128作业29作业33采用FCFS算法，三个作业的周转时间分别为：28、37和40，因此，平均作业周转时间T=(28+37+40)/3=35先来先服务算法(3)

•若三个作业提交顺序改为作业2、1、3，平均作业周转时间约为29。若三个作业提交顺序改为作业3、2、1，平均作业周转时间约为18。FCFS调度算法的平均作业周转时间与作业提交的顺序有关。2

最短作业优先算法(1)

SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。算法易于实现，效率不高，主要弱点是忽视了作业等待时间。会出现饥饿现象。最短作业优先算法(2)

例如，四个作业同时到达系统并立即进入调度：作业名所需CPU时间作业19作业24作业310作业48假设系统中没有其他作业，现实施SJF调度算法，最短作业优先算法(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

J2

J4

J1

J3

4122131最短作业优先算法(4)如果对它们施行FCFS调度算法，平均作业周转时间

T=(9+13+23+31)/4=19

平均带权作业周转时间

W=(9/9+13/4+23/10+31/8)/4=2.51

J1

J2J3

J4

9132331最短作业优先算法(5)SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。最短作业优先算法(6)可根据每个进程的执行历史来预测它的下一个CPU长度，令tn是第n个实际的执行长度，τn是其预测值，那么，下一个CPU执行长度的预测公式：

τn+1=αtn+(1-α)τn

其中，α(0<α<1)用于控制最近的tn和其预测值τn在预测中的作用，其值常为0.5。

SJF算法进一步讨论(1)SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业,此算法不但适用于JOB调度，同样也适用于进程调度。SJF算法进一步讨论(2)一个例子,假如四个就绪作业其到达系统和所需CPU时间如下：作业名到达系统时间CPU时间(毫秒)---------------------------------------

Job108Job214Job329Job435

SJF算法进一步讨论(3)

J1J2J4J1J3015101726SJF算法进一步讨论(4)

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毫秒。3

响应比最高者优先(HRRF)算法

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

响应比定义

作业进入系统后的等待时间与估计运行时间之比称作响应比，现定义；响应比＝1+已等待时间/估计运行时间•短作业容易得到较高响应比，•长作业等待时间足够长后，也将获得足够高的响应比，•饥饿现象不会发生。HRRF算法举例(1)例如，以下四个作业先后到达系统进入调度：作业名到达时间所需CPU时间作业10 20作业25 15作业3105作业415 10HRRF算法举例(2)

假设实施SJFSJF的作业调度顺序为作业1、3、4、2，

平均作业周转时间T=（20+25-10+35-15+50-5）/4=25

平均带权作业周转时间W=（20/20+15/5+20/10+45/15）/4=2.25

HRRF算法举例(3)

假设实施FCFS如果对它们施行FCFS调度算法，作业调度顺序为作业1、2、3、4，平均作业周转时间T=（20+35-5+40-10+50-15）/4=28.75

平均带权作业周转时间W=（20/20+30/15+30/5+35/10）/4=3.125

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；

HRRF算法举例(5)

对作业流执行HRRF调度算法

平均作业周转时间T=（20+25-10+40-5+50-15）/4=26.25

平均带权作业周转时间W=（20/20+15/5+35/15+35/10）/4=2.46

4

优先数法(1)

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

优先数法(2)

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

分类调度算法

预先按一定原则把作业划分成若干类，以达到均衡使用系统资源和兼顾大小作业的目的。分类原则包括作业计算时间、对内存的需求、对外围设备的需求等。作业调度时还可为每类作业设置优先级，从而照顾到同类作业中的轻重缓急。6

用与不用磁带的作业搭配作业调度时，把使用磁带机和不使用磁带机的作业搭配挑选。可使要用磁带机的作业在执行时省去等待装磁带的时间。显然对缩短系统的平均周转时间是有益的。2.7低级调度

2.7.1低级调度的功能2.7.2低级调度算法2.7.3实时调度2.7.4多处理器调度2.7.5实例研究：UNIXSVR4调度算法2.7.6实例研究：Windows2000/XP调度算法2.7.7实例研究：Linux调度算法2.7.1低级调度的功能低级调度负责动态地把处理器分配给进程或内核级线程。操作系统中实现低级调度的程序称为进程(线程)调度程序，或分派程序(Dispatcher)。进程调度算法多数适用于线程调度。何时发生CPU调度呢?

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

低级调度的主要功能

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

2.7.2低级调度算法

1

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

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

时间片调度做法是：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。2

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

例如，现有进程P1、P2、P3，所需CPU时间单位为：14、10和8。采用时间片长为2个单位的轮转法：则平均周转时间由FCFS的23.3下降到14个CPU时间单位。

P1P2P3P1P2

P3P1P2P3P1P2P3P1P2P1P1时间片轮转调度算法(3)轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备。轮转策略与间隔时钟时间片轮转调度算法(4)基本轮转法改进轮转法时间片轮转调度算法(5)

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

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

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

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

优先权调度(2)

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

计算公式

p-pri=min{127,(p-cpu/16+PUSER+p-nice)}p-pri为进程优先数p-nice用户调节参数PUSER为常数

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

多级反馈队列调度

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

一个三级反馈队列调度策略

低级就绪队列高级就绪队列中级就绪队列等待磁盘磁带等待其他外设运行选中,时间片500ms超过时间片启动磁盘磁带启动其他外设选中,时间片200ms选中,时间片100ms5

保证调度算法(1)

向用户做出明确的性能保证，然后去实现它。容易实现的一种保证是：当工作时己有n个用户登录在系统，则将获得CPU处理能力的1/n。类似的，如果在一个有n个进程运行的用户系统中，每个进程将获得CPU处理能力的1/n。保证调度算法(2)保证调度算法必须跟踪各个进程自创建以来已经使用了多少CPU时间。计算各个进程应获得的CPU时间，即自创建以来的时间除以n。由于各个进程实际获得的CPU时间已知，所以很容易计算出实际获得的CPU时间和应获得的CPU时间之比，于是调度将转向比率最低的进程。6

彩票调度算法(1)

基本思想：为进程发放针对各种资源（如CPU时间）的彩票。调度程序随机选择一张彩票，持有该彩票的进程获得系统资源。进程都是平等的，有相同的运行机会。如果某些进程需要更多的机会，可被给予更多彩票，增加其中奖机会。彩票调度算法(2)

彩票调度法有趣特性：反映迅速，合作进程可交换彩票。彩票调度算法(3)彩票调度可以解决其他算法难以解决的问题。例如，一个视频服务器。2.7.3实时调度

实时操作系统的特性实时系统是那些时间因素非常关键的系统。实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。硬实时系统和软实时系统实时系统通常分为硬实时（hardrealtime）系统和软实时（softrealtime）系统。前者意味着存在必须满足的时间限制；后者意味着偶尔超过时间限制时可以容忍的。

周期性和非周期性事件实时系统响应的事件可划分为周期性事件和非周期性事件。例如，m个周期性事件，事件i的周期为Pi，每个事件需要Ci秒的CPU时间来处理，则只有满足以下条件：

C1/P1+C2/P2+…+Cm/Pm≤1

时，才可能处理所有的负载。满足该条件的实时系统称作任务可调度可的（schedulable）。软实时系统一个软实时系统处理三个事件流，其周期分别为100ms，200ms和500ms，如果事件处理时间分别为50ms，30ms和100ms，则这个系统是可调度的，因为0.5+0.15+0.2≤1如果加入周期为1秒的第4个事件，则只要其处理时间不超过150ms，该系统仍将时可调度的。

实时调度算法(1)

1）单比率调度算法基本思想：为每个进程分配一个与事件发生频率成正比的优先数。例如，周期为20ms的进程优先数为50，周期为100ms的进程优先数为10，运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式分配策略。实时调度算法(2)

2）限期调度算法

基本思想：当一个事件发生时，对应的进程就按照截止期限被加入就绪进程队列。对于一个周期性事件，其截止期限即为事件下一次发生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。实时调度算法(3)

3）最少裕度法

基本思想：首先计算各个进程的富裕时间，即裕度（laxity），然后选择裕度最少的进程执行。裕度=截止时间-(就绪时间+计算时间)2.7.4多处理器调度

流行的多处理器系统有：

•松散耦合多处理器系统：

•紧密耦合多处理器系统：现代操作系统往往采用进程调度与线程调度相结合的方式来完成多处理器调度。1

同步的粒度

同步的粒度，就是系统中多个进程之间同步的频率，它是刻画多处理系统特征和描述进程并发度的一个重要指标。同步粒度的划分

•细粒度（fine-grained）：

•中粒度（medium-grained）：

•粗粒度（coarse-grained）：

•超粗粒度（verycoarse-grained）：

•独立（independent）：

多处理器调度的设计要点

设计要点之一是如何把处理器分配给进程：静态分配策略动态分配策略设计要点之二是否要在单个处理器上支持多道程序设计。设计要点之三是如何指派进程。多处理器的调度算法(1)

实验证明，随着处理器数目的增多，复杂低级调度算法的有效性逐步下降。多数采取动态分配策略的多处理器系统中，低级调度算法往往采用最简单的FCFS或优先数算法。多处理器的调度算法(2)多处理器调度的主要研究对象是线程调度算法。尽管线程也给单处理器系统带来很大益处，但在多处理器环境中线程的作用才真正得到充分发挥。多处理器调度算法(3)

1）负载共享调度算法

基本思想：进程并不分配给一个特定处理器，系统维护一个全局性就绪线程队列，当一个处理器空闲时，就选择一个就绪线程占有处理器运行。多处理器调度算法(4)

负载共享调度算法优点•

把负载均分到所有可用处理器上，保证了处理器效率的提高。•不需要集中的调度程序，一旦一个处理器空闲，调度程序就可以运行在该处理器上以选择下一个运行的线程。•运行线程的选择可以采用各种可行的策略。

多处理器调度算法(5)

三种不同负载共享算法(1)先来先服务。(2)最少线程数优先。(3)有剥夺的最少线程数优先。多处理器调度算法(6)

负载共享调度算法不足•