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

被引：4

作者：

童钊 ^{[1
,2
]}

肖正 ^{[2
]}

李肯立 ^{[2
]}

机构：

[1] 湖南师范大学数学与计算机科学学院

[2] 湖南大学信息科学与工程学院

来源：

电子学报 | 2016年 / 44卷 / 07期

基金：

湖南省自然科学基金; 国家自然科学基金重点项目;

关键词：

分布式计算; 多用户; 任务调度; 排队模型; 概率型调度;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

页码：1679 / 1688

页数：10

共 12 条

[1] 一种基于VFD多核系统的硬实时任务节能调度算法 [J].

吴小东 ;

韩建军 ;

王天江 .

计算机研究与发展, 2012, 49 (05) :1018-1027

[2] 截止时间约束下独立网格任务的协同调度模型 [J].

肖鹏 ;

胡志刚 .

电子学报, 2011, 39 (08) :1852-1857

[3] 数据网格虚拟机动态存储层次的研究 [J].

艾丽华 ;

罗四维 .

电子学报, 2010, 38 (11) :2680-2685

[4] 基于最大负载偏移率的并行负载平衡性能分析 [J].

张理论 ;

叶红 ;

吴建平 ;

宋君强 .

计算机研究与发展, 2010, 47 (06) :1125-1131

[5] 虚拟计算环境中的多机群协同调度算法 [J].

张伟哲 ;

田志宏 ;

张宏莉 ;

何慧 ;

刘文懋 .

软件学报, 2007, (08) :2027-2037

[6] Multi-Criteria Job Scheduling in Grid Using an Accelerated Genetic Algorithm [J].

Gkoutioudi, Kyriaki Z. ;

Karatza, Helen D. .

JOURNAL OF GRID COMPUTING, 2012, 10 (02) :311-323

[7]

A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system[J] . Yun Wen,Hua Xu,Jiadong Yang.Information Sciences . 2010 (3)

[8]

Contention-aware scheduling with task duplication[J] . Oliver Sinnen,Andrea To,Manpreet Kaur.Journal of Parallel and Distributed Computing . 2010 (1)

[9]

Genetic algorithms for task scheduling problem[J] . Fatma A. Omara,Mona M. Arafa.Journal of Parallel and Distributed Computing . 2009 (1)

[10] Complexity Results for Throughput and Latency Optimization of Replicated and Data-parallel Workflows [J].

Benoit, Anne ;

Robert, Yves .

ALGORITHMICA, 2010, 57 (04) :689-724

← 1 2 →