云环境下周期和非周期混合实时任务双容错调度算法

doi:10.11772/j.issn.1001-9081.2015.03.648

计算机应用 ›› 2015, Vol. 35 ›› Issue (3): 648-653.DOI: 10.11772/j.issn.1001-9081.2015.03.648

云环境下周期和非周期混合实时任务双容错调度算法

曹洁^1,2, 曾国荪^1,2

1. 同济大学计算机科学与技术系, 上海 200092;
2. 国家高性能计算机工程技术中心同济分中心, 上海 200092

收稿日期:2014-10-08 修回日期:2014-11-06 出版日期:2015-03-10 发布日期:2015-03-13
通讯作者: 曹洁
作者简介:曹洁(1980-),男,河南新乡人,博士研究生,CCF会员,主要研究方向:并行分布处理、云计算;曾国荪(1964-),男,江西吉安人,教授,博士,主要研究方向:并行分布计算、可信网络软件
基金资助:
国家863计划项目(2009AA012201);国家自然科学基金资助项目(61272107,61202173,61103068);上海市优秀学科带头人计划项目(10XD1404400);华为创新研究计划项目(IRP-2013-12-03);高效能服务器和存储技术国家重点实验室开放基金资助项目(2014HSSA10)

Dual fault-tolerant scheduling algorithm of periodic and aperiodic hybrid real-time tasks in cloud environment

CAO Jie^1,2, ZENG Guosun^1,2

1. Department of Computer Science and Technology, Tongji University, Shanghai 200092, China;
2. Tongji Branch, National Engineering and Technology Center of High Performance Computer, Shanghai 200092, China

Received:2014-10-08 Revised:2014-11-06 Online:2015-03-10 Published:2015-03-13

摘要/Abstract

摘要：

云环境中的处理机故障已成为云计算不可忽视的问题,容错成为设计和发展云计算系统的关键需求。针对一些容错调度算法在任务调度过程中调度效率低下以及任务类型单一的问题,提出一种处理机和任务主副版本分组的容错调度方法;并给出了副版本可重叠执行的判定方法,以及任务最坏响应时间的计算公式。通过实验和分析表明,和以前算法相比,将处理机分成两组分别执行任务主版本和任务副版本,减少了任务调度所需进行可调度测试的时间,增加了副版本重叠执行的机会,减少了所需的处理机个数,对提高系统处理机的利用率和容错调度的效率具有重要的意义。

关键词: 云计算, 周期任务, 非周期任务, 容错, 实时调度

Abstract:

The problem of cloud computing processors failure cannot be ignored in the cloud environment. Fault-tolerance becomes a key requirement in the design and development of cloud computing systems. Aiming at the problem of low scheduling efficiency and single type of task in most fault-tolerant scheduling algorithms, the fault-tolerant scheduling method based on processors, primary-backup copies of hybrid tasks grouped was proposed. A method to determine whether two backup copies can overlap was presented. What's more, the calculation formulas of periodic task worst-case response time and completion time of aperiodic tasks preemptive execution were given. The simulation result shows that the proposed algorithm has a remarkable saving of cloud computing system processors needed and scheduling computation time compared with Hybrid real time task Fault Tolerant Scheduling (HFTS) algorithm. It is of great significance for improving the reliability of cloud system and the schedulability of real-time tasks set, as well as the processor efficiency.

Key words: cloud computing, periodic task, aperiodic task, fault tolerance, real-time scheduling

中图分类号:

TP301.6

曹洁, 曾国荪. 云环境下周期和非周期混合实时任务双容错调度算法[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.

参考文献

[1] MANIMARAN G, MURTHY C. A fault-tolerant dynamic scheduling algorithm for multiprocessor real-time systems and its analysis[J]. IEEE Transactions on Parallel and Distributed Systems, 1998,9(11):1137-1152.
[2] AL-OMARI R, SOMANI A K, MANIMARAN G. Efficient overloading techniques for primary-backup scheduling in real-time systems[J]. Journal of Parallel and Distributed Computing, 2004,64(5):629-648.
[3] LIU C, LAYLAND J. Scheduling algorithms for multiprogramming in a hard real-time environment[J]. Journal of the ACM, 1973, 20(1):46-61.
[4] DHALL S, LIU C. On a real-time scheduling problem[J]. Operations Research, 1978,26(1):127-140.
[5] BERTOSSI A, MANCINI L, FEDERICO R. Fault-tolerant rate-monotonic first-fit scheduling in hard-real-time systems[J]. IEEE Transactions on Parallel and Distributed Systems, 1999,10(9):934-945.
[6] ZHU X, ZHU J, MA M. Fault-tolerant scheduling for real-time tasks with QoS requirements on heterogeneous clusters[J]. Journal of Software, 2011,22(7):1440-1456.(朱晓敏,祝江汉,马满好.异构集群系统中具有QoS需求的实时任务容错调度[J].软件学报,2011,22(7):1440-1456.)
[7] LUO W, YANG F, PANG L,et al. A real-time fault-tolerant scheduling algorithm for distributed systems based on deferred active backup-copy[J]. Journal of Computer Research and Development, 2007,44(3):521-528.(罗威,阳富民,庞丽萍,等.基于延迟主动副版本的分布式实时容错调度算法[J].计算机研究与发展,2007,44(3):521-528.)
[8] STROSNIDER J, LEHOCZKY J, SHA L. The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments[J]. IEEE Transactions on Computers, 1995,44(1):73-91.
[9] LEHOCZKY J, RAMOS-THUEL S. An optimal algorithm for scheduling soft aperiodic tasks in fixed-priority preemptive systems[C]//Proceedings of the 13th Real-Time Systems Symposium. Piscataway:IEEE, 1992:110-123.
[10] YANG C, GUI W, JI L. A fault-tolerant scheduling algorithm of hybrid real-time tasks based on multiprocessors[J]. Chinese Journal of Computers, 2003,26(11):1479-1486.(阳春华,桂卫华,计莉.基于多处理机的混合实时任务容错调度[J].计算机学报,2003,26(11):1479-1486.)
[11] JOSEPH M, PANDYA P. Finding response times in a real-time system[J]. The Computer Journal, 1986,29(3):390-395.
[12] BERTOSSI A A, MANCINI L V, MENAPACE A. Scheduling hard-real-time tasks with backup phasing delay[C]//Proceedings of the IEEE International Symposium on Distributed Simulation and Real-Time Applications. Washington, DC:IEEE Computer Society, 2006:1657-1662.
[13] CALHEIROS R, RANJAN R, de ROSE C A F,et al. Cloudsim:a novel framework for modeling and simulation of cloud computing infrastructures and services[J]. arXiv preprint arXiv:0903.2525, 2009. CALHEIROS R, RANJAN R, de ROSE C A F,et al. CloudSim:a novel framework for modeling and simulation of cloud computing infrastructures and services[EB/OL].[2014-08-06]. http://www.docin.com/p-275250546.html.
[14] BURCHARD A, LIEBEHERR J, OH Y,et al. New strategies for assigning real-time tasks to multiprocessor systems[J]. IEEE Transactions on Computers, 1995,44(12):1429-1442.

[1]	杨龙海, 王学渊, 蒋和松. 改进SM2签名方法的区块链数字签名方案[J]. 计算机应用, 2021, 41(7): 1983-1988.
[2]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[3]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[4]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[5]	李静, 罗金飞, 李炳超. 主动容错副本存储系统的可靠性分析模型[J]. 计算机应用, 2021, 41(4): 1113-1121.
[6]	刘宇, 朱朝阳, 李金泽, 劳源基, 覃团发. 检测型的联盟区块链共识算法d-PBFT[J]. 计算机应用, 2021, 41(3): 756-762.
[7]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[8]	林腾涛, 查思明, 陈蕾, 龙显忠. 图趋势过滤诱导的噪声容错多标记学习模型[J]. 计算机应用, 2021, 41(1): 8-14.
[9]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[10]	陈程军, 毛莺池, 王绎超. 基于激活-熵的分层迭代剪枝策略的CNN模型压缩[J]. 计算机应用, 2020, 40(5): 1260-1265.
[11]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.
[12]	李靖, 景旭, 杨会君. 基于实用拜占庭容错算法的区块链电子计票方案[J]. 计算机应用, 2020, 40(4): 954-960.
[13]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[14]	王庆永, 毛莺池, 王绎超, 王龙宝. 基于多微云协作的计算任务卸载[J]. 计算机应用, 2020, 40(2): 328-334.
[15]	刘福鑫, 李劲巍, 王熠弘, 李琳. 基于Kubernetes的云原生海量数据存储系统设计与实现[J]. 计算机应用, 2020, 40(2): 547-552.

云环境下周期和非周期混合实时任务双容错调度算法

Dual fault-tolerant scheduling algorithm of periodic and aperiodic hybrid real-time tasks in cloud environment

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics