期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

软件容错模型中的部分抢占实时调度算法 被引量：1

Partial preemptive real-time scheduling algorithm in software fault-tolerant model
在线阅读 下载PDF
导出
摘要 为了减少软件容错模型中实时调度算法的抢占次数,提出了一种部分抢占调度算法(PPA),该算法不仅考虑了如何尽可能多地执行主部分,还考虑了如何减少抢占次数,采用了类似非抢占最早时限优先算法(EDFA)来调度主部分.对不同CPU利用率和软件错误概率的任务集合进行模拟实验,结果表明,PPA算法在可以获得与目前所知的同类算法近似调度性能的同时,还可以在一定情况下极大地减少任务调度间的抢占次数,从而减少了系统中因抢占次数过多带来的额外运行时调度开销等负面因素. A scheduling algorithm called partial-preemptive prediction algorithm（PPA）was proposed in the software fault-tolerant model to reduce the preemption. PPA considers how to reduce the preemption during scheduling as well as how to execute the primaries as many as possible. PPA uses a method similar to non-preemptive earliest deadline first algorithm（EDFA） to schedule the primaries. Simulations on task sets with different CPU utilization and fault possibility show that PPA can obtain the similar scheduling performance as well as the well-known algorithms so far. Moreover, PPA can reduce the preemption dramatically than previous algorithms under certain conditions, thus reduces the negative impact introduced by the preemption such as overhead runtime computation time.
作者 王健 孙建伶 王新宇 杨小虎 王申康
机构地区 浙江大学计算机科学与技术学院
出处 《浙江大学学报（工学版）》 EI CAS CSCD 北大核心 2009年第6期1047-1052,共6页 Journal of Zhejiang University：Engineering Science
关键词 硬实时系统 软件容错 调度算法 抢占 最早时限优先算法 hard real-time system software fault-tolerant scheduling algorithm preemptive on EDFA
分类号 TP393.08 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献12

  • 1BURNS A.Scheduling hard real-time systems:a review[J].Software Engineering Journal,1991,6(3):116-128.
  • 2秦啸,韩宗芬,庞丽萍.基于异构分布式系统的实时容错调度算法[J].计算机学报,2002,25(1):49-56. 被引量：38
  • 3SHIN K G,RAMANATHAN P.Real-Time computing:a new discipline of computer science and engineering[J].Proc IEEE,1994,82(1):6-24.
  • 4RAMANATHAN P.Graceful degradation in real-time control applications using (m,k)-firm guarantee[C]∥Proc IEEE Fault-Tolerant Computing Symp.Seattle:IEEE,1997:132-141.
  • 5HAN C C,SHIN K G,WU J.A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults[J].IEEE Trans on Computer,2003,52(3):362-372.
  • 6李庆华,韩建军,Abbas A Essa,张薇.硬实时系统中基于软件容错的动态调度算法[J].软件学报,2005,16(1):101-107. 被引量：18
  • 7刘东,张春元,李瑞,黄影,李毅.软件容错模型中的容错实时调度算法[J].计算机研究与发展,2007,44(9):1495-1500. 被引量：13
  • 8HORNING J J,LAUER H C,MELLIAR-SMITH P M,et al.A program structure for error detection and recovery[M].London,UK:Springer-Verlag,1974:171-187.
  • 9CHEN Li-ming,AVIZIENIS A.N-Version programming:a fault tolerance approach to reliability of software operation[C]∥Digest of 8th Annual International Symposium on Fault Tolerant Computing.New York:IEEE,1978:3-9.
  • 10王济勇,林涛,王金东,韩光洁,赵海.EDF调度算法抢占行为的研究及其改进[J].电子学报,2004,32(1):64-68. 被引量：12

二级参考文献28

  • 1李庆华,韩建军,Abbas A Essa,张薇.硬实时系统中基于软件容错的动态调度算法[J].软件学报,2005,16(1):101-107. 被引量：18
  • 2韩建军,李庆华,Abbas A.Essa.基于软件容错的动态实时调度算法[J].计算机研究与发展,2005,42(2):315-321. 被引量：13
  • 3[1]Krishna C M,Shin G K.Real-Time Systems [M].Columbus,OH:McGraw-Hill Companies,Inc.1997.73-80.
  • 4[2]Katcher D I,Arakawa H,Strosnider J K.Engineering and analysis of fixed priority schedulers [J].IEEE Transactions on Software Engineering,1993,19(9):920-934.
  • 5[3]Katcher D I.Engineering and analysis of real-time operating systems [D].Ph.D.Dissertation,Dept.of Electrical and Computer Engineering,Carnegie Mellon University,Pittsburgh,PA,August 1994.
  • 6[4]Liu C L,Layland J W.Scheduling algorithms for multiprogramming in a hard real time environment [J].Journal of the ACM,1973,20(1):44-61.
  • 7[5]Jeffay K,Stanat D F,Martel C U.On non-preemptive scheduling of periodic and sporadic tasks [A].Proceedings of the 12th IEEE Symposium on Real-Time Systems [C].San Antonio,Texas,IEEE Computer Society Press,December 1991.129-139.
  • 8[6]Secka A.Automatic debugging of a real-time system using analysis and prediction of various scheduling algorithm implementations [D].Dept.of Electrical and Computer Engineering,University of Maryland,College Park,MD,November 2000.
  • 9[7]Kettler K A,Katcher D I,Strosnider J K.A modeling methodology for real-time/multimedia operating systems [A].Proceedings of the Real-Time Technology and Applications Symposium [C].Chicago,Illinois,IEEE Computer Society Press,May 1995.
  • 10[8]Michalewica Z,Janikow C.Handling constraints in genetic algorithms [A].Proceedings of the fourth international conference on genetic algorithms [C].San Mateo,CA,Morgan Kaufmann Publishers,1991.151-157.

共引文献67

同被引文献13

  • 1Sha L, Abdelzaher TF, Arz6n KE, Ccrvin A, Baker TP, Bums A, Buttazzo GC, Caccamo M, Lchoczky JP, Mok AK. Real time scheduling theory: A historical perspective. Real-Time Systems, 2004,28(2-3):101-155. Idol: 10.1023/B:TIME.0000045315.61234. le].
  • 2Han CC, Shin KG, Wu J. A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults. IEEE Trans. on Computers, 2003,52(3):362-372. [doi: 10.1109/TC.2003.1183950].
  • 3李庆华,韩建军,EssaAA,张薇.硬实时系统中基于软件容错的动态调度算法.软件学报,2005,16(1):101-107.http://www.jos.org.cn/1000-9825/16/101.htm.
  • 4王健,孙建伶,王新宇,杨小虎,王申康,陈俊波.容错多处理机中一种高效的实时调度算法.软件学报,2009,20(10):2628-2636.http://www.jos.org.cn/1000-9825/577.htm [doi: 10.3724/SP. J.1001.2009.00577].
  • 5Punnekkat S. Schedulability analysis for fault-tolerant real-time systems [Ph.D. Thesis]. York: University of York, 1997.
  • 6Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 1973, 20(1):46-61. [doi: 10.1145/321738.321743].
  • 7Audsley NC, Burns A, Wellings AJ. Deadline monotonic scheduling theory and application. Control Engineering Practice, 1993, 1(1):71-78. [doi: 10.1016/0967-0661(93)92105-D].
  • 8Wang Y, Saksena M. Scheduling fixed-priority tasks with preemption threshold. In: Proc. of the 6th Int'l Conf. on Real-Time Computing Systems and Applications. 1999.328-335.
  • 9Regehr J. Scheduling tasks with mixed preemption relations for robustness to timing faults. In: Proe. of the IEEE Real-Time Systems Symp. Texas: IEEE Computer Society Press, 2002.315-326.
  • 10Chen JX. Extensions to fixed priority with preemption threshold and reservation-based scheduling [Ph.D. Thesis]. Waterloo: University of Waterloo, 2005.

引证文献1

二级引证文献5

浙江大学学报（工学版）
2009年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部