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

doi:10.3969/j.issn.0372-2112.2016.07.023

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

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

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

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 Zhao^1,2, XIAO Zheng², LI Ken-li²

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

摘要/Abstract

摘要：

多用户网络应用是分布式计算中最主要的形式之一.为了充分挖掘分布式系统中的计算资源,任务调度是解决该问题的关键.然而,由于多用户网络应用中存在的不确定性,使得当前的调度方法在动态性、实时性、适应性等方面都存在诸多不足.考虑到用户实时性需求,本文提出了概率型调度的思想.该思想将任务的分配看作概率事件,以用户角度的最短响应时间为目标,给出了多用户网络应用的排队模型,并进一步将调度定义为一个非线性规划问题.分析表明上述方法在任务到达过程、服务率方面存在限制,进而提出了一个基于强化学习理论自适应调度算法.该算法首先利用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引言

中图分类号:

TP391

童钊, 肖正, 李肯立. 分布式系统中多用户网络应用的概率型调度算法研究[J]. 电子学报, 2016, 44(7): 1679-1688.

TONG Zhao, XIAO Zheng, LI Ken-li. A Queueing Model and Probabilistic Scheduling for Multi-user Network Applications[J]. Acta Electronica Sinica, 2016, 44(7): 1679-1688.

参考文献

[1] Jiang Y C,Jiang J C.Contextual resource negotiation-based task allocation and load balancing in complex software systems[J].IEEE Trans Parallel and Distribut ed Systems,2009,20(5):641-653.
[2] Gary M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-C ompleteness[M],New York,NY,USA:W H Freeman and Co, 1979.
[3] Ullman J D.NP-complete scheduling problems[J].J Computer and Systems Sciences,1975,10:384-393.
[4] Gkoutioudi K Z,Karatza H D.Multi-criteria job scheduling in grid using an accelerated genetic algorithm[J].J Grid Computing,2012,10(2):311-323.
[5] Omara F A,Arafa M M.Genetic algorithms for task scheduling problem[J].J Parall el and Distributed Computing,2010,70(1):13-22.
[6] Hu X S,Dick R P.Temperature-aware scheduling and assignment for hard real-time applications on MPSoCs[J].IEEE Trans Very Large Scale Integration Systems,2011,19(10):1884-1897.
[7] Chakrabarti P P,Kumar R.Online scheduling of dynamic task graphs with communication and contention for multiprocessors[J].IEEE Trans on Parallel and Distributed Systems,2012,23(1):138-153.
[8] Wen Y,Xu H,Yang J D.A heuristic-based hybrid genetic-variable neighborhood sea rch algorithm for task scheduling in heterogeneous multiprocessor system[J].In formation Sciences,2011,181(3):567-581.
[9] Sinnen O,To A,Kaur M.Contention-aware scheduling with task duplication[J].J Parall el and Distributed Computing,2011,71(1):77-86.
[10] Benoit A,Robert Y.Complexity results for throughput and latency optimization of replicated and data-parallel workflows[J].Algorithmica,2010,57(4):689-724.
[11] 艾丽华,罗四维.数据网格虚拟机动态存储层析的研究[J].电子学报,2010,38(11):2680-2685. AI Li-hua,LUO Si-wei.Research on dynamic storage hierarchy of data grid virtual machine[J].Acta Electronica Sinica,2010,38(11):2680-2685.(in Chinese)
[12] Subrate R,Zomaya A Y,Landfeldt B.Game-theoretic approach for load balancing in computational grids[J].IEEE Trans on Parallel and Distributed Systems,2008,19(1):66-76.
[13] Jiang Y C,Huang Z C.The rich get richer:preferential attachment in the task allocation of cooperative networked multiagent systems with resource caching[J].IEEE Trans on Systems,Man,and Cybernetics-Part A:Systems and Humans,2012,24(5):1040-1052.
[14] Aktaruzzaman M.Literature Review and Survey:Resource Discovery in Computational Grids[R].Technical Report,School of Computer Science,University of Windsor,Windsor,Ontario,Canada,2003.
[15] 张伟哲,田志宏,张宏莉,等.虚拟计算环境中的多机群协同调度算法[J].软件学报,2007,18(8):2027-2037. Zhang Weizhe,Tian Zhihong,Zhang Hongli,et al.Multi-cluster co-allocation scheduling algorithms in virtual computing environment[J].Journal of Software,2007,18(8):2027-2037.(in Chinese)
[16] 肖鹏,胡志刚.截止时间约束下独立网格任务的协同调度模型[J].电子学报,2011,39(8):1852-1857. Xiao Peng,Hu Zhigang.Co-scheduling model for independent tasks with deadline constraint in computational grid[J].Acta Electronica Sinica,2011,39(8):1852-1857.(in Chinese)
[17] He L,Jarvis S A,Spooner D P,Bacigalupo D,Tan G,Nudd G R.Scheduling DAG-based applications in multicluster environments with background workload using task duplication[J].International Journal of Computer Mathematics,2010,87(11):2387-2397.
[18] Sakellariou R,Zhao H.A low-cost rescheduling policy for efficient mapping of workflows on grid systems[J].J Scientific Programming,2004,12(4):253-262.
[19] 张理论,叶红,吴建平,等.基于最大负载偏移率的并行负载平衡性能分析[J].计算机研究与发展,2010,47(6):1125-1131. Zhang Lilun,Ye Hong,Wu Jianping.Parallel load-balancing performance analysis based on maximal ratio of load offset[J].Journal of Computer Research and Development,2010,47(6):1125-1131.(in Chinese)
[20] Qin X,Xie T.An availability-aware task scheduling strategy for heterogeneous systems[J].IEEE Trans on Computers,2008,7(57):188-199.
[21] Donald Gross,John F Shortle,James M Thompson,Carl M Harris.Fundamentals of Queueing Theory[M].Hoboken,NJ:John Wiley & Sons,2008.
[22] Kaelbling L P,Littman M L,Moore A W.Reinforcement learning:a survey[J].Journal of Artificial Intelligence Research,1996,4:237-285.
[23] 吴小东,韩建军,王夭江.一种基于VFD多核系统的硬实时任务节能调度算法[J].计算机研究与发展,2012,49(5):1018-1027. Wu Xiaodong,Han Jianjun,Wang Tianjiang.Energy-aware scheduling of hard real-time tasks in VFD-based multi-core systems[J].Journal of Computer Research and Development,2012,49(5):1018-1027.(in Chinese)

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张敏惠, 童杨, 王怡. 基于Kappa-mu/M分布的联合多用户分集与并行中继继选择RF/FSO系统性能研究[J]. 电子学报, 2022, 50(1): 26-35.
[2]	刘文亚, 王翔, 赵尚弘, 牟迪. 同频干扰下混合MUD-RF/FSO航空中继通信系统性能分析[J]. 电子学报, 2021, 49(10): 1960-1968.
[3]	张浩为, 谢军伟, 胡祺勇, 葛佳昂, 宗彬锋, 路文龙. 数字阵列雷达在线交错调度算法[J]. 电子学报, 2019, 47(6): 1260-1266.
[4]	熊兵, 左明科, 黎维, 王进. 面向软件定义核心网的OpenFlow分组转发优先制排队模型研究[J]. 电子学报, 2019, 47(10): 2040-2049.
[5]	卢晶, 段勇, 刘海波. 基于z值的分布式密度峰值聚类算法[J]. 电子学报, 2018, 46(3): 730-738.
[6]	雷维嘉, 王娟兵, 谢显中. 大规模MIMO中继系统中多用户物理层安全传输方案[J]. 电子学报, 2018, 46(12): 2878-2887.
[7]	曹杰, 廖勇, 王丹, 周昕, 李瑜锋. 基于非理想CSI的下行MU-MIMO鲁棒波束成形[J]. 电子学报, 2016, 44(9): 2093-2099.
[8]	唐震洲, 李昌, 阮秀凯, 胡倩. 双时隙多用户线性网络编码协作的中断概率分析[J]. 电子学报, 2016, 44(2): 289-294.
[9]	任俊亮, 邢清华, 李龙跃, 贾哲. 分布式传感器调度模型与自适应概率粒子群优化算法[J]. 电子学报, 2015, 43(9): 1756-1762.
[10]	李光平, 张广驰, 崔苗, 冯久超. 基于中继放大转发的多天线基站下行传输性能分析[J]. 电子学报, 2013, 41(7): 1305-1312.
[11]	徐超, 何炎祥, 陈勇, 刘健博, 吴伟, 李清安. 一种多核系统可靠性加强的任务调度方法[J]. 电子学报, 2013, 41(5): 1019-1024.
[12]	李劲, 岳昆, 刘惟一. 基于融合的无线传感器网络k-集覆盖的分布式算法[J]. 电子学报, 2013, 41(4): 659-665.
[13]	韩永, 姚念民, 蔡绍滨, 陈金忠. iSCSI虚拟交换机包转发调度算法FC-WFQ[J]. 电子学报, 2013, 41(3): 587-592.
[14]	任啸天, 徐晖, 黄知涛, 王丰华, 陆凤波. 基于Fast-ICA的CDMA信号扩频序列优化盲估计[J]. 电子学报, 2012, 40(8): 1532-1538.
[15]	黄英, 雷菁, 魏急波, 姜文利. 基于多用户协同的中继编码设计[J]. 电子学报, 2012, 40(10): 1971-1975.