江苏龙网

  1. 主页 > 生活百科 > >

嵌入式操作系统周期任务经典调度算法

调度算法

引言随着嵌入式实时操作系统应用的不断深入，多个实时任务并发执行，再加上任务之间不停地动态切换，这对任务调度算法提出了较高的要求 。实时操作系统中各个任务的优先级是不同的，而且经常会遇到超负荷的情况. 。在这种超载情况下，使任务集内各任务满足各自的时限，嵌入式操作系统必须保证在确定的时间内对事件进行处理，因此必须要有一个良好的任务调度算法 。周期任务和非周期任务是实时嵌入式系统中的常见任务类型，系统实时任务调度策略主要包括时间驱动调度策略、优先级驱动调度策略 。常见的动态优先级调度算法有最早截止期优先调度算法和最小空闲时间优先算法、单调速率调度算法和最大价值优先算法等 。
【嵌入式操作系统周期任务经典调度算法】实时系统的任务按产生请求的频率可分为周期性任务与非周期性任务：周期性任务按照固定的请求间隔持续地产生请求，不同的任务请求间隔不一定相同 。非周期性任务在任意一段时间间隔内可能产生不定数量的请求 。按任务优先级分配方式可分为静态优先级任务和动态优先级任务 。
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 再次被调度 。


推荐阅读


上一篇：保肝护肾男人茶,桑果茶怎么做

下一篇：7万茶企不敌家茅台,同茶不同价茶叶市场混乱