分布式系统中多用户网络应用的概率型调度算法研究

A Queueing Model and Probabilistic Scheduling for Multi-user Network Applications

多用户网络应用是分布式计算中最主要的形式之一.为了充分挖掘分布式系统中的计算资源,任务调度是解决该问题的关键.然而,由于多用户网络应用中存在的不确定性,使得当前的调度方法在动态性、实时性、适应性等方面都存在诸多不足.考虑到用户实时性需求,本文提出了概率型调度的思想.该思想将任务的分配看作概率事件,以用户角度的最短响应时间为目标,给出了多用户网络应用的排队模型,并进一步将调度定义为一个非线性规划问题.分析表明上述方法在任务到达过程、服务率方面存在限制,进而提出了一个基于强化学习理论自适应调度算法.该算法首先利用Markov决策过程(MDP)描述该调度问题,然后对任务到达过程和服务率知识进行在线的学习.一旦获得任务分配概率,遵从该概率可进行快速的任务调度.实验表明上述两个算法相比于Min-Min、Max-Min、Suffrage、ECT四种经典调度算法具有更短的平均响应时间.除此性能外,通过实验分析了该概率型调度方法的稳定性.

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.