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

关键词：分布式计算 多用户 任务调度 排队模型 概率型调度 

单位：湖南师范大学数学与计算机科学学院; 湖南大学信息科学与工程学院