面向WaaS平台的多工作流容错调度策略

doi:10.19665/j.issn1001-2400.20241005

西安电子科技大学学报 ›› 2025, Vol. 52 ›› Issue (1): 181-195.doi: 10.19665/j.issn1001-2400.20241005

• 计算机科学与技术 & 网络空间安全 • 上一篇下一篇

面向WaaS平台的多工作流容错调度策略

支文韬¹^,²(), 赵辉¹^,²^,³(), 孟繁鑫¹(), 王静¹(), 万波¹^,²^,³(), 王泉¹^,³()

1.西安电子科技大学计算机科学与技术学院,陕西西安 710071
2.西安电子科技大学杭州研究院,浙江杭州 311231
3.陕西省智能人机交互与可穿戴技术重点实验室,陕西西安 710071

收稿日期:2024-01-06 出版日期:2024-10-24 发布日期:2024-10-24
通讯作者: 王静(1981—),女,副教授,博士,E-mail:wangjing@mail.xidian.edu.cn
作者简介:支文韬(1999—),男,西安电子科技大学硕士研究生,E-mail:22031212306@stu.xidian.edu.cn；
赵辉(1983—),男,副教授,博士,E-mail:hzhao@mail.xidian.edu.cn；
孟繁鑫(1998—),男,西安电子科技大学硕士研究生,E-mail:20031211543@stu.xidian.edu.cn；
万波(1976—),男,教授,博士,E-mail:wanbo@xidian.edu.cn；
王泉(1970—),男,教授,博士,E-mail:qwang@xidian.edu.cn
基金资助:
陕西省重点研发计划(2024GX-YBXM-010);陕西省重点研发计划(2024GX-YBXM-140);陕西省重点研发计划(2024GX-YBXM-039);陕西省创新能力支撑计划(2023-CX-TD-08);陕西省秦创原“科学家+工程师”团队(2023KXJ-040);中央高校基本科研业务费专项资金(ZYTS24089)

Multi-workflow fault-tolerant scheduling strategy for WaaS platforms

ZHI Wentao¹^,²(), ZHAO Hui¹^,²^,³(), MENG Fanxin¹(), WANG Jing¹(), WAN Bo¹^,²^,³(), WANG Quan¹^,³()

1. School of Computer Science and Technology,Xidian University,Xi’an 710071,China
2. Hangzhou Institute of Technology,Xidian University,Hangzhou 311231,China
3. Shaanxi Province Key Laboratory of Smart Human-Computer Interaction and Wearable Technology,Xi’an 710071,China

Received:2024-01-06 Online:2024-10-24 Published:2024-10-24

摘要/Abstract

摘要：

随着科学计算复杂性提高,工作流成为实现科学计算自动化的重要模型。WaaS平台从IaaS供应商处租用虚拟机,为用户提供科学工作流计算服务。目前针对WaaS平台的工作流调度研究并未考虑虚拟机宕机导致任务运行失败以及虚拟机供应延迟的情况。针对此问题,提出一种面向WaaS平台的多工作流容错调度策略。首先,针对WaaS平台不直接调度硬件资源而是在虚拟机和容器层面调度工作流的特点,考虑虚拟机宕机以及供应延迟对调度的影响,建立适合WaaS平台的工作流调度模型。其次,提出一种WaaS平台下多工作流容错调度策略,包括预处理、容错方法选择、任务分配和资源调整四个阶段。其中,设计一种截止时间划分算法来确定调度顺序,通过将任务复制和重新提交相结合的方式选择容错算法,考虑任务属性和虚拟机供应延迟来进行虚拟机选择与任务分配,设计资源调整算法为即将开始的任务提前部署资源,以避免虚拟机或容器的供应延迟。最后,通过在不同虚拟机宕机概率、工作负载和截止时间约束下的实验对比,证明了提出的WaaS平台容错调度策略的有效性。

关键词: 多工作流, 容错调度算法, 工作流即服务平台, 资源供应延迟

Abstract:

As the complexity of scientific computation increases,workflows have become an essential model for automating scientific computations.Workflow as a Service(WaaS) platforms rent virtual machines from Infrastructure as a Service(IaaS) providers to offer users the service of running scientific workflow computations.However,current researches on workflow scheduling in WaaS platforms do not consider the potential for virtual machine downtime to lead to task failures and the delays in virtual machine provisioning.To address this issue,this paper proposes a multi-workflow fault-tolerant scheduling strategy for WaaS platforms.First,considering that WaaS platforms do not schedule hardware resources but operate at the level of virtual machines and containers,we establish a workflow scheduling model suitable for WaaS platforms,taking into account the impact of virtual machine provisioning delays on scheduling.Second,we propose a multi-workflow fault-tolerant scheduling strategy for WaaS platforms,which includes preprocessing,fault-tolerance selection method,task scheduling,and resource adjustment.This involves designing an improved deadline division algorithm for determining the scheduling order,creating a fault-tolerance selection algorithm that combines replication and resubmission,considering task attributes and virtual machine provisioning delays for virtual machine selection and task allocation,and designing a resource adjustment algorithm for avoiding the waiting time for the provisioning delay of virtual machines or containers by deploying resources in advance for the upcoming tasks.Finally,by comparing the proposed scheduling strategy under different virtual machine downtime probabilities,workloads,and deadlines with other algorithms,we demonstrate the effectiveness of the proposed fault-tolerant scheduling strategy for WaaS platforms.

Key words: multi-workflow, fault tolerance scheduling algorithm, WaaS platforms, resource provisioning delay

中图分类号:

TP301.6

支文韬, 赵辉, 孟繁鑫, 王静, 万波, 王泉. 面向WaaS平台的多工作流容错调度策略[J]. 西安电子科技大学学报, 2025, 52(1): 181-195.

ZHI Wentao, ZHAO Hui, MENG Fanxin, WANG Jing, WAN Bo, WANG Quan. Multi-workflow fault-tolerant scheduling strategy for WaaS platforms[J]. Journal of Xidian University, 2025, 52(1): 181-195.

图/表 18

表1

文中主要符号对照表"

符号	符号名称	符号	符号名称
W	所有工作流集合	type(vm_k)	虚拟机k所对应的类型
Wⁱ	工作流i	pc(vmt_i)	类型为i的虚拟机的性能
Tⁱ	工作流i任务的集合	VM_available	所有可用虚拟机集合
$t j i$	工作流i的第j个任务	avgpc	所有可用虚拟机的平均性能
$t e n t r y i$	工作流i的入口任务	VM_idle	所有空闲虚拟机集合
$t e x i t i$	工作流i的出口任务	Cⁱ	可以处理Wⁱ中任务的容器集合
pred( $t j i$ )	任务 $t j i$ 的前驱任务集合	$c j i$	可以处理Wⁱ的第j个容器
succ( $t j i$ )	任务 $t j i$ 的后继任务集合	vtc(vm_k)	虚拟机vm_k上部署的容器
data( $t j i$ , $t k i$ )	$t j i$ 与 $t k i$ 之间的数据传输量	pt( $t j i$ ,vm_k)	任务 $t j i$ 在vm_k上的处理时间
ftwⁱ	工作流Wⁱ的完成时间	lp $t j i$	$t j i$ 在最高性能虚拟机上处理时间
VM	所有租用过的虚拟机集合	avgp $t j i$	$t j i$ 的平均处理时间
vm_i	租用的虚拟机i	cost( $t j i$ ,vm_k)	任务 $t j i$ 在vm_k上的处理成本
vm_fast	最高性能虚拟机	cost(vm_k)	vm_k的总成本
VMT	所有虚拟机类型集合	est( $t j i$ ,vm_k)	任务 $t j i$ 在vm_k上的最早开始时间
vmt_i	虚拟机类型i	eft( $t j i$ ,vm_k)	任务 $t j i$ 在vm_k上的最早完成时间

表1

图1

图2

图3

表2

表3

表4

图4

表5

图5

表6

图6

表7

图7

表8

图8

表9

图9

参考文献 19

[1]	RATHI S, MEHROTRA D, NAGPAL R, et al. Dynamic Multi-Workflow Scheduling:A Comparative Analysis of Real-time Data[C]//Proceedings of the 2024 IEEE Congress on Evolutionary Computation(CEC). Piscataway:IEEE, 2024:1-6.
[2]	TANG X Y, CAO W B, TANG H Y, et al. Cost-Efficient Workflow Scheduling Algorithm for Applications with Deadline Constraint on Heterogeneous Clouds[J]. IEEE Transactions on Parallel and Distributed Systems, 2022, 33(9):2079-2092.
[3]	单晓杭, 章衡, 谢毅. 基于二维编码两阶段协同进化遗传算法的云工作流调度优化[J]. 计算机集成制造系统, 2023, 29(2):568-580.
	SHAN Xiaohang, ZHANG Heng, XIE Yi. Two Stage Coevolutionary Genetic Algorithm with Two Dimensional Coding for Cloud Workflow Scheduling[J]. Computer Integrated Manufacturing Systems, 2023, 29(2):568-580.
[4]	马学森, 许雪梅, 蒋功辉, 等. 混合自适应粒子群工作流调度优化算法[J]. 计算机应用, 2023, 43(2):474. doi: 10.11772/j.issn.1001-9081.2022010001
	MA Xuesen, XU Xuemei, JIANG Gonghui, et al. Hybrid Adaptive Particle Swarm Optimization Algorithm for Workflow Scheduling[J]. Computer Applications and Software, 2023, 43(2):474.
[5]	MIKRAM H, El K S, SAADI Y. HEPGA:A New Effective Hybrid Algorithm for Scientific Workflow Scheduling in Cloud Computing Environment[J]. Simulation Modelling Practice and Theory, 2024, 130:102864.
[6]	向鹏, 林兵, 俞宏杰, 等. 多vCPU环境中基于容器的科学工作流调度策略[J]. 华南师范大学学报(自然科学版), 2023, 55(1):102-112.
	XIANG Peng, LIN Bing, YU Hongjie, et al. Container-driven Scheduling Strategy for Scientific Workflows in Multi-vCPU Environments[J]. Journal of South China Normal University(Natural Science Edition), 2023, 55(1):102-112.
[7]	SHIN J, ARRAYO D, TANTAWI A, et al. Cloud-Native Workflow Scheduling Using a Hybrid Priority Rule and Dynamic Task Parallelism[C] // Proceedings of the 13th Symposium on Cloud Computing(SoCC’22). New York: ACM, 2022:72-77.
[8]	RAJASEKAR P, PLANAICHAMY Y. Scheduling Multiple Scientific Workflows Using Containers on IaaS Cloud[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 12(7):7621-7636.
[9]	TAHERI H, ABRISHAMI S, NAGHIBZADEH M. A Cloud Broker for Executing Deadline-Constrained Periodic Scientific Workflows[J]. IEEE Transactions on Services Computing, 2023, 16(5):3089-3100.
[10]	LI Z J, CHANG V, HU H Y, et al. Real-Time and Dynamic Fault-Tolerant Scheduling for Scientific Workflows in Clouds[J]. Information Sciences, 2021, 568:13-39.
[11]	YAO G S, REN Q, LI X P, et al. A Hybrid Fault-Tolerant Schedulingfor Deadline-Constrained Tasks in Cloud Systems[J]. IEEE Transactions on Services Computing, 2020, 15(3):1371-1384.
[12]	MARAHATTA A, XIN Q, CHI C, et al. PEFS:AI-driven Prediction Based Energy-Aware Fault-Tolerant Scheduling Schemefor Cloud Data Center[J]. IEEE Transactions on Sustainable Computing, 2020, 6(4):655-666.
[13]	党伟超, 武婷玉. 基于注意力时空卷积和A2C的虚拟机主动容错优先迁移决策[J]. 计算机应用研究, 2023, 40(12):3606-3613.
	DANG Weichao, WU Tingyu. Active Fault-Tolerant Priority Migration Decision Model for Virtual Machines Based on Attentional Spatio-Temporal Convolution and A2C[J]. Application Research of Computers, 2023, 40(12):3606-3613.
[14]	ALAEI M, KHORSAND R, RAMEZANPOUR M. An Adaptive Fault Detector Strategy for Scientific Workflow Scheduling Based on Improved Differential Evolution Algorithm in Cloud[J]. Applied Soft Computing, 2021, 99:106895.
[15]	MATANI A, NAJI H R, MATALLEBI H. A Fault-Tolerant Workflow Scheduling Algorithm for Grid with Near-Optimal Redundancy[J]. Journal of Grid Computing, 2020, 18(3):377-394.
[16]	WEN Z Y, QASA R, LI Z K, et al. Dynamically Partitioning Workflow over Federated Clouds for Optimising the Monetary Cost and Handling Run-Time Failures[J]. IEEE Transactions on Cloud Computing, 2020, 8(4):1093-1107.
[17]	MASOUMI M, MOTALLEBI H. A Structure-Aware Algorithm for Fault-Tolerant Scheduling of Scientific Workflows[J]. The Journal of Supercomputing, 2022, 78(15):17348-17377.
[18]	DONG T T, XUE F, TANG H L, et al. Deep Reinforcement Learning for Fault-Tolerant Workflow Scheduling in Cloud Environment[J]. Applied Intelligence, 2022, 53(9):9916-9932.
[19]	YAO G, DING Y, HAO K. Using Imbalance Characteristic for Fault-Tolerant Workflow Scheduling in Cloud Systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 28(12):3671-3683.

类型	性能/MIPS	价格/(美元·h^-1)
Small	2	1
Medium	4	2
Large	8	4
Extra-large	16	8

宕机概率/%	工到达率/(个·min^-1)	截止时间系数
0	0.5	1.1
5	1	1.3
10	2	1.5
15	6	1.7
20	12	1.9

算法	虚拟机宕机概率/%
算法	0	5	10	15	20
FCVD	94.0	92.9	89.3	88.8	87.4
OSAR	82.9	79.6	76.3	74.8	74.2
ICFWS	33.2	31.7	34.1	34.4	28.7
SRPSM-FV	84.1	83.2	79.9	78.7	75.4

算法	工作流到达率/(个·min^-1)
算法	0.5	1.0	2.0	6.0	12.0
FCVD	88.4	89.7	89.2	82.9	80.1
OSAR	74.1	79.2	77.2	77.9	80.0
ICFWS	41.0	40.5	35.0	16.1	4.8
SRPSM-FV	83.1	81.5	81.1	79.4	80.5

算法	工作流到达率/(个·min^-1)
算法	0.5	1.0	2.0	6.0	12.0
FCVD	25 745	27 367	40 000	83 581	139 115
OSAR	26 096	31 184	37 488	80 720	131 208
ICFWS	60 589	55 098	79 023	167 987	273 676
SRPSM-FV	47 200	70 592	117 440	240 360	365 488

面向WaaS平台的多工作流容错调度策略

Multi-workflow fault-tolerant scheduling strategy for WaaS platforms

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 18

参考文献 19

相关文章 15

Metrics

本文评价

推荐阅读 0

算法	截止时间系数
算法	1.1	1.3	1.5	1.7	1.9
FCVD	63.8	89.3	92.6	95.5	95.8
OSAR	63.8	78.4	80.5	90.7	95.5
ICFWS	5.7	3.2	41.3	44.9	41.3
SRPSM-FV	67.1	79.0	82.3	90.1	97.0

算法	截止时间系数
算法	1.1	1.3	1.5	1.7	1.9
FCVD	41 265	40 562	41 163	35 707	34 782
OSAR	36 840	366 48	37 280	36 352	37 320
ICFWS	83 259	74 264	69 320	62 749	71 603
SRPSM-FV	141 048	117 648	113 640	95 192	86 856

算法	工作流到达率/(个·min^-1)
算法	0.5	1.0	2.0
FCVD	63.5	75.7	89.2
OSAR	13.7	33.0	58.7
ICFWS	24.9	48.4	85.2
SRPSM-FV	26.2	35.3	37.5

[1]	韩家曦, 赵辉, 冯南之, 王静, 万波, 王泉. 边缘计算平台中面向分簇的半在线调度方法[J]. 西安电子科技大学学报, 2024, 51(6): 104-116.
[2]	张超, 赵辉, 张智峰, 王静, 万波, 王泉. 边缘协作环境下最小化完工时间任务调度方法[J]. 西安电子科技大学学报, 2024, 51(4): 114-127.
[3]	高卫峰, 王琼, 李宏, 谢晋, 公茂果. 无人机集群任务分配的多目标算法研究[J]. 西安电子科技大学学报, 2024, 51(2): 1-12.
[4]	韩辉,慕建君,焦晓鹏,赵展展. 纠单个相邻对换错误置换码构造与编译码方法[J]. 西安电子科技大学学报, 2023, 50(3): 105-111.
[5]	刘天宇,曹磊. 多任务机制驱动的高维多目标进化算法[J]. 西安电子科技大学学报, 2022, 49(4): 134-143.
[6]	孙希延,宋少杰,纪元法,梁维彬,李有明. 适用于BOC及其衍生信号的无模糊跟踪算法[J]. 西安电子科技大学学报, 2022, 49(2): 58-66.
[7]	杜瑞忠,王一,田俊峰. 一种支持动态可验证的密文检索方案[J]. 西安电子科技大学学报, 2022, 49(1): 35-46.
[8]	赵辉,冯南之,王泉,万波,王静. 面向边缘计算平台的半线上任务动态调度方法[J]. 西安电子科技大学学报, 2021, 48(6): 8-15.
[9]	闫群民,马瑞卿,马永翔,王俊杰. 一种自适应模拟退火粒子群优化算法[J]. 西安电子科技大学学报, 2021, 48(4): 120-127.
[10]	刘天宇,王翥. 一种多样性控制的多目标粒子群算法[J]. 西安电子科技大学学报, 2021, 48(3): 106-114.
[11]	张华,高浩然,杨兴国,李文敏,高飞,温巧燕. TargetedFool:一种实现有目标攻击的算法[J]. 西安电子科技大学学报, 2021, 48(1): 149-159.
[12]	李涵,张晨,黄荷姣,郭宇. 一种支持前向安全更新和验证的加密搜索算法[J]. 西安电子科技大学学报, 2020, 47(5): 48-56.
[13]	刘乃安,陈智浩,刘国堃,李洋. 一种面向区块链验证节点的声誉证明共识机制[J]. 西安电子科技大学学报, 2020, 47(5): 57-62.
[14]	汪昱东,郭继昌,王天保. 一种改进的雾天图像行人和车辆检测算法[J]. 西安电子科技大学学报, 2020, 47(4): 70-77.
[15]	肖利军,郭继昌,顾翔元. 一种采用冗余性动态权重的特征选择算法[J]. 西安电子科技大学学报, 2019, 46(5): 155-161.