一种基于三支决策的云任务调度优化算法

Cloud Task Scheduling Algorithm Based on Three-way Decisions

云任务调度作为云计算体系的一个重要组成部分,其调度策略的效果直接影响到云平台资源利用率及用户服务质量。为解决当前云调度策略中Min-Min算法和Ma-Min算法容易因云任务分布导致负载不均衡、资源综合使用率低和任务总体完成时间较大等问题,提出一种基于三支决策的云任务调度优化算法(Cloud Task Scheduling Algorithm based on three-Way Decision,CTSA-3WD)。根据云任务的执行时间和计算资源的实际情况来标定任务集合中的轻负载任务和重负载任务。借鉴三支决策基本思想,根据两种任务在其任务集合中所占比例进行三支划分,有针对性地对划分后的3个任务集合设计合适的调度策略:针对轻负载任务占比高的任务集合,使用Max-Min算法;针对重负载任务占比高的任务集合,使用Min-Min算法;针对轻重负载任务接近的任务集合,采用基于Min-Min和Max-Min的改进任务调度算法。对分配完毕的节点中的关键资源进行重新调度,在满足总体完成时间减少的前提下选择最匹配的任务分配给轻负载资源。CloudSim仿真平台的实验结果表明,所提出的云任务调度优化算法(CTSA-3WD)相比Min-Min,Max-Min及选择调度算法可以有效提高整体资源利用率,提升了用户的服务质量,同时也使得整个系统中的资源达到更好的负载均衡水平。

As an essential component of the cloud computing system,task scheduling directly impacts resource utilization and service quality.To solve the problems existing in Min-Min and Max-Min algorithms in the current cloud platform,such as load imbalance,low comprehensive resource utilization,and sizeable overall task completion time due to task distribution,a task sche-duling optimization algorithm based on the three-way decision(CTSA-3 WD)is proposed.First,the algorithm divides tasks into light-load and heavy-load tasks according to their execution time and computational resource requirements.Secondly,the algorithm divides the tasks into three categories according to the proportion of the task set’s two types of tasks.It develops scheduling strategies for these three task sets.Specifically,the strategy uses the Max-Min algorithm for tasks with a high percentage of light load tasks and uses the Min-Min algorithm for a high proportion of heavily loaded tasks.An improved task scheduling algorithm based on Min-Min and Max-Min is used for the set,which has close numbers between light and heavy-duty tasks.Third,the critical resources in the allocated nodes are rescheduled.The algorithm selects the best matching tasks to be allocated to the light-load resources,subject to the overall completion time reduction.The experimental based on the CloudSim reveals that the CTSA-3 WD algorithm can effectively improve the overall resource utilization and quality of service to users compared to Min-Min,Max-Min,selective scheduling algorithms.Moreover,it also makes the resources in the whole system reach a better load-balancing level.