在线调度算法中的积极的在线截止日期安排

--理论计算机科学电子笔记91（2004）148-157www.elsevier.com/locate/entcs积极的在线截止日期安排林德华1，2香港大学计算机科学系香港颜纯云3莱斯大学美国德克萨斯州休斯顿杜家强2 及黄慧霞女士2香港大学计算机科学系香港摘要本文研究了单机上带截止期工件调度的在线算法。长期以来人们已经知道，除非系统欠载，否则没有在线调度算法可以是1-竞争的，即，匹配最优的最优化算法的性能。然而，最近的研究表明，一些使用适度更快处理器（或额外处理器）的在线算法可以显着提高竞争力[10]，甚至是1-竞争力[16，12]。本文进一步研究了具有更高性能保证的在线调度算法（即，优于1-竞争力的算法），特别是，提出了一个额外的资源分析的最早期限优先战略（EDF）相对于这样一个更高的性能保证。关键词：在线算法，额外资源分析，最终期限调度，最早期限优先1 是项研究获香港研究资助局HKU-7024/01 E资助。2Email：twla m，kkt o，whwong@www.example.comcs.hku.hk3 电子邮件地址：twngan@cs.rice.edu1571-0661 © 2004由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2003.12.010T.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-157149CCC4C1介绍这篇论文关注的是在允许抢占的处理器上调度具有截止线的作业的在线算法（参见，例如，[2、14、18、15、6]）。一个典型的例子是最早期限优先（EDF）算法，它已被广泛用于许多实时系统（见[19] EDF的调查）。我们通过在截止日期前完成的作业的总工作（或价值）来衡量这种在线算法。 一个在线算法被称为1-竞争对于某个分数1≤1，如果对于任何作业序列，它保证达到任何一个线性算法得到的总功（或值）的至少1通知1-竞争性算法匹配最优的最优算法的性能长期以来人们都知道，当系统欠载时，EDF实际上是1-竞争的[7];然而，一般来说，EDF以及任何在线算法都不是1-竞争的[8];事实上，最好的算法最多可以匹配任何在线算法获得的总工作量的1[14]。（一般来说，如果我们的目标是使总价值最大化，算法是1/（λ+ 1）2-竞争[14]，其中λ是重要性比，它是每单位功的最大可能值与每单位功的最小可能值之比近年来，已经有许多关于如何使用更快的处理器或其他额外资源来获得在线查询器的更好性能保证的研究;这样的研究通常被称为资源增强或额外资源分析（例如，[3、5、6、9、10、11、12、15、16、17]）。直观地说，允许在线调度程序使用比在线调度程序快的处理器提供了一种补偿在线调度程序缺乏未来信息的方法为了简化我们的讨论，我们首先讨论旨在最大化总工作的调度结果。Kalyanasundaram和Pruhs [10]是第一个证明一个速度适中的处理器可以保证1-竞争算法，其中c是可以任意接近1的常数。后来Lam等人[16]进一步表明，当使用速度为2的处理器4时，补充有准入控制的EDF（由EDF-AC表示）确实是1-竞争性的，最近Koo等人[12]表明，如果在线调度器仅利用两个单位速度的处理器，也可以实现1-竞争性。知道更快的处理器可以允许在线调度器匹配最优调度算法，人们自然会要求比最优调度算法更好的性能。粗略地说，对于某些k >1，期望具有k-竞争算法。然而，从技术的角度来看，这样的保证是不可能的，因为总是存在作业序列4speed-x处理器可以在一个单位时间内处理x个单位的工作150T.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-157≤≥≥[|对于这些问题，没有在线算法能够胜过最优的在线算法;例如，作业序列可能是欠载的（即，它可以完全由OKLINE算法完成）或者仅具有短的过载时段。上面的观察促使我们研究一个要求较低的概念，称为k-攻击算法，可以理解如下。理想情况下，我们希望一个在线算法尽可能完成所有作业;当它不能完成所有作业时，必须有一些冲突的作业，我们要求算法保证它在这些作业上的性能至少是最优算法的k定义1.1一个在线算法A被称为是k-攻击的，如果A能满足以下要求。给定任何作业序列I，A将作业划分为两类，称为过载作业和欠载作业，使得• 对于超载作业，A所获得的功（或值）至少为k倍于任何并行算法（使用单位速度处理器）;以及• 对于欠载作业，A在截止日期前完成所有作业。根据定义，对于任何c 1，一个算法是c-竞争的当且仅当它是c-攻击性的。换句话说，进取心可以被视为竞争力的延伸。 如前所述，使用两倍快的处理器的EDF-AC是1-竞争性的[16]，因此是1-侵略性的。 然而，是否能够实现更高程度的积极性并不是微不足道的。在本文中，我们回答了一个肯定的答案，EDF-AC可以是k-侵略的任何k1时，使用速度-（k+ 1）的处理器。我们对EDF-AC的积极分析确实是严格的，因为我们可以表明，使用速度为（k+1）的处理器，EDF-AC对于任何k>0都不是（k+k）积极此外，如果速度因子被减小到略小于k+1，则EDF-AC不是k-侵略性的。这样的下限结果可以推广到任何在线算法，决定在发布时间，即，当工作被释放时，立即做出承诺工作以满足其最后期限我们对EDF-AC的积极分析可以扩展到目标是最大化总价值而不是完成的总工作的情况。特别是，我们表明，一个简单的扩展的EDF AC可以是k-积极的任何k1时，使用速度-（（2k + 1）logλ）处理器，其中λ是重要性比。本文的其余部分组织如下：第2节介绍了EDF-AC的积极分析时，关注的是总的工作，或等效的，λ= 1。第3节将分析扩展到一般λ的情况（即，具有非均匀值密度的作业第4节表明，我们的分析T.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-157151很紧在离开本节之前，我们给出了最后期限调度问题（在文献中通常称为最终期限调度问题）和EDF-AC的精确定义。问题定义：考虑一个单处理器系统。作业以不可预测的方式发布，每个作业要求一定量的工作（处理时间）。作业的工作、截止日期和价值只有在作业发布时才知道最后期限是严格的，因为在最后期限之后完成一项工作的价值为零请注意，系统可能会过载，在这种情况下，没有办法调度每个已发布的作业以满足最后期限。调度器的目标是最大化满足最后期限的作业的总价值（或工作）允许无偿抢占（即，被抢占的作业可以在任何时间从抢占点重新启动）。由于作业可能具有不同的值密度，即，价值与处理时间的不同比率。系统的重要性比λ被定义为最大可能值密度与最小可能值密度之比当λ= 1时，所有作业具有相同的值密度。总功最大化问题实际上是总价值最大化问题的一个特例，其中λ= 1。为了简化我们的论证，我们假设工作有不同的发布时间和截止日期，因为联系可以被一致地打破，比如说，通过工作标识号。此外，我们假设第一个作业在时间0发布EDF和EDF-AC：本文中EDF是指调度具有最早截止期的作业的策略。请注意，当前作业将在发布具有较早截止日期的新作业时被抢占。EDF通常补充有某种准入控制，以避免在系统过载时过度抢占。在下文中，EDF-AC表示利用以下简单形式的准入控制增强的EDF。在发布时，作业必须通过测试才能进入EDF调度。该测试只是检查新工作与以前承认的工作是否都可以使用EDF在截止日期前完成。一旦工作被接纳，EDF-AC保证完成它。2EDF-AC的攻击性在本节中，我们将证明，当作业具有均匀值密度时（或者等价地，当我们希望最大化总作业时），EDF-AC在使用速度为（k+ 1）的处理器时是k-攻击性的，其中k是至少为1的任何数字。定理2.1 EDF-AC，当使用速度-（k +1）处理器时，对于任何k ≥ 1，是k-攻击的。152T.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-157∪∪我们用反证法证明定理2.1 假设EDF-AC，使用速度-（k+ 1）处理器，对于某些作业序列不是k-积极的。 也就是说，存在一些作业序列，不允许分类成过载和欠载作业，使得EDF-AC完成所有欠载作业，并且对于过载作业，EDF-AC实现的总工作至少是最优算法的k设I是包含最少作业的作业序列。我们将首先证明I必须满足某些性质（见引理2.2和2.4）。然后证明了EDF-AC对任何具有这些性质的工件序列都是k-攻击的。换句话说，EDF-AC对于I是k-攻击的，并且我们获得矛盾以完成定理2.1的证明。引理2.2当调度作业集I时，EDF-AC在恰好一个连续的周期内是忙的。证据 假设EDF-AC在两个或更多个不相交的时段内繁忙。设t1为最后一个繁忙时段的开始时间。将I分为I1和I2两部分，一部分用于在tl之前发布的作业，另一部分用于其余的作业如果我们安排I1和I2分别用EDF-AC生成的时间表是不相交的，它们的并集与I的时间表完全相同。由于I是最小的反例，表明EDF-AC不是k-侵略性的，因此I1（分别为I2）中的作业可以分为过载作业O1和欠载作业U1（分别为O2和U2），这样k-侵略性属性就成立了（参见引言中的定义）。考虑以下I的分类。就业岗位O=O1O2被认为是过载的，U=U1U2中的作业被认为是欠载的.EDF-AC在调度I时，及时完成U中的所有作业，而对于过载作业，EDF-AC调度的工作量仍将超过任何一种并行算法k倍。换句话说，我应该是K-攻击型的，这与我们对I的假设相矛盾。QI的第二个性质与一个称为否定的概念有关，定义如下。定义2.3考虑当EDF-AC不能接纳一个新发布的作业J.也就是说，当J被释放时，发现使用EDF将J与先前接纳的所有作业一起调度会导致某些作业错过截止日期。任何这样的工作都被认为是对J。注意是一份工作可能会自我否定。引理2.4设Jl为I中具有最后期限的作业。在调度过程中，至少有一次Jl拒绝了一个任务。证据相反，假设Jl从不拒绝任何工作。请注意，一个作业只能拒绝另一个作业，如果后者有一个更早的截止日期。以来T.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-157153它不会否定自己，任何工作都不能否定它。因此，J1在其释放时间被EDF-AC接纳考虑Jl被接纳后的任何时刻任何新发布的作业，如果被EDF-AC拒绝，则必须被除Jl之外的作业拒绝。因此，如果我们从I中移除Jl，则EDF-AC将不承认更多的工作。由于Jl是最新的截止日期作业，因此移除它并不影响I中的任何其他作业的EDF-AC调度。注意，I−{Jl}包含的作业比I少一个，因此EDF-AC对于I−{Jl}是k-攻击性的。换句话说，I-{Jl}中的作业可以以这样的方式被分类为过载作业O和欠载作业UK-aggressive属性所拥有的。考虑以下I的分类：O中的作业是过载的，U中的作业是欠载的。当EDF-AC调度I时，欠载作业全部被调度，而对于过载作业，EDF-AC调度的工作量仍然会超过任何一个线性算法的k倍。换句话说，我应该是K-侵略性的，这与I的定义相矛盾。Q利用I的上述两个性质，我们可以证明EDF-AC对I是k-侵略的。定理2.1的证明 根据引理2.2和2.4，我们可以假设，只包含一个忙期，而Jl，具有最后期限的作业，I，在某个时间t拒绝另一个工作J。设p（J）和d（J）分别表示工件J的加工时间和截止期。下面我们证明了I可以满足k-攻击性的要求，特别是通过将I的所有任务分配为重载。 由于所有作业的截止日期不晚于d（Jl），最优算法只能完成d（J1）的工作。 我们想示出了EDF-AC可以完成至少kd（J1）个功单位回想一下，J在时间t被Jl否认。根据定义，在时间t，如果我们尝试使用EDF来调度J连同由EDF-AC接纳的所有先前作业，则Jl只能在其截止日期之后完成（即，d（Jl））。注意，速度为（k+ 1）的处理器花费p（J）/（k+ 1）个单位的时间来处理J。的这意味着，在时间t，所有先前被接纳的作业必须能够使处理器保持忙碌直到d（Jl）-p（J）/（k+1）。因此，EDF-AC在从0到d（J1）-p（J）/（k+1）的整个时段期间是忙的该区间的长度至少为d（Jl）-d（J）/（k+1）> d（Jl）-d（Jl）/（k+1）=k d（Jl）/（k+1）。使用速度为（k+1）的处理器，EDF-AC可以完成至少k d（J1）个单位的工作，从而满足K-侵略性要求。这与EDF-AC对I不具有k-攻击性的事实相矛盾。Q请注意，上面的证明隐式地展示了如何将作业分类为过载作业和欠载作业，以便EDF-AC满足k-侵略性的要求。详情如下。考虑EDF-AC制定的时间表。它可能包含多个繁忙时段，在这种情况下，我们将154T.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-157[|[|对每个忙期进行独立分类，每次将在一个忙期内释放的作业分类如下。我们将在一个繁忙时段内释放的作业中找到最新的截止日期作业J如果作业J在其调度期间拒绝另一个作业，则该时段中的所有作业被分类为过载，并且分类完成。否则，J被归类为欠载，并且从考虑中移除。一旦我们移除J，剩余作业的调度可能再次包含多个忙期。它们使用相同的策略递归地分类。上面的证明表明k-侵略性质对这个分类成立.3一般价值密度当工作具有非常不同的价值密度时，要保证积极性就更加困难了实际上，EDF-AC的积极性保证随着重要性比率（即，作业组内作业的最大值密度和最小值密度之间的比率）增加。使用第2节的证明技术，我们可以证明EDF-AC在使用速度-（kλ+ 1）处理器时是k-攻击的，其中λ >1是重要性比。幸运的是，我们可以使用EDF-AC作为构建块来设计改进的算法，称为λ-EDF-AC，其仅需要速度-（（2 k +1）[log λ|）处理器。我们假设值密度在1和λ之间。λ-EDF-AC 算法将处理器分成logλspeed-（2k+ 1）个虚拟处理器。它们中的每一个都为一些作业运行EDF-AC。特别地，第i个处理器将调度值密度在[2i-1， 2i）之间的作业，并且值密度λ的作业也由logλ个处理器调度，即使λ是a。2的幂定理3.1λ-EDF-AC在每个虚拟处理器是速度时是k-侵略的（2k +1），即， 当单个处理器的速度为speed-（（2 k +1）[log λ|）的。证据请注意，每个虚拟处理器的作业调度都是k主动的。换句话说，给予第i个处理器的作业Si可以被分类为过载作业Oi和欠载作业Ui，使得第i个虚拟处理器中的EDF-AC完成Ui中的所有作业，并且达到至少k乘以Oi的任何线性算法所获得的功。 因此，U=Ui，O=Oi定义了一组作业的分类，以表明λ-EDF-ACisk-aggressive：U中的所有作业都由λ-EDF-AC完成。 对于O的工作，λ-EDF-AC获得的值至少是并行算法对于每个Oi 所能获得的值之和的k倍，其中该和至少是通过并行算法对于作业集O所获得的最大值。QT.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-157155一一一AA一- -4攻击性下限一个算法被称为在释放时决定是否在作业被释放时立即做出承诺作业以满足其截止日期的决定。注意，EDF-AC是在释放时间决定的算法。对于这种类型的算法，我们可以证明上述速度和攻击性是紧密的。定理4.1设是一个在线算法，对于某个正整数k，使用速度为k + 1的处理机。如果在释放时间决定，则对 于 任 何 ε > 0 都不是（k + ε）-积极的。证据考虑以下k+ 2个工件的序列S。第一个工件J0的发布时间为0，处理时间为ε/2，截止时间为ε/2。所有剩余的k+1个工件的释放时间、加工时间和截止时间分别为δ、1和1+δ，其中δ ε/（2k+2）。必须积极地投入第一份工作，因为这是当时唯一可用的工作。则它可以积极地提交至多k个延迟作业，并且必须拒绝至少一个延迟作业J。 (This是因为（k+ 1 +ε/ 2）/（k+ 1）= 1 +ε/（2k + 2）>1+δ。）由于主动算法必须完成所有欠载作业，因此J必须归类为过载。一个最优的优化算法可以选择只在J上工作。作为（k+ε）-攻击算法，因此，A必须完成一组超载作业，总工作量至少为k+ ε。但是，正如我们已经看到的，必须拒绝至少一个加工时间为1的工件，因此只能完成k+ε/2 0，使用速度-（k +1-ε）处理器。 如果A在释放时间决定，则A不是k-攻击型的。证据考虑以下k+ 2个工件的序列S。前k+1个工件的发布时间为0，处理时间为1-ε/3k，截止时间为1。最后一个作业的发布时间为ε/4k，处理时间为1−ε/ 4k，截止时间为1。A不能承诺所有的前k+1个工作，因为它只能在1个单位时间内完成k+1-ε工作，而k+1个工作的总工作是k+1-（k+1）ε/3k，这是更大的。因此，A至少拒绝这些k+ 1个作业中的一个，因此必须将其视为过载作业。由于一个线性算法可能对该作业要具有k-攻击性，必须提交所有剩余的k个作业。结果，必须拒绝最后一个作业（稍大的工作），因为完成它意味着算法完成的工作量为kε/2+1ε/4k，大于我们前面提到的最大值。因此，最后一个作业必须归类为重载。算法可以选择完成工作，因此为了具有k-侵略性，算法必须完成总计k−ε/4，这不是这种情况（A只完成k−ε/3功）。Q156T.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-1575结论意见和今后的工作虽然我们证明了使用速度-（k+ 1）处理器的EDF-AC是k-攻击性的，但这种优点绝对不限于EDF-AC。可以证明，在[12]中引入的EDF-Plus算法也具有此特性。有几个与侵略性有关的公开问题对于我们来说，是否存在任何在线算法在给定额外的单位速度处理器时是k-侵略性的，这是k= 1时的特殊情况已在[12]中解决。此外，我们想研究的多处理器调度的上下文中的侵略性。引用[1] Baruah，S.，单处理器工作负载的过载容限。在IEEE实时技术和应用研讨会上，第2-11页[2] Baruah，S.，G.科伦湾米什拉A.拉古纳坦湖Rosier和D.沙沙，在线调度中存在过载。 在proc 1991年IEEE实时系统研讨会，第101- 110页，1991年。[3] Berman，P. and C.科尔斯顿速度比千里眼更强大在Proc.6th SWAT，第255-263页[4] Borodin，A.和R. El-Yaniv，在线计算和竞争分析。剑桥大学出版社，1998年。[5] Brehob，M.，E. Torng和P.Uthaisombut，将额外资源分析应用于负载平衡。Journal of Scheduling，3（5）：273[6] Chrobak，M. ，L. Epstein，J. Noga，J. Sgall河 你好，T。 Tichy'anN. Vakhan ia，过载系统中的Pr eempt iv调度.在Proc. ICALP，第800-811页[7] 德尔图佐斯湾L.，控制机器人：物理过程的程序控制。在Proc. IFIP Congress，第807-813页[8] 德尔图佐斯湾L.和A. K. L.莫，硬实时任务的多处理器联机调度IEEE软件工程学报，15（12）：1497[9] Edmonds，J.， 在黑暗中调度。 在Proc. STOC，第179-188页[10] 卡利亚纳孙达拉姆湾和K. R.普鲁斯速度和千里眼一样强大J. ACM，47（4）：617[11] 卡利亚纳孙达拉姆湾和K. R. Pruhs，最大化在线作业完成率。Proc. ESA，第235-246页，1998年[12] 库角是的，T. W. Lam，T. W. Ngan和K. K.最优期限调度中的额外处理器与未来信息。在Proc. SPAA，第133-142页[13] 科伦湾和D. Shasha，MOCA：多处理器在线竞争算法实时系统调度。理论计算机科学，128：75[14] 科 伦 湾 和 D. Shasha ， Dover ： A optimal on-line scheduling algorithm for overloadeduniprocessor real-time systems.SIAM J. Comput. ，24（2）：318[15] Lam，T. W.和K. K.在硬截止期调度中，在速度和处理器之间进行权衡。在Proc. SODA，第623-632页T.- W. Lam等/ Electronic Notes in Theoretical Computer Science 91（2004）148-157157[16] Lam，T. W.和K. K.过载情况下在线截止日期调度的性能保证。在Proc. SODA，第755-764页[17] 菲利普斯角A，C. Stein，E. Torng和J. Wein，通过资源增加的最优时间关键调度。在Proc. STOC，第140-149页[18] Sgall，J.，在线调度-一项调查。以.菲亚特和G. Woeginger，编辑，在线算法：最新技术，第196计算机科学讲义，施普林格出版社，1998年。[19] 斯坦科维奇，J.A.，M.斯普里湾Ramamritham和G. C. Buttazzo，Deadline scheduling forreal time systems：EDF and related algorithms。Kluwer Academic Publishers，1998.