QoS敏感的云工作流调度优化方法

发布时间：2019-05-29 09:27

【摘要】：由于云计算具有灵活性、高可扩展性和经济性等特性,许多组织将传统工作流应用迁移到云计算环境中,形成了云工作流。云工作流调度指在云平台上对用户提交的工作流进行资源分配与任务执行,调度过程要考虑用户的服务质量(Quality-of-Service,QoS)需求,如执行时间、费用等。针对QoS敏感的云工作流调度问题,本文提出两种云工作流调度优化方法,分别适用于云工作流调度的任务-资源映射阶段和任务执行阶段的调度优化。任务-资源映射阶段,工作流中的各项任务需要预先被分配至最佳资源,分配过程要考虑满足用户的QoS约束。现有的调度算法要从时间和费用两方面进行研究,很少考虑可靠性。但在实际系统中,资源和数据传输的故障都会对工作流的成功运行造成负面影响。论文考虑了时间、费用和可靠性三个重要QoS因素。针对时间和可靠性双重约束下费用最小化的云工作流调度问题,提出了基于萤火虫算法和动态优先级的最优调度方案搜索方法。特别地,结合云工作流调度问题的特点,重新定义了萤火虫算法中的位置、距离以及位置更新方式,同时对于每一种调度方案,采取动态优先级算法确定任务顺序,以减少工作流完成时间。任务执行阶段依据任务-资源映射关系,将任务调度到相应的资源上执行,调度过程中会产生调度开销,从而影响到云工作流的QoS水平。任务聚类将细粒度任务合并成粗粒度任务,调度到同一资源上,减少调度开销从而优化流程执行时间。不合理任务聚类过程会产生时间不均衡和依赖不均衡问题,这将导致任务执行并行度降低。针对时间不均衡问题,本文提出了时间均衡聚类算法RBCA,该算法使用回溯法进行任务聚类,使得聚类后各类运行时间更加均衡。针对依赖不均衡问题,本文提出了依赖均衡聚类算法DBCA,定义了关联度这一概念用来衡量任务之间依赖的相似程度,将关联度高的任务聚为一类,从而解决依赖不均衡。本文在Workflow Sim云工作流仿真平台上进行实验仿真。实验证实,基于萤火虫算法和动态优先级的多QoS云工作流调度方法在收敛速度和最优值均优于传统萤火虫算法,同时也优于另外两种云工作流调度算法GA和S-CLPSO。基于均衡聚类的云工作流调度优化方法相比传统的均衡聚类算法HRB、HIFB,聚类结果更为均衡,更能优化流程的执行时间。
[Abstract]:Because cloud computing has the characteristics of flexibility, high scalability, and economy, many organizations migrate traditional workflow applications into the cloud computing environment, forming a cloud workflow. The cloud workflow scheduling refers to the resource allocation and task execution of the workflow submitted by the user on the cloud platform, and the scheduling process takes into account the quality-of-service (QoS) requirements of the user, such as the execution time, the cost, and the like. In order to solve the problem of QoS-sensitive cloud workflow scheduling, two cloud workflow scheduling optimization methods are proposed, which are respectively applicable to the task-resource mapping stage and the scheduling optimization of the task execution stage of the cloud workflow scheduling. The task-resource mapping stage, the tasks in the workflow need to be allocated to the optimal resource in advance, and the allocation process takes into account the user's QoS constraints. The existing scheduling algorithm is to be studied in terms of time and cost, and the reliability is seldom considered. However, in the actual system, the failure of resources and data transmission will have a negative impact on the successful operation of the workflow. The paper takes into account three important QoS factors of time, cost and reliability. Aiming at the problem of cloud workflow scheduling under the double constraint of time and reliability, a search method of optimal scheduling scheme based on firefly and dynamic priority is proposed. In particular, in combination with the characteristics of the cloud workflow scheduling problem, the position, distance and location updating method in the firefly algorithm are redefined, and the task order is determined by adopting a dynamic priority algorithm for each scheduling scheme so as to reduce the completion time of the workflow. The task execution stage performs task scheduling to the corresponding resources according to the task-resource mapping relationship, and the scheduling cost is generated in the scheduling process, thereby affecting the QoS level of the cloud workflow. Task clustering combines fine-grained tasks into coarse-grained tasks, schedules to the same resource, reduces scheduling overhead, and optimizes process execution time. Unreasonable task clustering can produce time-imbalance and dependency-dependent problems, which will lead to a reduction in the parallelism of tasks. In view of the problem of time-imbalance, this paper presents a time-balanced clustering algorithm RBCA, which uses the backtracking method to carry out task clustering, so that the running time after clustering is more balanced. In order to solve the problem of dependency, this paper puts forward the DBCA which is dependent on the equilibrium clustering algorithm, and defines the degree of the degree of similarity between the task and the task, and the task of the high degree of association is gathered into a class, so that the problem of dependency is solved. In this paper, the experimental simulation is carried out on the workflow simulation platform of Workflow Sim. It is proved that the multi-QoS cloud workflow scheduling method based on the firefly algorithm and the dynamic priority is superior to the traditional firefly algorithm at the convergence speed and the optimal value, and is superior to the other two cloud workflow scheduling algorithms GA and S-CLPSO. Compared with the traditional balanced clustering algorithm HRB, HIFB, the clustering result is more balanced compared with the traditional balanced clustering algorithm HRB and HIFB, and the execution time of the process can be more optimized.
【学位授予单位】：杭州电子科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;TP311.13

【参考文献】