基于优先级表的实时调度算法及其实现
作者:
基金项目:

Supported bythe National Natural Science Foundation of China under Grant Nos.60373055, 60374058(国家自然科学基金)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [12]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    讨论了综合考虑任务的截止期和价值两个特征参数的优先级表设计方法,提出了EDV(earliest deadline value)与VED(value earliest deadline)两种不同的基于优先级表的实时任务调度算法,并且利用多重链表给出了这两种算法的实现,包括任务接收策略与任务完成/夭折策略的算法实现.这种优先级表设计方法及其基于多重链表的实现方法也适用于对任务的其他两种甚至3种不同特征参数之间的综合.基于累积实现价值率、加权截止期保证率与差分截止期保证率3个方面,分析了VED算法与EDV算法的性能,实验结果表明,在所有负载条件下VED算法与EDV算法相对于EDF(earliest deadline first)算法与HVF(highest value first)算法都有很大的性能改进.

    Abstract:

    This paper proposes a new scheduling scheme based on priority table design by integrating two characteristic parameters (i.e. deadline and value) of a task. Two real-time scheduling algorithms from the scheme are presented: earliest deadline value (EDV) and value earliest deadline (VED). Furthermore, how to implement the two algorithms using multi-linked lists is given, including task acceptance policy and task completion/abortion policy. This scheme can also be applied to integrate two other characteristic parameters or even three characteristic parameters of a task. Based on hit value ratio, weighted guarantee ratio and differentiated guarantee ratio, the performance of the VED and EDV algorithms are analyzed, the experimental results show that the VED and EDV algorithms can improve the performance compared to the classical EDF (earliest deadline first) and HVF (highest value first) algorithms under all workload conditions.

    参考文献
    [1]Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 1973,20(1):46~61.
    [2]Jensen ED, Locke CD, Toduda H. A time-driven scheduling model for real-time operating systems. In: Proc. of the 6th IEEE Real-Time Systems Symp. San Diego: IEEE Computer Society Press, 1985.112~122.
    [3]Buttazzo G, Spuri M, Sensini F. Value vs. deadline scheduling in overload conditions. In: Proc. of the 19th IEEE Real-Time Systems Symp. Pisa: IEEE Computer Society Press, 1995.90~99.
    [4]Biyabani SR, Stankovic JA, Ramamritham K. The integration of deadline and criticalness in hard real-time scheduling. In: Proc. of the 9th IEEE Real-Time Systems Symp. Huntsville: IEEE Computer Society Press, 1988. 152~160.
    [5]Tseng S-M, Chin YH, Yang W-P. Scheduling value-based transactions in real-time main-memory databases. In: Lin KJ, ed. Proc.of the 1st Int'l Workshop on Real-Time Databases: Issues and Applications. Newport Beach: Kluwer Academic Publishers, 1996.111~117.
    [6]Burns A, Prasad D, Bondavalli A, Giandomenico FD, Ramamritham K, Stankovic J, Strigini L. The meaning and role of value in scheduling flexible real-time systems. Journal of Systems Architecture, 2000,46(4):305~325.
    [7]Huang JD, Stankovic JA, Towesly D, Ramamritham K. Experimental evaluation of real-time transaction processing. In: Proc. of the 10th Real-Time Systems Symp. Santa Monica: IEEE Computer Society Press, 1989. 144~153.
    [8]Wendorf JW. Implementation and evaluation of a time-driven scheduling processor. In: Proc. of the 9th IEEE Real-Time Systems Symp. Huntsville: IEEE Computer Society Press, 1988. 172~180.
    [9]Carlson J, Lennvall T, Fohler G. Value-based overload handling of aperiodic tasks in offline scheduled real-time systems. In:Work-in-Progress Session of the 13th Euromicro Conf. on Real-Time Systems. IEEE Computer Society Press, 2001.46~49.
    [10]Lennvall T, Carlson J, Fohler G. Value-based overload handling in distributed offline scheduled real-time systems. Technical Report, Department of Computer Engineering, Malardalen University, 2001.
    [11]Jin H, Wang HA, Wang Q, Dai GZ. An integrated design method of task priority. Journal of Software, 2003,14(3):376~382 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/14/376.htm
    [12]金宏,王宏安,王强,戴国忠.一种任务优先级的综合设计方法.软件学报,2003,14(3):376~382.http:∥www.jos.org.cn/1000-9825/14/376.htm
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王永炎,王强,王宏安,金宏,戴国忠.基于优先级表的实时调度算法及其实现.软件学报,2004,15(3):360-370

复制
分享
文章指标
  • 点击次数:4847
  • 下载次数: 8474
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2003-03-24
  • 最后修改日期:2003-10-08
文章二维码
您是第19939242位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号