[1]黄迎春,邓庆绪.基于副版本零调整策略的实时任务主副版本容错调度[J].东南大学学报(自然科学版),2018,48(2):260-264.[doi:10.3969/j.issn.1001-0505.2018.02.011]
 Huang Yingchun,Deng Qingxu.Fault-tolerant scheduling for real-time tasks based on non-adjusting strategy of alternate[J].Journal of Southeast University (Natural Science Edition),2018,48(2):260-264.[doi:10.3969/j.issn.1001-0505.2018.02.011]
点击复制

基于副版本零调整策略的实时任务主副版本容错调度()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
48
期数:
2018年第2期
页码:
260-264
栏目:
计算机科学与工程
出版日期:
2018-03-20

文章信息/Info

Title:
Fault-tolerant scheduling for real-time tasks based on non-adjusting strategy of alternate
作者:
黄迎春12邓庆绪1
1东北大学计算机科学与工程学院, 沈阳 110169; 2沈阳理工大学信息科学与工程学院, 沈阳 110159
Author(s):
Huang Yingchun 12 Deng Qingxu2
1School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China
2School of Information Science and Engineering, Shenyang Ligong University, Shenyang 110159, China
关键词:
实时任务 容错调度 BEDF-NENF算法 主副版本 副版本调整时间
Keywords:
real-time task fault-tolerant scheduling BEDF-NENF(backward earliest deadline first and non-adjusting earliest notification-time first)algorithm primary-alternate alternate reconstruction time
分类号:
TP302
DOI:
10.3969/j.issn.1001-0505.2018.02.011
摘要:
为了降低硬实时周期性任务主副版本容错调度的副版本调整开销,提出了一种BEDF-NENF容错调度算法.采用反向最早截止期优先(BEDF)策略为副版本预分配处理器时间,运行时则采用零调整最早通知时间优先(NENF)策略调度主版本.结果表明,BEDF-NENF算法能够按照最后机会策略调度副版本.当主版本错误概率不大于0.05时,BEDF-NENF算法的副版本调整平均比较次数和副版本调整时间比率均为0,与BEDF-RM算法、BEDF-EDF算法、BEDF-ENF算法的主版本完成率之差约为1%. BEDF-NENF算法不仅能够取得与同类调度算法接近的主版本完成率,而且能够通过省略副版本重新调整操作来降低调度的复杂性,节省调度时间.
Abstract:
To reduce the adjusting overhead of alternates in fault-tolerant scheduling for hard real-time periodic tasks, the BEDF-NENF(backward earliest deadline first and non-adjusting earliest notification-time first)algorithm of fault-tolerant scheduling is proposed. The processor time of alternates is pre-allocated by the backward earliest deadline first(BEDF)strategy, while at the run time the primary version is scheduled by the non-adjusting earliest notification-time first(NENF)strategy. The results show that the BEDF-NENF algorithm allocate alternates by the latest chance strategy. When the error probability of primary version is not greater than 0.05, both the average comparison number and the time ratio of alternates reconstruction of the BEDF-NENF algorithm equal to zero. And the differences of the success ratio of the primary version between the BEDF-NENF algorithm and the scheduling algorithms such as the BEDF-RM(backward earliest deadline first and rate monotonic)algorithm, the BEDF-EDF(backward earliest deadline first and earliest deadline first)algorithm, the BEDF-ENF(backward earliest deadline first and earliest notification-time first)algorithm are about 1%. The BEDF-NENF algorithm can not only achieve the approximate success ratio of the primary version compared with the similar scheduling algorithms, but also simplify the complexity of scheduling and save time of scheduling by omitting the reconstruction operation of alternates.

参考文献/References:

[1] Liestman A L, Campbell R H. A fault-tolerant scheduling problem [J]. IEEE Transactions on Software Engineering, 1986, 12(11): 1089-1095. DOI:10.1109/tse.1986.6312999.
[2] Chetto H, Chetto M. Some results of the earliest deadline scheduling algorithm [J]. IEEE Transactions on Software Engineering, 1989, 15(10): 1261-1269. DOI:10.1109/tse.1989.559777.
[3] Han C C, Kang G S, Wu J. A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults [J]. IEEE Transactions on Computers, 2003, 52(3):362-372.
[4] Liu D, Xing W, Li R, et al. A fault-tolerant real-time scheduling algorithm in software fault-tolerant module [J]. Journal of Computer Research & Development, 2007, 44(9): 961-964.DOI:10.1007/978-3-540-72590-9_145.
[5] Pathan R M, Jonsson J. Exact fault-tolerant feasibility analysis of fixed-priority real-time tasks[C]// IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Macau, China, 2010: 265-274.DOI:10.1109/rtcsa.2010.24.
[6] Huang Y, Deng Q. Fault-tolerant scheduling of primary-alternate version based on variable workload[C]// International Symposium on System and Software Reliability. Shanghai, China, 2017: 119-128.DOI:10.1109/isssr.2016.027.
[7] Pathan R M. Fault-tolerant and real-time scheduling for mixed-criticality systems [J]. Real-Time Systems, 2014, 50(4): 509-547.DOI:10.1007/s11241-014-9202-z.
[8] Lin J, Cheng A M K, Steel D, et al. Scheduling mixed-criticality real-time tasks with fault tolerance[C]// The Workshop on Mixed Criticality. Rome, Italy, 2014: 39-44.
[9] Thekkilakattil A, Dobrin R, Punnekkat S. Fault tolerant scheduling of mixed criticality real-time tasks under error bursts [J]. Procedia Computer Science, 2015, 46: 1148-1155.DOI:10.1016/j.procs.2015.01.027.
[10] Huang P, Yang H, Thiele L. On the scheduling of fault-tolerant mixed-criticality systems[C]// 2014 51st ACM/EDAC/IEEE Design Automation Conference. San Francisco, USA, 2014:1-6.DOI:10.1109/dac.2014.6881458.
[11] Liu C L,Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment [J]. Journal of the Association for Computing Machinery, 1973: 20(1): 46-61.DOI:10.1145/321738.321743.

备注/Memo

备注/Memo:
收稿日期: 2017-08-28.
作者简介: 黄迎春(1976—),男,博士生;邓庆绪(联系人),男,教授,博士生导师, dengqx@mail.neu.edu.cn.
基金项目: 国家自然科学基金资助项目(61472072)、国家重点基础研究发展计划(973计划)预研基金资助项目(2014CB360509)、沈阳理工大学重点实验室开放基金资助项目(4771004kfs46).
引用本文: 黄迎春,邓庆绪.基于副版本零调整策略的实时任务主副版本容错调度[J].东南大学学报(自然科学版),2018,48(2):260-264. DOI:10.3969/j.issn.1001-0505.2018.02.011.
更新日期/Last Update: 2018-03-20