异构分布式系统动态实时容错调度启发式算法

doi:10.16182/j.issn1004731x.joss.201705027

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (5): 1132-1140.doi: 10.16182/j.issn1004731x.joss.201705027

异构分布式系统动态实时容错调度启发式算法

董崇杰¹, 陈俞强^1,2

1.东莞职业技术学院,广东东莞 523808;
2.广东工业大学,广东广州 510006

收稿日期:2016-04-29 修回日期:2016-08-23 出版日期:2017-05-08 发布日期:2020-06-03
作者简介:董崇杰(1982-),男,山东菏泽,硕士,副教授,研究方向为数据库技术。
基金资助:
国家自然科学基金(61106019),广东省高等学校优秀青年教师培养计划(YQ2015232),广东省科技计划项目(2014A010103002),东莞市社会科技发展项目(2013108101045), 2013108101046)

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

Dong Chongjie¹, Chen Yuqiang^1,2

1. Dongguan Polytechnic, Dongguan 523808, China;
2. Guangdong University of Technology, Guangzhou 510006, China

Received:2016-04-29 Revised:2016-08-23 Online:2017-05-08 Published:2020-06-03

摘要/Abstract

摘要： 传统的异构分布式实时调度算法基本没有考虑任务的动态特性。提出一种非周期不可抢占式异构分布式的动态容错模型,在该模型上基于不同调度需求给出两种不同容错调度算法：DRFSA(Dynamic and Reliability-driven of hybrid with Fault-tolerant Scheduling Algorithm)算法与DSFSA(Dynamic and Schedulability-driven of hybrid with Fault-tolerant Scheduling Algorithm)算法。DRFSA算法以提高可靠性代价为调度目标,通过合理调度提高系统可靠性。DSFSA算法以可调度性为调度目标,通过减少任务执行时间来增加系统可调度性。算法能够在异构系统中调度动态的实时任务,且能够尽可能响应任务需求。

关键词: 基/副版本, 动态实时任务, 异构分布式, 可靠性, 可调度性

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

中图分类号:

TP391.9

董崇杰, 陈俞强. 异构分布式系统动态实时容错调度启发式算法[J]. 系统仿真学报, 2017, 29(5): 1132-1140.

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.

参考文献

[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.)

异构分布式系统动态实时容错调度启发式算法

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价

[1]	高宏鼐, 付丽疆, 夏倩, 郭亚. 可观测度在光合作用模型性能评估中的应用[J]. 系统仿真学报, 2022, 34(6): 1330-1342.
[2]	李炜, 葛振福, 申富媛, 龚建兴. 基于FDRE的3D威亚编码器故障检测与容错控制[J]. 系统仿真学报, 2019, 31(4): 740-749.
[3]	杜海东, 曹军海, 申莹, 滕尚儒. 非完美维修策略下退化系统可靠性仿真评估研究[J]. 系统仿真学报, 2018, 30(8): 2834-2840.
[4]	王爱珍, 吕勋. 基于非完美调试和测试工作量的软件可靠性研究[J]. 系统仿真学报, 2018, 30(7): 2593-2599.
[5]	夏新涛, 常振, 李云飞. 轴承振动性能预报及可靠性分析[J]. 系统仿真学报, 2018, 30(4): 1390-1399.
[6]	孙晓哲, 陈宗基, 顾永亮. 基于动态重构的余度容错飞控计算机系统研究[J]. 系统仿真学报, 2018, 30(10): 3957-3964.
[7]	李成兵, 郝羽成, 王文颖. 城市群复合交通网络可靠性研究[J]. 系统仿真学报, 2017, 29(3): 565-571.
[8]	卢睿, 李林瑛. 有滞留时间约束的单臂集束型装备调度研究[J]. 系统仿真学报, 2016, 28(8): 1776-1782.
[9]	方永锋, 陈建军. 可修复k/n表决系统随时间的生命状态分析与仿真[J]. 系统仿真学报, 2016, 28(8): 1846-1853.
[10]	刘旭南, 赵丽娟, 盖东民, 杜章雨, 郝良英. 基于采煤机可靠性的智能牵引调速系统研究[J]. 系统仿真学报, 2016, 28(7): 1601-1608.
[11]	迟玉伦, 李郝林. 基于Bayes方法的机床主轴加速寿命试验可靠性研究[J]. 系统仿真学报, 2016, 28(7): 1667-1672.
[12]	杜海东, 曹军海, 吴纬, 徐丹. 基于仿真的复杂系统可靠性冗余分配优化设计[J]. 系统仿真学报, 2016, 28(3): 648-653.
[13]	王大勇, 王慧. 基于仿真优化的掘进机铲板综合性能研究[J]. 系统仿真学报, 2016, 28(2): 434-441.
[14]	张银龙, 李波, 卞士川. 基于ANSYS的装配式公路钢桥可靠性分析[J]. 系统仿真学报, 2015, 27(8): 1907-1913.