引言

随着嵌入式实时操作系统应用的不断深入，多个实时任务并发执行，再加上任务之间不停地动态切换，这对任务调度算法提出了较高的要求。实时操作系统中各个任务的优先级是不同的，而且经常会遇到超负荷的情况.。在这种超载情况下，使任务集内各任务满足各自的时限，嵌入式操作系统必须保证在确定的时间内对事件进行处理，因此必须要有一个良好的任务调度算法。周期任务和非周期任务是实时嵌入式系统中的常见任务类型，系统实时任务调度策略主要包括时间驱动调度策略、优先级驱动调度策略。常见的动态优先级调度算法有最早截止期优先调度算法和最小空闲时间优先算法、单调速率调度算法和最大价值优先算法等。

实时系统的任务按产生请求的频率可分为周期性任务与非周期性任务：周期性任务按照固定的请求间隔持续地产生请求，不同的任务请求间隔不一定相同。 非周期性任务在任意一段时间间隔内可能产生不定数量的请求。按任务优先级分配方式可分为静态优先级任务和动态优先级任务。

1）固定优先级调度算法

在实时调度算法中，固定优先级调度算法事先根据任务的属性，如任务的周期、截止期限等为系统中的所有任务静态分配一个优先级。当任务的截止期限等于周期时，提出了RMS调度算法，它根据任务的执行周期长短的不同来决定优先级，即任务的周期越小优先级越高，任务的周期越大优先级越低。以RMS为代表的固定优先级调度算法，一方面不仅具有运行时间开销小和易于实现的优点，而且在系统超载情况下，仍然可以保证高优先级的任务得到执行；但另一方面却是不能充分地利用系统资源。

2）动态优先级调度算法

在实时调度算法中，动态优先级调度算法根据任务资源需求的变化以及任务的属性，如任务周期、截止期限等动态地决定任务的优先级。当任务的截止期限等于周期时，提出了EDF调度算法，该算法根据就绪队列中任务的截止期限分配优先级，距离绝对截止期限的最近的任务具有最高的优先级，即任务的绝对截止期限越小优先级越高，任务的绝对截止期限越大优先级越低。以EDF为代表的动态优先级调度算法，一方面可以充分地利用系统的资源；但是另一方面在系统负荷严重超载时，系统性能很不稳定，导致大多数任务在截止期限到来之时仍无法满足。

3）静态优先调度算法与动态优先调度算法的比较

静态调度是指系统脱机地进行调度可行性分析后生成一个可调度表，在运行的过程中，调度表中的信息不再发生任何变化。该类调度算法假定系统实时任务的属性是提前已知的并且在执行过程中很少发生变化，特别适合于对那种确定问题的求解，具有较好的可预测性。

单调速率调度算法(Rate Monotonic Algorithm, RM)

单调速率调度算法是一种被广泛使用的调度算法, 并且已被证明是一种最佳的静态优先级算法。单调速率调度（RMS）算法是C.L.Liu和J.W.Layland在1973年引入提出的一种基于周期和多任务的静态优先级可抢占调度算法。RMS是针对周期任务的优先级调度算法，当任务的截止时间等于其周期时，RMS算法已被证明是静态最优的调度算法。

当较低优先级的进程正在运行并且较高优先级的进程可以运行时，较高优先级进程将会抢占低优先级。在进入系统时，每个周期性任务会分配一个优先级，它与其周期成反比，即周期越短，优先级越高；周期越长，优先级越低。这种策略背后的理由是：更频繁地需要 CPU 的任务应分配更高的优先级。此外，单调速率调度假定：对于每次 CPU 执行，周期性进程的处理时间是相同的。也就是说，在每次进程获取 CPU 时，它的 CPU 执行长度是相同的。

假设有两个进程 P1 和 P2。P1 和 P2 的周期分别为 50 和 100，即 ρ1 = 50 和 ρ2= 100。P1 和 P2 的处理时间分别为 t1 = 20 和 t2 = 35。每个进程的截止期限要求，它在下一个周期开始之前完成 CPU 执行。
首先，P1 开始，并在时间 20 完成 CPU 执行，从而满足第一个截止期限。P2 在这点开始运行，并运行直到时间 50。此时，它被 P1 抢占，尽管它的 CPU 执行仍有 5ms 的时间。P1 在时间 70 完成 CPU 执行，在这点调度器恢复 P2。P1 在时间 75 完成 CPU 执行，也满足第一个截止期限。然后，系统一直空闲直到时间 100，这时，P1 再次被调度。
单调速率调度可认为是最优的，因为如果一组进程不能由此算法调度，它不能由任何其他分配静态优先级的算法来调度。

最早截止时间优先(Earliest DeadlineFirst, EDF)

最早截止时间优先EDF算法是非常著名的实时调度算法之一。EDF调度算法是单处理器环境下调度性能最优的一种动态调度系统任务的算法。EDF调度算法的优先级是以所调度任务的截止期与当前时刻的差值来确定的差值越小证明任务的截止期越早，与其他差值大的任务相比优先级就越高，越需优先执行避免错过任务截止期而导致任务夭折。因此，采用EDF调度算法可以保证当前离截止期最近的任务获得系统资源和控制权，优先进行调度。EDF调度算法最大的优点是大幅度提升处理器的利用率，采用EDF调度算法进行调度时，处理器的利用率可以达到最大值。 但EDF调度算法在进行任务调度时系统开销较大，且任务调度过程中无法对系统负载情况进行量化判断，无法应对系统高负载情况下的任务调度问题。EDF算法在调度过程中存在任务错失截止期的情况，进而影响其他等待调度任务的正常调度，致后续多个任务错失截止期而夭折。在系统超负载的情况下调度算法会导致系统任务调度的成功率大幅度降低，影响嵌入式系统的实时调度性能。

在每一个新的就绪状态，调度器都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务，并将执行该任务所需的资源分配给它。在有新任务到来时，调度器必须立即计算EDF，排出新的定序，即正在运行的任务被剥夺，并且按照新任务的截止时间决定是否调度该新任务。如果新任务的最后期限早于被中断的当前任务，就立即处理新任务。按照EDF算法，被中断任务的处理将在稍后继续进行。该算法的思想是从两个任务中选择截至时间最早的任务，把它暂作为当前处理任务，再判断该任务是否在当前周期内，若不在当前周期内，就让另一任务暂作当前处理任务，若该任务也不在当前周期内，就让CPU空跑到最靠近的下一个截至时间的开始，若有任务在该周期内，就判断该任务的剩余时间是否小于当前截至时间与当前时间的差,若小于，则让该任务运行到结束。否则，就让该任务运行到该周期的截止时间，就立即抢回处理器，再判断紧接着的最早截至时间，并把处理器给它,做法同上，如此反复执行。

最小空闲时间优先算法(Least Slack First，LSF)

最小空闲时间优先LSF算法结合任务执行的缓急程度来给任务分配优先级。任务所剩的空闲时间越少，就越需要尽快执行。最小空闲时间优先调度算法改进了EDF算法的性能，算法中任务优先级由任务空闲时间片数值来决定， 即任务截止时间与剩余执行时间之差，空闲时间片数值越小，任务优先执行的级别越高，LSF调度算法通过紧急任务优先执行策略一定程度上解决了EDF算法存在的问题，但调度算法存在任务调度频繁抢占问题，增加了系统的开销同时也降低了实时系统的性能。