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

《RM和EDF算法原论文翻译.docx》由会员分享，可在线阅读，更多相关《RM和EDF算法原论文翻译.docx（16页珍藏版）》请在优知文库上搜索。

1、RM和EDF-硬实时环境下多线程的调度算法摘要：单处理器的多线程调度问题的探讨范围已经从它本身的特征拓展到程序运行的牢靠性。探讨表明最佳固定优先级调度在大盘任务序列集的状况卜.的最大调度利用率仅为70%.此外，依据当前任务序列截止期动态安持优先级可以使调度率利用率等于1。本文还探讨了将两种调度方法结合起来的兑法。1引言近年来，运用计算机来限制和监测工业生产过程已得到广泛应用和不断扩展,并且在将来很可能得到更大的拓展。此类应用的多数状况卜，计经机由肯定数目的时限监控程序和批非时限任分流所共用。然而，在其他的应用中,非时限作业不存在且计算机的有效利用只能通过谭慎调度时限监测程序来达到。后者被称为“

2、纯过程限制”且为本文呈现的组合调度分析供应了理论背景。本文探讨了此类程序设计中的两种调度算法，这两种均为可抢断优先级驱动算法，这意味着正在处理的任务可被任何高优先级任务中断。第一个算法用一个固定优先级安排能使处理器利用率到达约70%甚至更大。其次个算法通过动态安排优先级可以达到处理器的全利用。此外，本文还探讨方两个算法的结合.2背景个程序限制计算机执行个或更多的监控程序。追踪航天器运行轨迹的天线尖端就是此类监控程序的一个例子。每个程序与一系列任务序列集相联且共同被执行。此类任务中的一些任务是为了响应计兑机监控的设备所发牛的事务。这些任务不能先于事务执行。每个任务都必需在事务按耍求择放后的固定时

3、间内执行完毕。在此时间段内的服务都需确保稳定性。将运行环境分类为“硬实时”是为了在可接受的响应时间统计分布上与“软实时”相对应。多数现有多程序设计文献是针对商业分时系统的统计数据分析（文献包含了具体的参考书目）。也有文献针对更有意思的方面，比如调度批量:处理设备或是混合批量分时设备，这些调度通常是在如文献3M8中多处理器配置环境下。仅有少数论文干脆探讨如何攻克“硬实时”程序设计的难关。ManaChCr11提出了硬实时环境卜的任务的调度的算法，但它的结果受到一个不现实状况的限制，比如对全部任务只有一个恳求时间，即便将多截止时间考虑在内。IHnPSOn概括性的探讨了软件调度问题并且提出了一套A1.

4、Go1.多程序设计步骤，这些步骤可以通过软件执行或是设计成用于特殊目的的调度器。对于资源的配置、优先级安排刚好序，他提出了一个计算估计的响应时间的程序，此程序是基于针对须要牢靠性保证的程序所供应的时间信息。然而，它并没有描述这个程序所必需运用的算法“ManinllO)的文章描述了“实时”系统的范用且有条理的探讨了编程过程中遇到的难题。Martin提出在实时软件研发期间必需保持严格的工程管理限制，他的这一论述得到Jarauchllll的白动结账软件系统论文的剧烈回应。这些研讨旨在强谢软件设计中运用更为系统的方法的重要性。3环境为了汨到硬实时环境下程序运行的分析结果，必需对运行环境作出一些假设。并

5、不是全部的这些假设都是肯定必要的，在后面的率节中会探讨放宽假设条件后的影响。(AI)存在硬截止期的全部任务的恳求是周期性的，且恳求可被常常的中断。(A2)截Ih期仅由运行实力的限制组成，也就是说，每个任务必需在下个恳求发生前完成。(A3)恳求中的任务是相互独立的，某个任务不依靠于这个恳求中其他任务是否初始化或己经完成.(A4)每个任务的运行时间不变且不随时间变更。运行时间是指处理器无中断地执行任务所须要的时间。(A5)系统中的全部非周期任务都是特殊的，它们是初始和故障熨原程序，它们可以在自身运行时取代周期性任务，并且没有饿、关键截止期。假设(AI)与MartinI12形成对比，但显得对纯过程限

6、制更加有效。假设(A2)消退了单个任务的排队问题.对于假设(A2)而言，每个外设功能必需拥有少址但可能至关重要的缓冲硬件。任何计算机内部结束的限制跳转都必需允许至少一个单元的采样延迟.留意到假设(A3)并不解除任务r,的出现只能遵循任务r,的出现次数，此数为固定的，即为N,这种状况可以通过选择任务r,和r,.的周期来建模，以便使h的周期是r,的N倍，并且N次r,恳求会与I次r,息求一样等等.假设(A4)的运行时间作为最大任务处理时间且可.以被中断。通过这种方法，恳求继承者所需的时间和抢占代价也能被考虑在内。因为仃大容员的主存，而且主存和协助存储设备之间的数据传输相互全段，程序在现代计算机系统环

7、境下运行，因此假设(A4)是一个很好的近似，即使它并不准确。这些假设使得一个任务的完成特征有以下两个指标：它的恳求周期和它的运行时间。除非另有说明，在本文中我们用KG,J来表示，个周期任务，且它们的恳求周期是小石,。，运行时间各为G，g.,Cw。任务的恳求速率是其恳求时间的倒数。一个调度算法是一套确定在特定时刻所执行的任务的规则。本文探讨的调度算法是优先级卵动的可抢断算法。也就是说，任何时刻,具有最高优先级别的任务总是最先得到执行。假如当前有其他的较低优先级任务正在执行，则该较低优先级任务被抢占，让位给具有最高优先级的任务执行，直至就需队列中没有高于该任务优先级的任务时，该任务笈原执行。如此来

8、，此算法等价于安排任务优先级的方法。若安持给任务的优先级是不变的，我们称之为“静态”调度并法。静态调度算法又称“固定”优先级调度匏法。若安排给任务的优先级可能随恳求的不同而不同，我们称之为“动态”调度算法.假如某些任务优先级是固定的而其余是变动的，则该算法称为“混合调度算法”。4固定优先级调度算法图1在的恳求之间执行r,本节我们得到个优先级安排规则，该规则源于静态调度算法。确定该规则的一个很重要的方面是一个任务的“关键时刻)一个任务恳求的截止期定义为同一任务的卜一次恳求的时间间隔。依据一些调度算法，对于任务序列集的调度,若r是一个未完成恳求的技止时刻，则我们说,时刻发生了溢出对手给定的任务序列

9、集，一个调度算法是可行的当全部任务都能调度完毕且未发牛.溢出。我们定义任务恳求的响应时间为恳求发出时刻与响应当恳求结束时刻之间的时间段。任务的“关键时刻”是指在该时刻的任务恳求有最长的响应时间。任务的“关键时间域”是指关键时刻和响应任务恳求结束时刻之间的时间间隔。我们提出如卜定理：定理1任务的关键时刻均发生在同时恳求它和比其优先级席的任务时。证明用KT2.兀表示一系列按优先级依次排列的任务，噎的优先级域低。若使在1.时刻时任务J发出恳求，假定在乙与乙+7：之间发出/对任务Q的再一次恳求,而任务3，小的恳求发生在时刻GG+tG+27;t2+kTl,如图1所示“明显，r,对J的抢断会对完成任务J造

10、成肯定延迟，任务J的恳求是在乙时刻发出的，直至任务在时刻口之前完成。此外，从图I我们可以直观的看到提前恳求4时间并不会加速任务J的完成.提前恳求时间既不会变更也不公延退任务J的完成时间。因此，当4与乙重合时，完成任务J的延迟时间热长。对丁全部任务r,i=2,.m-1,同理可知，故定理得证。图2两个任务的调度这个结论的价值在于通过荷洁的计算就可以确定一个给定的任务优先级是否能产生一个可行的调度算法.特殊的，假如全部发生在其关键时刻的任务恳求都能在它们各自的截止期之前完成，则此调度算法是可行的。例如，任务不7的恳求周期分别为7；=2.4=5,运行时间为G=1.G=1。G的优先级高于G,从图2（八）

11、中我们可以看出优先级安排是可行的。此外，从图2(b)中可看出C：的值最大可增至2。另方面,若使，J的优先级高于勺，如图2(c)所示，则C.G的值都不得超过1。定理1也得到了一个最佳优先级安排算法，我们会在定理2中做阐述。让我们进一步时调度任务小马的一般结论做扩展”小巧的恳求周期分别为TJ.,且l1,若“的优先级更高，则依据定理1,必需满遨不等式：T2TlCl+C2T1(1)若得优先级更高，则必需满意不等式：C1+G7；(2)由于：iT2TiCl+TiTtC2T2TlTlT2故(I)已包含(2)。也就是说，在7；京的状况下，无论何时，只要门的优先级高于天，则任务可调度，而当r,的优先级高于G时.

12、，任务也能被遍度。因此,更一般的来说，优先级安排的一个合理的规则好像是依据任务的恳求速率来安排优先级而不去管它们的运行时间。特殊的,任务的恳求速率越高，优先缎越大。这种优先级安打方法称为“单调速率优先级安排二结果表明，当不能被RM算法调度的任务序列集同样也不能被其他固定优先级安排规则调度时，RM算.法是最优的。定理2对于一个任务序列集，若存在可行的优先级安排，则对于此任务序列集，RM算法是可行的。证明弓.q.J为个包含1个任务的序列集Il存在可行的优先级安排算法。,和r,的优先级相邻旦石的优先级较高。设交换r,和r,的优先级后，不难发觉所得到的优先级安排仍是可行的.对一个已排序的任务序列集，依

13、照上述方法对相邻优先级的一对任务进行重新排序，即可.得到RM算法，因此定理2得证。5可达到的处理器利用率目前，对于固定优先级系统，已有可判定处理器利用率上确界的工具。定义“(处理器)利用率因子”为：执行任务序列集的过程中，处理器耗费时间的问陶.换句话说，利用率因子等价于1减去处理淞空余时间的间隔。由丁cj;是处理四执行任务q的时间间隔，对于，个任务，利用率因子为：u=(C,l)尽管可通过增大C或诚小7；的值来提升处理器利用率，但由于全部任务在其关键时刻必需满意截止期的要求，故利用率的上界受到限制。探讨处理器利用率因子的最小值明显是没有乐趣的“若优先级安排是可行的且增大任何任务的运行时间都会使得

14、此优先级安排不行行，则称任务序列集完全利用了处理器。对于个给定的固定优先被调度算法，利用率因子的上确界为完全利用处理器的任务序列集中利用率因子的最小值.对于全部处理器利用率因子低丁这个确界的全部任务，存在一个可行的固定优先级安排算法。另一方面，当且仅当任务的彼此关联适当，才能达到高于这个上确界的利用率。由于RM党法是最优的，对于给定的任务序列集而言，它的利用率因子大于或等于其他优先级安排算法。因此，RM和法利港及任务全部的恳求周期和运行时间的用率因子的下确界即为所要确定的上确界.这个确界起初由两个任务组成,然后扩充为陶.隹数量的任务。定理3对于固定优先级的两个任务，处理器利用率因子的上确界为I

15、(=2(2-l).证明任务r和口的周期和运行时间分别为7；再和C,.G。设4工。依据RM兑法，A的优先级而于口.在口的关键时间域内，有77个任务的恳求。我们通过调整g的值使得在关键时间域内能使处理器得到完全利用。有以下两种状况：状况I运行时间Cl足够小，使得在的关键时间域内全部外的恳求都能在下个G恩求之前完成。即：CiT2-TlT2Tt.因此，G的最大值为c2=2-ci2i-.相应的处理器利用率因子为u=+G(;)-(IR)I7711.在此状况卜.，处理涔利用率因子U在G中单调递减。状况2冕/工1个G的执行时间与下一个2的恳求重合。在这种状况Fcl2-l2l.G的最大值为G=-GE7J+7JW7J.相应利用率因子为U=(T2ITt)TjTt+Ct(Tt)-(T1)T2IT.在这种状况下，U在C,中单调递增。很明显U的最小值发生在这两种状况的交界处“即，对手C1=7；-7；7；/7；J.我们有U=1-(7；/?;)i7Jl-(;)(7J)-1./7；.为了表示便利，我们使=77J.f=TJTla等式(3)可以写为t=-(i-)(+n.因为U随着单调递增，当/为最小值1时，U也达到最小值.通过削减了来削减U,当/=