操作系统处理机调.pptx

第三章 处理机调度与死锁 第三章第三章 处理机调度与死锁处理机调度与死锁 王培崇第三章 处理机调度与死锁 本章授课目的本章授课目的 使学生理解和掌握处理机调度和死锁的基本概念，使学生理解和掌握处理机调度和死锁的基本概念，掌握常用的处理机调度算法和预防、避免死锁的方法。掌握常用的处理机调度算法和预防、避免死锁的方法。第三章 处理机调度与死锁 3.13.1处理机调度的层次处理机调度的层次3.1.1 高级、中级和低级调度高级、中级和低级调度 1.高级调度高级调度(High Scheduling)即即 作业调度作业调度调调度度作作业业进进入入内内存存，并并为为其其分分配配必必要要的的资资源源。考考虑虑如如下两点：下两点：1)接接纳纳多多少少个个作作业业：主主要要考考虑虑内内存存大大小小、执执行行效效率系统吞吐量等因素。率系统吞吐量等因素。2)接纳哪些作业接纳哪些作业：取决于具体的调度算法。：取决于具体的调度算法。第三章 处理机调度与死锁 1 1作业和作业步作业和作业步(1)作业(Job)。包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。第三章 处理机调度与死锁(2)作业步(Job Step)。每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，上一个作业步的输出作为下一个作业步的输入。一个典型的作业可分成三个作业步：“编译”作业步;“连结装配”作业步;“运行”作业步;(3)作业流。若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。第三章 处理机调度与死锁 2 2作业控制块作业控制块JCB(Job Control Block)JCB(Job Control Block)系统感知作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在JCB中通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。第三章 处理机调度与死锁 JCBJCB的建立、调度、撤销：的建立、调度、撤销：作业进入系统时，系统便为每个作业建立一个JCB，根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。第三章 处理机调度与死锁 2.低级调度低级调度(Low Level Scheduling)：进程调度：进程调度 也也称称微微观观调调度度，从从处处理理机机资资源源分分配配的的角角度度来来看，即占有看，即占有CPU来运行。来运行。处处理理机机需需要要经经常常选选择择就就绪绪进进程程或或线线程程进进入入运运行状态。行状态。低低级级调调度度的的时时间间尺尺度度通通常常是是毫毫秒秒级级的的。由由于于低低级级调调度度算算法法的的频频繁繁使使用用，要要求求在在实实现现时时做做到到高效。高效。第三章 处理机调度与死锁 低级调度的主要功能低级调度的主要功能 (1)保存处理机的现场信息。(2)按某种算法选取进程。如优先数算法、轮转法等，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。(3)把处理器分配给进程。第三章 处理机调度与死锁 进程调度中的三个基本机制进程调度中的三个基本机制(1)排队器。事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快地找到它。(2)分派器(分派程序)。分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程，然后进行上下文切换，将处理机分配给它。(3)上下文切换机制。当对处理机进行切换时，会发生两对上下文切换操作。第三章 处理机调度与死锁 低级（进程）调度方式：低级（进程）调度方式：1)非抢占方式非抢占方式(Non-preemptive Mode)在下面情况下发生：在下面情况下发生：正正在在执执行行的的进进程程执执行行完完毕毕，或或因因发发生生某某事事件件而而不不能能再再继续执行；继续执行；执行中的进程因提出执行中的进程因提出I/O请求而暂停执行；请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，在进程通信或同步过程中执行了某种原语操作，显显然然，在在要要求求比比较较严严格格的的实实时时系系统统中中，不不宜宜采采用用这这种种调调度方式。度方式。第三章 处理机调度与死锁 2)抢占方式抢占方式(Preemptive Mode)抢占的原则有：抢占的原则有：(1)优先权原则。优先权原则。(2)短作业短作业(进程进程)优先原则。优先原则。(3)时间片原则。时间片原则。大多数实时系统会采用这种调度方式大多数实时系统会采用这种调度方式。第三章 处理机调度与死锁 3.中级调度中级调度(Intermediate-Level Scheduling)中中级级调调度度又又称称中中程程调调度度(Medium-Term Scheduling)。主要目的：是为了提高内存利用率和系统吞吐量。主要目的：是为了提高内存利用率和系统吞吐量。涉涉及及进进程程在在内内外外存存间间的的交交换换，从从存存储储器器资资源源管管理理的的角角度度来来看看，把把进进程程的的部部分分或或全全部部换换出出到到外外存存上上，可可为为当当前前运运行行进进程程的的执执行行提提供供所所需需内内存存空空间间，将将当当前进程所需部分换入到内存。前进程所需部分换入到内存。如如果果资资源源允允许许后后，决决定定哪哪个个外外存存被被挂挂起起的的进进程程被调度进入。被调度进入。第三章 处理机调度与死锁 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.2.13.2.1调度队列模型调度队列模型1 1仅有进程调度的调度队列模型仅有进程调度的调度队列模型（1）在分时系统中，仅仅设有进程调度。（2）用户键入的命令和数据都直接送入内存。对于命令，是由OS为之建立一个进程。（3）系统可以把处于就绪状态的进程组织成栈、树或一个无序链表。例如：就绪进程组织成FIFO队列形式。每当OS创建一个新进程时，便将它挂在就绪队列的末尾，然后按时间片轮转方式运行。第三章 处理机调度与死锁 进程执行时现的三种情况：(1)任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态；(2)任务在本次分得的时间片内尚未完成，OS便将该任务再放入就绪队列的末尾；(3)在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞队列。图3-1示出了仅具有进程调度的调度队列模型。第三章 处理机调度与死锁 图图 3-1 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 第三章 处理机调度与死锁 2 2具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型（1）在批处理系统中，既要进程调度，而且还有作业调度；(2)作业调度算法负责从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列；（3）进程调度按照一定的进程调度算法选择一个进程，把处理机分配给该进程。图3-2示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。第三章 处理机调度与死锁 2.具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 图图 3-2 具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型 第三章 处理机调度与死锁(1)就绪队列的形式。就绪队列的形式。批处理中，最常用的调度算法是优先级算法。高优批处理中，最常用的调度算法是优先级算法。高优先级的作业排在队列的最前面。先级的作业排在队列的最前面。(2)设置多个阻塞队列。设置多个阻塞队列。对于小型计算机系统也可以只设置一个阻塞队列，但是对于小型计算机系统也可以只设置一个阻塞队列，但是如果是较复杂的系统，设置多个阻塞队列较好。如果是较复杂的系统，设置多个阻塞队列较好。图图 3-2 示示出出了了具具有有高高、低低两两级级调调度度的的调调度度队队列列模模型型。该模型与图该模型与图3-1的模型主要区别在于如下两个方面。的模型主要区别在于如下两个方面。第三章 处理机调度与死锁 3 3同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型设置有中级调度的系统：进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在中级调度的作用下，又可使外存就绪转为内存就绪。图3-3示出了具有三级调度的调度队列模型。第三章 处理机调度与死锁 图图 3-3 具有三级调度时的调度队列模型具有三级调度时的调度队列模型 第三章 处理机调度与死锁 3.2.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1.面向用户的准则面向用户的准则(1)周转时间短。周转时间短。可把平均周转时间描述为：可把平均周转时间描述为：作作业业的的周周转转时时间间T与与系系统统为为它它提提供供服服务务的的时时间间TS之之比比，即即W=T/TS，称称为为带带权权周周转转时时间间，而而平平均均带带权权周周转转时时间间则则可可表示为表示为:第三章 处理机调度与死锁(2)响应时间快。响应时间快。(3)截止时间的保证。截止时间的保证。(4)优先权准则。优先权准则。总的原则：具有公平性，但是可以特事特总的原则：具有公平性，但是可以特事特办。办。第三章 处理机调度与死锁 2.面向系统的准则面向系统的准则 (1)系统吞吐量高。系统吞吐量高。在单位时间内系统完成的作业数目。在单位时间内系统完成的作业数目。(2)处理机利用率高。处理机利用率高。大中型机追求的目标，对于微机以及实时系统则较少大中型机追求的目标，对于微机以及实时系统则较少考虑。考虑。(3)各类资源的平衡利用。各类资源的平衡利用。第三章 处理机调度与死锁 3.3 调调 度度 算算 法法 3.3.1 先来先服务和短作业先来先服务和短作业(进程进程)优先调度算法优先调度算法 1.先来先服务调度算法先来先服务调度算法 第三章 处理机调度与死锁 2.短作业短作业(进程进程)优先调度算法优先调度算法 它们可以分别用于作业调度和进程调度。它们可以分别用于作业调度和进程调度。短短作作业业优优先先(SJF)的的调调度度算算法法:是是从从后后备备队队列列中中选选择择一一个个或或若若干干个个估估计计运运行行时时间间最最短短的的作作业业，将将它它们们调调入入内内存存运行。运行。短短进进程程优优先先(SPF)调调度度算算法法:从从就就绪绪队队列列中中选选出出一一估估计计运运行行时时间间最最短短的的进进程程，将将处处理理机机分分配配给给它它，使使它它立立即即执执行行并并一一直直执执行行到到完完成成，或或发发生生某某事事件件而而被被阻阻塞塞放放弃弃处处理理机时，再重新调度。机时，再重新调度。第三章 处理机调度与死锁 图图 3-4 FCFS和和SJF调度算法的性能调度算法的性能 第三章 处理机调度与死锁 SJ(P)F调度算法也存在不容忽视的缺点：调度算法也存在不容忽视的缺点：(1)该算法对长作业不利。该算法对长作业不利。(2)该该算算法法完完全全未未考考虑虑作作业业的的紧紧迫迫程程度度，不不能能保保证证紧紧迫迫性作业性作业(进程进程)会被及时处理。会被及时处理。(3)由由于于作作业业(进进程程)的的长长短短只只是是根根据据用用户户所所提提供供的的估估计计执执行行时时间间而而定定的的，而而用用户户又又可可能能会会有有意意或或无无意意地地缩缩短短其其作作业业的的估估计计运运行行时时间间，致致使使该该算算法法不不一一定定能能真真正正做做到到短短作作业业优先调度。优先调度。第三章 处理机调度与死锁 3.3.2 高优先权优先调度算法高优先权优先调度算法 1.优先权调度算法的类型优先权调度算法的类型 1)非抢占式优先权算法（非抢占式优先权算法（Non-preemptive)Non-preemptive)某某一一进进程程被被调调度度运运行行后后，除除非非由由于于它它自自身身的的原因不能运行，否则一直运行下去。原因不能运行，否则一直运行下去。第三章 处理机调度与死锁 2)抢占式优先权调度算法抢占式优先权调度算法(PreemptivePreemptive)当当有有比比正正在在运运行行的的进进程程优优先先级级更更高高的的进进程程就就绪绪时时，系系统统可可强强行行剥剥夺夺正正在在运运行行进进程程的的CPUCPU，提提供供给给具具有有更更高优先级的进程使用高优先级的进程使用 这这种种抢抢占占式式的的优优先先权权调调度度算算法法，能能更更好好地地满满足足紧紧迫迫作作业业的的要要求求，故故而而常常用用于于要要求求比比较较严严格格的的实实时时系系统中，统中，以及对性能要求较高的批处理和分时系统中。以及对性能要求较高的批处理和分时系统中。第三章 处理机调度与死锁 2.优先权的类型优先权的类型 1)静态优先权静态优先权 静静态态优优先先权权是是在在创创建建进进程程时时确确定定的的，且且在在进进程程的的整整个个运运行行期期间间保保持持不不变变。一一般般地地，优优先先权权是是利利用用某某一一范范围围内内的的一个整数来表示的。一个整数来表示的。第三章 处理机调度与死锁 确定进程优先权的依据有如下三个方面：确定进程优先权的依据有如下三个方面：(1)进程类型。进程类型。(2)进程对资源的需求。进程对资源的需求。(3)用户要求。用户要求。静态优先权法简单易行，系统开销小，但不够精确，静态优先权法简单易行，系统开销小，但不够精确，很可能出现优先权低的作业很可能出现优先权低的作业(进程进程)长期没有被调度的情况。长期没有被调度的情况。因此，仅在要求不高的系统中才使用静态优先权。因此，仅在要求不高的系统中才使用静态优先权。第三章 处理机调度与死锁 2)动态优先权动态优先权 在在进进程程创创建建时时创创立立一一个个优优先先数数，但但在在其其生生命命周周期期内优先数可以动态变化。如等待时间长优先数可改变。内优先数可以动态变化。如等待时间长优先数可改变。可以防止某个进程长时间占用处理机。可以防止某个进程长时间占用处理机。第三章 处理机调度与死锁 3.高响应比优先调度算法高响应比优先调度算法 优先权的变化规律可描述为：优先权的变化规律可描述为：由由于于等等待待时时间间与与服服务务时时间间之之和和，就就是是系系统统对对该该作作业业的的响响应应时间，故该优先权又相当于响应比时间，故该优先权又相当于响应比RP。据此，又可表示为：。据此，又可表示为：第三章 处理机调度与死锁 (1)如如果果作作业业的的等等待待时时间间相相同同，则则要要求求服服务务的的时时间间愈愈短，其优先权愈高，因而该算法有利于短作业。短，其优先权愈高，因而该算法有利于短作业。(2)当当要要求求服服务务的的时时间间相相同同时时，作作业业的的优优先先权权决决定定于于其其等等待待时时间间，等等待待时时间间愈愈长长，其其优优先先权权愈愈高高，因因而而它它实实现的是先来先服务。现的是先来先服务。(3)对对于于长长作作业业，作作业业的的优优先先级级可可以以随随等等待待时时间间的的增增加加而而提提高高，当当其其等等待待时时间间足足够够长长时时，其其优优先先级级便便可可升升到到很高，很高，从而也可获得处理机。从而也可获得处理机。该调度算法的特点：第三章 处理机调度与死锁 3.3.3 基于时间片的轮转调度算法基于时间片的轮转调度算法 1.时间片轮转法(RRRound Robin)把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行。时间片可以分为几十ms到几百ms不等。（皇帝轮流做，今年到我家）第三章 处理机调度与死锁 例子：图3-5示出了时间片分别为q=1和q=4时，A、B、C、D、E五个进程的运行情况；图3-6为q=1和q=4时各进程的平均周转时间和带权平均周转时间。图中的RR(Round Robin)表示轮转调度算法。第三章 处理机调度与死锁 图3-5 q=1和q=4时的进程运行情况 第三章 处理机调度与死锁 图3-6 q=1和q=4时进程的周转时间 第三章 处理机调度与死锁 2.多级反馈队列调度算法 算法特点:(1)设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。(2)该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。第三章 处理机调度与死锁 (3)最后一级采用时间片轮转，其他队列采用先进先出；(4)系统从第一级调度，当第一级为空时，系统转向第二个队列，.。（5）当运行进程用完一个时间片，放弃CPU时，则进入下一级队列等待调度；如果进程处于等待状态重新被唤醒时，进入原来的就绪队列；（6）当进程第一次就绪时，进入第一级队列。第三章 处理机调度与死锁 图图 3-5 多级反馈队列调度算法多级反馈队列调度算法 就绪队列1就绪队列2就绪队列3就绪队列nS1S2S3至CPU至CPU至CPU至CPU(时间片：S1 S2 S3)第三章 处理机调度与死锁 3.多级反馈队列调度算法的性能（1）终端型用户：由于主要是短的交互式作业，一般会保证在一级调度内完成，会令用户满意。（2）短批处理作业：一般会在1、2级内得到处理；（3）长批处理作业：在此调度算法中肯定会被轮转调度得到执行，不会担心长时间得不到相应。第三章 处理机调度与死锁 3.4 实实 时时 调调 度度 3.4.1 实现实时调度的基本条件实现实时调度的基本条件 1.提供必要的信息提供必要的信息(1)就绪时间。(2)开始截止时间和完成截止时间。(3)处理时间。(4)资源要求。(5)优先级。第三章 处理机调度与死锁 2.系统处理能力强系统处理能力强 在在实实时时系系统统中中，通通常常都都有有着着多多个个实实时时任任务务。处处理理机机要要保保证在特定的时间内使作业得到调度。如下：证在特定的时间内使作业得到调度。如下：假假定定系系统统中中有有m个个周周期期性性的的硬硬实实时时任任务务，它它们们的的处处理理时时间间可可表表示示为为Ci，周周期期时时间间表表示示为为Pi，则则在在单单处处理理机机情情况况下下，必必须满足下面的限制条件：须满足下面的限制条件：第三章 处理机调度与死锁 假如系统中有6个硬实时任务，它们的周期时间都是 50 ms，而每次的处理时间为 10 ms，则不难算出，此时是不能满足上式的，因而系统是不可调度的。解决的方法是提高系统的处理能力，其途径有二：其一仍是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；其二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：注意：上述考虑并没有计算消息传递，任务切换等开销。第三章 处理机调度与死锁 3.采用抢占式调度机制 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。但这种调度机制比较复杂。这种机制采用比较广泛，因为很难对任务的开始和截止进行预先的估计，所以非抢占式调度机制一般很少采用。第三章 处理机调度与死锁 4.具有快速切换机制具有快速切换机制 该机制应具有如下两方面的能力：(1)对外部中断的快速响应能力。为使在紧迫的外部事件请求中断时系统能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。(2)快速的任务分派能力。在完成任务调度后，便应进行任务切换。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。第三章 处理机调度与死锁 3.4.2 实时调度算法的分类实时调度算法的分类 1.非抢占式调度算法非抢占式调度算法(1)非抢占式轮转调度算法。系统选择队列队首的任务运行，任务完成后，将其挂在队尾等待下次调度。主要用于实时要求不高的系统中。(2)非抢占式优先调度算法。为要求响应的任务设置较高的优先级，并将其挂在队首，等待当前任务执行完毕后进入执行。第三章 处理机调度与死锁 2.抢占式调度算法抢占式调度算法(1)基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法（有时钟中断才切换）（有时钟中断才切换）(2)立即抢占的优先权调度算法。立即抢占的优先权调度算法。图图 3-6 实时进程调度比较实时进程调度比较第三章 处理机调度与死锁 3.3.3 常用的几种实时调度算法常用的几种实时调度算法 1.最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)算法算法 算法思想是：当一个事件发生时，对应的进程就被加入就绪进程队列。该就绪队列按照截止期限排序，对于一个周期性事件，其截止期限即为下一次发生的时间。该调度算法首先运行队首进程，即截止时间最近的那个进程。第三章 处理机调度与死锁 1)非抢占式调度方式用于非周期实时任务图3-7示出了将该算法用于非抢占调度方式之例。系统首先调度任务1执行，在任务1执行期间，任务2、3又先后到达。由于任务3的开始截止时间早于任务2，故系统在任务1后将调度任务3执行。在此期间又到达作业4，其开始截止时间仍是早于任务2的，故在任务3执行完后，系统又调度任务4执行，最后才调度任务2执行。第三章 处理机调度与死锁 图图 3-7 EDF算法用于非抢占调度方式算法用于非抢占调度方式 第三章 处理机调度与死锁 2)抢占式调度方式用于周期实时任务图3-10示出了将最早截止时间优先算法用于抢占调度方式之例。任务A的周期时间为20 ms，每个周期的处理时间为10 ms；任务B的周期时间为50 ms，每个周期的处理时间为25 ms。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。其中任务A的到达时间为0、20、40、；任务A的最后期限为20、40、60、；任务B的到达时间为0、50、100、；任务B的最后期限为50、100、150、(注：单位皆为ms)。第三章 处理机调度与死锁 图3-10 最早截止时间优先算法用于抢占调度方式之例 第三章 处理机调度与死锁 为了说明通常的优先级调度不能适用于实时系统，该图特增加了第二和第三行。第二行中假定任务A具有较高的优先级，所以在t=0 ms时，先调度A1执行，在A1完成后(t=10 ms)才调度B1执行；在t=20 ms时，调度A2执行；在t=30 ms时，A2完成，又调度B1执行；在t=40 ms时，调度A3执行；在t=50 ms时，虽然A3已完成，但B1已错过了它的最后期限，这说明了利用通常的优先级调度已经失败。第三行与第二行类似，只是假定任务B具有较高的优先级。第三章 处理机调度与死锁 第四行是采用最早截止时间优先算法的时间图。在t=0时，A1和B1同时到达，由于A1的截止时间比B1早，故调度A1执行；在t=10时，A1完成，又调度B1执行；在t=20时，A2到达，由于A2的截止时间比B2早，B1被中断而调度A2执行；在t=30时，A2完成，又重新调度B1执行；在t=40时，A3又到达，但B1的截止时间要比A3早，仍应让B1继续执行直到完成(t=45)，然后再调度A3执行；在t=55时，A3完成，又调度B2执行。在该例中利用最早截止时间优先算法可以满足系统的要求。第三章 处理机调度与死锁 2.最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 该该算算法法是是根根据据任任务务紧紧急急(或或松松弛弛)的的程程度度，来来确确定定任任务务的的优优先先级级。任任务务的的紧紧急急程程度度愈愈高高，为为该该任任务务所所赋赋予予的的优优先先级级就就愈愈高，高，以使之优先执行。如下例：以使之优先执行。如下例：松弛度截止时间（就绪时间计算时间）松弛度截止时间（就绪时间计算时间）松松弛弛度度越越小小说说明明越越紧紧迫迫，优优先先级级会会越越高高，就就绪绪后后应应该该尽尽快快执执行。行。理理解解：在在保保证证进进程程被被调调度度执执行行的的情情况况下下，最最晚晚应应该该在在什什么么时时间间得得到到调调度度，才才能能够够保保证证顺顺利利完完成成任任务务。中中间间可可以以有有多多大大的宽裕度。的宽裕度。第三章 处理机调度与死锁 例子：在一个实时系统中，有两个周期性的进程A和B，任务A要求每20毫秒执行一次，执行时间为10毫秒；任务B只要求每50毫秒执行一次，执行时间为25毫秒。请计算A、B进程的每次的调度时间。第三章 处理机调度与死锁 图图 3-8 A和和B任务每次必须完成的时间任务每次必须完成的时间 依照此图中进程AB必须完成的时间点，向前推算什么时候队各进程进行调度。（允许抢占cpu）第三章 处理机调度与死锁 在在刚刚开开始始时时(t1=0)，A1必必须须在在20ms时时完完成成，而而它它本本身身运运行又需行又需 10 ms，可算出，可算出A1的松弛度为的松弛度为10ms；B1必必须须在在50ms时时完完成成，而而它它本本身身运运行行就就需需25 ms，可可算算出出B1的的松松弛弛度度为为25 ms，故故调调度度程程序序应应先先调调度度A1执执行行。在在t2=10 ms时，时，A2的松弛度可按下式算出：的松弛度可按下式算出：A2的松弛度的松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间 =40 ms-10 ms-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=55mst6=55ms，任任务务A A尚尚未未进进入入第第4 4周周期期，而而任任务务B B已已进进入入第第2 2周期，故再调度周期，故再调度B2B2执行。执行。t7=70 t7=70 msms，A4A4的的松松弛弛度度已已减减至至0 0 ms(ms(即即80-10-70)80-10-70)，而而B2B2的的松松弛弛度度为为20 20 ms(ms(即即100-10-70)100-10-70)，故故此此时时调调度度又又应应抢抢占占B2B2的处理机而调度的处理机而调度A4A4执行。执行。第三章 处理机调度与死锁 图图 3-9 利用利用ELLF算法进行调度的情况算法进行调度的情况