关键词: 任务选择算法 动态抢占阈值调度 选择树

Abstract:

Scheduling algorithms with a preemption threshold have the characteristics of no preemption scheduling and full preemption scheduling. It both decreas es a waste of the CPU resources caused by excessive random preemptions and guarantees suitable CPU utilization. However, the runtime overhead of job sel ection algorithms affects the performance of the system seriously. To solve the problem, a job selection algorithm is proposed that uses a selection tre  e as the scheduling queue structure. The proposed algorithm selects a job in O（｜log2n｜ ） time, resulting in a significant reduction in the runtime o  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.

Key words: job selection algorithm, dynamic preemption threshold scheduling, selection tree