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

《华东理工大学《操作系统》第四章处理机调度》由会员分享，可在线阅读，更多相关《华东理工大学《操作系统》第四章处理机调度（31页珍藏版）》请在金锄头文库上搜索。

1、4.1 分级调度l处理机是计算机系统中的重要资源l处理机调度算法对整个计算机系统的综合性 能指标有重要影响l可把处理机调度分成四个层次： 高级调度 中级调度 低级调度线程调度第四章 处理机调度11)高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天 2)中级调度涉及进程在内外存间的交换，从存 储器资源管理的角度来看，把进程的部分或 全部换出到外存上，可为当前运行进程的执 行提供所需内存空间，将当前进程所需部分 换入到内存。指令和数据必须在内存里才能 被处理机直接访问23)低级调度也称微观调度，进程调度，从处理机资源 分配的角度来看，处理机需要经常选择就绪进程进 入运行状态，

2、低级调度的时间尺度通常是毫秒级的 。由于低级调度算法的频繁使用，要求在实现时做 到高效 4)线程调度:选择就绪线程进入运行状态，注：只有批处理系统中存在作业调度，实时与分时系统 中不存在作业调度，只有进程调度、交换调度和线 程调度3作业状态转换图数据提交状态完成状态后备状态执行状态作业控制进程 输入设备数据源程序输出设备作业说 明书 输 入 井运行等待就绪输 出 井输 入 程 序输 出 程 序作 业 调 度进程 调度4批处理作业的调度作业调度又称高级调度或宏观调度，相应地 称进程调度为低级（微观）调度。 主要功能：1)审查系统能否满足用户作业的资源要求； 只要通过调用相应的资源管理程序的有关部

3、分，审核其 JCB表中是否能满足要求即可 2)按照一定的算法从输入井中的后备作业中选取作业；调度的关键在选择恰当的算法 3)为选中作业做好执行前的准备，建立进程，分配资源； 4)作业结束后回收资源及JCB。5调度算法的确定基于一定因素，一般系统的设 计目标有：1）调度算法性能的衡量（1）每天运行尽能多的作业； （2）使CPU保持忙； （3）使I/O保持忙； （4）对所有作业公平合理。常用指标： 周转时间：指将一个作业提交给计算机系统后到该作 业的结果返回给用户所需时间。 吞吐率：在单位时间内，一个计算机系统所完成的总 工作量。 响应时间：从用户向计算机发出一个命令到系统把相 应结果返回所需时间

4、。 设备利用率：输入输出设备的使用情况。6周转时间与平均周转时间假定某一作业进入“ 输入井”的时间即作业 提交时间为TSi ，作业i 的完成时间为TEi，它的周转时间为Ti TEi TSi则作业平均周转时间 为：其中，n为被测定作业流中 的作业数l一个作业的周转时间 即该作业在系统内停 留的时间，包含两部 分：等待时间和执行 时间。lTi=Twi+TrilTwi指作业由后备状态 到执行状态的等待时 间。lTri作业进入执行态， 在内存的时间l用来衡量不同调度算法对 同一作业流的调度性能7B.带权周转时间l带权周转时间是作业 周转时间与作业执行 时间的比：Wi=Ti/Tri 平均带权周转时间：其

5、中，其中，ri ri 为某作业为某作业i i的实际执行时间的实际执行时间用来比较某种调度算法对不同作业流的调度性能。82)常见的批处理作业调度算法（1）先来先服务算法 （FCFS：First Come First Serve）每个作业按照它们在队列中的等待时间长短来调度， 可能造成短作业等长时间。 （2）最短作业优先算法（SJF：Shortest Job First）短作业优先，吞吐量大，但长作业可能得不到服 务9(3).响应比高者优先（HRN)的调度算法：响应比RP定义如下: 其中响应时间为作业进入系统后等待时间加上估计的运行时 间，因此，响应比可写为：所谓响应比高者优先的算法，就是在每调度

6、一个作业投 入运行时，计算后备作业表中每个作业的响应比，挑选 响应比最高者。兼顾FCFS和SJF 10作业调度程序根据JCB优先数决定进入内存的次序,系统开销 小 （a）静态优先级（外部优先数）用户提交作业时，根据急迫程度规定适当的优先数系统或操作员根据作业类型及要求资源情况指定。（b）由系统动态计算优先级(内部优先数)例如：可按如下公式计算作业的优先数：优先数 = 用户规定优先数 作业处理时间 +作业等待时间 输出量（4）基于优先级调度算法：静态法和动态法113）作业调度算法应用例子1假设在单道批处理环境下有四个作业，已知它 们进入系统的时间、估计运行时间 应用先来先服务、最短作业优先和最高

7、响应比 优先作业调度算法，分别计算出作业的平均 周转时间和带权的平均周转时间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最高响应比优先

8、作业算法计算结果154.3 进程调度算法1进程调度进程调度的任务是控制协调进程对CPU的竞争即按一定的调度 算法从就绪队列中选中一个进程，把CPU的使用权交给被选 中的进程 要解决的问题： WHAT：按什么原则分配CPU进程调度算法 WHEN：何时分配CPU进程调度的时机 HOW： 如何分配CPUCPU调度过程（进程的切换）162 进程调度的功能记录系统中所有进程的情况，PCB.选择占有处理机的进程。不同的系统，不同 的选择策略。进行进程上下文切换进程上下文由进程程序段、数据段、寄存 器及相关数据结构PCB等组成。173 进程调度的时机当一个进程运行完毕，或由于某种错误而 终止运行当一个进程在

9、运行中等待资源被阻塞如P原 语分时系统中时间片到在进程通信中，执行中的进程执行了 sleep(),wait()185各种进程调度算法1）先进先出进程调度算法（FIFO）按照进程就绪的先后次序来调度进程优点:实现简单缺点:没考虑进程的优先级短进程可能等待长时间192)基于优先级的调度 （HPFHighest Priority First）优先选择就绪队列中优先级最高的进程投入运行确定优先数的方法: 1)静态优先数法：在进程创建时指定优先数，在进程运行时优先数 不变 2)动态优先数法：在进程创建时创立一个优先数，但在其生命周期 内优先数可以动态变化。如等待和占有CPU时间 长短优先数可改变203)

10、时间片轮转调度算法 (RRRound Robin)把CPU划分成若干时间片（每个时间片的大小视情况而异，如50ms，100ms或200ms等）,并且按顺序 赋给就绪队列中的每一个进程，进程轮 流占有CPU，当时间片用完时，即使进 程未执行完毕，系统也剥夺该进程的 CPU，将该进程排在就绪队列末尾。同 时系统选择另一个进程运行. 21分时系统中常用时间片轮转法时间片选择问题：固定时间片可变时间片 与时间片q大小有关的因素：1）系统响应时间R2）就绪队列中所允许的最大进程数NR与就绪队列中所允许的最大进程数N和q成比例 RNq. q=R/NN一定时，q正比于系统所要求的响应时间224） 多队列反馈

11、轮转算法：*首先系统中设置多个就绪队列； * 每个就绪队列分配给不同时间片，优先级高的为 第一级队列，时间片最小，随着队列级别的降低 ，时间片加大；l当第一级队列空时，就去调度第二级队列，如此 类推；l每个进程并不固定在一个队列上，系统将新创建 的进程放入优先权最高的队列中去；当进程在CPU上运行完一个时间片以后并被投入 下一个队列；每个队列均按先进先出的算法组织；进程由于等待而放弃CPU后，进入等待队列，一 旦等待的事件发生，则回到原来的队列末尾。23优先数优先数时间片时间片S1S10 0时间片时间片S2S21 1时间片时间片SjSjj j时间片时间片Si-1Si-1i-1i-1时间片时间片

12、SiSii iPCBPCB队列队列PCBPCB队列队列PCBPCB队列队列PCBPCB队列队列PCBPCB队列队列多级反馈队列多级反馈队列注：时间片S1S2S3 Si244.6实时系统调度方法l1.实时系统的特点 实时实时是指计算机对于外来信息能够以足够快的速度进行是指计算机对于外来信息能够以足够快的速度进行 处理，并在被控对象允许的时间范围内作出快速反应。处理，并在被控对象允许的时间范围内作出快速反应。要求： （1）提供必要的调度信息就绪时间、开始时限、完成时限、处理时间、资源要求、优先级 （2）快速的外部中断响应能力 （3）调度方式硬实时任务广泛采用抢占调度方式 有些软实时任务也可用非抢占

13、方式 （4）快速任务分派，进程切换252.实时调度算法1）时间片轮转法仅能获得秒级的响应时间，只适用于一般实时信息处理，不 能用于要求严格的实时控制系统中。 2）非抢占优先调度算法常用于多道批处理系统中。此算法精心处理后可获得数秒至 数百毫秒的响应时间，可用于不太严格的实时控制系统中。 3）基于固定点抢占的优先权调度算法允许抢先的固定点间隔比时间片小得多，固定点到来即可将 CPU分配给高优先级任务，可达几十毫秒至几毫秒。可用于大 多数的实时系统中。 4）立即抢占的优先权调度可达几毫秒至100微秒。263.时限调度算法l以满足用户要求的时限为调度原则l 分两种：l 处理开始时限l 处理结束时限l

14、基本思想：按用户的时限要求顺序设置优先级， 时限要求最近的任务优先占有处理机27时限调度算法举例l具有处理开始时限要求的非周期实时任务调 度l时延要求不严格时，可采用处理开始时限优 先的非抢占调度策略1处理开始时限执行任务任务到达 12341342342 t28时限调度算法举例l2）具有处理完成时限要求的周期实时任务 调度，采用抢占式调度策略l如系统中有两个周期性实时任务A、B，A要 求每30ms执行一次，处理完成时限为30ms, 执行时间为15ms,而B要求每75ms执行一次, 处理完成时限为75ms,执行时间为45ms.29进程开始时间执行时间完成时限A101530 A2301560 A3601590 A49015120 . B104575 B27545150 B315045225 .A1B1A2B1B1A3A4B2153045607590105130t030作业l4.2l4.4l4.631