RM和EDF算法原论文翻译.docx

RM和EDF硬实时环境下多线程的调度算法摘要：单处理器的多线程调度问题的研究范围已经从它本身的特征拓展到程序运行的可靠性。研究表明最佳固定优先级调度在大型任务序列集的情况下的最大调度利用率仅为70%。此外，根据当前任务序列截止期动态分配优先级可以使调度率利用率等于1。本文还讨论了将两种调度方法结合起来的算法。1 引言近年来，运用计算机来控制和监测工业生产过程已得到广泛应用和不断扩展，并且在未来很可能得到更大的拓展。此类应用的多数情况下，计算机由一定数目的时限监控程序和一批非时限任务流所共用。然而，在其他的应用中，非时限作业不存在且计算机的有效利用只能通过谨慎调度时限监测程序来达到。后者被称为“纯过程控制”且为本文呈现的组合调度分析提供了理论背景。本文研究了此类程序设计中的两种调度算法，这两种均为可抢断优先级驱动算法，这意味着正在处理的任务可被任何高优先级任务中断。第一个算法用一个固定优先级分配能使处理器利用率到达约70%甚至更大。第二个算法通过动态分配优先级可以达到处理器的全利用。此外，本文还讨论了两个算法的结合。2 背景一个程序控制计算机执行一个或更多的监控程序。追踪航天器运行轨迹的天线尖端就是此类监控程序的一个例子。每个程序与一系列任务序列集相联且共同被执行。此类任务中的一些任务是为了响应计算机监控的设备所发生的事件。这些任务不能先于事件执行。每个任务都必须在事件按要求释放后的固定时间内执行完毕。在此时间段内的服务都需确保稳定性。将运行环境分类为“硬实时”1是为了在可接受的响应时间统计分布上与“软实时”相对应。多数现有多程序设计文献是针对商业分时系统的统计数据分析（文献2包含了详细的参考书目）。也有文献针对更有意思的方面，比如调度批量处理设备或是混合批量分时设备，这些调度通常是在如文献3-8中多处理器配置环境下。仅有少数论文直接讨论如何攻克“硬实时”程序设计的难关。Manacher1提出了硬实时环境下的任务的调度的算法，但它的结果受到一个不现实情况的限制，比如对所有任务只有一个请求时间，即便将多截止时间考虑在内。Lampson9概括性的讨论了软件调度问题并且提出了一套ALGOL多程序设计步骤，这些步骤可以通过软件执行或是设计成用于特殊目的的调度器。对于资源的配置、优先级分配及时序，他提出了一个计算估计的响应时间的程序，此程序是基于针对需要可靠性保证的程序所提供的时间信息。然而，它并没有描述这个程序所必须使用的算法。Martin10的文章描述了“实时”系统的范围且有条理的讨论了编程过程中遇到的难题。Martin提出在实时软件研发期间必须保持严格的工程管理控制，他的这一论述得到了Jarauch11的自动结账软件系统论文的强烈回应。这些研讨旨在强调软件设计中运用更为系统的方法的重要性。3 环境为了得到硬实时环境下程序运行的分析结果，必须对运行环境作出一些假设。并不是所有的这些假设都是绝对必要的，在后面的章节中会讨论放宽假设条件后的影响。(A1) 存在硬截止期的所有任务的请求是周期性的，且请求可被经常的中断。(A2) 截止期仅由运行能力的限制组成，也就是说，每个任务必须在下一个请求发生前完成。(A3) 请求中的任务是互相独立的，某个任务不依赖于这个请求中其他任务是否初始化或已经完成。(A4) 每个任务的运行时间不变且不随时间变化。运行时间是指处理器无中断地执行任务所需要的时间。(A5) 系统中的所有非周期任务都是特殊的，它们是初始和故障恢复程序，它们可以在自身运行时取代周期性任务，并且没有硬、关键截止期。假设(A1)与Martin12形成对比，但显得对纯过程控制更加有效。假设(A2)消除了单个任务的排队问题。对于假设(A2)而言，每个外设功能必须拥有少量但可能至关重要的缓冲硬件。任何计算机内部结束的控制跳转都必须允许至少一个单元的采样延迟。注意到假设(A3)并不排除任务的出现只能遵循任务的出现次数，此数为固定的，即为。这种情况可以通过选择任务和的周期来建模，以便使的周期是的倍，并且次请求会与1次请求一致等等。假设(A4)的运行时间作为最大任务处理时间且可以被中断。通过这种方法，请求继承者所需的时间和抢占代价也能被考虑在内。因为有大容量的主存，而且主存和辅助存储设备之间的数据传输相互重叠，程序在现代计算机系统环境下运行，因此假设(A4)是一个很好的近似，即使它并不确切。这些假设使得一个任务的完成特征有以下两个指标：它的请求周期和它的运行时间。除非另有说明，在本文中我们用来表示个周期任务，且它们的请求周期是，运行时间各为。任务的请求速率是其请求时间的倒数。一个调度算法是一套决定在特定时刻所执行的任务的规则。本文研究的调度算法是优先级驱动的可抢断算法。也就是说，任何时刻，具有最高优先级别的任务总是最先得到执行。如果当前有其他的较低优先级任务正在执行，则该较低优先级任务被抢占，让位给具有最高优先级的任务执行，直至就需队列中没有高于该任务优先级的任务时，该任务恢复执行。如此一来，此算法等价于分配任务优先级的方法。若分配给任务的优先级是不变的，我们称之为“静态”调度算法。静态调度算法又称“固定”优先级调度算法。若分配给任务的优先级可能随请求的不同而不同，我们称之为“动态”调度算法。如果某些任务优先级是固定的而其余是变动的，则该算法称为“混合调度算法”。4 固定优先级调度算法图1 在的请求之间执行本节我们得到一个优先级分配规则，该规则源于静态调度算法。决定该规则的一个很重要的方面是一个任务的“关键时刻”。一个任务请求的截止期定义为同一任务的下一次请求的时间间隔。根据一些调度算法，对于任务序列集的调度，若是一个未完成请求的截止时刻，则我们说时刻发生了溢出。对于给定的任务序列集，一个调度算法是可行的当所有任务都能调度完毕且未发生溢出。我们定义任务请求的响应时间为请求发出时刻与响应该请求结束时刻之间的时间段。任务的“关键时刻”是指在该时刻的任务请求有最长的响应时间。任务的“关键时间域”是指关键时刻和响应任务请求结束时刻之间的时间间隔。我们提出如下定理：定理1任务的关键时刻均发生在同时请求它和比其优先级高的任务时。证明 用表示一系列按优先级顺序排列的任务，的优先级最低。若使在时刻对任务发出请求，假定在与之间发出了对任务的再一次请求，而任务的请求发生在时刻，如图1所示。显然，对的抢断会对完成任务造成一定延迟，任务的请求是在时刻发出的，直至任务在时刻之前完成。此外，从图1我们可以直观的看到提前请求时间并不会加速任务的完成。提前请求时间既不会改变也不会延迟任务的完成时间。因此，当与重合时，完成任务的延迟时间最长。对于所有任务，同理可知，故定理得证。图2 两个任务的调度这个结论的价值在于通过简单的计算就可以决定一个给定的任务优先级是否能产生一个可行的调度算法。特别的，如果所有发生在其关键时刻的任务请求都能在它们各自的截止期之前完成，则此调度算法是可行的。例如，任务的请求周期分别为，运行时间为。的优先级高于，从图2(a)中我们可以看出优先级分配是可行的。此外，从图2(b)中可看出的值最大可增至2。另一方面，若使。的优先级高于，如图2(c)所示，则的值都不得超过1。定理1也得到了一个最佳优先级分配算法，我们会在定理2中做阐述。让我们进一步对调度任务的一般结论做扩展。的请求周期分别为，且。若的优先级更高，则根据定理1，必须满足不等式： (1)若得优先级更高，则必须满足不等式： (2)由于：故(1)已包含(2)。也就是说，在的情况下，无论何时，只要的优先级高于，则任务可调度，而当的优先级高于时，任务也能被调度。因此，更一般的来说，优先级分配的一个合理的规则似乎是根据任务的请求速率来分配优先级而不去管它们的运行时间。特别的，任务的请求速率越高，优先级越大。这种优先级分配方法称为“单调速率优先级分配”。结果表明，当不能被RM算法调度的任务序列集同样也不能被其他固定优先级分配规则调度时，RM算法是最优的。定理2 对于一个任务序列集，若存在可行的优先级分配，则对于此任务序列集，RM算法是可行的。证明 为一个包含个任务的序列集，且存在可行的优先级分配算法。和的优先级相邻且的优先级较高。设。交换和的优先级后，不难发现所得到的优先级分配仍是可行的。对于一个已排序的任务序列集，依照上述方法对相邻优先级的一对任务进行重新排序，即可得到RM算法，因此定理2得证。5 可达到的处理器利用率目前，对于固定优先级系统，已有可判定处理器利用率上确界的工具。定义“（处理器）利用率因子”为：执行任务序列集的过程中，处理器耗费时间的间隔。换句话说，利用率因子等价于1减去处理器空余时间的间隔。由于是处理器执行任务的时间间隔，对于个任务，利用率因子为：尽管可通过增大或减小的值来提升处理器利用率，但由于所有任务在其关键时刻必须满足截止期的要求，故利用率的上界受到限制。研究处理器利用率因子的最小值显然是没有乐趣的。若优先级分配是可行的且增大任何任务的运行时间都会使得此优先级分配不可行，则称任务序列集完全利用了处理器。对于一个给定的固定优先级调度算法，利用率因子的上确界为完全利用处理器的任务序列集中利用率因子的最小值。对于所有处理器利用率因子低于这个确界的所有任务，存在一个可行的固定优先级分配算法。另一方面，当且仅当任务的彼此关联适当，才能达到高于这个上确界的利用率。由于RM算法是最优的，对于给定的任务序列集而言，它的利用率因子大于或等于其他优先级分配算法。因此，RM算法利遍及任务所有的请求周期和运行时间的用率因子的下确界即为所要确定的上确界。这个确界起初由两个任务组成，然后扩充为任意数量的任务。定理3 对于固定优先级的两个任务，处理器利用率因子的上确界为。证明 任务和的周期和运行时间分别为和。设。根据RM算法，的优先级高于。在的关键时间域内，有个任务的请求。我们通过调整的值使得在关键时间域内能使处理器得到完全利用。有以下两种情况：情况1 运行时间足够小，使得在的关键时间域内所有的请求都能在下一个请求之前完成。即：因此，的最大值为相应的处理器利用率因子为在此情况下，处理器利用率因子在中单调递减。情况2 个的执行时间与下一个的请求重合。在这种情况下的最大值为相应利用率因子为在这种情况下，在中单调递增。很显然的最小值发生在这两种情况的交界处。即，对于我们有 (3)为了表示方便，我们使，。等式(3)可以写为因为随着单调递增，当为最小值1时，也达到最小值。通过减少来减少，当时，达到其最小值：这就是我们要证明的关系式。注意到，当时，也就是，若低优先级任务的请求周期是其他任务请求周期的倍数时，利用率因子变为1。现在我们得到了任意数量任务的利用率因子范围。我们进一步提出“任意两个请求周期的比值不超过2”的限制条件。定理4 对于固定优先级顺序的个任务，且限定任意两个请求周期的比值不超过2，则处理器利用率因子的上确界为。证明 用表示个任务，为任务的运行时间，这个任务完全利用了处理器且使得处理器利用因子最小。假设，用表示处理器利用率因子。我们希望得到假设令显然，也完全利用了处理器。用表示其相应的处理器利用率因子。得到或者，我们可使令同样，也完全利用了处理器。用表示其相应的处理器率因子。得到因此，若的确是最小的利用率因子，则相似的，能得到因此为了简化书写，令因此且故最终得到 (4)正如两个任务的情况一样，对于所有的而言，若，则利用率能达到1。为了找到利用率因子的上确界，必须使等式(4)中的减小。这可通过根据每个的值都为0设定的第一个导数，和解如下差分方程得到：(5)为了计算简便，令。等式(5)的通解为： (6)由此可得：这就是我们要证明的关系式。当时，等式(6)的利用率边界值与不加请求周期限制条件的两个任务的情况一样。对于，等式(6)变为：增大，可得因此定理4中请求周期的最大比值不超过2的限制条件实际上可免除，我们可以这么规定：定理5 对于固定优先级顺序的任务序列集，处理器的利用率上确界为：证明 用表示可完全利用处理器的个任务，表示相应的利用率因子。假设对于一些，。特别的，令，且。用任务代替，且。通过增大使得处理器能得到完全利用，的最大值为，关键时间域内的时间被而非所占用。令表示此类任务的利用率因子。我们得到或是由于且，。因此我们得到判定处理器的利用率因子的上确界，我们只需考虑任意两个请求周期的比值小于2的任务序列集。这个定理可由定理4直接得出。6 放宽利用范围前面的章节已经说明了实时处理器的任务序列集利用率的上确界可达。由于必须把任务转换之间的实际损耗考虑在内，故我们必须找到方法提升此上确界。是利用率达到1的最简单的方法之一就是对于，使得。由于这个方法不能常常奏效，另一个途径是对任务或其他较低优先级的任务进行缓冲，并且放宽它们的硬截止期。设整个任务序列集有一个有限的周期且能以某些合理的方式执行缓冲的任务，例如，以先到先执行的方式。然后可由本论文所给的下设条件计算出最大延迟时间及需要缓冲的任务数量。一个更好的解决方法是用动态方法分配任务的优先级。本论文的剩余章节会详细阐述一个动态优先级分配算法。若一个任务序列集可被某些优先级分配算法调度，则此任务序列集也能被这个算法调度，且还是最优的。换句话说，采用此动态优先级分配算法，处理器利用率因子的上确界一律为100%。7 截止期驱动调度算法现在我们开始研究一个称为“截止期驱动调度算法”的动态调度算法。这个算法使得服务器根据当前所请求任务序列集的截止期动态分配任务的优先级。截止期最靠前的任务优先级别最高，截止期最远的任务优先级最低。在任意时刻，未执行任务中拥有最高优先级的任务将被执行。与任务优先级不随时间变化的静态分配相比，这种分配任务优先级的方法是动态的。于是我们要建立使得截止期驱动调度算法可行的充分必要条件。图3处理器空闲周期之后发生溢出定理6 当服务器采用截止期驱动调度算法来调度任务时，在溢出之前没有处理器的空闲时间。证明 设处理器的空闲时间在溢出之前。确切的说，以0为时间起点，表示溢出发生的时刻，分别表示最靠近时刻的处理器空闲周期的起点和终点时刻（即在和之间没有处理器空闲时间）。图3表示了这种情况，用表示处理器空闲周期之后的个任务的第一次请求时间。假设从开始我们使任务1的所有请求提前，使得与重合。因为在和之间没有处理器空闲时间，在提前后也并不会有处理器空闲时间。此外，溢出会在或之前发生。对所有其他任务均重复此方法，我们可得到若所有任务都在时刻被初始化，则会有一个在处理器空闲周期之后的溢出发生。然而，这与初始时刻为0且服务器的空闲周期发生在溢出之前的假设矛盾，故定理6得证。定理6将被用来证明如下定理：定理7 对于一个给定的任务序列集，截止期驱动调度算法是可行的当且仅当证明 为了说明必要性，通过计算，在和之间的所有任务所需要的总计算时间为若需要的总时间超过了处理器的有效时间，即 (7)或是则没有可行的调度算法。为了说明充分性，假设当满足时这个调度算法是不可行的，即在和之间有一次溢出。此外，根据定理6，在时刻发生溢出，且处理器在和之间没有空闲时间。用表示在之前的所有个任务的请求时间，且表示截止期为的所有任务的请求时间，表示截止期在之后的所有任务的请求时间。如图4所示。图4 在时刻发生溢出考察两种情况：情况1 在之前未发生时刻的计算请求。在这种情况下，和之间的计算所需总时间为由于没有处理器空闲周期，故同样地，对于所有均有，则且这与式子(7)矛盾。图5 在时刻后未执行任务且在时刻发生溢出情况2 在之前发生了某些时刻的计算请求。由于在时刻发生了溢出，必然存在时刻使得在时刻，处理器发出请求均不在内。换句话说，在范围内，只有截止期在或之前的请求能被执行，如图5所示。此外，至少有一件请求时间为的任务被执行直至，意味着截止期在或之前且在之前发出的所有的任务请求且都会在时刻之前完成。因此，在内的处理器所需总时间小于等于时刻发生溢出意味着这就意味着这与式子(7)矛盾，由此证明了定理7。综上所述，如果一个任务序列集能被任意算法调度，则截止期驱动的调度算法是最优的。8 混合调度算法在这一节我们会研究一类结合RM和截止期驱动的调度算法。我们称此类算法为混合调度算法。混合调度算法缘起于对电脑硬件中断的观察，目前电脑的硬件中断充当了一个固定优先级调度器并且与硬件动态调度器不兼容。在另一方面，如果任务是截止期驱动而非固定优先级分配，则执行慢节奏任务的软件调度器的花费并没有显著提高。具体说来，对于具有最短周期的任务，根据RM算法，这个任务会被优先执行。当处理器未被任务占用时，剩余任务会按照截止期驱动调度算法执行。用表示关于的不减函数。对于所有和，我们说是亚线性的当且仅当处理器对于任务序列集的可用函数是指从0到的累积处理时间。假设用固定优先级算法调度个任务。用表示任务的处理器可用函数。很明显，是的不减函数，此外，根据关键时间域的论点，是亚线性的。因此我们得到：定理8 若处理器的可用函数是亚线性的，且使用截止期驱动调度算法来调度任务序列集，则溢出没有处理器空闲周期。证明 与定理6的证明同理。定理9截止期驱动调度算法为可行的充分必要条件是处理器的可用函数为其中为的所有倍数。证明 该定理证明与定理7类似，首先证明必要性，注意到任何时刻处理器所需总时间不能超过可用的处理器总时间，所以对于所有，我们必须使其次证明充分性，假设满足定理的假设条件且在时刻发生了溢出。观察定理7证明中的两种情况。对于情况1，有这与假设矛盾。注意到为的倍数，对于情况2，有令表示最小的非负数，则存在使得为的倍数。显然故这也与假设矛盾，由此定理9得证。尽管定理9中的结果是一个通解，它的应用涵盖了一系列大量的不等式。在具体案例中，用充分条件来分析调度的可行性比直接使用定理9更有效。例如，我们考虑用混合调度算法调度三个任务，其中周期最短的任务有一个固定的优先级，其余两个用截止期驱动算法调度。，已经证明若则混合调度算法是可行的。同样可证明若则混合调度算法也是可行的。上述证明包含了比较直观但为数众多的控制不等式，详情可查看文献13。遗憾的是，这些充分条件和定理9中的充分必要条件都是针对低处理器利用率的情况。9 比较和评论定理9中的限制条件强有力的表明了混合调度算法的利用率通常达不到100%。我们通过下面一个简单的例子加以证明。令且。由于