基于依赖型任务和Sarsa(λ)算法的云计算任务调度

Task Scheduling in Cloud Computing Based on Dependent Task and Sarsa

摘要:

针对现有的云计算任务调度算法具有的任务调度时间长和系统负载不均衡的缺点,提出了一种基于依赖型任务和Sarsa(λ)算法结合的依赖型任务调度方法;首先对调度目标模型进行了定义,以最小化调度策略的最晚完成时间作为调度目标,然后将任务调度模型建模为马尔科夫决策过程MDP,在此基础上,基于MDP采用Sarsa算法实现对状态动作值的更新,为了加快算法的收敛速度,在状态动作值更新的过程中加入资格迹,给出了资格迹的更新方式；最后,定义了基于依赖型任务DAG图和Sarsa(λ)的云计算任务调度算法；在Cloudsim环境下进行仿真试验,结果表明文中方法能有效地实现依赖型任务调度,且较其它方法相比,具有任务调度时间短和负载均衡的优点,是一种适合云计算环境的可行任务调度方法。

关键词:任务调度;强化学习;云计算;负载均衡

Abstract:

Aiming at conquering the defects of long task scheduling time and unbalance of system load in the existing task scheduling method, a task scheduling method based on dependence task and Sarsa(λ) is proposed. Firstly, the scheduling model is defined and minimizing the finishing time of scheduling strategy as the scheduling goal. The task scheduling model is modeled as the Markov decision process (MDP), then the state action value is renewed by combing MDP and Sarsa algorithm. In order to accelerate the convergence rate, the eligibility is added to the updating for state action value, and the updating for eligibility is given. Finally, the task scheduling algorithm in cloud computing by combing dependence task DAG graph and Sarsa(λ) is specified. The experiment is operated in the Cloudsim environment, the result shows the method in this paper can realize dependent task cluster scheduling, and compared with the other methods, it has the less task scheduling time and higher load balance, therefore, it is a feasible scheduling method suitable for cloud environment.

Key words:task scheduling; reinforcement learning; cloud computing; load balance