《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；兀.|.（7,用U表示处理器利用率因子。我们希望得到C1=T2-Tt.C1=7-7J
12、,0.C2-ic；=Cy明显，CCGI,cn:也完全利用了处理器。用U表示其相应的处理器利用率因子。得到t-(,=(7j)-()o.或者,我们可使CI=TZ-7-.0.C1=T2-Ttcro=Cm.同样，c；,c；C也完全利用了处理器。用u表示其相应的处理器率因子。得到-c=-()+(27j)o.因此，若U的确是最小的利用率因子，则Ci=Ti-Tv相像的，能得到因此为了简化书写，令H1=(Tm-Ti)TlJ=,2”m.因此CI=T.特殊的，令O=M+r,1且r0用任务r；代咨r,7：=仪；且C=C。通过增大Cm使得处理港能得到完全利用，Cni的最大值为Ca-1),二关键时间域内的时间被r,而非
13、r；所占用.令U表示此类任务的利用率因子.我们得到U,U+(q-)C,Tm+(C,T-(C,fT)或是(7,+(-i)(+r)-(i0且l(4W+r)-gZ)V0,UU.因此我们得到判定处理器的利用率因子的上确界，我们只需考虑随意两个恳求周期的比值小于2的任务序列集。这个定理可由定理4千脑得出。6放宽利用范围前面的章节已经说明白实时处理器的任务序列集利用率的上确界可达In2。由于必需把任务转换之间的实际损耗考虑在内，故我们必需找到方法提升此上确界。是利用率达到I的酸简洁的方法之一就是对于i=1.2,.W-I,使得匚/7；=0。由于这个方法不能常常奏效，另一个途径是对任务或其他较低优先级的任务进
14、行缓冲，并且放宽它们的硬截止期。设整个任务序列集有一个有限的周期且能以某些合理的方式执行缓冲的任务，例如，以先到先执行的方式。然后可由本论文所给的下设条件计算出最大延迟时间及须要绫冲的任务数量。一个更好的解决方法是用动态方法安排任务的优先级。本论文的剩余章节会具体阐述一个动态优先级安排算法。若一个任务序列集可被某些优先级安排比法调度，则此任务序列集也能被这个算法调度，且还是最优的“换句话说，采纳此动态优先级安排免怯，处理疑利用率因子的上确界一律为100%。7稚止期驱动调度算法现在我们起先探讨一个称为“截止期驱动调度竟法”的动态调度莫法。这个算法使得服务器依据当前所恳求任务序列集的截止期动态安排
15、任务的优先级。截止期最苑前的任务优先级别最高，截止期最远的任务优先级最低。在随意时刻，未执行任务中拥有最高优先级的任务相被执行。与任务优先级不随时间变更的静态安排相比，这种安排任务优先级的方法是动态的。干是我们要建立使得截止期驱动调度算法可行的充分必要条件。REQUESTSFORTASK1REQUESTSFORTASK2REQUESTSFORTASK3REQUESTSFORTASKm图3处理器空闹周期之后发生溢出定理6当服务器采纳截止期驱动调度算法来调度任务时，在溢出之前没有处理器的空闲时间.证明设处理器的空闲时间在溢出之前.准确的说，以。为时间起点，八表示溢动身生的时刻，4小分别表示最靠近时
16、刻A的处理潜空闲周期的起点和终点时刻(即在4和八之间没有处理器空闹时间)。图3表示了这种状况，用表示处理器空闱周期1.JJ之后的个任务的第一次恳求时间。假设从起先我们使任务1的全部恳求提前，使得。与重合。因为在八和人之间没有处理罂空闱时间，在。提前后也并不会有处理器空闲时间。此外，溢出会在右或八之前发生.对全部其他任务均重灾此方法，我们可得到若全部任务都在A时刻被初始化，则会有一个在处理港空闲周期之后的溢动身生。然而，这与初始时刻为0且服务器的空闹周期发生在溢出之前的假设冲突，故定理6得证。定理6将被用来证明如卜.定理：定理7对下一个给定的任务序列桀，截止期驱动调度算法是可行的当且仅当(C17
17、)+(G7)+.+(Cml)l.证明为r说明必要性，通过计算，在/=0和r=7；4，之间的全部任务所须要的总计算时间为(也,7JC+(7J7;几)G+(必如)。若须要的总时间超过了处理器的有效时间，即(也7JG+(5TJG+(孙，T)Gi,m7；或是(Cl7j)+(G.7;)+(CIj?)1则没有可行的调度算法.为了说明充分性，假设当满意(C171)+(G.7;)+(C)l时这个调度算法是不行行的，即在，=0和，=7；/7；之间有一次溢出.此外，依据定理6,在，=八0TT7；，)时刻发生溢出，且处理器在0和r=7之间没有空闲时间.用44,表示在t之前的全部”，个任务的恳求时间，且4，咫，表示截
18、止期为T的全部任务的恳求时间，&.仇.表示截止期在丁之后的全部任务的恳求时间。如图4所示。OT!a；iOP：-BP啊!：0P:%:口；E：-；口口口；n%:；口；口III*图4在T时刻发生溢出考察两种状况：状况1在7.之前未发生九包,.时刻的计算恳求。在这种状况下，O和丁之间的计算所需总时间为T7Ci+TT2C2+TiTa,Cn.由于没有处理器空闲周期，故Jc,+jG+mcm.同样地，时于全部X均有*2A则(T)C.+(T7)G+(TTw)CwT且(Cl/7；)+(C,/7；)+.+(Cfl/7；1)l这与式子(7)冲突。WEREFU1.FI1.1.EDBEFORET图5在丁时刻后未执行任务仇
19、且在T时刻发生溢出状况2在7.之前发生了某些九时刻的计算恳求。由于在了时刻发生了溢出，必定存在时刻7使得在配网,，时刻，处理器发出恳求均不在/f7内。换句话说，在7-4147范围内，只有技止期在丁或丁之前的恳求能被执行，如图5所示。此外，至少有一件恳求时间为,的任务被执行直至，=7意味若截止期在丁或丁之前I1.在r之前发出的全部的任务恳求I1.都会在7”时刻之前完成。因此，在rr7内的处理器所需总时间小于等于1.(T-)7jJC1+1.(T-)7JC2+,+tT-TyITuCm.时刻发生溢出意味若1.(r-D/Jcl+1.(-)Jc,+.+(-7,)Jq11-r这就意味着(C,)+(GT)+(
20、Cn,)这与式子(7)冲突，由此证明白定理7。综上所述，假如一个任务序列集能被随意算法调度，则故止期驱动的调度算法是最优的。混合调度算法在这一节我们会探讨一类结合RM和截止期驱动的调度算法。我们称此类算法为混合调度算法。混合调度算法缘起于对电脑硬件中断的视察，目前电脑的硬件中断充当一个固定优先级调度器并且与硬件动态调度器不兼容.在另一方面,假如任务是截止期驱动而非固定优先级安扑，则执行慢节奏任务的软件调度器的花费并没有显著提高.具体说来，对于具有最短周期的任务1,2,M，依据RM算法，这&个任务会被优先执行。当处理器未被任务1.2./占用时，剩余任务Al,A+2,1会依据截止期驱动调度算法执行
21、。用“表示关于/的不减函数。对于全部,和丁，我们说是亚线性的当且仅当a(t)a(tT)-a(f)处理器对于任务序列集的可用函数是指从O到r的累积处理时间。假设用固定优先级算法调度&个任务。用生表示任务A+1.4+2.,加的处理器可用函数。很明显，为是，的不减函数，此外，依据关键时间域的论点，为(/)是亚线性的。因此我们得到：定理8若处理器的可用函数是亚线性的，且运用被止期驱动调度免法来调度任务序列集，则溢出没有处理器空闲周期。证明与定理6的证明同理。定理9截止期郭动调度算法为可行的充分必要条件是处理器的可用函数为|?/心G“+|_心Cz+WCn,qQ)其中，为ZZ.2，,一的全部倍数。证明该定
22、理证明与定理7类似，首先证明必要性，留意到任何时刻处理器所需总时间不能超过可用的处理沿总时间，所以对于全部r,我们必需使1几JG“+1.几G.2+1.”7jQq其次证明充分性，假设满意定理的假设条件且在了时刻发生了溢出。视察定理7证明中的两种状况。对丁状况1,有1.t-,iJQ11+1.7JQ.2Amcmal(t)这与假设冲突。留意到为的倍数，对于状况2,有1.(T-r)/7；Hjc;H+1.(T-r)/2jc；t2+.+1.(r-n/7；jc；x(T-n令表示最小的非负数，则存在，使得r-T-为7i.j.lMm-的倍数.明显(7一7一0/或J=Iy一乃/几JJ=I2.,m4故1.(T-7,+
23、1.-7)/九2”+y-T-)lTxCnatiT-r)at(T-T,-)这也与假设冲突，由此定理9得证。尽管定理.9中的结果是一个通解，它的应用涵盖了一系列大地的不等式。在具体案例中，用充分条件来分析调度的可行性比干脆运用定理9里有效.例如,我们考虑用混合调度算法调度三个任务，其中周期最短的任务有一个固定的优先级，其余两个用截止期驱动算法调度。，已经证明若l-(q7J)-min(7J-q)7,(7J)(GK)+()则混合调度算法是可行的。同样可证明若C2a,(T2),TyT2C2+G,(;/7；J7；),(1.7；7J+1)G+C,l(7;)则混合调度算法也是可行的。上述证明包含了比较直观但为
24、数众多的限制不等式,详情可查看文献13。缺憾的是，这些充分条件和定理9中的充分必要条件都是针对低处理器利用率的状况。9比较和评论定理9中的限制条件强有力的表明白混合调度算:法的利用率通常达不到100%。我们通过卜面一个简洁的例子加以证明。令工=3,(=4.1=5且G=G=1.由于(2O)=13,易得G的最大值为2,相应的利用率因子为U=1.1.2=98.3%.345若用截止期驱动尊法调度这一：个任务，G可增大到20833并且利用率达到100%。若它们都用RMw:法调度，G,限定不超过1,则利用率因子最大为t/=-+-+-=78.3%345这只比调度三个任务的利用率最小值高一点点。尽管没找到混合
25、调度算法处理器利用率上确界的最接近的表达式，这个例子有力佐证了混合调度算法比固定优先级RM鸵法的边界值所受限制更少。因此混合调度算法对很多应用来说更为合适。10结论为了支撑后续分析，本文的前几章给出了五条运行环境的假设条件。其中最重要也是最为牵强的或许是假设(AI)。全部任务均有周期性恳求，假设条件(A4)和任务运行时间均不变。若没有这些条件作为前提，每个任务的关键时间域将被定义为在恳求与截止期之间的时间区域，在此区域内，计算时间的最大值由优先级较高的任务确定.除非能得到运行时间和恳求的具体信息，任务运行时间的限制会在假设的周期和为常数的运行时间的基础上，运用周期等于最短恳求间隔，任务运行时间
26、为最长的运行时间加以计算。在这种状况下，我们的分析工作都是无效的，任务的非周期性会严峻制约处理滞利用率。固定的优先级依次是随着任务恳求和截止期之间的最短时间间隔而不是未定义的恳求周期而单调的。若一些裁止期比假设(A2)中的更为案密，只要包含最高优先级的任务在内尽管会对利用率造成微弱影晌，但单调性仍旧成立。对于任何必需确保程定性的实时任务而言，假设(Al)、(A4)中所包含的值都特别高，使得它们成为程序设计的目标值。总而言之，本文通过表示程序应用特征的一些假设条件探讨了以限制和监视为代表的实时环境卜多程序运行的难题。提出了一个好优的固定优先级调度算法,该算法依据任务恳求速率，利用单调性关系来安排任务优先级.对大型任务序列集，这个算法的处理器利用率因子上确界约在70%左右。证明臼破止期驱动的动态调度算法通常是最优的Il能达到100%的处理器利用率。接着探讨了两种调度算法的结合，这些探讨为截止期驱动调度匏法的好处和可能在实际中得到应用供应了诸多依据。
