English

应用科学学报 ›› 2009, Vol. 27 ›› Issue (2): 198-202.

• 计算机科学与应用 • 上一篇    下一篇

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

吴悦 唐立三 杨洪斌   

  1. 上海大学计算机工程与科学学院，上海200072
  • 收稿日期:2008-04-16 修回日期:2008-10-23 出版日期:2009-04-01 发布日期:2009-04-01
  • 作者简介:吴悦，教授，博士，研究方向：计算机应用和智能EDA，E-mail: ywu@shu.edu.cn
  • 基金资助:
    上海市重点学科建设基金(No.J50103) 资助项目

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

  1. School of Computer Engineering and Science, Shanghai University, Shanghai 200072, China
  • Received:2008-04-16 Revised:2008-10-23 Online:2009-04-01 Published:2009-04-01

PDF

1519

被引次数

2

摘要：

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

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

Abstract:

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.

Key words: real-time tasks overload, aperiodic task, dynamic knapsack, greedy algorithm

中图分类号: