EEPW论坛

发信人: ColdFire(天地一沙鸥), 信区: Embedded. 本篇人气: 80 标 题: 优先级调度和运行前调度的比较分析（转载） 发信站: 南京大学小百合站 (Mon Dec 23 08:53:07 2002) 作者：Jia Xu 计算机科学系 York大学 EMAIL: jxu@cs.yorku.ca 优先级调度和运行前调度的比较分析 上网时间 : 2002年11月30日 与优先级调度方法相对，采用运行前调度方法具有容易满足实现约束、可以采用优化算法 的优点，而优先级调度算法不能有效处理复杂约束、系统开销大，以及处理器资源利用率 低、系统运行特性难以分析和预测等。本文对两者进行了分析，并详细介绍了相关概念和 方法。 近年来，优先级调度日益受到广泛关注。优先级调度作为实时嵌入式系统设计方法，在许 多政府机构实施的重要项目中得到应用并受到广泛好评。例如，美国宇航局(NASA)、联邦 航空局(FAA)、美国海军和欧洲航天局等机构均采用了优先级调度。 在这些应用中，安全性至关重要，因为一旦无法满足时序约束，产生的后果将非常严重。 因此，设计工程师必须仔细考察优先级调度方法的特性，从而确定优先级调度方法是否是 最理想的选择。 一些公开发表的论文认为优先级调度方法优于其它的可选方法。本文提出了另一种观点， 对这些问题的探讨将有助于实时系统设计工程师在选择调度方法时做出明智的选择。尽管 其它论文从未明确阐述过这些问题，而且系统设计工程师显然也忽略了本文提出的观点， 但对这些问题的明确阐述确实能使许多实时系统开发人员受益匪浅。 本文假定硬实时系统(hard-real-time system)具有如下特性：包含的进程具有严格时序约 束且数目相对较多；这些进程具有不同的时序特性和相关性；处理器利用率并不很低，即 没有太多的CPU空闲容量。美国海军的A-7E飞行器操纵程序就是一个很好的实例。本文基于 J. Xu和D.L. Parnas的联合研究成果。 进程与调度 为了对复杂硬实时系统的性能进行预估，必须预先了解各进程的主要特性，否则不可能保 证得到满足所有时序约束的优先级条件。 1.周期性进程 周期性进程由反复执行的运算组成，每个固定的时间周期执行一次运算。周期性进程的一 个典型应用就是读取传感器数据并更新内部变量和输出的当前状态。 周期性进程p的四要素是rp, cp, dp, prdp：prdp表示周期；cp表示进程p在最坏情形下的 运算时间；dp表示时限，即在每个周期中，从周期起始到进程p执行完毕之间的时间间隔； rp表示释放时间，即在每个周期中，从周期起始到进程p最早开始执行之间的时间间隔。此 外，假定rp, cp, dp, prdp以及其它任何表示时间的参数均为整数。 周期性进程p可包含无数个周期性进程执行p0, p1, p2,...，每个周期执行一次进程。第i 个进程执行对应于第i个周期的进程pi，而pi的释放时间可表示为rpi = rp + prdp × (i -1)；pi的时限可表示为dpi= dp + prdp × (i-1)。 2.异步进程 异步进程由响应内部或外部事件的运算组成，异步进程的典型应用是响应操作人员的请求 。尽管无法预知执行异步进程a的精确请求时间，但通常可以预先得到两个连续请求间的最 短时间mina。异步进程a可由三要素ca, da, mina描述：ca 表示进程a在最坏情形下的运算 时间；da 表示时限，即从向进程a发出请求到进程a完成执行之间的时间间隔。异步进程a 可具有无数个异步进程执行a0, a1, a2, ...,，每个进程执行对应于一个异步请求。对于 对应于第i个请求的第i个异步进程执行ai，如果ai的请求时间为rai，则ai的时限为dai = rai + da。 3.调度 下面引入进程执行单元和处理器时间单元的概念。如果周期性进程p或异步进程a的运算时 间为cp或ca，那么假定进程执行pi或ai由cp或ca进程执行单元组成，而且每个处理器都与 起始于0的进程时间轴关联并分成连续的处理器时间单元。 调度能在一个或多个处理器时间轴上，将无数个进程执行单元映射到无数个处理器时间单 元上。在0与进程执行中由第一个执行单元所映射的处理器时间单元之间，所存在的处理器 时间单元数量被称为进程执行起始时间；0到进程执行中由最后一个执行单元所映射的处理 器时间单元之间，所存在的处理器时间单元数称为进程执行完成时间。如果调度中，每个 进程执行的起始时间大于或等于进程执行的释放时间或请求时间，并且进程的完成时间小 于或等于进程的执行时限，那么该调度是有效的。 4.进程分段 每个进程p均可由有限的分段序列p[0]、p[1]、...p[n[p]]组成，其中p[0]表示进程p的第 一个分段，p[n[p]]则表示进程p的最后一个分段。给定进程p的释放时间rp、时限dp和进程 p中每个分段p[i]的运算时间，可以简单地计算出每个分段的释放时间和时限。 5.优先和排斥关系 进程分段有序对之间可以存在各类关系，如优先关系(precedence relation)和排斥关系( exclusion relation)。 如果只有当进程分段i执行完成，进程分段j才能开始执行，则称进程分段i优先于进程分段 j。当某些进程分段需要由其它进程分段产生的信息时，这些进程分段之间就可能存在优先 关系。 如果从进程分段i开始执行运算到结束运算之间，不能执行任何进程分段j的运算，则称进 程分段i排斥进程分段j。当某些进程分段必须防止其它进程分段同时访问共享资源(如数据 和I/O设备)时，这些进程分段之间就可能存在排斥关系。 优先级调度和运行前调度概述 下面，本文将简要介绍优先级调度和运行前调度方法。 1.优先级调度方法 大多数优先级调度方法均遵循两个基本假定：a)调度在进程运行时执行；b)进程分配有固 定的优先级，当两个进程竞争同一处理器时，具有较高优先级的进程将获得处理器资源。 速率单调调度(Rate Monotonic Scheduling)是最具代表性的优先级调度方法。该方法假定 所有的进程都是周期性的，并且进程的主要特性在运行之前都已确定，即预先了解进程在 最坏情形下的执行时间和周期。 设计工程师可根据进程的周期设定固定的优先级：周期越短，优先级越高。任何时候，只 要所有进程中具有最高优先级的进程就绪，即可分配到处理器。而且在运行前，还可根据 已知的进程特性进行可调度性分析。如果满足特定的方程，即可在运行中执行实际的调度 ，并假定运行中可以满足所有的时限要求。 优先级最高限度协议(Priority Ceiling Protocol)的假定与速率单调调度相同，只是进程 可能具有由旗语(semaphores)保护的临界区，并提供专门的协议来处理这些临界区。每个 旗语均分配一个优先级最高限度值，优先级最高限度与使用该旗语的最高优先级进程具有 相等的优先级。具有最高优先级的进程一旦就绪，即可分配到处理器资源。任何进程p进入 其临界区之前，必须首先获取监控临界区的旗语S的优先级锁定。如果进程p的优先级不高 于当前除p以外，其它进程锁定的旗语中具有最高优先级的最高限度，那么进程p将被阻塞 ，S上的锁定将被拒绝。当进程p阻塞了更高优先级的进程，那么p将继承被p阻塞的进程的 最高优先级。 当p离开临界区，则进程p将恢复其进入临界区时的优先级。如果进程p不试图进入临界区， 并且其优先级(继承或分配的优先级)高于另一正在执行的进程pi的优先级，则可占先运行 。 如果满足以下条件，则速率单调调度(周期越短，优先级越高)可以调度(即满足所有时限要 求)采用优先级最高限度协议的n个周期性进程：其中Ci 表示执行时间，Ti 表示周期，Bi 表示最坏情形下由较低优先级进程引发的pi阻塞时间。 2.运行前调度方法 采用运行前调度，一般进程的调度是离线计算；同时，该方法还要求能够预先了解系统中 进程的主要特性。 采用运行前调度的方法对周期性进程进行调度是可能的。该方法由调度的离线计算(compu ting off-line)和调度运行两部分组成，即离线计算周期值等于给定进程集周期的最小公 倍数的全部周期进程的调度，并根据先前计算的调度策略执行周期性进程。 在运行前调度中，对给定的周期可离线地计算多个可选调度，而每个调度都对应于不同的 操作“模式”。一个小的运行时间调度器可在对应于外部或内部事件的可选调度中进行选 择，而小的运行时间调度器也可用来为数目较少，且时限极短的异步进程分配资源。 如果预先了解两个连续请求之间的最短时间，那么就可将异步进程转化为等价的周期性进 程。因此，也可以采用运行前调度方法调度异步进程。 运行前调度与优先级调度的比较 下面将简要说明优先级调度方法的缺点。可以看到无论是速率单调调度还是优先级最高限 度协议，优先级调度都无法为某类问题提供可行的解决方案，而采用运行前调度的最优算 法则可以解决。这些缺点直接源于固定优先级调度方法中固有的基本假定，而不仅仅是基 于该调度方法的某个特定运算或公式的特性。因此，这些缺点并不能通过某些设计巧妙的 快速修复(quick fix)技术加以弥补。 1. 优先级调度方法难以处理复杂的应用约束问题 文章给出的可调度性分析假定所有的任务都是独立的，即任务之间不存在优先关系，并且 释放时间等于周期的起始时间。我们很难延伸优先级调度方法的可调度性分析，来考虑那 些通常在实时应用中存在的应用约束，如优先约束、释放时间不等于周期的起始时间、低 抖动要求等。主要由于以下两个原因： (a)附加的应用约束很可能与分配给进程的优先级相冲突，一般不可能将大型复杂系统中不 同应用约束所需的诸多不同进程执行序列映射到严格的优先级层次。 对具有进程优先级的附加应用约束进行调整将产生一些细微的误差。例如，有作者建议采 用进程优先级增强优先约束，但优先约束所需的优先级设定可能同其它标准(如进程的周期 长度)规定的优先级相冲突。即便不存在任何冲突，仅采用优先级也不足以控制进程的执行 顺序。假定进程A的优先级高于进程B，如果B比A先到达并要求先执行，且B是当时唯一要求 执行的进程，那么尽管A的优先级比B高，B也将先于A执行。 相反，在运行前调度方法中，调度在运行前进行运算，因而能相对容易地考虑到诸多附加 约束，如任意释放时间、时限和优先约束等。此外，还可通过直接规定进程分段对的优先 关系和排斥关系，以避免采用复杂的运行同步机制实现进程同步，并防止同时对共享资源 的访问。例如，A的优先级高于B就可通过在运行前调度中，将A排在B之前，以保证A 总是 在B之前执行。 (b)附加的应用约束增加了调度问题的运算复杂度，而一旦进程包含临界区，调度运算本身 已经很复杂了。对于那些具有很高运算复杂度的问题，调度器需要相当长的时间才能找到 良好的解决方案。对于优先级调度方法，调度在进程运行中执行，因而调度器缺乏必要的 时间以找到良好的解决方案。 相反，运行前调度是离线运算，调度算法的时间效率并不是关心的关键内容，因此设计工 程师可以任意选用最优的调度算法或其它算法，这在大多数情形下可以更好地满足所有的 时序和资源约束。 由于固定优先级调度模式本身存在的约束(如固定优先级)，并且由于调度在运行时执行， 因此考虑附加约束往往导致固定优先级调度只适用于一些非常特殊的情形，或者需要作出 极为简化的假设，这些工作或者本身极为复杂，或者将显著降低系统的可调度性，从而导 致难以分析和预测系统的执行时性能。 2.一般而言，优先级调度方法的处理器利用率低于运行前调度方法 2.1.基于优先级的调度策略是一种直观推断算法，与最优的运行前调度算法相比，更难以 找到可行的调度。 (a)即便所有的进程都完全可占先(在大型复杂的硬实时系统中，这种情形不大可能出现)， 基于优先级的进程调度也不是最优的。例1中，速率单调调度算法不能完全满足两个可占先 进程A和B的时限，但这两个进程可以通过采用调度完全可占先进程的最优算法，如最早时 限优先算法进行成功调度。 例1．进程A：释放时间rA = 0；运算时间cA = 3；时限dA = 6；周期prdA = 6；优先级A = 0。进程B：释放时间rB = 0；运算时间cB = 4；时限dB = 8；周期 prdB = 8；优先级B = 1。 速率单调调度算法生成的调度：B 错过了首个时限。 最优算法(如EDF)生成的调度：满足所有的时限。 | A | B | A |B | A |B | A | B | 0 3 7 10 12 15 18 21 24 | A | B | A |B | A |B | A | B | 0 3 7 10 12 15 18 21 24 (b)如果某些进程不可占先，基于优先级的调度进程将更难满足时限。例如，在下面的情形 下，为满足所有给定的时序约束，即便已存在可执行进程，也必须使处理器处于空闲状态 。如下例所示： 例2．进程A：释放时间rA = 0；运算时间 cA = 10；时限dA = 12。进程B：释放时间rB = 1；运算时间cB = 1；时限dB = 2。不允许B占先A。 优先级调度算法可生成如下调度，其中B错过了时限： | A |B| 0 10 11 | A |B| 0 10 11 相反，采用最优算法就能找到满足所有进程时限的可行调度： |B| A | 1 2 12 |B| A | 1 2 12 时序约束要求处理器在时间0和1之间必须处于空闲状态，即使进程A的释放时间为0。因为 一旦A开始执行，必将导致B错过时限。 在大多数实际应用中，会出现因其它进程已进入临界区而不能占先进程分段的情况。因此 ，该示例实际上给出了一个很普遍的情形，但基于优先级的策略并不能正确地处理此类情 形。 优先级调度方法较难满足时序约束，因为基于优先级的方案只能为给定的进程集产生非常 有限的可能调度子集，这严重地限制了优先级驱动策略在运行时满足时序和资源共享约束 的能力。 通常，调度算法生成的调度集越小，找到可行调度的机会就越小，且算法所能实现的处理 器利用率水平也就越低。例如，对于例2中给出的进程集，若坚持采用优先级驱动策略，就 需要将处理器容量提高为原来的(cA+ cB)/(1+cB) = 11/2倍，并且所实现的处理器利用率 远低于在例2中生成有效调度的最优调度方案。通过采用离线计算调度的最优算法，可实现 比采用基于优先级方案更高的资源利用率。因此，采用基于优先级的方案将增加系统成本 ，从而失去竞争优势。 实际上，从上述示例中可以注意到：任意优先级调度算法与最优算法的处理器利用率之比 可任意降低，如在例2中，通过增加A的运算时间，并将A的时限设定为cA+2，同时保持其它 参数不变，即可任意降低处理器利用率。 2.2 在运行中进行进程调度时，必须避免死锁。在运行时避免死锁通常要求运行时的同步 机制保持恒定，并当运行同步机制阻塞进程时，进程仍能继续执行而不产生死锁。如果再 结合优先级的使用，处理器利用率将进一步降低。例3显示了优先级最高限度协议阻碍进程 执行并导致进程错过时限的实例，尽管进程仍能继续执行并满足时限而不产生死锁。 例3. 进程A：在t1时刻就绪，整个进程是受旗语s0监控的临界区；运算时间cA = t2 - t1 ；优先级A = 0。进程B：在t3时刻 就绪，整个进程是受旗语s1监控的临界区；运算时间c B = t5 - t4；时限为t3 + cB；优先级B = 1；进程C：在t2时刻就绪，整个进程是受旗语 s0监控的临界区；运算时间cC = t4 - t2；时限为t5；优先级C = 2。 s0 的优先级最高限 度为0； s1 的优先级最高限度为 1。 根据优先级最高限度协议，由于进程A和进程C均使用受同一旗语s0监控的临界区。因此， 当进程C于t2时刻进入临界区时，它将以优先级0执行，在t3时阻碍进程B，从而导致进程B 错过时限： |A | C |B | t1 t2 t3 t4 t5 |A | C |B | t1 t2 t3 t4 t5 但是进程B可以通过占先进程C来满足时限，并且不会导致死锁： |A |C | B | C | t1 t2 t3 t5 |A |C | B | C | t1 t2 t3 t5 上述实例中，为避免在运行时调度进程引发死锁，需要采用极端保守的策略：即要求进程 以相同的旗语监控临界区的任意进程的最高优先级执行临界区。 相反，如果采用运行前调度方法，调度将能离线建立，因此调度算法可考虑能构造无死锁 调度的所有可行方法。 这里应该注意到，任何优先级调度算法与最优算法的处理器利用率之比可以任意降低，如 例3中可通过增大cC将处理器利用率降至任意低。 2.3.采用优先级调度方法时，由于调度在运行时建立，因而需要耗费大量的系统资源，即 在实时应用之外所消耗的时间大大超过了采用运行前调度方法所需的时间。 (a)优先级调度器需要占用运行时资源进行调度运算，即计算何时执行何进程。而在运行前 调度方法中，通常预先确定调度。 (b)由于优先级调度器在运行前并不知道调度，因此需要假定最坏情形，并在每次被另一进 程占先时保存/恢复完整的当前信息。在运行前调度方法中，调度在运行前确定，因而可以 预先确定需要保存或恢复的最少信息，从而显著地降低了现场切换所需的时间。 (c)为了实现不同的进程管理功能，如挂起和激活进程、操作进程队列等，优先级调度器还 需占用大量运行时的资源。相反，在运行前调度方法中，由于预先规定了调度，因而可实 现自动代码优化，即通过采用非常简单的机制(如程序调用)或在无需保存和恢复当前信息 的情况下简单地连接代码，将处理器执行从一个进程切换至另一进程，从而极大地降低系 统的开销。 如果进程周期相对比较重要，那么进程周期的最小公倍数(LCM)和运行前调度的长度将会变 得相当冗长。然而在实际中，设计工程师往往可以灵活地调整周期长度以得到满意的进程 周期LCM长度。尽管这可能导致处理器利用率降低，但与采用优先级调度导致的处理器利用 率降低相比，完全可以忽略不计。 在优先级调度方法中，若存在许多不同的进程周期，则通常需要设定许多优先等级，这无 疑极大地增加了执行时调度开销。如果通过为不同周期的进程子集分配相同的优先级以减 少优先级的等级数目，那么将延长进程的响应时间，并进一步降低可调度性及处理器利用 率。 3.与运行前调度方法相比，优先级调度方法的系统运行特性更难进行分析和预测 为实现进程同步并防止多个进程同时访问共享资源，优先级调度方法要求采用复杂的运行 机制，然而精确分析和预测调度器的执行特性将非常困难。例如，在一项利用优先级队列 实现固定优先级调度的研究中，由定时器中断定期释放的调度器将使任务在队列之间进行 切换。研究表明，由于时钟中断处理程序的优先级高于任何应用任务，因此当较低优先级 的任务从一个队列切换至另一队列时，即使是高优先级的任务也可能经历较长的延迟。尽 管预先假定系统只含有20项任务且任务不含临界区，而且优先级也不会发生改变，但在这 样的情形下精确预测调度器的开销仍然是一项异常复杂的工作，而调度器开销的预测也相 当重要。 相反，在运行前调度方法中，调度在运行前进行计算。因此，可以通过直接定义进程分段 对的优先关系和排斥关系以避免使用复杂的运行同步机制，从而实现进程同步并防止多个 进程同时访问共享资源。如上所述，可以通过非常简单的机制(如程序调用)或在无需保存 或恢复当前信息的情形下只通过连接代码，使处理器执行从一个进程切换至另一进程，这 样不但大大降低了系统的运行时开销，还能更容易地分析和预测系统执行时的特性。与采 用运行时同步机制所需的复杂可调度性分析相比，离线运算调度可以直接检验所有满足时 限要求的进程。 据报道，在1997年7月实施的“火星登陆”任务中，飞行器经历了多次系统重启，并导致数 据丢失。据称，当采用优先级调度的VxWorks 实时系统内核中的固有优先级机制关闭时， “优先级倒置”就将引发上述问题。报道指出，如果在火星登陆任务中采用运行前调度器 ，就能避免这些问题。 4.与运行前调度方法相比，优先级调度方法针对变化的应用需求进行系统设计和修改的灵 活性较小。 与运行前调度方法相比，优先级调度方法灵活度较小，因为进程分配的严格优先级限制了 进程的执行顺序。而采用运行前调度方法则不存在上述约束，因此设计工程师在软件开发 的任何阶段都可以实现从任意运行前调度到任何其它运行前调度的切换。 (a)人们通常认为优先级调度方法比其它方法具有更优越的稳定性，因为对于重要的进程可 以分配高优先级以在瞬间系统过载情况下满足时限要求。速率单调调度方法为周期较短的 进程分配较高的优先级，因为实践表明，如果周期较长的进程分配更高优先级，那么将严 重降低整个系统的可调度性。然而，重要的进程并不一定具有较短的周期，因此一些设计 工程师建议将重要的进程分割成多个具有较短周期的进程，但这不仅增加了运行时的开销 ，还将引发新的人为约束，从而增加了整个系统的复杂度并导致可调度性下降。实时应用 中，在不同的情况下可能需要采用不同的进程执行顺序，并且有时不同的进程集将成为必 要进程。这些问题不能简单地通过对进程分配严格的优先级来解决。 运行前调度方法需要保证重要进程至少应与优先级调度方法相当，或更好。当采用运行前 调度方法时，一旦系统出现过载，将会执行另一替代运行前调度，该调度只包含特定条件 下的必要进程集。由于在运行前就能详细设计运行前调度，因此设计工程师可灵活地考虑 许多可能出现的不同过载情况，并根据不同的实际情况采取不同的调度策略。 (b)下面给出了一个有关优先级调度方法“灵活度”的实例，即只基于任务集整体处理器利 用率信息的优先级调度方法可以进行可调度性分析。这种方法可提供更大的灵活性，因为 由增加额外任务而引发的系统可调度性决策只要求对总的可调度性范围进行重新计算，并 决策由新增功能所引发的新利用率问题是否会产生新的超越范围问题。 在基于可调度性分析的处理器利用率问题中，往往忽略了这样一个事实，即这样的分析可 能导致系统设计工程师对系统容量的利用不充分。基于分析的处理器利用率总是显得不尽 如人意，因为这种方法只给出了可调度性的充分条件，而不是必要条件。换言之，如果设 计工程师希望得到可靠的可调度性分析，就不能采用固定优先级调度算法，并且需要采取 措施进一步降低处理器利用率，以满足由可调度性分析提供的处理器利用率条件，即使是 在初始条件下，利用固定优先级调度算法对处理器进行调度这样的最简单情形中。 例4.假定系统由20个进程p1、p2...、p20组成，每个进程的执行时间为1，周期为28。 速率单调调度的可调度性分析并不能保证该进程集可调度，因为处理器的总利用率为20× (1/28) = 0.71，大于可调度性分析所需的处理器利用率上限20×(21/20 - 1)。 例4中，因为可调度性分析不能保证进程集可被调度，因此这些进程将被丢弃，尽管速率单 调调度算法实际上完全可以满足这些进程的时限要求： |p1 |p2 | ... |p20 | | ... | | 0 1 2 19 20 21 27 28 |p1 |p2 | ... |p20 | | ... | | 0 1 2 19 20 21 27 28 需要指出的是，当所有的进程完全可占先时，基于优先级最高限度协议可调度性分析的处 理器利用率将完全等同于速率单调调度。因此，该实例也完全适用于优先级最高限度协议 。 与基于可调度性分析的处理器利用率相比，静态优先级调度最坏情形下的响应时间可调度 性分析可提供更为宽松的条件。然而，静态优先级调度最坏情形下的响应时间可调度性分 析与基于可调度性分析的处理器利用率具有相同的基本缺点，即只给出可调度性的充分条 件，而没有给出必要条件。尽管静态优先级调度的最坏情形下响应时间可调度性分析能够 保证例4中极简单进程集的可调度性，但将舍弃在更早给出的示例中的那些不可调度进程集 ，即使采用运行前调度方法可以调度这些进程集。 研究表明，运行前调度方法处理异步进程的能力不如优先级调度方法。在Lock的文章[Loc k92]中，为了说明循环执行(这是预执行调度方法中一种极为严格的形式)的难度，作者采 用了循环执行方法处理上述相同的问题，但并未举例说明固定优先级执行如何解决相同的 调度示例问题，而实际上固定优先级执行将面临相同，甚至更大的困难。在另一篇文章[A uTB93]中，作者试图表明优先级调度方法也能解决[XuPa90]给出的示例问题，但示例问题 的参数有所不同。如果采用本文给出的原始参数，那么该文章提出的解决方案就完全无能 为力。 下面将给出一个反向成立的实例。该实例表明，采用运行前调度方法时，所有的周期性进 程的运行前调度一旦确定，执行时调度器就可利用这些信息，通过更有效地调度异步进程 实现更高的可调度性。例如，完全可以通过具有较长时限的异步进程避免具有较短时限的 周期性进程出现阻塞。 例5.异步进程A：运算时间cA = 3；时限dA = 15；两个连续请求间的最短时间minA = 15。 进程B：释放时间rB = 0；运算时间cB = 3；时限dB = 3；周期prdB = 8；B不允许占先A。 优先级调度方案不能保证进程A和B总能满足时限。下面给出的示例表明：无论采用何种优 先级调度策略，进程B都将错过时限。 假定进程A于时间7到达，A的优先级调度方案使A在时间7立即执行，因此，A将阻塞B的第二 个实例(instance)并导致B错过时限。 | B | | A | B | 0 3 7 10 13 | B | | A | B | 0 3 7 10 13 当采用优先级调度策略时，无论可调度性分析是基于整个处理器利用率还是基于最坏情形 下的响应时间，可调度性分析都将A和B视为不可调度进程并舍弃。相反，在运行前调度方 法中则至少存在两种有效方法来调度上述进程。 (a)将异步进程A转换为新的周期性进程newA：释放时间rnewA = 0；运算时间cnewA = 3； 时限dnewA = 8；周期prdnewA = 8。然后，采用[XuPa90]给出的算法建立下述运行前调度 ，其中周期性进程newA以类似于轮询的方式模拟异步进程A，从而保证A 和B都不会错过时 限。 | B | newA | | 0 3 6 8 | B | newA | | 0 3 6 8 (b)另一可行的解决方案是采用[XuLa98]提出的方法，即采用[XuPa90]的算法为所有的周期 性进程建立运行前调度。本例中，将为进程B建立如下运行前调度： | B | | 0 3 8 | B | | 0 3 8 在该方法中，运行时间调度器可利用运行前调度的信息对异步进程进行调度。这种情况下 ，进程A可通过如下方式进行调度：在任何时间t，一旦进程A能立即执行，必然导致进程B 错过时限，即一旦运行前调度中为进程B保留的时隙的最末时刻减t小于进程A和B的运算时 间之和；或者一旦周期性进程的时限小于或等于进程A的时限(本例中指当前正在执行的进 程B)，进程A将被延迟，直到进程B执行完毕。通过利用运行前调度的信息，设计工程师应 当能够为包含时间间隔[3, 5]的异步进程A构造“安全起始时间间隔”表，并且在运行时对 于预执行调度的每个实例，只要允许A在安全起始时间间隔[3, 5]以内开始执行，就能保证 进程A和B均满足时限。利用运行前调度的信息，还能在运行前计算出异步进程在最坏情形 下的响应时间。在本例中，当A于时间6到达时，这时给出的是A在最坏情形下的响应时间， 于是进程A将延迟直到进程B执行完毕，即进程A于时间14执行完毕。因此，进程A的最坏情 形响应时间为14-6＝8，小于初始的时限dA = 15。如果在运行前调度中，进程B总是在保留 的时隙内执行，那么就能保证进程A和B总能满足时限。 在上述示例中，异步进程子集的运行时间调度集成了周期性进程的运行前调度策略，如果 将类似(b)的方法的潜在执行时间开销与在运行时调度所有任务的优先级调度机制的开销相 比，将会发现： (1)如果采用集成方法，异步进程调度器需要处理的进程数非常少，因为在大多数实时系统 中，大量的运算由周期性进程执行，而具有硬时限(hard deadline)的异步进程数一般非常 少。 此外，采用该方法时，大部分异步进程可以转换为周期性进程。设计工程师可根据每种方 法所需的处理器保留容量确定哪些异步进程应当转换为新的周期性进程，而哪些进程仍保 留为异步进程。 (2)异步进程调度器中用于调度决策的绝大部分参数在运行前都是确定的，因而设计工程师 可以预先计算那些用作决策的绝大部分条件，这样就可将运行时进程调度所需的运算量降 至最低。与例5(b)类似，在许多情况下，应当能在运行前为每个异步进程构造“安全起始 时间间隔”表，这样异步进程就可以通过简单的表查询进行调度，从而大大降低系统的运 行时间开销。 (3)大多数重要的调度决策在运行前就已做出。实际上，当进行运行前调度运算时，在大多 数实时应用中占用大量运算的周期性进程的相对顺序在进程执行之前就已确定。 采用运行前调度方法的实时系统设计工程师可以自由选择任意的最优算法构造包含新进程 的新运行前调度，并为系统增添新的功能。此外，系统的在线修正也并不复杂，设计工程 师可轻松地在运行前调度中插入代码，这样当进程被外部信号激活时，处理器执行就能在 执行过程中由先前设计的运行前调度转向新设计的运行前调度。系统设计工程师也无需采 用严格的进程优先级，这样在设计新的运行前调度中就具有更大的灵活性，以满足不断变 化的需求。 综上所述，在优先级调度方法中，设计工程师除了可以设置优先级以外，在满足应用要求 方面几乎没有任何其它选择。因此在优先级调度方法中，优先级可以重载。设计专家建议 ，具有如下特征的进程应分配较高的优先级： a.较短的周期； b.较高的重要性； c.较低的抖动要求； d.优先限制，等。 因此，利用严格的优先级以期同时满足各种不同的应用约束，对于系统设计工程师而言， 这几乎就是不可能的任务。 本文总结 本文解释并举例说明了以下事实： 1. 与运行前调度方法相比，优先级调度方法具有以下缺点： a. 无法有效地处理复杂的应用约束； b. 处理器利用率较低； c. 系统开销较大； d. 很难分析和预测系统的执行时特性。 2. 相反，采用运行前调度方法具有以下优势： a. 更容易保证所有的时限约束及其它约束得到满足； b. 设计工程师可以采用那些考虑了各种应用约束的更优算法，并有利于得到可行的调度方 案； c. 大大降低了调度和现场切换所需的运行时间开销。 3. 形成这些差异的主要原因是： a. 当采用优先级调度方法时，进程的执行顺序受制于严格的优先级约束，因此优先级策略 只适用于生成非常有限的可行调度子集； b. 当采用运行前调度方法时，可以离线计算调度，而优先级调度方法则是在线计算调度。 如果一些异步进程满足如下条件：(a)具有较长的执行间隔，(b)具有较短的时限和运算时 间，或(c)具有比大多数周期性进程更长的时限，则可以综合两种调度方法并采用较小的运 行时间调度器进行调度。尽管运行前调度方法在很多方面比优先级调度方法更具优势，但 在一些情形中“纯粹的”运行前调度并不适用，因为极少被调用的异步进程的时限非常短 。在这些情况下，将异步进程转换为周期性进程可能需要极大的处理器容量。优先级最高 限度协议中用于防止“优先级倒置”和死锁的策略也适用于调度任何不能转换为周期性进 程的进程。运行时间调度应当集成运行前调度，从而充分利用已知的进程特性。已知的这 些特性可用来确定哪些异步进程在运行时调度，哪些进程可以系统地为异步进程保留处理 器容量，从而使这些进程在必要时中断其它进程以满足时限要求。 参考文献 [AuTB93] N. Audsley, K. Tindell and A. Burns, ``The end of the line for static cyclic scheduling,'' Proc. Fifth Euromicro Workshop on Real-Time Systems, 36- 41, 1993. [Lock92]C. D. Locke, ``Software architecture for hard real-time applications: cyclic executives vs. fixed priority executives,'' Journal of Real-Time System s, 4, 37--53, 1992. [XuLa98] J. Xu and Kam-yiu Lam, ``Integrating run-time scheduling and pre-run- time scheduling of real-time processes.'' Proc. 23rd IFAC/IFIP Workshop on Rea l-Time Programming, Shantou, China, June 1998. [XuPa90] J. Xu and D. L. Parnas, ``Scheduling processes with release times, de adlines, precedence, and exclusion relations,'' IEEE Trans. on Software Engine ering, vol. 16, 360-369, Mar. 1990. Reprinted in "Advances in Real-Time System s," edited by J. A. Stankovic, and K. Ramamrithan, IEEE Computer Society Press , 140-149, 1993. Also reprinted in Software Fundamentals: Collected Papers by David L. Parnas, edited by Daniel M. Hoffman, and David M. Weiss, Addison-Wesl ey, 439-465, 2001. -- ※ 来源:．南京大学小百合站 http://bbs.nju.edu.cn[FROM: 61.144.207.46]