嵌入式体系筹划进程中任务优先级调理的战略

    调理步调的结果是调理任务的实行序次，非调理实体的存在却会导致调理步调的屈从降落，为时限调理步调而筹划的体系总是尽大概地淘汰非调理实体的数量以及这些实体所占用的CPU时间，本文先容嵌入式体系筹划进程中任务优先级调理的战略。 

    在已往的几年里，牢固优先级调理技能的生长敏捷。分时体系和一些及时体系，恳叱责部的任务要同时运行。它付与每个任务一个有效的优先级，并且该优先级在任务等待实行的进程中垂垂递增。着末每一个任务都将得到一个有效的优先级，该优先级将确保该任务至少会得到一个短暂的CPU实行时间。 

    一个高优先级的任务大概会发明本身正在等待一个低优先级的任务开释资源。如许将高优先级任务的有效优先级降落到了低优先级任务的有效优先级以下。这种技能可以实现，但是敷衍调试倒是有害的。优先级承继以及优先级限定协议便是专为办理如许的标题而发明的。该技能推进了低优先级任务的优先级，与此 

    同时生存了肯定的资源确保高优先级的任务在须要时可以利用。 

    实际上，绝大多数的及时利用体系都采取静态优先级调理要领，本文先容怎样通过限期调理(deadline scheduling)来包管体系的及时性。 

    速率单调阐发 

    速率单调性阐发(rate monotonic analysis)证明，要是一个牢固优先级抢占体系在实行的一系列相互独立的周期性任务，那么不存在为周期性任务静态分派优先级的算法，而为如许的任务分派较短的时间来得到较高的优先级却更容易找到步调。 

    为此，人们研发了RMA调理，RMA的一个告急特性是可以阐发体系的可实现性(feasibility)。采取RMA，布局筹划职员可以网络体系的环境，然后阐发体系的可实现性，从而得到“调理步调正是云云变乱”大概是“牢固优先级调理步调不克不及举行如许的调理”平阐发结果。 

    大抵、通用版本的RMA利用超过跨过69%的CPU时间，这将构成实际体系的可实现性方面的标题。要是布局筹划工程师退回到老式的时间线阐发，RMA以致要占用100%的CPU时间，标题是我们采取的是单调乏味的手工仿真，而不是高等的代数运算。 

    在某些体系中，险些全部的变乱都是周期性的，但是大多数的体系中都存在大量的非周期性变乱，实际便是云云。可以在一个周期严格的体系中处理惩罚处罚非周期性变乱，通常是将它们分派到一个周期性调理的时隙中，由于须要实现这种时隙的轮询，以是会极大地低沉体系的性能。体系筹划工程师也必须决定轮询这些非周期性变乱的频度，以及处理惩罚处罚这些变乱容许的时间长度。 

    然后，要思量软及时方面的标题。通过弹出一个任务的优先级使之高于该时段指示的优先级程度，从而在RMA中可以对告急性举行度量。如许就会导致那些没有施加优先级弹出的任务出现标题，这种环境恰好与RMA的团体假想相反。步调将阐发可实现性，然后确保体系的告成。RMA不是为不可实现的体系而筹划的。 

    牢固优先级调理 

    牢固优先级调理最大的标题是对时限的恳求具有易忘性，也便是说这种优先级调理对硬及时不敏感。这就像是一个基于定时器的交通灯，没有恣意的交通流量传感器。上面的时间线(H)表现一个高优先级的任务，下面的时间线(L)表现一个低优先级的任务。调理步调会起首实行高优先级的任务，如许就容易在该任务的时限内完成该任务。任务H完成后，调理步调就切换到任务L，然而在任务L的时限内大概没有富裕的时间来完成任务L。要是调理步调对这些时限的环境很相识，那么调理步调就有大概在任务H之前先运行任务L，如许大概可以大概餍足两个任务全部的时限恳求。 

    一个有经历的及时步调筹划师大概用一些筹划本领来处理惩罚处罚如许的标题，如在体系运行时奥妙地处理惩罚处罚优先级，大概是用加锁的要领来实现，然而在此工程师面对的是如那边理处罚调理步调而不是怎样利用调理步调的标题。 

    牢固优先级调理最大的上风在于：1. 每一个主流的利用体系大概任务切换内核都支持牢固优先级调理。2. 及时工程师在他们的职业生存中不绝都在利用这种技能。3. 很多册本、论文和专业课程都是围绕牢固优先级调理技能来编写的。 

    牢固优先级调理步调须要几百字节的资源以及占用很少的CPU时间。相比之下，动态优先级调理步调通常都很巨大。动态优先级调理步调则明显要超过跨过上面的指标。 

    硬及时 

    一个好的及时利用体系是独立于细致应用而筹划的，但这并非意味着它不必干涉干涉硬及时处理惩罚处罚。 

    严格意义上说，没有几个别系是 

    真正的硬及时体系。纵然错过了时限齐备仍将连续。大概一个真正的硬及时体系同真正意义上的“不绝顿”谋略是同样的典范。 

    硬及时大概非常特别，然而有关这种技能的应用倒是大量存在。以数据流媒体办事器为例，要是不克不及够及时地发送信息包，天下并不会因此而完结；即便偶然偶尔间错过了时限，大概都不会出现标题。办事器的评判部分取决于办事器并发办事的数据流的数量，同时也部分取决于这些数据流的风致。在确保富裕确定性的环境下，可以鉴定一个办事器何时仍旧可以大概投入高兴来运行，这种环境下办事器可以发挥100%的本领同时确保数据流不出现错误，如许的软件就非常有价格。 

    时限调理 

    动态优先级调理通常都从时限调理开始，大概敷衍周期性任务来说，是从时限集开始。调理步调将根据这些时限来决定任务的实行序次。 

    调理步调可以从时限中得到很多信息，但是要餍足时限的恳求须要很高的开销。要是一个任务记录了时限以及到达该时限时所须要的CPU时间总数，调理步调就可以实行可实现性阐发。要是调理步调确定可以布局一种调理，在确保餍足新的时限恳求的同时也能餍足全部已经承继的时限，那么体系将承继这个时限。除非经授权调理步调容许实现该典范任务准入的办理控制，不然它不大概作出一个实际的容许。 

    要是全部任务都运行正常，并且从不试图利用比它们在资源度量中申请的CPU时间更多的话，那么准入控制就富裕了。要是偶然偶尔任务低估了它们对处理惩罚处罚器的需求，一个获准参加控制的调理步调容许具有对非法资源度量的任务与别的任务的时限举行折衷思量。 

    为了保卫出现这种环境，调理步调大概会采取一种欺凌步调。要是一个任务试图超过跨过当时限，那么就大概会出现一些不良的环境。比如大概会从体系中消除该任务。大概这些任务只是被别的任务抢先占用，并且容许这些任务在稍后的时间再连续运行。在上述恣意的环境下，这些任务很有大概会超过跨过当时限的束缚，但是并不会影响别的调理的正确性。老式批处理惩罚处罚谋略机用户对此大概非常熟习，在那样的谋略机体系中采取的任务调理战略非常像如今的时限调理。 

    最早时限第一 

    第一个硬及时动态优先级调理步调称为最早时限第一(EDF)。Liu和Layland的文献证明，要是存在某一种调理可以大概餍足全部的时限恳求，那么每一次总是实行当前具有最早未完成时限的任务就可以餍足全部时限的恳求。 

    EDF的吸引力在于屈从高、容易谋略和推测。这是动态优先级调理研究的一个紧张构成部分。EDF的缺点在于，理论表明这种算法能对可调理负载举行优化，但是它不克不及办理过载标题。孕育产生过载时，EDF性能退化很快。这种环境不会对严格的硬及时体系导致标题。 

    EDF调理的实现相对容易。实行行列步队总是由下一个时限来分类。当一个任务处于激活状态时必须将该任务参加到实行行列步队中，大提要是任务的时限在当前正在实行的任务的时限之前，那么该任务就会抢先占用当前的任务。 

    要是全部的任务都是周期性的(这些任务的出现仅仅由于时间的流逝)，那么抢先占用就没有须要。如许就简化了调理步调并且低沉了任务切换的开销。 

    要是任务可以在周期中的恣意时间实行，那么可实现性阐发就大抵可行。也便是说，早期的结果是可以承继的，并且任务准备好随时实行。从另一个角度来看，如许就容许任务的实行可以根据周期小幅变革。微小的时限控制要在伪多项式时间典范中举行阐发。 

    松弛时间 

    松弛时间(slack time)是指一个任务从开始实行到下一次的时限开始之间的时间好坏。这便是可实现的调理窗口的宽度。 

    基于调理任务的松弛时间须要为调理举行资源度量，它在过载的环境下性能会略微降落，并且通过扩充可以相对更好地调理多个处理惩罚处罚器。这种算法就称为最小松弛第一(LLF)要领。 

    LLF算法须要举行得当修改来保卫出现过多的任务间切换。要是多个任务具有近乎一样的松弛时间，那么严格意义上的LLF就恳求调理步调在每一次得到控制权时都必须对这些任务举行切换。LLF对算法举行了修改，要是任务切换不会变革已经餍足的时限，那么调理步调不会举行任务的切换。 

    非周期性任务 

    调理步调的结果是调理齐备任务，但是也有例外，像克制办事、DMA以及某些任务由于某些缘故因由必须调理比原定实行序列更高的优先级，因而粉碎原有的实行序次。这些都称之为非调理的实体，且在时限调理步调中是最不受欢迎的。一些阐发技能容许非调理实体的存在，但是却会导致调理步调的屈从降落。为时限调理步调而筹划的体系总是尽大概地淘汰非调理实体的数量以及这些实体所占用的CPU时间。 

    非周期性任务对动态优先级调理步调来说是一个寻衅。1. 可实现性阐发通常是一个必不可少的任务。要是体系须要尽大概地餍足时限的恳求，那么可实现性阐发就不得当。2. 要是一个变乱已经到达，而这时可实现性阐发的结果表明不该该为这个任务提供办事。3. 非周期性变乱的负载通常都形貌为一种统计散布。 

    非周期任务/变乱可以利用比动态优先级任务更高的优先级来调理。这种要领有效的条件好坏周期性变乱须要硬及时办事并且周期性变乱相对来说是软及时。紧张的标题是调理步调必须将全部的非周期性活动视为不可调理的实体，如许就使得在调理周期性任务时屈从低下，这是由于存在大量不可调理的任务的缘故。 

    颠末动态优先级调理步调调理的周期性办事器可以大概为非周期性变乱提供办事。这种要领将非周期性变乱置于调理步调的控制之下。为了使得这种要领确切可行，调理标题专家举行了充分的研究。标题在于：怎样给非周期性变乱提供较快的应声时间而不会为此而占用太多处理惩罚处罚器时间。为了给非周期性变乱提供与优先级调理体系中近乎一样的应声时间，办事器必须具有很短的调理周期。为了处理惩罚处罚某一刹时同时到达的非周期性变乱的峰值负载，办事器为此而付出的代价就会很高，以是偶然偶尔须要占用全部的处理惩罚处罚器时间来处理惩罚处罚这些非周期性的变乱。 

    要是可以将非周期性变乱分类为软及时，那么调理步调就可以更好地处理惩罚处罚这些非周期性变乱。这是切合实际环境的。比如，键盘输入大概渴望在1/10秒的时间内得到相应，但是要是可巧某一次的键盘相适时间是2/10秒标题也不会太大，以黑白周期性办事器在每一个周期可以生存比匀称资源开销略微多一点的体系资源而不是占用最大的体系资源[2]。 

    本文总结 

    本文讨论的标题具备肯定的前瞻性。大概即日还不须要动态优先级调理如许的技能和东西，但是其生长潜力巨大，尤其在及时筹划方面。