华东理工大学《操作系统》第四章处理机调度

4.1分级调度处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响可把处理机调度分成四个层次：

高级调度中级调度低级调度线程调度第四章处理机调度11)高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天2)中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问23)低级调度也称微观调度，进程调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效4)线程调度:选择就绪线程进入运行状态，注：只有批处理系统中存在作业调度，实时与分时系统中不存在作业调度，只有进程调度、交换调度和线程调度3作业状态转换图数据提交状态完成状态后备状态执行状态作业控制进程…输入设备数据源程序输出设备作业说明书输入井运行等待就绪输出井输入程序输出程序作业调度进程调度4批处理作业的调度作业调度又称高级调度或宏观调度，相应地称进程调度为低级（微观）调度。主要功能：1)审查系统能否满足用户作业的资源要求；只要通过调用相应的资源管理程序的有关部分，审核其JCB表中是否能满足要求即可2)按照一定的算法从输入井中的后备作业中选取作业；调度的关键在选择恰当的算法3)为选中作业做好执行前的准备，建立进程，分配资源；4)作业结束后回收资源及JCB。5调度算法的确定基于一定因素，一般系统的设计目标有：1）调度算法性能的衡量（1）每天运行尽能多的作业；（2）使CPU保持忙；（3）使I/O保持忙；（4）对所有作业公平合理。常用指标：周转时间：指将一个作业提交给计算机系统后到该作业的结果返回给用户所需时间。吞吐率：在单位时间内，一个计算机系统所完成的总工作量。响应时间：从用户向计算机发出一个命令到系统把相应结果返回所需时间。设备利用率：输入输出设备的使用情况。6周转时间与平均周转时间假定某一作业进入“输入井”的时间即作业提交时间为TSi，作业i的完成时间为TEi，它的周转时间为Ti＝TEi–TSi则作业平均周转时间为：

其中，n为被测定作业流中的作业数一个作业的周转时间即该作业在系统内停留的时间，包含两部分：等待时间和执行时间。Ti=Twi+TriTwi指作业由后备状态到执行状态的等待时间。Tri作业进入执行态，在内存的时间用来衡量不同调度算法对同一作业流的调度性能7B.带权周转时间带权周转时间是作业周转时间与作业执行时间的比：Wi=Ti/Tri平均带权周转时间：其中，ri

为某作业i的实际执行时间用来比较某种调度算法对不同作业流的调度性能。82)．常见的批处理作业调度算法（1）先来先服务算法 （FCFS：FirstComeFirstServe）每个作业按照它们在队列中的等待时间长短来调度，可能造成短作业等长时间。（2）最短作业优先算法（SJF：ShortestJobFirst）短作业优先，吞吐量大，但长作业可能得不到服务9(3).响应比高者优先（HRN)的调度算法：

响应比RP定义如下:

其中响应时间为作业进入系统后等待时间加上估计的运行时间，因此，响应比可写为：所谓响应比高者优先的算法，就是在每调度一个作业投入运行时，计算后备作业表中每个作业的响应比，挑选响应比最高者。兼顾FCFS和SJF10作业调度程序根据JCB优先数决定进入内存的次序,系统开销小（a）静态优先级（外部优先数）

用户提交作业时，根据急迫程度规定适当的优先数系统或操作员根据作业类型及要求资源情况指定。（b）由系统动态计算优先级(内部优先数)例如：可按如下公式计算作业的优先数：优先数=

用户规定优先数–作业处理时间+作业等待时间–输出量（4）基于优先级调度算法：静态法和动态法113）．作业调度算法应用例子1假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间12先来先服务调度算法计算结果

作业

进入时间

运行时间

（分钟）

开始时间

结束时间

周转时间

（分钟）

带权周转时间

JOB1

8：00

120

8：00

10：00

120

1

JOB2

8：50

50

10：00

10：50

120

2.4

JOB3

9：00

10

10：50

11：00

120

12

JOB4

9：50

20

11：00

11：20

90

4.5

作业平均周转时间

=

112..5

作业带权平均周转时间

=4.975

450

19.9

13最短作业优先作业算法计算结果14最高响应比优先作业算法计算结果154.3进程调度算法

1．进程调度进程调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程要解决的问题：WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的切换）162进程调度的功能记录系统中所有进程的情况，PCB.选择占有处理机的进程。不同的系统，不同的选择策略。进行进程上下文切换进程上下文由进程程序段、数据段、寄存器及相关数据结构PCB等组成。173进程调度的时机当一个进程运行完毕，或由于某种错误而终止运行当一个进程在运行中等待资源被阻塞如P原语分时系统中时间片到在进程通信中，执行中的进程执行了sleep(),wait()185．各种进程调度算法1）先进先出进程调度算法（FIFO）按照进程就绪的先后次序来调度进程优点:实现简单缺点:没考虑进程的优先级短进程可能等待长时间192)基于优先级的调度

（HPF—HighestPriorityFirst）优先选择就绪队列中优先级最高的进程投入运行

确定优先数的方法:1)静态优先数法：在进程创建时指定优先数，在进程运行时优先数不变2)动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待和占有CPU时间长短优先数可改变203)时间片轮转调度算法

(RR—RoundRobin)

把CPU划分成若干时间片（每个时间片的大小视情况而异，如50ms，100ms或200ms等）,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行.

21分时系统中常用时间片轮转法时间片选择问题：固定时间片可变时间片与时间片q大小有关的因素：1）系统响应时间R2）就绪队列中所允许的最大进程数N

R与就绪队列中所允许的最大进程数N和q成比例R＝Nq.q=R/NN一定时，q正比于系统所要求的响应时间

224）多队列反馈轮转算法：*首先系统中设置多个就绪队列；*每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大；当第一级队列空时，就去调度第二级队列，如此类推；每个进程并不固定在一个队列上，系统将新创建的进程放入优先权最高的队列中去；当进程在CPU上运行完一个时间片以后并被投入下一个队列；每个队列均按先进先出的算法组织；进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的队列末尾。23优先数时间片S10时间片S21时间片Sjj时间片Si-1i-1时间片SiiPCB队列PCB队列PCB队列PCB队列PCB队列…………多级反馈队列注：时间片S1<S2<S3<……<Si244.6实时系统调度方法1.实时系统的特点实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内作出快速反应。要求：（1）提供必要的调度信息

就绪时间、开始时限、完成时限、处理时间、资源要求、优先级（2）快速的外部中断响应能力（3）调度方式

硬实时任务广泛采用抢占调度方式有些软实时任务也可用非抢占方式（4）快速任务分派，进程切换

252.实时调度算法1）时间片轮转法

仅能获得秒级的响应时间，只适用于一般实时信息处理，不能用于要求严格的实时控制系统中。2）非抢占优先调度算法

常用于多道批处理系统中。此算法精心处理后可获得数秒至数百毫秒的响应时间，可用于不太严格的实时控制系统中。3）基于固定点抢占的优先权调度算法

允许抢先的固定点间隔比时间片小得多，固定点到来即可将CPU分配给高优先级任务，可达几十毫秒至几毫秒。可用于大多数的实时系统中。4）立即抢占的优先权调度可达几毫秒至100微秒。263.时限调度算法以满足用户要求的时限为调度原则分两种：

处理开始时限处理结束时限基本思想：按用户的时限要求顺序设置优先级，时限要求最近的任务优先占有处理机27时限调度算法举例具有处理开始时限要求的非周期实时任务调度时延要求不严格时，可采用处理开始时限优先的非抢占调度策略1处理开始时限执行任务任务到达12341342342t28时限调度算法举例2）具有处理完成时限要求的周期实时任务调度，采用抢占式调度策略如系统中有两个周期性实时任务A、B，A要求每30ms执行一次，处理完成时限为30ms,执行时间为15ms,而B要求