低复杂度的阈值优化实时调度算法

Low complexity preemption threshold optimization real-time scheduling algorithm

嵌入式实时系统在其CPU及内存资源相对稀缺时,必须采用复杂度低,系统开销小的调度算法。基于阈值的调度算法可以提高任务的调度性,减少任务间的切换,以此减少内存需求和系统开销。提出了基于抢占差值的阈值分配优化算法。算法在最小阈值分配法基础上,从高优先级向低优先级方向设置任务的阈值,为任务集找出一组满足最大抢占差值的阈值分配方案。经过理论分析及实例验证,算法可以显著降低任务的切换次数,并且算法的复杂度优于传统的优化算法。

Since the CPU and memory resources in embedded real-time system are relatively limited, the scheduling algorithm used in the system must be low complexity and low overhead. The threshold based algorithm can achieve-higher schedulability and fewer context switches, thus the memory requirements and system overheads can be decreased. A preemption dispersion based threshold assignment optimization algorithm is presented. Based on the minimum threshold assignment algorithm, the proposed algorithm sets the preemption threshold from high priority task to lower ones and searches the threshold assignment that achieves the maximum preemption dispersion for given tasks. Theoretical analysis and certification show that the algorithm can achieve fewer context switches and the complexity outperforms the traditional ones.