基于任务复制的多维QoS云计算任务调度

doi:10.11772/j.issn.1001-9081.2014.09.2527

计算机应用 ›› 2014, Vol. 34 ›› Issue (9): 2527-2531.DOI: 10.11772/j.issn.1001-9081.2014.09.2527

基于任务复制的多维QoS云计算任务调度

张巧龙¹,张桂珠¹,²,吴德龙¹

1. 江南大学物联网工程学院，江苏无锡 214122；
2. 轻工过程先进控制教育部重点实验室(江南大学)，江苏无锡 214122

收稿日期:2014-03-20 修回日期:2014-05-24 出版日期:2014-09-01 发布日期:2014-09-30
通讯作者: 张巧龙
作者简介:
张巧龙(1988-),男,河南信阳人,硕士研究生,CCF会员,主要研究方向:云计算、数据挖掘;
张桂珠(1964-),女,江苏无锡人,副教授,主要研究方向:数据挖掘、人工智能、云计算。
基金资助:
国家自然科学基金资助项目;江苏省自然科学基金资助项目

Multi-dimensional QoS cloud task scheduling algorithm based on task replication

ZHANG Qiaolong¹,ZHANG Guizhu¹,²,WU Delong¹

1. School of Internet of Things Engineering, Jiangnan University, Wuxi Jiangsu 214122, China
2. Key Laboratory of Advanced Process Control for Light Industry of Ministry of Education (Jiangnan University), Wuxi Jiangsu 214122, China

Received:2014-03-20 Revised:2014-05-24 Online:2014-09-01 Published:2014-09-30
Contact: ZHANG Qiaolong

摘要/Abstract

摘要：

为了满足云计算环境下用户服务质量(QoS)需求和提高虚拟资源空闲时间段的利用率，提出了一种基于任务复制的多维QoS任务调度策略。首先,构建云资源模型和用户QoS模型，然后根据虚拟资源的利用情况和QoS的满意度对虚拟机进行性能测评，选择综合性能更高的虚拟资源进行任务的分配；在任务执行时为了缩短任务的完成时间，在调度过程中引入了在空闲时间段复制父任务的方式。通过仿真实验将该算法与HEFT、CPOP进行比较，实验结果显示：当用户偏好可靠性执行时，该算法平均可靠性比HEFT和CPOP高；当用户偏好完成时间和费用花费执行时，该算法平均完成时间比HEFT和CPOP少；当用户无偏好执行时，该算法平均完成时间和平均花费均比HEFT和CPOP少。结果表明该算法能有效提高资源利用率和用户的满意度。

Abstract:

Under the cloud environment, in order to take full advantage of idle time of virtual resources and meet the user's Quality of Service (QoS) requirements, a multi-dimensional QoS cloud task scheduling algorithm based on task replication was proposed. First, a cloud resource model and a user's QoS model were built. Then according to the utilization of resources and QoS satisfaction, the virtual resource with higher overall performance was chosen. Simultaneously, this algorithm duplicated a parent task in idle time to reduce the execution time. In the comparison experiments with HEFT (Heterogeneous Earliest Finish Time) and CPOP (Critical Path On a Processor), when the user's preferences perform reliability, the average reliability of the proposed algorithm was higher than that of HEFT and CPOP; when the user's preferences perform makespan and cost, the average makespan of the proposed algorithm was smaller than that of HEFT and CPOP; when the user's preferences perform nothing, the average makespan and cost of the proposed algorithm was smaller than that of HEFT and CPOP. The experimental results indicate that the proposed algorithm can improve satisfaction of customers and utilization of resources.

中图分类号:

张巧龙张桂珠吴德龙. 基于任务复制的多维QoS云计算任务调度[J]. 计算机应用, 2014, 34(9): 2527-2531.

ZHANG Qiaolong ZHANG Guizhu WU Delong. Multi-dimensional QoS cloud task scheduling algorithm based on task replication[J]. Journal of Computer Applications, 2014, 34(9): 2527-2531.

参考文献

［1］RIMAL B P, CHOI E, LUMB I. A taxonomy and survey of cloud computing systems ［C］// NCM'09: Proceedings of the 2009 Fifth International Joint Conference on INC, IMS and IDC. Washington, DC: IEEE Comp Society, 2009:44-51.

［2］MICHAEL R G, DAVID S J. Computers and intractability: a guide to the theory of NP-completeness ［M］. San Francisco: W.H. Freeman Publishers, 1979.

［3］TOPCUOGLUH, HARIRI S, WU M, Performance-effective and low-complexity task scheduling for heterogeneous computing ［J］. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274.

［4］BANSAL S, KUMARP, SINGH K. An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems ［J］. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(6):533-544.

［5］SONG J, GE L. A genetic fuzzy clustering algorithm and application ［J］.Journal of Computer Applications, 2008,28(5): 1197-1199. (宋娇,葛临东.一种遗传模糊聚类算法及其应用［J］. 计算机应用, 2008, 28(5): 1197-1199.)

［6］DU X, JIANG C, XU G, et al.A grid DAG task graph scheduling algorithm based on fuzzy clustering ［J］. Journal of software, 2006, 17(11): 2277-2288. (杜晓丽,蒋昌俊,徐国荣,等.一种基于模糊聚类的网格DAG任务图调度算法［J］.软件学报,2006,17(11):2277-2288.)

［7］HOU E S H, ANSARI N, REN H. A genetic algorithm for multiprocessor scheduling ［J］. IEEE Transactions on Parallel and Distributed Systems, 1994, 5(2): 113-120.

［8］LI J, PENG J. Cloud computing environment task scheduling algorithm based on improved genetic algorithm ［J］. Journal of Computer Applications, 2011, 31(1): 184-186. (李建锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法［J］.计算机应用,2011,31(1):184-186.)

［9］CHEN W-N, ZHANG J. An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements ［J］. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2009, 39(1): 29-43.

［10］YARKHAN A, DONGARRA J J. Experiments with scheduling using simulated annealing in a grid environment ［C］// GRID 2002: Proceedings of the 2002 Grid Computing. Berlin: Springer-Verlag, 2002: 232-242.

［11］BUX M, LESER U. DynamicCloudSim: simulating heterogeneity in computational clouds ［C］// SWEET '13： Proceedings of the 2nd ACM SIGMOD Workshop on Scalable Workflow Execution Engines and Technologies. New York: ACM, 2013: Article No. 1.

［12］CALHEIROS R N, RANJAN R, BELOGLAZOV A, et al.CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms ［J］. Software: Practice and Experience, 2011, 41(1): 23-50.

[1]	杨先凤, 贵红军, 傅春常. 统一计算设备架构下的F-X域预测滤波并行算法[J]. 计算机应用, 2021, 41(2): 486-491.
[2]	李宏梅杨天国张磊莫瑞超许小龙徐占洋. 云环境下面向数据密集型应用的容错性资源配置方法[J]. 计算机应用, 0, (): 0-0.
[3]	龚道永, 宋长明, 刘沙, 漆锋滨. 超级计算机网络引导技术研究与分析[J]. 计算机应用, 2019, 39(6): 1577-1582.
[4]	伏舒存, 付章杰, 邢国稳, 刘庆祥, 许小龙. 移动边缘环境下面向工作流管理的计算迁移方法[J]. 计算机应用, 2019, 39(5): 1523-1527.
[5]	付眸杨贺昆吴唐美何润冯朝胜康胜. 基于Spark Streaming的快速视频转码方法[J]. 计算机应用, 0, (): 0-0.
[6]	赵瑞祥, 郑凯, 刘垚, 王肃, 刘艳, 沈焕学, 周谦豪. 基于申威众核处理器的混合并行遗传算法[J]. 计算机应用, 2017, 37(9): 2518-2523.
[7]	付晨, 钟诚, 叶波. MapReduce并行加速数据流多模式相似性搜索[J]. 计算机应用, 2017, 37(1): 37-41.
[8]	薛胜军, 胡敏达, 许小龙. 云环境下公平性优化的资源分配方法[J]. 计算机应用, 2016, 36(10): 2686-2691.
[9]	薛胜军, 邱爽, 许小龙. 云环境下能耗感知的公平性提升资源调度策略[J]. 计算机应用, 2016, 36(10): 2692-2697.
[10]	关国栋, 滕飞, 杨燕. 基于心跳超时机制的Hadoop实时容错技术[J]. 计算机应用, 2015, 35(10): 2784-2788.
[11]	匡桂娟, 曾国荪, 熊焕亮. 关注用户服务评价反馈的云资源再分配方法[J]. 计算机应用, 2015, 35(7): 1837-1842.
[12]	陈诚, 战荫伟, 李鹰. 基于网页链接分类的PageRank并行算法[J]. 计算机应用, 2015, 35(1): 48-52.
[13]	熊焕亮吴沧海匡桂娟杨文姬. 固定结构约束下并行计算关键路径不变的可扩展方法[J]. 计算机应用, 2014, 34(12): 3417-3423.
[14]	刘智翔宋安平徐磊郑汉垣张武. 多重网格格子Boltzmann方法的并行算法[J]. 计算机应用, 2014, 34(11): 3065-3068.
[15]	张广蓉陈庆奎章刚赵海燕高丽萍霍欢. 基于MapReduce的并行化模糊划分算法[J]. 计算机应用, 2014, 34(11): 3073-3077.

基于任务复制的多维QoS云计算任务调度

Multi-dimensional QoS cloud task scheduling algorithm based on task replication

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics