非周期实时任务过载的判别和处理机制  

Judgement and Mechanism of Handling on Aperiodic Real-Time Task Overload

作　　者：吴悦[1] 唐立三[1] 杨洪斌[1] 

机构地区：[1]上海大学计算机工程与科学学院,上海200072

出　　处：《应用科学学报》2009年第2期198-202,共5页Journal of Applied Sciences

基　　金：上海市重点学科建设基金(No.J50103)资助项目

摘　　要：提出一种基于任务价值的非周期实时任务过载处理机制.在给出一种非周期实时任务过载判断方法的基础上,将任务的截止期和价值这两个参数结合起来,提出处理实时任务过载的数学模型,并采用改进的动态贪婪算法求解.设计了任务参数和任务价值函数,从实现价值率方面分析改进的动态贪婪算法的性能.实验结果表明,在所有额定负载条件下,改进的动态贪婪算法相对于截止期优先、最高价值优先和鲁棒最高价值优先等算法能达到更高的实现价值率.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.

关 键 词：实时任务过载 非周期任务 动态背包 贪婪算法 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论]