Real-Time Scheduling Algorithm of Dynamic with Fault-Tolerant in Heterogeneous Distributed Systems

doi:10.16182/j.issn1004731x.joss.201705027

Abstract

Abstract: The traditional heterogeneous distributed real-time scheduling algorithm didn't give consideration to the dynamic behavior of tasks. An aperiodic non-preemptible and heterogeneous distributed dynamic fault-tolerant model and presenting two fault-tolerant scheduling algorithms was proposed based on this model: DRFSA algorithm and DSFSA algorithm. DRFSA(Dynamic and Reliability-driven of hybrid with Fault-tolerant Scheduling Algorithm)algorithm is to improve the system reliability as the scheduling objective through the reasonable scheduling. DSFSA (Dynamic and Schedulability-driven of hybrid with Fault-tolerant Scheduling Algorithm) algorithm is to improve schedulability as the scheduling objective and tries to enhance the schedulability through less task execution time. Both algorithms can dispatch the dynamic real-time tasks in the heterogeneous system andsimultaneously can respond to the task demands as far as possible.

Key words: primary copy/backup copy, dynamic real-time task, heterogeneously distributed, reliability, schedulability

CLC Number:

TP391.9

Dong Chongjie, Chen Yuqiang. Real-Time Scheduling Algorithm of Dynamic with Fault-Tolerant in Heterogeneous Distributed Systems[J]. Journal of System Simulation, 2017, 29(5): 1132-1140.

References

[1] Kieckhafer R M, Walter C J, Finn A M, et al.The MAFT architecture for distributed fault tolerance[J]. IEEE Transactions on Computers (S0018-9340), 2012, 37(4): 398-405.
[2] L H Xu, J Bruck.Deterministic voting in distributed systems using error-correcting codes[J]. IEEE Trans on Parallel and Distributed Systems (S1045-9219), 1998, 9(8): 813-824.
[3] T H Lin, K G Shin.Damage assessment for optimal rollback recovery[J]. IEEE Trans on Computers (S0018-9340), 2013, 47(5): 603-613.
[4] Oh Y, Son SH.Multiprocessor support for real-time fault-tolerant scheduling[J]. Journal of Systems Architecture (S1383-7621), 2011, 57(5): 485-486.
[5] Al-Omari R, Somani A K, Manimaram G.An adaptive scheme for fault-toleran scheduling of soft real-time tasks in mulitprocessor systems[J]. Journal of Parallel and Distributed Computing (S1097-2803), 2015, 65(5): 595-608.
[6] Pathan R M.Fault-tolerant and real-time scheduling for mixed-criticality systems[J]. Real-Time Systems (S0893-3405), 2014, 50(4): 509-547.
[7] C M Krishna.Fault-tolerant scheduling in homogeneous real-time systems[J]. ACM Computing Surveys (S0360-0300), 2014, 46(4): 1-34.
[8] Abhaya Kumar Samal, Rajib Mall, Chittaranjan Tripathy.Fault tolerant scheduling of hard real-time tasks on multiprocessor system using a hybrid genetic algorithm[J]. Swarm and Evolutionary Computation (S2210-6502), 2014, 14(5): 92-105.
[9] 秦啸, 韩宗芬, 庞丽萍, 等. 混合型实时容错调度算法的设计和性能分析[J]. 软件学报, 2000, 11(5): 686-693.
(QIN Xiao, HAN Zong-fen, PANG Li-ping, et al.Design and Performance Analysis of a Hybrid Real-Time Scheduling Algorithm with Fault-Tolerance[J]. Journal of Software, 2000, 11(5): 686-693.)
[10] 曹洁, 曾国荪. 云环境下周期和非周期混合实时任务双容错调度算法[J]. 计算机应用, 2015, 35(3): 648-653.
(CAO Jie, ZENG Guosun.Dual fault-tolerant scheduling algorithm of periodic and aperiodic hybrid real-time tasks in cloud environment[J]. Journal of Computer Applications, 2015, 35(3): 648-653.)
[11] 庞丽萍, 秦啸, 李胜利, 等. NFRL: 一种分布系统的实时容错调度算法[J]. 小型微型计算机系统, 2000, 21(3): 232-234.
(PANG Li-ping, QIN Xiao, LI Sheng-li, et al.NFRL: An Algorithm For Fault-Tolerant Real-Time Scheduling Based on Distributed Systems[J]. Journal of Chinese Mini-Micro Computer Systems, 2000, 21(3): 232-234.)
[12] 张坤龙, 秦啸, 韩宗芬, 等. 异构分布式实时系统中容错调度模型的研究[J]. 华中理工大学学报, 2000, 28(8): 17-18.
(Zhang Kunlong, Qin Xiao, Han Zongfen, et al.Study of the Model for Fault-Tolerant Scheduling in Heterogeneous Distributed Real-Time Systems[J]. Huazhong Univ. of Sci .& Tech, 2000, 28(8): 17-18.)
[13] Guo Hui, Wang Zhi-guang, Zhou Jian-li.Load Balancing Based Process Scheduling with Fault-Tolerance in Heterogeneous Distributed Systems[J]. Chinese Journal of Computers (S0254-4164), 2013, 28(11): 1807-1816.
[14] 罗威, 阳富民, 庞丽萍, 等. 异构分布式系统中实时周期任务的容错调度算法[J]. 计算机学报, 2007, 30(10): 1740-1749.
(LUO Wei, YANG Fu-Min, PANG Li-Ping, et al.A Real-Time Fault-Tolerant Schedul ing Algorithm of Periodic Tasks in Heterogeneous Distributed Systems[J]. Chinese Journal of Computers, 2007, 30(10): 1740-1749.)
[15] 邓建波, 张立臣, 邓惠敏. 异构分布式系统混合型实时容错调度算法[J]. 计算机科学, 2011, 38(3): 87-92.
(DENG Jian-bo, ZHANG Li-chen, DENG Hui-mi.Real-time Scheduling Algorithm of Hybrid with Fault- Tolerant in Heterogeneous Distributed Systems[J]. Computer Science, 2011, 38(3): 87-92.)
[16] Garey R, Johnson D S.Computers and Intractability: a Guide to the Theory of NP-Completeness[M]. New York, USA: W.H. Freeman Company, 2015.
[17] 陈晗鸣, 罗威, 李明辉. 分布式系统中基于主/副版本的实时容错调度综述[J]. 计算机应用研究, 2012, 29(11): 4017-4022.
(CHEN Han-ming, LUO Wei, LI Ming-hui.Survey of primary /backup copy based real-time and fault-tolerant scheduling in distributed systems[J]. Application Research of Computers, 2012, 29(11): 4017-4022.)
[18] 张童, 刘云生, 查亚兵. 面向服务仿真系统的最大可靠性容错调度算法[J]. 系统仿真学报, 2009, 21(4): 1816-1818.
(ZHANG Tong, LIU Yun-sheng, ZHA Ya-bing.Fault-tolerant Scheduling Algorithm for Maximizing Reliability of Service-Oriented Simulation System[J]. Journal of System Simulation, 2009, 21(4): 1816-1818.)
[19] 景维鹏, 吴智博, 刘宏伟, 等. 支持优先级约束任务的容错调度算法[J]. 清华大学学报(自然科学版), 2011, 51(增1): 1440-1444.
(JING Wei-peng, WU Zhi-bo, LIU Hong-wei, et al.Fault-tolerant scheduling algorithm for precedence constrained tasks[J]. Journal of Tsinghua University (Science and Technology), 2011, 51(S1): 1440-1444.)