嵌入式系统设计过程中任务优先级调度的策略

调度程序的功能是调度任务的执行顺序，非调度实体的存在却会导致调度程序的效率下降，为时限调度程序而设计的系统总是尽可能地减少非调度实体的数量以及这些实体所占用的CPU时间，本文介绍嵌入式系统设计过程中任务优先级调度的策略。 

在过去的几年里，固定优先级调度技术的发展迅速。分时系统和一些实时系统，要求所有的任务要同时运行。它赋予每个任务一个有效的优先级，并且该优先级在任务等候执行的过程中逐步递增。最后每一个任务都将获得一个有效的优先级，该优先级将确保该任务至少会获得一个短暂的CPU执行时间。 

一个高优先级的任务可能会发现自己正在等待一个低优先级的任务释放资源。这样将高优先级任务的有效优先级下降到了低优先级任务的有效优先级以下。这种技术可以实现，但是对于调试却是有害的。优先级继承以及优先级限制协议就是专为解决这样的问题而发明的。该技术推进了低优先级任务的优先级，与此同时保留了一定的资源确保高优先级的任务在需要时可以使用。 

实际上，绝大多数的实时操作系统都采用静态优先级调度方式，本文介绍如何通过时限调度(deadline scheduling)来保证系统的实时性。 

速率单调分析 

速率单调性分析(rate monotonic analysis)证明，如果一个固定优先级抢占系统在执行的一系列彼此独立的周期性任务，那么不存在为周期性任务静态分配优先级的算法，而为这样的任务分配较短的时间来获得较高的优先级却更容易找到办法。 

为此，人们研发了RMA调度，RMA的一个重要特征是可以分析系统的可实现性(feasibility)。采用RMA，结构设计人员可以收集系统的情况，然后分析系统的可实现性，从而获得“调度程序正是如此工作”或者是“固定优先级调度程序不能进行这样的调度”等分析结果。 

简单、通用版本的RMA使用超出69%的CPU时间，这将构成实际系统的可实现性方面的问题。如果结构设计工程师退回到老式的时间线分析，RMA甚至要占用100%的CPU时间，问题是我们采用的是单调乏味的手工仿真，而不是高等的代数运算。 

在某些系统中，几乎所有的事件都是周期性的，但是大多数的系统中都存在大量的非周期性事件，现实就是如此。可以在一个周期严格的系统中处理非周期性事件，通常是将它们分配到一个周期性调度的时隙中，由于需要实现这种时隙的轮询，所以会极大地降低系统的性能。系统设计工程师也必须决定轮询这些非周期性事件的频度，以及处理这些事件允许的时间长度。 

然后，要考虑软实时方面的问题。通过弹出一个任务的优先级使之高于该时段指示的优先级水平，从而在RMA中可以对重要性进行度量。这样就会造成那些没有施加优先级弹出的任务出现问题，这种情况正好与RMA的整体设想相反。程序将分析可实现性，然后确保系统的成功。RMA不是为不可实现的系统而设计的。 

固定优先级调度 

固定优先级调度最大的问题是对时限的要求具有易忘性，也就是说这种优先级调度对硬实时不敏感。这就像是一个基于定时器的交通灯，没有任何的交通流量传感器。如图1所示。上面的时间线(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]。