分布式系统中基干非合作博弈调度算法.docVIP

分布式系统中基于非合作博弈的调度算法 　　摘 要：针对分布式系统中任务调度问题，根据分布式环境下的任务调度特性，建立了一个非合作博弈的多角色任务调度框架，在此基础上提出了一种基于纳什均衡联合调度策略的分布式强化学习算法.相比于静态调度算法，该算法需要更少的系统知识.能使调度器主动学习任务到达和执行的相关先验知识，以适应相邻调度器的分配策略，目标是使得调度器的策略趋向纳什均衡.模拟实验结果表明：所提出的算法在任务的预期时间和公平性上相对于OLB（机会主义负载均衡）、MET（最小执行时间）、MCT（最小完成时间）等同类调度算法具有更好的调度性能. 关键词：分布式计算；强化学习；任务调度；负载均衡 中图分类号：TP301.6 文献标识码：A 文章编号：1674-2974（2016）10-0139-09 Abstract：To address the task scheduling problem in distributed systems， based on an important feature of task scheduling in distributed computing environment， we have established a non-cooperative game framework for multi-layer multi-role， and put forward a distributed reinforcement learning algorithm of the joint scheduling strategy of Nash equilibrium. Compared with static scheduling algorithm， the proposed algorithm needs less system information. It enables the scheduler to actively learn task arrival， perform related knowledge and adapt to the adjacent scheduler allocation policy. The target is to move the schedulers strategy toward Nash equilibrium. Simulation experiments show that the proposed algorithm achieves excellent performance in expected response time of tasks and fairness， compared with classical scheduling algorithms such as OLB， MET and MCT. Key words：distributed computing； reinforcement learning； task scheduling； load balance 随着科技的发展，基于Internet的计算方式发展迅速.如今云计算试图对线上资源进行虚拟化整合并使得需求更加透明[1-2].可以得知，当今的计算方式从独立的计算模式向网络化方向发展.云计算作为目前广泛部署的分布式系统，该系统可以提供巨大的计算能力满足并发请求，使得云计算在日常生活中变得更加重要.而在云计算系统中，任务的负载均衡是发挥其巨大潜力的关键因素[3]. 在分布式系统中，存在大量的不确定性.由于网络不稳定的通信消耗以及计算能力的波动，导致任务的执行时间是随机的，这些参数取决于系统的当前状态.基于历史记录或工作负载建模的预测用来评估工作的执行时间[4].精度差和复杂度高是这类方法的缺点.此外，由于任务随机到达，其大小和CCR（Computation to Communication Ratio，计算通信比）是无法预测的.因此，在分布式系统中动态算法受到广泛研究.在分布式计算系统中，批处理模式是一类动态调度方法.Min-Min，Max-Min和Suffrage是三个典型的启发式批处理算法，这种算法为了获得任务到达和执行信息，很多时间用于等待和评估，缺乏实时性.相反，在线模式中，任务到达后被立即调度，如机会主义负载均衡（OLB， Opportunistic Load Balancing）的算法，最小执行时间（MET， Minimum Execution Time），最小完成时间（MCT， Minimum Completion Time）等调度算法[5-6].然而它们忽略了后续任务的到达和对整体性能的影响.为了获得全