动态抢占阈值调度中的快速任务选择算法

A Fast Real-Time Job Selection Algorithm for Dynamic Preemption Threshold Scheduling

基于动态抢占阈值的实时调度算法集非抢占调度和纯抢占调度的特点,既减少了由于过多的随意抢占造成的CPU资源浪费,又保证了较高的CPU资源利用率。然而,现有的任务选择算法运行时的额外代价严重影响了系统的整体性能。针对这个问题,本文提出一种使用"选择树"作为任务队列结构的、时间复杂度为Ο[log2n]的快速任务选择算法。本文从理论上证明该算法正确性的同时,在使用ARM9芯片的Nokia智能手机上验证了该算法在嵌入式实时系统中的有效性。实验表明,该算法在充分利用处理器的同时能够有效降低动态阈值调度算法的额外代价。

Scheduling algorithms with a preemption threshold have the characteristics of no preemption scheduling and full preemption scheduling. It both decreases a waste of the CPU resources caused by excessive random preemptions and guarantees suitable CPU utilization. However, the runtime overhead of job selection algorithms affects the performance of the system seriously. To solve the problem, a job selection algorithm is proposed that uses a selection tree as the scheduling queue structure. The proposed algorithm selects a job in O（｜log2n｜ ） time, resulting in a significant reduction in the runtime overhead of scheduling. In this paper, the correctness of the job selection algorithm is presented. Also, the job selection algorithm is implemented in a Nokia handset with the ARM9 processor to verify its effectiveness on embedded systems. The experiments performed on the system show that the proposed algorithm can further utilize the processor by reducing the scheduling overhead.