改进的最小空闲时间优先调度算法

最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.

An Improved Least-Slack-First Scheduling Algorithm

The LSF (least slack first) algorithm assigns a priority to a task according to its executing urgency. The smaller the remaining slack time of a task is, the sooner it needs to be executed. However, LSF may frequently cause switching or serious thrashing among tasks, which augments the overhead of a system and restricts its application. Assigning a preemption threshold in the scheduling policy can decrease the switching among tasks, however, the existing assigning methods are limited to the fixed priority such that they are not applied to the LSF algorithm. In order to relieve the thrashing caused by LSF, some applicable assigning schemes are presented to the LSF algorithm based on the preemption threshold. Every task is dynamically assigned a preemption threshold that is dynamically changing with the executing urgency of the task and is not limited by the number of tasks. Simulations show that, by using the improved LSF policy, the switching among tasks decreases greatly while the missed deadline percentage decreases. The proposed algorithm is useful for designing and implementing a real-time operating system.