电子学报2016，Vol.44Issue(7)：1679-1688,10.DOI:10.3969/j.issn.0372-2112.2016.07.023
分布式系统中多用户网络应用的概率型调度算法研究
A Queueing ModeI and ProbabiIistic ScheduIing for MuIti-user Network AppIications
摘要
Abstract
Multi-user network application is one of the most popular forms of distributed computing.To fully exploit computing resources in distributed systems,task scheduling is critical.However,in scheduling of multi-user network application because lots of uncertainties exist such as task arrival,task completion time,etc.,the state of the art scheduling approaches fail in dynamic,real time,or adaptability.On account of the real time property,we put forward the concept of probabilistic schedu-ling to compress scheduling time,which regards task allocation as a probabilistic event.Unexpectedly,compared with tradition-al scheduling approaches which are always determinate,probabilistic scheduling has other advantages like insensitivity to task execution time estimation and steady performance.Based on the idea of probabilistic scheduling and considering the shortest re-sponse time from the perspective of users,a queueing model is given for multi-user network application,and scheduling is de-fined as a non-linear programming problem.But due to its limitation on task arrival process and service rate,a self-adaptive al-gorithm is proposed by use of reinforcement learning theory.The scheduling problem is described by Markov Decision Process (MDP),and then task arrival process and service rate can be learned on line.Once the allocation probability is acquired, scheduling is quite fast by following such probability distribution.The two algorithms are validated and they outperform such four classic algorithms as Min-Min,Max-Min,Suffrage,and ECT at the average response time.Except for the mean of response time,their variance is also examined to confirm the stability generated by probabilistic scheduling.关键词
分布式计算/多用户/任务调度/排队模型/概率型调度Key words
distributed computing/multi-user/task scheduling/queueing model/probabilistic scheduling分类
信息技术与安全科学引用本文复制引用
童钊,肖正,李肯立..分布式系统中多用户网络应用的概率型调度算法研究[J].电子学报,2016,44(7):1679-1688,10.基金项目
国家自然科学基金重点项目（No．61133005）；国家自然科学基金青年项目（No．61402157）；湖南省自然科学基金（No．13JJ4038）；湖南师范大学青年基金 （）
