操作系统-第四章处理机调度.ppt

1、第四章 处理机调度 4.1 分级调度 (4.1.2调度的层次) 作业调度(一级调度，宏调度) 进程调度(二级调度，微调度) 交换调度(中级调度) 线程调度,图4.1 作业的状态及其转换,第四章 处理机调度 4.1 .1作业的状态及转换 作业一般都要经历提交、收容、执行和完成等4个状态。,4.1.3 作业和进程的关系 作业是用户需要计算机完成某项任务时要求计算机所作工作的集合。进程是已提交完毕程序的执行过程的描述，是资源分配的基本单位。区别与关系： (1) 作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实

2、体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。,(2) 一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立。 (3) 作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道系统中。,4.2作业调度 4.2.1作业调度的功能 1、通过作业控制块JCB(如图4.2)记录系统中各作业的情况。 2、从后备队列中选出一个或几个作业进入内存。 3、为选中的作业做好执行前的准备工作，如分配必要的资源并建立相应的进程。 4、作业执行结束后做好善后工作，如收回资源、撤销作业控制块等。,图4.3 作业调度中状态的转换过程,4.2.2 作业调度目标

3、与性能衡量 这里先介绍调度目标。 一般来说，调度目标主要是以下4点： (1) 对所有作业应该是公平合理的； (2) 应使设备有高的利用率； (3) 每天执行尽可能多的作业； (4) 有快的响应时间。 由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不可能的。,1. 周转时间： 作业i的周转时间Ti为 Ti=Tei-Tsi 其中Tei为作业i的完成时间，Tsi为作业的提交时间。 对于被测定作业流所含有的n（n=1）个作业来说，其平均周转时间为： 一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间；执行时间，即： Ti=TwiTri 这里，Twi主要指作业i由后备状态

4、到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。,2. 带权周转时间 作业的周转时间包含了两个部分，即等待时间和执行时间。为了更进一步反映调度性能，使用带权周转时间的概念。带权周转时间是作业周转时间与作业执行时间的比： Wi=Ti/Tri 对于被测定作业流所含有的几个作业来说，其平均带权周转时间为： 对于分时系统，除了要保证系统吞吐量大、资源利用率高之外，还应保证有用户能够容忍的响应时间。因此，在分时系统中，仅仅用周转时间或带权周转时间来衡量调度性能是不够的。,3. 响应时间 响应时间是用户从提交一个请求开始直到在屏幕上显示出结果或显示正在处理的提示信息为止的这段时间间隔。 不同场

5、合对响应时间的要求 （）分时系统和实时信息处理系统类似，响应时间都以人所能接受的等待时间来确定，通常是35秒钟，否则分时系统的用户就没有独占计算机的感觉，实时信息处理系统的终端用户就没有及时处理的感觉。 （）对实时控制系统，响应时间要求有很大的差别，它是以控制对象所要求的开始截止时间或完成截止时间来确定，一般为秒级、毫秒级、甚至有的要低于100微秒。,4.2.3 (4.4)作业调度算法 1、先来先服务 2、短作业优先 3、小作业优先 4、响应比高者优先 作业等待时间+估计运行时间 估计运行时间,响应比=,4.3 进程调度 4.3.1进程调度的功能 1、由PCB记录系统中进程的执行情况。 2、选

6、择占有处理机的进程。 3、进行进程上下文切换。 上下文切换: 进程调度是由进程调度程序实现的，它的主要任务是： 1)保护离开CPU的那个进程的现场。 2)按照一定的算法，从就绪进程中选一个进程，准备把CPU分配给它。 3)恢复选中进程的现场。,4.3.2何时调度 每当CPU有空的时候，就要重新调度。CPU有空是指： 1、正在执行的进程正常结束。 2、执行中的进程因阻塞原语而阻塞。 3、执行中的进程调用了P操作。 4、执行中的进程提出IO请求。 5、分时系统中时间片用完。 6、执行完系统调用。 7、就绪队列中的进程优先级发生变化。,4.3.3 进程调度性能评价 进程调度虽然是系统内部的低级调度，

7、但进程调度的优劣直接影响作业调度的性能。 进程调度性能的衡量方法可分为定性和定量两种。 在定性衡量方面:调度的可靠性、简洁性 进程调度的定量评价：（类似作业高度评价） CPU的利用率评价 进程在就绪队列中的等待时间与执行时间之比等。 一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。,4.4 进程调度算法 1、先来先服务 实现方法 （）系统只要有按FIFO规则建立的后备作业队列或就绪进程队列即可，就是一个作业控制块JCB或进程控制块PCB加入队列时加在相应队列末尾。 （）调度退出队列时从相应队列首开始顺序扫描，将相关的JCB或PCB调度移出相应队列。,调度例子 假如在一个多

8、道程序系统中，有用户区空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业调度和进程调度均采用FCFS算法。现有5个作业，它们的作业名、进入输入井的时间、需要计算时间以及内存量要求如表5_1所示，并假设输入井中有作业进行调度。,按照调度算法调度的次序是: ，.,5个作业的平均周转时间T和平均带权周转时间W如下：T(42+60+66+96+96)/5=72(分钟) W(1+2+2.75+4+8)/5=3.55,优缺点 FCFS调度算法具有一定的公平性，并且实现也比较容易，这是它的优点。但是，它的缺点是实际上不公平，它比较有利于长作业（长进程），而不利于短作业（短进程）。因为当计

9、算时间很长的作业先进入输入井被选中装入内存运行时，就可能使那些计算时间短的后进入输入井的作业等待很长时间，而且使计算时间短的作业周转时间变长，从而使作业的平均周转时间也变长，降低了系统的吞吐能力。,2、 短作业（短进程）优先调度算法 短作业优先调度算法SJF，是指对执行时间短的作业优先调度的算法。 的实现方法 该调度算法是从后备作业队列中选择一个或若干个，估计运行时间最短且当时系统能满足它们资源要求的作业，将它们装入内存运行。,按照SJF调度算法调度的次序是: A B D E C,平均周转时间T和平均带权周转时间W如下：T=(42+60+66+72+108)/5=69.6（分钟）W=(1+2+

10、11/4+6+9/2)/5=3.25,3、优先级法 系统或用户按某种原则为进程执行一个优先级别，反应进程需要CPU轻重缓急的程度。 1)静态优先级 优先级一旦确定，就不再改变。 2)动态优先级 根据需要改变动态优先级。,平均周转时间T和平均带权周转时间W为：T=(60+50+50+120)/4=70（分钟） W=(1+5/3+5+12/5)/42.52,4、时间片轮转法 让每个进程在就绪队列中的等待时间与享受服务的时间成比例.,4 时间片轮转调度算法,调度算法(如图4.4) （）进程就绪队列往往按进程到达时间的先后排列。进程调度程序总是把处理机分配给队首进程，并规定其执行一段时间，即一个时间片

11、。 （）当进程执行完该时间片时，由一个计时器发出时钟中断，调度程序便根据此中断信号停止该进程的执行，并将它送入就绪队列末尾；然后，把处理机分配给就绪进程队列中新的队首进程一个时间片。,优点 这种调度算法可以保证就绪队列中的所有进程，在一给定的时间内，都能获得在处理机上执行一个时间片的时间。 时间片大小的选择 （）如果时间片过大，可使时间片轮转调度算法已退化为FCFS调度算法，因而无法获得令用户满意的响应时间。 （）如果时间片取得太小，其处理机调度开销将会变得很大，而处理机实际用于运行用户程序的时间比例将会变小。,5 多级反馈队列调度算法 多级反馈队列调度算法，是一种考虑较全面灵活的调度算法，它

12、不必事先知道各作业所需执行时间，且它可以满足各种类型进程的需要，因此它是目前公认较好的一种进程调度算法。 多级反馈队列调度法:设置多条就绪队列,进程被调度执行后,在被剥夺或放弃处理机后而在就绪时，可以改变其就绪队列(见下图）。,调度算法的实施过程 （）设置多级就绪队列。系统中有多个就绪进程队列，每个就绪队列对应一个调度级别，各级具有不同的优先级。第1级队列的优先级最高，第2级队列优先级次之，其余级队列的优先级随级增大而降低。 （）各级就绪队列具有不同大小的时间片。优先级最高的第1级队列中进程的时间片最小，随着队列的级数增大其中进程的优先级降低，但时间片却增大。,（）一个新进程在系统就绪队列中排

13、队的规则。当一个新进程进入内存后，首先被放到第1级就绪队列末尾。该队列中的进程按FCFS原则分配处理机，并运行相应于该队列的一个时间片。若进程在这个时间片中完成其全部工作，该进程离开就绪队列撤离系统；若进程运行完一个时间片后仍未完成，则该进程被强迫放弃处理机，放入下一级就绪队列的末尾。 （）按队列优先级高到低进行进程调度。每次进程调度都是从第1级就绪队列开始调度，仅当第1级队列空时，调度程序才调度第2级队列中的进程；依此类推。第n级队列中的进程采用时间片轮转方法进行调度。 （）一个进程进入较高优先级队列时可能要重新调度。,能照顾到短型作业用户的要求 能照顾到短批处理型作业用户的要求,可获得与终

14、端型作业一样的响应时间。 能照顾到长批处理型作业用户的要求 能照顾到输入输出型作业用户的要求 充分利用外部设备，以及对终端交互用户及时予以响应，通常输入输出型进程被唤醒可进入最高优先级队列，从而能很快得到处理机。,4.6 实时系统调度方法 4.6.1 实时系统的特点 (1) 有限等待时间（决定性） (2) 有限响应时间 (3) 用户控制 (4) 可靠性高 (5) 系统出错处理能力强,上述特性要求实时操作系统具有下述能力： (1) 很快的进程或线程切换速度 (2) 快速的外部中断响应能力 (3) 基于优先级的随时抢先式调度策略 基于优先级的调度策略大致有以下4种。即： 优先级+时间片轮转调度策略

15、； 基于优先级的非抢先式调度策略； 基于优先级的固定点抢先式调度策略； 基于优先级的随时抢先式调度策略。,4.6.2 实时调度算法的分类 (1) 静态表格驱动类 静态表格驱动类的实时调度算法，对可能的调度条件和参数进行静态分析，并将分析结果作为实际调度结果。这类调度方法多用于调度处理周期性任务，其主要分析参数为周期，执行时间、周期行结束时限和任务优先级等。最早时限优先法是比较典型的静态表格驱动算法。这里，最早时限优先法是优先调度时限最早的任务获得处理机的调度方法。,(2) 静态优先级驱动抢先式调度算法类 该类算法也进行静态分析，不过，它们的静态分析不直接产生调度结果，而只用来指定任务的优先级。频率单调调度算法就是一种静态优先级驱动的抢先式调度算法。 (3) 动态计划调度算法类 动态计划调度算法在调度任务执行之前排出调度计划，并分析计划的调度结果是否使得任务所要求的处理时限得到满足。如果能够满足，则按调度计划执行，否则修改调度计划。,(4) 尽力而为调度算法类 这一类算法不进行可能性分析，只对到达的事件和相关任务指定相应的优先级，并进行调度。尽力而为