满足公平性约束的云任务调度QoS算法

Qo S Algorithm for Cloud Task Scheduling with Fairness Constraints

为了提高资源行为动态异构的云环境中工作流任务的调度效率,提出了一种满足公平性约束的云任务调度Qo S算法。算法将工作流任务结构定义为有向无循环图DAG模型,改进了传统关键路径的一次性搜索模式,结合云资源可用性动态可变的特征,以动态自适应方式搜索关键路径,并确定关键任务。同时,在关键任务调度后,局部DAG的关键路径搜索根据资源可用性再次迭代更新,从而动态决策任务与资源间的调度方案。通过仿真实验,构建了3种不同类型的工作流结构作为测试数据源,并与其他6种同类型的启发式和元启发式算法进行了性能比较。实验结果表明,在资源可用性动态改变和工作流规模不断增大的情况下,算法在多数工作流结构中均能得到执行跨度更好的调度方案和更少的调度开销。

For improving the scheduling efficiency of workflow tasks in cloud environment with dynamic and heterogeneous behaviors of resources,Qo S algorithm for cloud task scheduling with fairness constraints is proposed in this paper.The algorithm defines workflow tasks＇ structure as directed acyclic graph（DAG）model and improves the one-time search pattern of the traditional critical path.Combined with the characteristics of dynamic and variability of cloud resources,our algorithm can dynamically and self-adaptively search the critical path and determine the critical task of DAG.Meanwhile,after scheduling the critical task,the searching of critical path in the partial DAG will be iteratively updated again according to resources＇ availability,which can dynamically determine the mapping between tasks and resources.Through the simulation experiments,we construct three different types of workflow structures as the testing data source,and compare the performance with other six same types of heuristics and meta-heuristics.Experimental results show that under the condition of dynamic and changing resource availability and continuously increasing workflow sizes,the algorithm can generate a better scheduling scheme of execution makespan and less scheduling overhead for most of the workflow types.