一种动态优先级实时任务调度算法

摘要

现有实时任务调度算法往往根据任务的时间属性或者价值确定任务优先级,较少同时兼顾任务的价值和执行紧迫性.文中根据任务的价值和剩余执行时间讨论任务的剩余价值密度,根据任务的截止期和空余执行时间分析任务的紧迫性；然后综合任务的剩余价值密度和执行紧迫性,提出了动态分派任务优先级的DPA策略；最后提出了基于DPA的抢占调度算法DRTP.DRTP算法分析了任务抢占调度的各种可能条件,分析了系统中可能出现的颠簸调度,并给出避免颠簸的条件.仿真实验结果显示,与其它同类算法相比,DRTP算法能够提高系统价值收益,降低任务截止期错失率,并大大减少任务抢占的次数.%Most of the existing real-time scheduling algorithms assign the priorities of tasks according to tasks' time and value, but few of them can synchronously consider the value and urgency of a task. In this paper, for a real-time task, we firstly discuss its dynamic value density according to its value and remainder execution time, and analyze its execution urgency by considering its deadline and spare time. Based on the dynamic value densities and execution urgencies of the real-time tasks, we propose a strategy named DPA to dynamically assign the priorities of the real-time tasks. Additionally, we also present a DPA-based scheduling algorithm named DTRP. For the algorithm, we analyze all the situations of preemptive scheduling, discuss the thrashing and the condition of avoiding the thrashing. The experimental results show that the DRTP algorithm is prior to other analogous algorithms on the accrual value of real-time system, the deadline miss ratio and the preemptive number.