摘要
提出一种基于任务价值的非周期实时任务过载处理机制.在给出一种非周期实时任务过载判断方法的基础上,将任务的截止期和价值这两个参数结合起来,提出处理实时任务过载的数学模型,并采用改进的动态贪婪算法求解.设计了任务参数和任务价值函数,从实现价值率方面分析改进的动态贪婪算法的性能.实验结果表明,在所有额定负载条件下,改进的动态贪婪算法相对于截止期优先、最高价值优先和鲁棒最高价值优先等算法能达到更高的实现价值率.
A real-time aperiodic task overload handling mechanism based on value of task is presented in this paper. A method of verifying task overload is first presented. A mathematical model termed dynamic constraint knapsack model is established by combining two parameters, deadline and value of task. An enhanced dynamic greed algorithm (EDGA) is then presented to handle the model. By determining parameters and the value function of tasks, performance of EDGA is analyzed in terms of hit value ratio. Experimental results show that EDGA can achieve higher hit value ratio compared to the earliest deadline first (EDF), highest value first (HVF) and robust highest value first (RHVF) algorithms under all workload conditions.
出处
《应用科学学报》
CAS
CSCD
北大核心
2009年第2期198-202,共5页
Journal of Applied Sciences
基金
上海市重点学科建设基金(No.J50103)资助项目
关键词
实时任务过载
非周期任务
动态背包
贪婪算法
real-time tasks overload, aperiodic task, dynamic knapsack, greedy algorithm