《第4章 处理机调度1.ppt》由会员分享，可在线阅读，更多相关《第4章 处理机调度1.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第4章 处理机调度l 分级调度分级调度l 作业调度作业调度l 进程调度进程调度l 调度算法调度算法l 实时系统调度方法实时系统调度方法课时：课时：6.0 在计算机系统中，可能同时有数百个批处理作业存放在磁盘的作业队列中，或者有数百个终端与主机相连接，这样一来内存和处理器等资源便供不应求。如何从这些作业中挑选作业进入主存运行、如何在进程之间分配处理器时间，无疑是操作系统资源管理中的一个重要问题。处理器调度用来完成涉及处理器分配的工作。概 述n 作业的状态及其转换 一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成等4个状态。（以前我们讲授过该部分内容）分级调度图4.
2、1 作业的状态及其转换 一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。处于提交状态的作业，因其信息尚未全部进入系统，所以不能被调度程序选取。收容状态也称为后备状态。输入管理系统不断地将作业输入到外存中对应部分（或称输入井，即专门用来存放待处理作业信息的一组外存分区）。若一个作业的全部信息已全部被输入进输入井，那么，在它还未被调度去执行之前，该作业处于收容状态。分级调度 作业调度程序从后备作业中选取若干个作业到内存投入运行。它为被选中作业建立进程并分配必要的资源，这时，这些被选中的作业处于执行状态。当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成状态。在这种状
3、态下，系统需做诸如打印结果、回收资源等类的善后处理工作。分级调度n 调度的层次 一般来说，处理机调度可以分为三级：l 高级调度：又称作业调度或长程调度（Long-term Scheduling）。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，回收系统资源。分级调度n 调度的层次l 中级调度：又称交换调度、平衡负载调度或中程调度（Medium-term Scheduling）。中级调度根据存储资源量和进程的当前状态来决定辅存和主存中的进程的对换，它所使
4、用的方法是通过把一些进程换出主存，从而，使之进入“挂起”状态，不参与低级调度，起到短期平滑和调整系统负荷的作用。交换调度主要涉及到内存管理与扩充。分级调度n 调度的层次l 低级调度：又称进程调度（或线程调度）、短程调度（Short-term Scheduling）。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。通常，我们所说的调度一般指进程调度。分级调度n 关于不同级别调度的说明：l 在多道批处理系统中，存在着作业调度和进程调度；l 在分时系统和实时系统中，一般不存在作业调度，而
5、只有进程调度、交换调度。因而，这些系统中没有作业提交状态和后备状态。它们的输入信息经过终端缓冲区为系统所接收，或者立即处理，或者经交换调度暂存外存中。现代操作系统偏向于后者。分级调度n 选择调度算法的原则 l 资源利用率使得CPU 或其他资源的使用率尽可能高且能够并行工作，CPU 利用率=CPU 有效工作时间/CPU 总运行时间。l 响应时间交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。使交互式用户的响应时间尽可能短，或尽快处理实时任务。分时系统和实时系统 调度算法设计原则n 选择调度算法的原则 l 周转时间批处理用户从作业提交开始，到作业完成为止的时间间隔称作业周转时
6、间，应使作业周转时间或平均作业周转时间尽可能短。批处理系统l 吞吐率使单位时间内处理的作业数尽可能多。l 公平性确保每个用户每个进程获得合理的CPU 份额或其他资源份额，不会出现饿死情况。调度算法设计原则n 周转时间与带权周转时间定义 作业i的周转时间为;Ti=Tei-Tsi 其中Tei为作业i的完成时间，Tsi为作业的提交时间。对于被测定作业流所含有的n（n=1）个作业来说，其平均周转时间为：调度算法设计原则n 周转时间与带权周转时间定义 带权周转时间 一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：等待时间；执行时间，即：Ti=TwiTri 这里，Twi主要指作业i由后备状态
7、到执行状态的等待时间，它不包括作业进入执行状态后的等待时间。调度算法设计原则n 周转时间与带权周转时间定义 带权周转时间 带权周转时间是作业周转时间与作业执行时间的比：Wi=Ti/Tri 对于被测定作业流所含有的几个作业来说，其平均带权周转时间为：调度算法设计原则n 调度算法的执行方式 l 非剥夺式一个作业一旦投入运行，除非进程本身自愿让出CPU，否则一直运行完成，调度算法不得剥夺其运行权。l 剥夺式系统实时地根据调度原则，当某就绪进程满足条件时，立即将正在运行的进程中断，并切换到其进程。调度算法设计原则n 作业调度（批处理系统）作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态
8、到完成状态的转变。l 作业调度功能 (1)记录系统中各作业的状况。系统为每个作业建立一个作业控制表JCB记录这些有关信息。系统通过JCB而感知作业的存在。JCB主要内容：作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。作业调度图4.2 作业控制块JCB作作业业名名作作业类业类型型资资源要求源要求资资源使用情况源使用情况优优先先级级(数数)当前状当前状态态其他其他作业调度n 作业调度（批处理系统）l 作业调度功能 (2)从后备队列中挑选出一部分作业投入执行。(3)为被选中作业做好执行前的准备工作。为选中作业建立相应进程，并分配系统资源。(4)在作业执行结束时做善后处理工作
9、。主要是输出作业管理信息，回收该作业所占用的资源，撤消与该作业有关的全部进程和该作业的作业控制块等等。作业调度n 进程调度 无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数，这将导致用户进程互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。进程调度n 进程调度l 进程调度的功能 (1)记录系统中所有进程的执行情况：进程管理模块将进程的执行情况和状态记录在PCB中。进程调度模块根据PCB来控制进程的执行。(2)选择占有处理机的进程：进程调度的主要功能是按照一定的策略选择一个处于就绪状态的
10、进程，使其获得处理机执行。(3)进行进程上下文切换 一个进程的执行是在进程的上下文中执行。当进程调度时，如果发生新进程被选中，系统要完成进程的切换。进程调度n 进程调度的时机 进程调度发生在什么时机呢？这与引起进程调度的原因以及进程调度的方式有关。引起进程调度的原因有以下几类：(1)正在执行的进程执行完毕；(2)进程执行了阻塞原语进入睡眠状态；(3)进程调用了PV操作，被阻塞或唤醒一进程；(4)进程提出IO请求后被阻塞；进程调度n 进程调度的时机 (5)进程的时间片已经用完；(6)在执行完系统调用，调度选择新用户进程执行；(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引
11、发进程调度。进程调度n 进程上下文切换 进程上下文由正文段、数据段、硬件寄存器的内容以及有关数据结构等组成。在发生进程调度时，系统要做进程上下文切换。进程上下文切换包括以下步骤：(1)决定是否做上下文切换以及是否允许做上下文切换。包括对进程调度原因的检查分析，以及当前执行进程的资格和CPU执行方式的检查等。进程调度n 进程上下文切换 (2)保存当前执行进程的上下文。(3)使用进程调度算法，选择一个处于就绪状态进程。(4)恢复或装配调度选中进程的上下文，将CPU控制权交给该进程。进程调度n 先来先服务（FCFS，First Come First Serve）算法 该算法是按照作业进入系统的作业后
12、备队列的先后次序来挑选作业，先进入系统的作业优先被挑选。这是一种非剥夺式算法，易实现，效率低，不利于短作业，但优待了长作业，可能使短作业周转时间变得很大。影响批作业的平均周转时间。该算法适用于作业调度和进程调度。调度算法n 先来先服务（FCFS）在实际操作系统中，尽管很少单独使用FCFS算法，但和其他一些算法配合起来，FCFS算法还是使用得相当多的。例如基于优先级的调度算法就是对具有同样优先级的作业或进程采用的FCFS方式。调度算法n 先来先服务（FCFS）例：下面三个作业同时到达系统并立即进入调度：例：下面三个作业同时到达系统并立即进入调度：调度算法n 先来先服务（FCFS）假设系统中没有其
13、他作业，现采用FCFS 算法进行调度，那么，三个作业的周转时间分别为：28、37 和40，因此，平均作业周转时间T=（28+37+40）/3=35 若顺序改为2、1、3，则平均周转时间为约29；如顺序改为3、2、1，则平均周转时间为约18。可以看出，FCFS 调度算法的平均作业周转时间与作业提交及调度的顺序有关。调度算法n最短作业优先SJF（Shortest Job First）该算法是以进入系统的作业所要求的CPU时间长短为标准，总是选取估计计算时间最短的作业投入运行。这是一种非剥夺式调度算法，它克服了FCFS 偏爱长作业的缺点，易于实现，但效率也不高。该算法适用于作业调度。调度算法n最短作
14、业优先SJF（Shortest Job First）主要不足：一是预先估计作业计算时间很难精确；二是忽视了长作业的等待时间，长作业可能会出现饥饿现象；三是该算法由于属于非剥夺机制，对分时、实时处理不理想。调度算法n最短作业优先SJF（Shortest Job First）例：若有以下四个作业同时到达系统并立即进入调度：调度算法n最短作业优先SJF（Shortest Job First）现对它们实施SJF 调度算法，这时的作业调度顺序为作业2、4、1、3，则：平均周转时间T=(4+12+21+31)/4=17 平均带权周转时间W=(4/4+12/8+21/9+31/10)/4=1.98 如果对它
15、们施行FCFS 调度算法，则：平均周转时间T=(9+13+23+31)/4=19 平均带权周转时间W=(9/9+13/4+23/10+31/8)/4=2.51调度算法n最短作业优先SJF（Shortest Job First）SJF 算法是非抢占式的，可以改进成抢占式的调度算法。当一个作业正在执行时，一个新作业进入就绪状态，如果新作业需要的CPU 时间比当前正在执行的作业剩余下来还需的CPU 时间短，抡占式短作业优先调度算法强行赶走当前正在执行的作业，这种方式叫最短剩余时间优先算法SRTF（Shortest Remaining Time First）算法。此算法适用于作业调度和进程调度。调度算
16、法n最高响应比（HRRF，Highest Response Ratio First）算法 响应比定义：响应比作业周转时间响应比作业周转时间/作业执行时间作业执行时间 每当调度一个作业运行时，都要计算后备作业队列中每个作业的响应比，选择响应比最高者投入运行。显然，短作业容易得到较高响应比，算法优待短作业；但长作业等待时间足够长，也将获得足够高的响应比，不至于长时间地等待下去。调度算法n最高响应比（HRRF，Highest Response Ratio First）算法 最高者优先算法既考虑作业等待时间，又考虑作业的运行时间，这样既照顾了短作业又不使长作业的等待时间过长，改进了调度性能。缺点是每次
17、计算各道作业的响应比会有一定的时间开销，需要估计期待的服务时间，性能要比SJF 差。调度算法n 优先级法 优先级法可被用作作业或进程的调度策略。首先，系统或用户按某种原则为作业或进程指定一个优先级来表示其优先权。该算法的核心是确定进程或作业的优先级。确定优先级的方法可分为静态法和动态法。调度算法n 优先级法l 静态优先级：作业的静态优先级按以下原则确定：(1)由用户自己根据作业的紧急程度输入一个适当的优先级。系统对高优先级用户收取高费用。(2)由系统或操作员根据作业类型指定优先级。作业类型一般由用户约定或由操作员指定。(3)系统根据作业要求资源情况确定优先级。调度算法n 优先级法l 静态优先级
18、 进程的静态优先级按以下原则确定：(1)按进程的类型给予不同的优先级。系统进程和用户进程。(2)将作业的静态优先级作为它所属进程的优先级。调度算法n 优先级法l 动态优先级（进程）进程的动态优先级一般根据以下原则确定：(1)根据进程占有CPU时间的长短来决定。一个进程占有处理机的时间愈长，则在被阻塞之后再次获得调度的优先级就越低。(2)根据就绪进程等待CPU的时间长短来决定。一个进程在就绪队列中等待时间越长，它获得的优先级就越高。调度算法n 轮转法（RR，round robin）轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。轮转法的基本概念是将CPU的处理时间分成固
19、定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。调度算法该算法一般仅适用于进程调度，不适用于作业调度。调度算法n 轮转法（RR，round robin）在轮转法中，时间片长度的选取非常重要。如果时间片长度过短，则调度程序剥夺处理机的次数增多。这将使进程上下文切换次数也大大增加，从而加重系统开销。反过来，如果时间片长度选择过长，可能变成了先来先服务法。时间片长度的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的。它可表示为：q=R/Nmax调度算法n 多级反馈轮
20、转法 该方法又称反馈循环队列或多队列策略，主要思想是将就绪进程或线程分为多级就绪队列，较高优先级的队列分配时间片较短。调度算法每次先从高一级就绪队列中选取，同一队列中按FCFS原则，只有选不到时才从较低一级的就绪进程队列中选取。时间片用完而未完成的进程加入低一级就绪队列，但时间片加长。调度算法先来先服务调度算法先来先服务调度算法 FCFS和SJF调度算法的性能 n 实时系统的特点 实时系统负责在用户要求的时限内进行事件处理和控制。实时系统与其他系统的最大区别在于，其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时间。实时系统系统中必须采用剥夺式优先级算法，以保证紧
21、急事件的处理及时性。实时调度方法实现实时调度的基本条件实现实时调度的基本条件 1.提供必要的信息提供必要的信息(1)就绪时间。(2)(2)开始截止时间和完成截止时间。(3)(3)处理时间。(4)(4)资源要求。(5)(5)优先级。4.6 实时系统调度方法 2.系统处理能力强系统处理能力强 在实时系统中，通常都有着多个实时任务。若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：1表示处理机表示处理机个数个数
22、系统才是可调度的。假如系统中有6个硬实时任务，它们的周期时间都是 50 ms，而每次的处理时间为 10 ms，则不难算出，此时是不能满足上式的，因而系统是不可调度的。解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：1表示处理机表示处理机个数个数3.采用抢占式调度机制采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。对于一些小
23、的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的任务。4.具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：(1)对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。(2)快速的任务分派能力。在完成任务调度后，便应进行任务切换
24、。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。实时调度算法的分类实时调度算法的分类 1.非抢占式调度算法非抢占式调度算法(1)非抢占式轮转调度算法。(2)(2)非抢占式优先调度算法。2.抢占式调度算法抢占式调度算法(1)基于时钟中断的抢占式优先权调度算法。(2)(2)立即抢占(Immediate Preemption)的优先权调度算法。图 实时进程调度 常用的几种实时调度算法常用的几种实时调度算法 1.最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)算法算法 图 EDF算法用于非抢占调度方式
25、2.最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms。又如，另一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列
26、中的队首任务执行。该算法主要用于可抢占调度方式中。图 A和B任务每次必须完成的时间 假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms时完成，而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出：A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 m
27、s-10 ms=20 ms 类似地，可算出B1的松弛度为15ms，故调度程序应选择B1运行。在t3=30 ms时，A2的松弛度已减为0(即40-10-30)，而B1的松弛度为15 ms(即50-5-30)，于是调度程序应抢占B1的处理机而调度A2运行。在t4=40 ms时，A3的松弛度为10 ms(即60-10-40)，而B1的松弛度仅为5 ms(即50-5-40)，故又应重新调度B1执行。在t5=45 ms时，B1执行完成，而此时A3的松弛度已减为5 ms(即60-10-45)，而B2的松弛度为30 ms(即100-25-45)，于是又应调度A3执行。在t6=55ms时，任务A尚未进入第4周
28、期，而任务B已进入第2周期，故再调度B2执行。在t7=70 ms时，A4的松弛度已减至0 ms(即80-10-70)，而B2的松弛度为20 ms(即100-10-70)，故此时调度又应抢占B2的处理机而调度A4执行。图 利用ELLF算法进行调度的情况 n 实时系统调度算法 实时调度算法可以分为动态实时调度算法和静态实时调度算法两类。1）单比率调度算法 单比率调度事先为每个进程分配一个与事件发生频率成正比的优先数，运行频率越高的进程其优先数就越高。运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式分配策略。可以证明该算法是最优的。实时调度方法n 实时系统调度算法 2）限期调度算法 基本思想是：当一个事件发生时，对应的进程就被加入就绪进程队列。该就绪队列按照截止期限排序。对于一个周期性事件，其截止期限即为事件下一次发生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。实时调度方法n 实时系统调度算法 3）最少裕度法 最少裕度法的基本思想是：首先计算各个进程的富裕时间，即裕度（laxity），然后选择裕度最少的进程执行。计算公式为：裕度=截止时间-(就绪时间+计算时间)裕度小说明很紧迫了，就绪后让它尽快运行。实时调度方法