• Article
  • | |
  • Metrics
  • |
  • Reference [12]
  • |
  • Related [20]
  • |
  • Cited by
  • | |
  • Comments
    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.

    Reference
    [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
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 24,2003
  • Revised:October 08,2003
You are the first2045233Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063