分布式系统中基于非合作博弈的调度算法

《分布式系统中基于非合作博弈的调度算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分布式系统中基于非合作博弈的调度算法摘要：针对分布式系统中任务调度问题，根据分布式环境下的任务调度特性，建立了一个非合作博弈的多角色任务调度框架，在此基础上提出了一种基于纳什均衡联合调度策略的分布式强化学习算法.相比于静态调度算法，该算法需要更少的系统知识.能使调度器主动学习任务到达和执行的相关先验知识，以适应相邻调度器的分配策略，目标是使得调度器的策略趋向纳什均衡.模拟实验结果表明：所提出的算法在任务的预期时间和公平性上相对于OLB（机会主义负载均衡）、MET（最小执行时间）、MCT（最小完成时间）等同类调度算法具有更

2、好的调度性能.关键词：分布式计算；强化学习；任务调度；负载均衡中图分类号：TP301.6文献标识码:分布式系统中基于非合作博弈的调度算法摘要：针对分布式系统中任务调度问题，根据分布式环境下的任务调度特性，建立了一个非合作博弈的多角色任务调度框架，在此基础上提出了一种基于纳什均衡联合调度策略的分布式强化学习算法.相比于静态调度算法，该算法需要更少的系统知识.能使调度器主动学习任务到达和执行的相关先验知识，以适应相邻调度器的分配策略，目标是使得调度器的策略趋向纳什均衡.模拟实验结果表明：所提出的算法在任务的预期时间和公平性上

3、相对于OLB（机会主义负载均衡）、MET（最小执行时间）、MCT（最小完成时间）等同类调度算法具有更好的调度性能.关键词：分布式计算；强化学习；任务调度；负载均衡中图分类号：TP301.6文献标识码:文章编号:1674-2974(2016)10-0139-09Abstract：Toaddressthetaskschedulingproblemindistributedsystems，basedonanimportantfeatureoftaskschedulingindistributedcomputingenviron

4、ment，wehaveestablishedanon-cooperativegameframeworkformulti-layermulti-role,andputforwardadistributedreinforcementlearningalgorithmofthejointschedulingstrategyofNashequilibrium.Comparedwithstaticschedulingalgorithm，theproposedalgorithmneedslesssysteminformation.I

5、tenablestheschedulertoactivelylearntaskarrival,performrelatedknowledgeandadapttotheadjacentschedulerallocationpolicy.ThetargetistomovetheschedulersstrategytowardNashequilibrium.Simulationexperimentsshowthattheproposedalgorithmachievesexcellentperformanceinexpecte

6、dresponsetimeoftasksandfairness,comparedwithclassicalschedulingalgorithmssuchasOLB，METandMCT.Keywords：distributedcomputing；reinforcementlearning；taskscheduling；loadbalance随着科技的发展，基于Internet的计算方式发展迅速.如今云计算试图对线上资源进行虚拟化整合并使得需求更加透明[1-2].可以得知，当今的计算方式从独立的计算模式向网络化方向发展.云

7、计算作为目前广泛部署的分布式系统，该系统可以提供巨大的计算能力满足并发请求，使得云计算在日常生活中变得更加重要.而在云计算系统中，任务的负载均衡是发挥其巨大潜力的关键因素[3].在分布式系统中，存在大量的不确定性.由于网络不稳定的通信消耗以及计算能力的波动，导致任务的执行时间是随机的，这些参数取决于系统的当前状态.基于历史记录或工作负载建模的预测用来评估工作的执行时间[4].精度差和复杂度高是这类方法的缺点.此外，由于任务随机到达，其大小和CCR(ComputationtoCommunicationRatio,计算通信比

8、)是无法预测的.因此，在分布式系统中动态算法受到广泛研究.在分布式计算系统中，批处理模式是一类动态调度方法.Min-Min，Max-Min和Suffrage是三个典型的启发式批处理算法，这种算法为了获得任务到达和执行信息，很多时间用于等待和评估，缺乏实时性.相反，在线模式中，任务到达后被立即调度，如机会主义负载均衡(