分布式系统中多用户网络应用的概率型调度算法研究-北京玛格泰克科技.PDF

第７期 电　　子　　学　　报 Ｖｏｌ．４４　Ｎｏ．７ ２０１６年７月 ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡ Ｊｕｌ．　２０１６ 分布式系统中多用户网络应用的 概率型调度算法研究 １，２ ２ ２ 童　钊 ，肖　正 ，李肯立 （１．湖南师范大学数学与计算机科学学院，湖南长沙４１００８２；２．湖南大学信息科学与工程学院，湖南长沙４１００８２） 　　摘　要：　多用户网络应用是分布式计算中最主要的形式之一．为了充分挖掘分布式系统中的计算资源，任务调 度是解决该问题的关键．然而，由于多用户网络应用中存在的不确定性，使得当前的调度方法在动态性、实时性、适应 性等方面都存在诸多不足．考虑到用户实时性需求，本文提出了概率型调度的思想．该思想将任务的分配看作概率事 件，以用户角度的最短响应时间为目标，给出了多用户网络应用的排队模型，并进一步将调度定义为一个非线性规划 问题．分析表明上述方法在任务到达过程、服务率方面存在限制，进而提出了一个基于强化学习理论自适应调度算法． 该算法首先利用Ｍａｒｋｏｖ决策过程（ＭＤＰ）描述该调度问题，然后对任务到达过程和服务率知识进行在线的学习．一旦 获得任务分配概率，遵从该概率可进行快速的任务调度．实验表明上述两个算法相比于ＭｉｎＭｉｎ、ＭａｘＭｉｎ、Ｓｕｆｆｒａｇｅ、 ＥＣＴ四种经典调度算法具有更短的平均响应时间．除此性能外，通过实验分析了该概率型调度方法的稳定性． 关键词：　分布式计算；多用户；任务调度；排队模型；概率型调度 中图分类号：　ＴＰ３９１　　　文献标识码：　Ａ　　　文章编号：　０３７２２１１２（２０１６）０７１６７９１０ 电子学报ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｅｊｏｕｒｎａｌ．ｏｒｇ．ｃｎ　 ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．０３７２２１１２．２０１６．０７．０２３ ＡＱｕｅｕｅｉｎｇＭｏｄｅｌａｎｄＰｒｏｂａｂｉｌｉｓｔｉｃＳｃｈｅｄｕｌｉｎｇｆｏｒ ＭｕｌｔｉｕｓｅｒＮｅｔｗｏｒｋＡｐｐｌｉｃａｔｉｏｎｓ １，２ ２ ２ ＴＯＮＧＺｈａｏ ，ＸＩＡＯＺｈｅｎｇ，ＬＩＫｅｎｌｉ （１．ＣｏｌｌｅｇｅｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＨｕｎａｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ４１００８２，Ｃｈｉｎａ； ２．ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＨｕｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ４１００８２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：　Ｍｕｌｔｉｕｓｅｒｎｅｔｗｏｒｋａｐｐｌｉｃａｔｉｏｎｉｓｏｎｅｏｆｔｈｅｍｏｓｔｐｏｐｕｌａｒｆｏｒｍｓｏｆｄｉｓｔｒｉｂｕｔｅｄｃｏｍｐｕｔｉｎｇ．Ｔｏｆｕｌｌｙｅｘｐｌｏｉｔ ｃｏｍｐｕｔｉｎｇｒｅｓｏｕｒｃｅｓｉｎｄｉｓｔｒｉｂｕｔｅｄｓｙｓｔｅｍｓ，ｔａｓｋｓｃｈｅｄｕｌｉｎｇｉｓｃｒｉｔｉｃａｌ．Ｈｏｗｅｖｅｒ，ｉｎｓｃｈｅｄｕｌｉｎｇｏｆｍｕｌｔｉｕｓｅｒｎｅｔｗｏｒｋａｐｐｌｉｃａｔｉｏｎ ｂｅｃａｕｓｅｌｏｔｓｏｆｕｎｃｅｒｔａｉｎｔｉｅｓｅｘｉｓｔｓｕｃｈａｓｔａｓｋａｒｒｉｖａｌ，ｔａｓｋｃｏｍｐｌｅｔｉｏｎｔｉｍｅ，ｅｔｃ．，ｔｈｅｓｔａｔｅｏｆｔｈｅａｒｔｓｃｈｅｄｕｌｉｎｇａｐｐｒｏａｃｈｅｓｆａｉｌ ｉｎｄｙｎａｍｉｃ，ｒｅａ