电子学报 ›› 2016, Vol. 44 ›› Issue (7): 1679-1688.DOI: 10.3969/j.issn.0372-2112.2016.07.023

• 学术论文 • 上一篇    下一篇

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

童钊1,2, 肖正2, 李肯立2   

  1. 1. 湖南师范大学数学与计算机科学学院, 湖南长沙 410082;
    2. 湖南大学信息科学与工程学院, 湖南长沙 410082
  • 收稿日期:2013-02-27 修回日期:2013-07-26 出版日期:2016-07-25
    • 作者简介:
    • 童钊 男,1985年2月生,湖南岳阳人.2007年获得北京理工大学计算机科学专业学士学位,2014年获得湖南大学工学博士学位,现为湖南师范大学数学与计算机科学学院讲师.主要研究方向为并行与分布式计算、资源管理、任务调度、并行算法设计.E-mail:tongzhao@hunnu.edu.cn;肖正 男,1981年4月生,湖南怀化人.2003年本科毕业于湖南大学通信工程专业,2009年获得复旦大学计算机应用技术专业博士学位,现为湖南大学信息科学与工程学院助理教授.主要研究方向为并行与分布式计算,分布式人工智能,协同计算.E-mail:zxiao@hnu.edu.cn;李肯立 男,1971年10月生,湖南娄底人.2000年获得中南大学数学专业硕士学位,2003年获得华中科技大学计算机科学博士学位,现为湖南大学信息科学与工程学院教授.2004年至2005年在伊利诺伊大学厄巴纳-香槟分校任访问学者.2013年获得教育部科技进步二等奖.CCF高级会员.主要研究方向为并行计算,网格计算,云计算,DNA计算.E-mail:lkl510@263.net
    • 基金资助:
    • 国家自然科学基金重点项目 (No.61133005); 国家自然科学基金青年项目 (No.61402157); 湖南省自然科学基金 (No.13JJ4038); 湖南师范大学青年基金 (No.11404)

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

TONG Zhao1,2, XIAO Zheng2, LI Ken-li2   

  1. 1. College of Mathematics and Computer Science, Hunan Normal University, Changsha, Hunan 410082, China;
    2. College of Information Science and Engineering, Hunan University, Changsha, Hunan 410082, China
  • Received:2013-02-27 Revised:2013-07-26 Online:2016-07-25 Published:2016-07-25

摘要:

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

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

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 scheduling to compress scheduling time,which regards task allocation as a probabilistic event.Unexpectedly,compared with traditional 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 response time from the perspective of users,a queueing model is given for multi-user network application,and scheduling is defined as a non-linear programming problem.But due to its limitation on task arrival process and service rate,a self-adaptive algorithm 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 1引言

中图分类号: