江苏龙网

  1. 主页 > 生活百科 > >

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

调度算法


单调速率调度可认为是最优的，因为如果一组进程不能由此算法调度，它不能由任何其他分配静态优先级的算法来调度 。
最早截止时间优先(Earliest DeadlineFirst, EDF)最早截止时间优先EDF算法是非常著名的实时调度算法之一 。EDF调度算法是单处理器环境下调度性能最优的一种动态调度系统任务的算法 。EDF调度算法的优先级是以所调度任务的截止期与当前时刻的差值来确定的差值越小证明任务的截止期越早，与其他差值大的任务相比优先级就越高，越需优先执行避免错过任务截止期而导致任务夭折 。因此，采用EDF调度算法可以保证当前离截止期最近的任务获得系统资源和控制权，优先进行调度 。EDF调度算法最大的优点是大幅度提升处理器的利用率，采用EDF调度算法进行调度时，处理器的利用率可以达到最大值 。但EDF调度算法在进行任务调度时系统开销较大，且任务调度过程中无法对系统负载情况进行量化判断，无法应对系统高负载情况下的任务调度问题 。EDF算法在调度过程中存在任务错失截止期的情况，进而影响其他等待调度任务的正常调度，致后续多个任务错失截止期而夭折 。在系统超负载的情况下调度算法会导致系统任务调度的成功率大幅度降低，影响嵌入式系统的实时调度性能 。
在每一个新的就绪状态，调度器都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务，并将执行该任务所需的资源分配给它 。在有新任务到来时，调度器必须立即计算EDF，排出新的定序，即正在运行的任务被剥夺，并且按照新任务的截止时间决定是否调度该新任务 。如果新任务的最后期限早于被中断的当前任务，就立即处理新任务 。按照EDF算法，被中断任务的处理将在稍后继续进行 。该算法的思想是从两个任务中选择截至时间最早的任务，把它暂作为当前处理任务，再判断该任务是否在当前周期内，若不在当前周期内，就让另一任务暂作当前处理任务，若该任务也不在当前周期内，就让CPU空跑到最靠近的下一个截至时间的开始，若有任务在该周期内，就判断该任务的剩余时间是否小于当前截至时间与当前时间的差,若小于，则让该任务运行到结束 。否则，就让该任务运行到该周期的截止时间，就立即抢回处理器，再判断紧接着的最早截至时间，并把处理器给它,做法同上，如此反复执行 。
最小空闲时间优先算法(Least Slack First，LSF)最小空闲时间优先LSF算法结合任务执行的缓急程度来给任务分配优先级 。任务所剩的空闲时间越少，就越需要尽快执行 。最小空闲时间优先调度算法改进了EDF算法的性能，算法中任务优先级由任务空闲时间片数值来决定，即任务截止时间与剩余执行时间之差，空闲时间片数值越小，任务优先执行的级别越高，LSF调度算法通过紧急任务优先执行策略一定程度上解决了EDF算法存在的问题，但调度算法存在任务调度频繁抢占问题，增加了系统的开销同时也降低了实时系统的性能 。




推荐阅读


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

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