基于强化学习和蚁群算法的协同依赖多任务网格集群调度
|
摘要
针对现有的网格集群资源调度方法所具有的任务调度时间长、系统负载不均衡和CPU利用率低的缺点,提出了一种基于强化学习和蚁群算法结合的协同依赖型任务调度方法.首先对调度目标模型进行了定义,然后采用改进的强化学习Sarsa算法实现集群资源的初始分配,以最小化任务调度时间为目标,寻求最优调度方案,并保存调度方案对应的Q值.在此基础上,设计了一种改进的蚁群算法实现网格集群资源到任务分配的进一步寻优,在不同资源节点上的概率选择上考虑了Q值因素,从而实现网格环境下的协同依赖多任务集群调度.在Gridsim工具下进行仿真试验,结果表明新方法能有效地实现协同依赖多任务网格集群调度,且较其他方法而言,具有任务调度时间少、CPU利用率高和负载均衡的优点,是一种适合网格环境的可行任务调度方法.
Current grid cluster resource scheduling method has the disadvantages of long scheduling time,unbalance system load and low CPU utilization rate. A cooperative dependent task scheduling method is proposed,which is based on reinforcement learning and ant colony algorithm. Firstly,the scheduling goal model is defined,then the improved reinforcement learning Sarsa algorithm is used to allocate the task resource,with minimizing the task scheduling time as the goal to get the optimal scheduling method and save the Q value of scheduling method. Then an improved ant colony algorithm is introduce to realize the task allocation to the resource node. The experiment is operated in the Gridsim environment,and the result shows that the method in this paper can realize the cooperative dependent task cluster scheduling,and compared with other methods,it has less task scheduling time,higher CPU usage rate and higher load balance. Therefore,it is a feasible scheduling method suitable for grid environment.
Current grid cluster resource scheduling method has the disadvantages of long scheduling time,unbalance system load and low CPU utilization rate. A cooperative dependent task scheduling method is proposed,which is based on reinforcement learning and ant colony algorithm. Firstly,the scheduling goal model is defined,then the improved reinforcement learning Sarsa algorithm is used to allocate the task resource,with minimizing the task scheduling time as the goal to get the optimal scheduling method and save the Q value of scheduling method. Then an improved ant colony algorithm is introduce to realize the task allocation to the resource node. The experiment is operated in the Gridsim environment,and the result shows that the method in this paper can realize the cooperative dependent task cluster scheduling,and compared with other methods,it has less task scheduling time,higher CPU usage rate and higher load balance. Therefore,it is a feasible scheduling method suitable for grid environment.
引文
[1]Foster I,Kesselman C,Tuecke S.The anatomy of the grid:Enabling scalable virtual organizations[J].International J Super Computer Application,2001,(3):200-222.
[2]马艳,龚斌,邹立达.网格环境下基于复制的能耗有效依赖任务调度研究[J].计算机研究与发展,2013,(2):420-429.
[3]Netto M A S,Buyya B.Rescheduling co-allocation requests based on flexible advance reservations and processor remapping[A].Proceedings of 9thGrid Computing Conference[C].2008:144-150.
[4]王观玉.网格计算中任务调度算法的研究和改进[J].计算机工程与科学,2011,(10):186-187.
[5]Li J Y,Qiu M K,Ming Z,et al.Online optimization for scheduling preemptable tasks on Iaa S cloud systems[J].Journal of Parallel and Distributed Computing,2012,(2):666-677.
[6]Braun T D,Siegel H J,Beck N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J].Journal of Parallel and distributed computing,2001,(6):810-837.
[7]Moreno R J.Scheduling and resource management techniques in dynamics grid environment[A].Proceedings of 8thInt’l Conf on Advanced Computing and Communications[C].Cochin:ADCOM,2000.
[8]卜宪宪.基于小生境和自适应遗传算法的网格任务调度优化研究[J].计算机测量与控制,2013,(2):470-479.
[9]王振宇,李照瑜.单层树型网格下独立任务的周期性调度[J].软件学报,2013,(2):378-390.
[10]蒲汛,彭喜化,于显平,等.基于均匀离散PSO算法的多Qo S网格任务调度策略[J].控制与决策,2013,(6):808-814.
[2]马艳,龚斌,邹立达.网格环境下基于复制的能耗有效依赖任务调度研究[J].计算机研究与发展,2013,(2):420-429.
[3]Netto M A S,Buyya B.Rescheduling co-allocation requests based on flexible advance reservations and processor remapping[A].Proceedings of 9thGrid Computing Conference[C].2008:144-150.
[4]王观玉.网格计算中任务调度算法的研究和改进[J].计算机工程与科学,2011,(10):186-187.
[5]Li J Y,Qiu M K,Ming Z,et al.Online optimization for scheduling preemptable tasks on Iaa S cloud systems[J].Journal of Parallel and Distributed Computing,2012,(2):666-677.
[6]Braun T D,Siegel H J,Beck N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J].Journal of Parallel and distributed computing,2001,(6):810-837.
[7]Moreno R J.Scheduling and resource management techniques in dynamics grid environment[A].Proceedings of 8thInt’l Conf on Advanced Computing and Communications[C].Cochin:ADCOM,2000.
[8]卜宪宪.基于小生境和自适应遗传算法的网格任务调度优化研究[J].计算机测量与控制,2013,(2):470-479.
[9]王振宇,李照瑜.单层树型网格下独立任务的周期性调度[J].软件学报,2013,(2):378-390.
[10]蒲汛,彭喜化,于显平,等.基于均匀离散PSO算法的多Qo S网格任务调度策略[J].控制与决策,2013,(6):808-814.