软件容错模型中的部分抢占实时调度算法

doi:10.3785/j.issn.1008-973X.2009.

2009, Vol. 43

Issue (6): 1047-1052 DOI: 10.3785/j.issn.1008-973X.2009.

计算机技术、自动化技术

软件容错模型中的部分抢占实时调度算法

王健,孙建伶,王新宇,杨小虎,王申康

（浙江大学计算机科学与技术学院, 浙江杭州 310027）

Partial preemptive real-time scheduling algorithm in software fault-tolerant model

WANG Jian, SUN Jian-ling, WANG Xin-yu, YANG Xiao-hu, WANG Shen-kang

(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China)

全文: PDF(663 KB)

摘要：

为了减少软件容错模型中实时调度算法的抢占次数,提出了一种部分抢占调度算法(PPA),该算法不仅考虑了如何尽可能多地执行主部分,还考虑了如何减少抢占次数,采用了类似非抢占最早时限优先算法(EDFA)来调度主部分.对不同CPU利用率和软件错误概率的任务集合进行模拟实验,结果表明,PPA算法在可以获得与目前所知的同类算法近似调度性能的同时,还可以在一定情况下极大地减少任务调度间的抢占次数,从而减少了系统中因抢占次数过多带来的额外运行时调度开销等负面因素.

关键词： 硬实时系统; 软件容错; 调度算法; 抢占; 最早时限优先算法

Abstract:

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.

Key words: hard real-time system software fault-tolerant scheduling algorithm preemptive on EDFA

出版日期: 2009-07-01

TP39308

通讯作者: 孙建伶，男，教授. E-mail: sunjl@zju.edu.cn

作者简介: 王健（1982-），男，四川攀枝花人，博士生，主要从事实时容错调度算法研究.

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	王健
	孙建伶
	王新宇
	等

引用本文:

王健, 孙建伶, 王新宇, 等. 软件容错模型中的部分抢占实时调度算法[J]. J4, 2009, 43(6): 1047-1052.

WANG Jian, SUN Jian-Ling, WANG Xin-Yu, et al. Partial preemptive real-time scheduling algorithm in software fault-tolerant model. J4, 2009, 43(6): 1047-1052.

链接本文:

http://www.zjujournals.com/xueshu/eng/CN/10.3785/j.issn.1008-973X.2009. 或 http://www.zjujournals.com/xueshu/eng/CN/Y2009/V43/I6/1047

［1］ BURNS A. Scheduling hard real-time systems: a review ［J］. Software Engineering Journal, 1991, 6(3): 116128．
［2］秦啸, 韩宗芬, 庞丽萍. 基于异构分布式系统的实时容错调度算法
[J].计算机学报, 2002, 25(1): 4956．
QIN Xiao, HAN Zong-fen, PANG Li-ping. Real-Time scheduling with fault-tolerance in heterogeneous distributed systems ［J］. Chinese Journal of Computers, 2002, 25(1): 4956．
［3］ SHIN K G, RAMANATHAN P. Real-Time computing: a new discipline of computer science and engineering ［J］. Proc IEEE, 1994, 82(1): 624．
［4］ RAMANATHAN P. Graceful degradation in real-time control applications using (m, k) – firm guarantee ［C］∥Proc IEEE Fault-Tolerant Computing Symp. Seattle: IEEE, 1997:132141．
［5］ HAN 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): 362372．
［6］李庆华, 韩建军, ABBAS A E, 等. 硬实时系统中基于软件容错的动态调度算法［J］. 软件学报, 2005, 16(1): 101107.
LI Qing-hua, HAN Jian-jun, ABBAS A E, et al. Dynamic scheduling algorithms with software fault tolerance in hard real-time systems ［J］. Journal of Software, 2005, 16(1): 101107．
［7］刘东, 张春元, 李瑞, 等. 软件容错模型中的容错实时调度算法
[J]. 计算机研究与发展, 2007, 44(9): 14951500.
LIU Dong, ZHANG Chun-yuan, LI Rui, et al. Fault-tolerant real-time scheduling algorithm in software fault-tolerant module ［J］. Journal of Computer Research and Development, 2007, 44(9): 14951500．
［8］ HORNING 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: 171187．
［9］ CHEN 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: 39．
［10］王济勇, 林涛, 王金东, 等. EDF调度算法抢占行为的研究及其改进［J］. 电子学报, 2004, 32(1): 6468．
WANG Ji-yong, LIN Tao, WANG Jin-dong, et al. Research on preemptions of preemptive EDF and improvement on its performance ［J］. Acta Electronica Sinica, 2004, 32(1): 6468．
［11］ JEFFAY K, STANAT D F, MARTEL C U. On non-preemptive scheduling of periodic and sporadic tasks ［C］∥Proceedings of the 12 th IEEE Symposium on Real-Time Systems. San Antonio: IEEE, 1991: 129139．
［12］ LIU C L, LAYLAND J W. Scheduling algorithms for multi-programming in a hard real-time environment ［J］. Journal of ACM, 1973, 20(1): 4661．

[1]	寿涌毅, 彭晓峰, 李菲, 赖昌涛. 抢占式资源受限项目调度问题的遗传算法[J]. 浙江大学学报(工学版), 2014, 48(8): 1473-1480.
[2]	刘加海,杨茂林,雷航,廖勇. 共享资源约束下多核实时任务分配算法[J]. J4, 2014, 48(1): 113-117.
[3]	朱予辰,冯冬芹,褚健. 基于EPA的块数据流通信调度与控制[J]. J4, 2012, 46(11): 2097-2102.
[4]	刘加海,杨茂林. 基于多核处理器平台的公平调度算法[J]. J4, 2011, 45(9): 1566-1570.
[5]	平玲娣王继民陈小平刘祖根. 基于子图归并的全局优化调度算法[J]. J4, 2007, 41(11): 1823-1827.
[6]	陈晓峰平玲娣陈健. 一种对数自适应队列调度算法[J]. J4, 2006, 40(3): 381-386.
[7]	尹红霞王智孙优贤. 一种基于弱实时的加权公平队列调度算法[J]. J4, 2005, 39(10): 1490-1495.

Viewed

Full text

Abstract

Cited

Shared

Discussed