基于排队论的煤矿应急云作业调度模型研究

朱洪雷，刘丙伟，孟繁明

（1.国网山东省电力公司检修公司 山东 济南250101；2.山东正晨科技股份有限公司 山东 济南250101）

基于排队论的煤矿应急云作业调度模型研究

朱洪雷1，刘丙伟1，孟繁明2

（1.国网山东省电力公司检修公司 山东 济南250101；2.山东正晨科技股份有限公司 山东 济南250101）

在云计算环境下，针对煤矿应急云的多用户和异构环境，为提高煤矿应急云平台中海量数据挖掘运算过程中作业的调度效率和系统负载平衡能力，提出一个基于排队论模型的煤矿应急云动态反馈作业调度算法，通过数据建模的方式，得出CMEC-MMS的平均队长比FIFO和FAIR Scheduler分别减少48%和29%，提高了作业调度的公平性并且提高了作业调度的效率。

云计算；作业调度；煤矿应急云；公平性；负载平衡

煤矿应急云环境可采用FIFO这种按照先后顺序进行调度的模式，煤矿应急云平台所要求的环境是一种多用户环境，FIFO不能满足煤矿应急云平台所要求的多用户作业调度需求。煤矿应急云环境也可以使用FAIR调度算法以及Capacity［2］调度算法，这两种算法支持多用户以及多队列，但这两种调度算是都是适合于同构环境的集群，因此这两种调度算法如果直接应用到煤矿应急云平台将没法保证资源有效利用，甚至会导致用户作业不能在规定时间内执行完毕。针对异构环境下的一种LATE［3］调度算法，可采用备份任务的方法来解决异构环境下的作业调度，针对上述这些问题，文中将设计一种适合煤矿应急云环境的作业调度模型。

1 排队论模型

排队论是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，通常由输入过程、排队规则、服务过程3部分组成排队过程。

（1）输入过程

输入过程通常有确定型和随机型两种。确定型输入是指客户到达数在时间t内是确定的，随机型［4］输入是指客户到达数在时间t内服从随机分布。公式（1）表示在时间t内到达n个客户的概率：

若相继到达的两个客户之前的间隔时间T服从负指数分布，即：

在公式（1）、（2）中，γ为单位时间内客户的期望到达数量，即平均到达率，在排队论中，通常讨论的输入过程以随机型为主。

2）排队规则

排队规则指到达排队系统的顾客按怎样的规则进行排队等待，可分为损失制，等待制和混合制3种［5］。

①损失制。当顾客到达时，所有的服务台均被占用，顾客随即离去。

②等待制。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去。

③混合制。在损失制和等待制两者之间的是混合制，即既有等待又有损失。存在有队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就离去。排队方式还分为单、多、循环队列。

3）服务机构和服务时间

服务机构可以是单个或多个服务台。服务时间一般也分成确定型和随机型两种。而随机型服务时间v则服从一定的随机分布。如果服从负指数分布，则其分布函数为：

公式（3）中μ为平均服务率，1/μ为平均服务时间。

2 基于排队论的煤矿应急云作业调度模型研究

煤矿应急云作业调度的M/M/S排队模型 （M是Markov的字头，代表指数分布）。本文将煤矿应急云 （Coal Mine Emergency Cloud）作业调度［6］模型（缩写为CMEC-MMS）引入到CMEC云平台的作业调度模块，该模型设计了一个作业排队队列，S个作业资源池服务窗口，所有作业统一提交到一个排队队列，然后控制器根据一定的策略选择作业到S个资源池服务窗口，Hadoop管理员可以根据需求配置每个服务窗口的容量以及同时运行的作业数目。

3 CMEC-MMS模型的简化推导

3.1 FIFO调度作业队长分布

3.2 煤矿应急云CMEC-MMS-Scheduler 算法总体设计

整体算法设计CMEC-MMS-Scheduler整体的算法设计如图1所示，在CMEC-MMS算法中，设计了一个作业排队队列和S个资源池服务窗口，还包括：作业分发控制、反馈机制参数统计、基于LATE的备份任务计算模块。

由作业分发控制模块从排队队列中取一个作业分发给资源池窗口中进行执行，参数统计模块首先是依据Hadoop心跳机制统计实际的平均到达率、平均服务率的参数值，然后反馈机制模块根据云作业调度CMEC-MMS-Scheduler模型计算出平均队长和平均逗留时间的理论值，并调整CMECMMS-Scheduler中的输入参数。

整体的CMEC-MMS-Scheduler算法伪代码如下：

图1 算法统计图

在CMEC-MMS-Scheduler设计中的一个先进之处就在于只设计了一个排队队列，当用户提交作业后，后由作业分发控制模块将作业分发到资源池窗口中运行。本文在排队队列中设计了一个优先级窗口，窗口大小是用户是可以控制的，具体选择哪个作业是给窗口内的作业进行打分，打分公式如下：

在公式（6）中Pri是作业的优先级，在调度系统中作业优先级取值为：VERY_HIGH，HIGH，NORMAL，LOW，VERY_LOW这里为了便于量化的计算，定义取值如表格1所示。

表1 优先级量化取值

参数t是一个时间因素，具体是用通过先后排队顺序的值，其意义在于进入排队越早，其值越大，也就是越早排队的应该优先被调度执行，参数α是一个调节因子，默认取值为0.5，表示两个因素所产生的影响是相同的。在一个窗口内计算每个作业的打分值G，并按照G进行排序，取得分值最高的作为调度作业，然后向后滑动窗口，如图2所示。

图2 CMEC-MMS-Scheduler优先级窗口设计

在图2中绿色部分为优先级窗口，灰色为排队队列，图中优先级窗口大小为3，系统开始时优先级窗口位于排队队列首部，分别计算窗口内的3个作业的得分值G，然后根据得分值G对作业进行排序，取得分值最高的作业交给作业分发控制模块并依据用户指定的资源池窗口来调度执行，具体步骤见算法整体设计如图3所示。

图3 CMEC-MMS-Scheduler优先级窗口滑动示意图

由于在煤矿应急云平台中，煤矿应急用户的作业特征往往会发生变化，随机会出现及时性要求高的作业提交到系统中，并没有固有规律可循，因此非常有必要根据用户的作业特征对调度器的相关参数进行调整。具体的反馈系统设计见图4所示。

图4 CMEC-MMS-Scheduler反馈系统

在图4中反馈机制主要包括两个核心模块：参数统计模块和反馈机制模块。将获得的平均到达率和平均服务率这两个核心参数的实际值传给反馈机制模块，根据CMEC-MMS调度算法模型计算出平均逗留时间和平均队长的理论值并与实际值进行对比，将具有较大平均逗留时间和平均队长的作业调度到有槽位数的资源池服务窗口执行。文中采用LATE调度算法来解决异构环境问题而导致的作业运行效率问题。

3.3 平均队长对比验证

本节通过多次不同的实验来对平均队长做验证，使用3种类型的作业来做测试：Wordcount、Tera Sort、Pi。这里也使用一个随机函数random（）来模拟生成和实际环境类似的优先级情况，分别做多次实验，每次实验时作业数目不断增加，然后计算平均队长，实验对比结果如图5所示。

图5 3种调度器的平均队长

从图5可以看出，FIFO调度器中作业的平均队长基本是线性增加的，而对于FAIR Scheduler和文中的CMEC-MMSScheduler调度器来说，在CMEC-MMS中，虽然只有一个排队队列但是有多个资源池窗口，也可以将3个作业同时调度到3个资源池窗口中分别执行，因此平均队长也为0。当作业数目增加到18时，FIFO、FAIR和CMEC-MMS-这3种调度器的作业平均队长分别为27、17和12，可以看出，CMEC-MMS的平均队长比FIFO和FAIR Scheduler分别减少48%和29%。

4 结 论

文中通过分析经典作业调度算法的优缺点，结合煤矿应急云多用户及异构环境的特征，提出基于排队论M/M/S模型，设计出一种基于排队论的带有反馈机制的动态云作业调度算法CMEC-MMS-Scheduler算法，提高了煤矿应急云平台作业调度的高效性和公平性，通过平均队长对比验证表明该算法在云作业调度中相对于经典算法具有较好的处理性能和负载平衡能力。

［1］Zaharia M，Borthakur D，Sarma J S，etal.Stoica，Job scheduling for multi-user mapreduce clusters［J］.EECS Department，University of California，Berkeley，Tech.Rep. USB/EECS，2009，4：55.

［2］Hadoop capacity Scheduler.Available:http://hadoop.apche. org/common/docs/c urrent/capacity_scheduler.htm l.accessed on Feb 18，2011［EB/OL］.

［3］Matei Zaharia，Dhruba Borthakur，Joydeep Sen Sarma，Khaled Elmeleegy，Scott Shenker，and Ion Stoica.Delay scheduling:a simple technique for achieving locality and fairness in cluster scheduling［C］∥In Euro Sys'10:Proceedings of the 5th European conference on Computer systems，pages 265-278，New York，NY，USA，2010.ACM.

［4］排队理论［EB/OL］.http://wiki.mbalib.com/wiki/排队论.

［5］司守奎，徐珂文，李日华.数学建模算法大全［D］.烟台：海军航空学院，2012.

［6］刘赛，李绪蓉，万麟瑞等.云环境下资源调度模型研究［J］.计算机工程与科学2013，35（3）:48-51.

Cloud job schedulingmodel based on queuing theory of coalm ine emergency

ZHU Hong-lei1，LIU Bing-wei1，MENG Fan-ming2
（1.State Grid Power Company Maintenance Company in Shandong Province，Shandong，Jinan 250101，China；2.Shandong Zhengchen Technology Company，Jinan 250101，China）

In the cloud computing environment for coalmine emergency cloud and heterogeneousmulti-user environment，improve coalmine emergencyminingmassive data cloud platform scheduling efficiency and system load balancing capabilities jobs during operation，propose a coal mine based on queuing theory model of emergency cloud dynamic Feedback job scheduling algorithms，datamodeling through simulation approach gives the average captain CMEC-MMS reduction of 48% and 29%respectively，compared with FIFO and improve the fairness of fAIR Scheduler job scheduling and job scheduling to improve efficiency has become a measure of coalmine emergency cloud platform level data processing performance is an importantindicator.

cloud computing；job scheduling；coalmine emergency cloud；fairness；load balancing

TN91

A

1674－6236（2016）20-0030-03

2015-10-15 稿件编号：201510086

朱洪雷（1970—），男，山东济南人，高级技师。研究方向：变电站运维技术。