截止期限约束的实例密集型云服务流调度算法

doi:10.3969/j.issn.1000-0801.2013.12.014

摘要/Abstract

摘要：

针对商业云计算中存在大量实例密集型服务流的问题，提出一种新的云环境下两阶段服务流调度算法。该算法先将用户自定义的全局截止期限分配到系统中的每个实例，再将每个实例的截止期限分配到实例中的每个任务中，最后在服务流执行阶段，动态调整后续任务的截止期限，解决了任务可能存在的未能在其截止期限内完成的时间异常问题。CloudSim仿真结果表明，与现有的算法相比，该算法能满足用户定义的截止期限，节约了执行成本，并减少了资源的竞争率，提高了调度的成功率。

关键词: 云计算, 服务流调度, 时间异常, 截止期限

Abstract:

The problem that there are many intensive-instance serviceflows in business cloud computing environment was aimed to solved, so a new two-phase serviceflows scheduling algorithm was proposed. In the first phase, the global deadline to each instance was assigned, and then the deadline to the each task of instances was assigned. In the serviceflows execution phase, in order to solve the possible problem of time exception which task was not meet its sub-deadline, the algorithm adjusted deadlines of subsequent task dynamically. The experimental results in CloudSim show that the algorithm compared with others algorithm saves the execution cost with meeting the user-defined deadline, avoids the fierce competition of cheaper services and improves the success ratio of the scheduling.

Key words: cloud computing, serviceflows scheduling, ime exception, deadline

刘炜,李陶深,黄汝维. 截止期限约束的实例密集型云服务流调度算法[J]. 电信科学, 2013, 29(12): 87-91.

Wei Liu,Taoshen Li,Ruwei Huang. A Deadline-Constrained Scheduling Algorithm for Intensive-Instance Serviceflows in Cloud Environment[J]. Telecommunications Science, 2013, 29(12): 87-91.

图/表 8

图1

图2

表1

表2

图3

表3

表4

图4

参考文献 12

1	Buyya R , Abramson D , Giddy J ， et al. Economic models for resource management and scheduling in grid computing. Concurrency and Computation: Practice and Experience, 2002,1（4）: 1507～1542
2	Van den Bossche R , Vanmechelen K , Broeckhove J . Cost-optimal scheduling in hybrid IaaS clouds for deadline constrained workloads. Proceedings of in Cloud Computing （CLOUD）IEEE 3rd International Conference, Miami,America, 2010: 228～235
3	Van den Bossche R , Vanmechelen K , Broeckhove J . Cost-efficient scheduling heuristics for deadline constrained workloads on hybrid clouds. Proceedings of in 2011 IEEE Third International Conference on in Cloud Computing Technology and Science （CloudCom）,Athens, Greece, 2011: 320～327
4	Abrishami S , Naghibzadeh M , Epema D H J . Deadline-constrained workflow scheduling algorithms for Infrastructure as a service clouds. Future Generation Computer Systems, 2013,29（1）: 158～169
5	Shen J , Yang Y , Yan J . Adapting P2P based decentralised workflow system swindew-s with web service profile support. Proceedings of the Ninth International Conference on Computer Supported Cooperative Work in Design,Chicago, 2015: 535～540
6	Yang Y , Liu K , Chen J ， et al. Peer-to-peer based grid workflow runtime environment of SwinDeW-G. Proceedings of e-Science and Grid Computing,Bangalore, 2007: 51～58
7	Yu J, Buyya R , Buyya R , Chen K T . Cost-based scheduling of scientific workflow applications on utility grids. Proceedings of International Conference on e-Science and Grid Computing, Melbourne, 2005: 8～147
8	Liu K , Jin H , Chen J ， et al. A compromised-time-cost scheduling algorithm in SwinDeW-C for instance-intensive cost-constrained workflows on a cloud computing platform. International Journal of High Performance Computing Applications, Melbourne, 2010,24（4）: 445～456
9	李文浩，王海洋， . 事务密集型环境下的工作流自适应调度算法. 计算机工程， 2010,36（19）: 84～86
10	晏婧，吴开贵， . 适用于实例密集型云工作流的调度算法. 计算机应用， 2010（11）: 2864～2866
11	Chiu D K W , Li Q , Karlapalem K . A meta modeling approach to workflow management systems supporting exception handling. Information Systems, 1999,24（2）: 159～184
12	罗海滨，范玉顺，吴澄 . 工作流技术综述. 软件学报， 2000,11（7）: 899～907

任务1	任务2	任务3	任务4	任务5	任务6
19 800	27 400	15 800	34 700	14 700	15 700

服务类型	执行指令速度（MIPS）	花费（美元/任务）
1	250	3
2	500	6
3	1 000	12
4	2 000	24

Cloudlet ID	状态	数据中心ID	VM ID	时间（s）	开始时间（s）	完成时间（s）	任务截止期限（s）
t_10,1	成功	2	12	79.2	0	79.2	109.34
t_10,2	成功	2	14	27.4	96.8	124.2	138.57
t_10,3	成功	2	5	31.6	157.4	189.0	191.25
t_10,4	成功	2	3	17.5	131.6	148.1	175.57
t_10,5	成功	2	6	14.7	173.2	187.9	191.25
t_10,6	成功	2	2	15.7	190.5	206.2	208.00

Cloudlet ID	状态	数据中心ID	VM ID	时间（s）	开始时间（s）	完成时间（s）	任务截止期限（s）
t_10,1	成功	2	12	79.2	0	79.2	109.34
t_10,2	成功	2	11	13.7	147.9	188.6	138.57
t_10,3	成功	2	1	31.6	204.4	236.0	241.25
t_10,4	成功	2	7	17.5	193.6	211.1	225.57
t_10,5	成功	2	10	14.7	221.1	235.8	241.25
t_10,6	成功	2	14	15.7	238.4	254.1	258.00

[1]	韩雪. 基于电力大数据的电力骨干通信网络毁伤韧性评估方法[J]. 电信科学, 2023, 39(5): 136-143.
[2]	邬江兴. 论网络技术体制发展范式的变革——网络之网络[J]. 电信科学, 2022, 38(6): 3-12.
[3]	邢文娟, 雷波, 赵倩颖. 算力基础设施发展现状与趋势展望[J]. 电信科学, 2022, 38(6): 51-61.
[4]	邓平科, 张同须, 施南翔, 张童, 邵天竺, 郑韶雯. 星算网络——空天地一体化算力融合网络新发展[J]. 电信科学, 2022, 38(6): 71-81.
[5]	马焜, 徐玲玉, 沈晓萍, 龚志城, 蓝建平, 陈双喜, 钱钧. 云计算中基于Shapley值改进遗传算法的虚拟机调度模型[J]. 电信科学, 2022, 38(12): 1-10.
[6]	刘志勇, 何忠江, 阮宜龙, 单俊峰, 张超. 大数据安全特征与运营实践[J]. 电信科学, 2021, 37(5): 160-169.
[7]	许剑,靳莉. 一种可量化的云计算平台安全评估模型[J]. 电信科学, 2020, 36(7): 163-167.
[8]	罗斯宁,王化龙,李弘宇,彭蔚. 基于改进蚁群算法的云计算用户任务调度算法[J]. 电信科学, 2020, 36(2): 95-100.
[9]	雷波, 刘增义, 王旭亮, 杨明川, 陈运清. 基于云、网、边融合的边缘计算新方案：算力网络[J]. 电信科学, 2019, 35(9): 44-51.
[10]	高永梅,程冠杰. 基于边缘计算的数据密集型服务部署[J]. 电信科学, 2019, 35(7): 87-99.
[11]	鲁泽霖,李强治. 电子商务平台的演化逻辑和运营机理[J]. 电信科学, 2019, 35(7): 152-158.
[12]	黄志兰,樊勇兵,樊宁,陈楠,吴林泽,林宝洪. 云资源池集成虚拟防火墙方案及关键技术[J]. 电信科学, 2019, 35(5): 140-148.
[13]	朱友康,乐光学,杨晓慧,刘建生. 边缘计算迁移研究综述[J]. 电信科学, 2019, 35(4): 74-94.
[14]	吴国威,樊宁,汪来富,王帅,沈军,金华敏. 云环境下基于属性加密体制算法加速方案[J]. 电信科学, 2019, 35(11): 101-107.
[15]	张云勇. 5G将全面使能工业互联网[J]. 电信科学, 2019, 35(1): 1-8.