朱洪雷，劉丙偉，孟繁明

（1.國(guó)網(wǎng)山東省電力公司檢修公司 山東 濟(jì)南250101；2.山東正晨科技股份有限公司 山東 濟(jì)南250101）

基于排隊(duì)論的煤礦應(yīng)急云作業(yè)調(diào)度模型研究

朱洪雷1，劉丙偉1，孟繁明2

（1.國(guó)網(wǎng)山東省電力公司檢修公司 山東 濟(jì)南250101；2.山東正晨科技股份有限公司 山東 濟(jì)南250101）

在云計(jì)算環(huán)境下，針對(duì)煤礦應(yīng)急云的多用戶和異構(gòu)環(huán)境，為提高煤礦應(yīng)急云平臺(tái)中海量數(shù)據(jù)挖掘運(yùn)算過(guò)程中作業(yè)的調(diào)度效率和系統(tǒng)負(fù)載平衡能力，提出一個(gè)基于排隊(duì)論模型的煤礦應(yīng)急云動(dòng)態(tài)反饋?zhàn)鳂I(yè)調(diào)度算法，通過(guò)數(shù)據(jù)建模的方式，得出CMEC-MMS的平均隊(duì)長(zhǎng)比FIFO和FAIR Scheduler分別減少48%和29%，提高了作業(yè)調(diào)度的公平性并且提高了作業(yè)調(diào)度的效率。

云計(jì)算；作業(yè)調(diào)度；煤礦應(yīng)急云；公平性；負(fù)載平衡

煤礦應(yīng)急云環(huán)境可采用FIFO這種按照先后順序進(jìn)行調(diào)度的模式，煤礦應(yīng)急云平臺(tái)所要求的環(huán)境是一種多用戶環(huán)境，F(xiàn)IFO不能滿足煤礦應(yīng)急云平臺(tái)所要求的多用戶作業(yè)調(diào)度需求。煤礦應(yīng)急云環(huán)境也可以使用FAIR調(diào)度算法以及Capacity［2］調(diào)度算法，這兩種算法支持多用戶以及多隊(duì)列，但這兩種調(diào)度算是都是適合于同構(gòu)環(huán)境的集群，因此這兩種調(diào)度算法如果直接應(yīng)用到煤礦應(yīng)急云平臺(tái)將沒法保證資源有效利用，甚至?xí)?dǎo)致用戶作業(yè)不能在規(guī)定時(shí)間內(nèi)執(zhí)行完畢。針對(duì)異構(gòu)環(huán)境下的一種LATE［3］調(diào)度算法，可采用備份任務(wù)的方法來(lái)解決異構(gòu)環(huán)境下的作業(yè)調(diào)度，針對(duì)上述這些問(wèn)題，文中將設(shè)計(jì)一種適合煤礦應(yīng)急云環(huán)境的作業(yè)調(diào)度模型。

1 排隊(duì)論模型

排隊(duì)論是研究系統(tǒng)隨機(jī)聚散現(xiàn)象和隨機(jī)服務(wù)系統(tǒng)工作過(guò)程的數(shù)學(xué)理論和方法，通常由輸入過(guò)程、排隊(duì)規(guī)則、服務(wù)過(guò)程3部分組成排隊(duì)過(guò)程。

（1）輸入過(guò)程

輸入過(guò)程通常有確定型和隨機(jī)型兩種。確定型輸入是指客戶到達(dá)數(shù)在時(shí)間t內(nèi)是確定的，隨機(jī)型［4］輸入是指客戶到達(dá)數(shù)在時(shí)間t內(nèi)服從隨機(jī)分布。公式（1）表示在時(shí)間t內(nèi)到達(dá)n個(gè)客戶的概率：

若相繼到達(dá)的兩個(gè)客戶之前的間隔時(shí)間T服從負(fù)指數(shù)分布，即：

在公式（1）、（2）中，γ為單位時(shí)間內(nèi)客戶的期望到達(dá)數(shù)量，即平均到達(dá)率，在排隊(duì)論中，通常討論的輸入過(guò)程以隨機(jī)型為主。

2）排隊(duì)規(guī)則

排隊(duì)規(guī)則指到達(dá)排隊(duì)系統(tǒng)的顧客按怎樣的規(guī)則進(jìn)行排隊(duì)等待，可分為損失制，等待制和混合制3種［5］。

①損失制。當(dāng)顧客到達(dá)時(shí)，所有的服務(wù)臺(tái)均被占用，顧客隨即離去。

②等待制。當(dāng)顧客到達(dá)時(shí)，所有的服務(wù)臺(tái)均被占用，顧客就排隊(duì)等待，直到接受完服務(wù)才離去。

③混合制。在損失制和等待制兩者之間的是混合制，即既有等待又有損失。存在有隊(duì)列長(zhǎng)度有限和排隊(duì)等待時(shí)間有限兩種情況，在限度以內(nèi)就排隊(duì)等待，超過(guò)一定限度就離去。排隊(duì)方式還分為單、多、循環(huán)隊(duì)列。

3）服務(wù)機(jī)構(gòu)和服務(wù)時(shí)間

服務(wù)機(jī)構(gòu)可以是單個(gè)或多個(gè)服務(wù)臺(tái)。服務(wù)時(shí)間一般也分成確定型和隨機(jī)型兩種。而隨機(jī)型服務(wù)時(shí)間v則服從一定的隨機(jī)分布。如果服從負(fù)指數(shù)分布，則其分布函數(shù)為：

公式（3）中μ為平均服務(wù)率，1/μ為平均服務(wù)時(shí)間。

2 基于排隊(duì)論的煤礦應(yīng)急云作業(yè)調(diào)度模型研究

煤礦應(yīng)急云作業(yè)調(diào)度的M/M/S排隊(duì)模型 （M是Markov的字頭，代表指數(shù)分布）。本文將煤礦應(yīng)急云 （Coal Mine Emergency Cloud）作業(yè)調(diào)度［6］模型（縮寫為CMEC-MMS）引入到CMEC云平臺(tái)的作業(yè)調(diào)度模塊，該模型設(shè)計(jì)了一個(gè)作業(yè)排隊(duì)隊(duì)列，S個(gè)作業(yè)資源池服務(wù)窗口，所有作業(yè)統(tǒng)一提交到一個(gè)排隊(duì)隊(duì)列，然后控制器根據(jù)一定的策略選擇作業(yè)到S個(gè)資源池服務(wù)窗口，Hadoop管理員可以根據(jù)需求配置每個(gè)服務(wù)窗口的容量以及同時(shí)運(yùn)行的作業(yè)數(shù)目。

3 CMEC-MMS模型的簡(jiǎn)化推導(dǎo)

3.1 FIFO調(diào)度作業(yè)隊(duì)長(zhǎng)分布

3.2 煤礦應(yīng)急云CMEC-MMS-Scheduler 算法總體設(shè)計(jì)

整體算法設(shè)計(jì)CMEC-MMS-Scheduler整體的算法設(shè)計(jì)如圖1所示，在CMEC-MMS算法中，設(shè)計(jì)了一個(gè)作業(yè)排隊(duì)隊(duì)列和S個(gè)資源池服務(wù)窗口，還包括：作業(yè)分發(fā)控制、反饋機(jī)制參數(shù)統(tǒng)計(jì)、基于LATE的備份任務(wù)計(jì)算模塊。

由作業(yè)分發(fā)控制模塊從排隊(duì)隊(duì)列中取一個(gè)作業(yè)分發(fā)給資源池窗口中進(jìn)行執(zhí)行，參數(shù)統(tǒng)計(jì)模塊首先是依據(jù)Hadoop心跳機(jī)制統(tǒng)計(jì)實(shí)際的平均到達(dá)率、平均服務(wù)率的參數(shù)值，然后反饋機(jī)制模塊根據(jù)云作業(yè)調(diào)度CMEC-MMS-Scheduler模型計(jì)算出平均隊(duì)長(zhǎng)和平均逗留時(shí)間的理論值，并調(diào)整CMECMMS-Scheduler中的輸入?yún)?shù)。

整體的CMEC-MMS-Scheduler算法偽代碼如下：

圖1 算法統(tǒng)計(jì)圖

在CMEC-MMS-Scheduler設(shè)計(jì)中的一個(gè)先進(jìn)之處就在于只設(shè)計(jì)了一個(gè)排隊(duì)隊(duì)列，當(dāng)用戶提交作業(yè)后，后由作業(yè)分發(fā)控制模塊將作業(yè)分發(fā)到資源池窗口中運(yùn)行。本文在排隊(duì)隊(duì)列中設(shè)計(jì)了一個(gè)優(yōu)先級(jí)窗口，窗口大小是用戶是可以控制的，具體選擇哪個(gè)作業(yè)是給窗口內(nèi)的作業(yè)進(jìn)行打分，打分公式如下：

在公式（6）中Pri是作業(yè)的優(yōu)先級(jí)，在調(diào)度系統(tǒng)中作業(yè)優(yōu)先級(jí)取值為：VERY_HIGH，HIGH，NORMAL，LOW，VERY_LOW這里為了便于量化的計(jì)算，定義取值如表格1所示。

表1 優(yōu)先級(jí)量化取值

參數(shù)t是一個(gè)時(shí)間因素，具體是用通過(guò)先后排隊(duì)順序的值，其意義在于進(jìn)入排隊(duì)越早，其值越大，也就是越早排隊(duì)的應(yīng)該優(yōu)先被調(diào)度執(zhí)行，參數(shù)α是一個(gè)調(diào)節(jié)因子，默認(rèn)取值為0.5，表示兩個(gè)因素所產(chǎn)生的影響是相同的。在一個(gè)窗口內(nèi)計(jì)算每個(gè)作業(yè)的打分值G，并按照G進(jìn)行排序，取得分值最高的作為調(diào)度作業(yè)，然后向后滑動(dòng)窗口，如圖2所示。

圖2 CMEC-MMS-Scheduler優(yōu)先級(jí)窗口設(shè)計(jì)

在圖2中綠色部分為優(yōu)先級(jí)窗口，灰色為排隊(duì)隊(duì)列，圖中優(yōu)先級(jí)窗口大小為3，系統(tǒng)開始時(shí)優(yōu)先級(jí)窗口位于排隊(duì)隊(duì)列首部，分別計(jì)算窗口內(nèi)的3個(gè)作業(yè)的得分值G，然后根據(jù)得分值G對(duì)作業(yè)進(jìn)行排序，取得分值最高的作業(yè)交給作業(yè)分發(fā)控制模塊并依據(jù)用戶指定的資源池窗口來(lái)調(diào)度執(zhí)行，具體步驟見算法整體設(shè)計(jì)如圖3所示。

圖3 CMEC-MMS-Scheduler優(yōu)先級(jí)窗口滑動(dòng)示意圖

由于在煤礦應(yīng)急云平臺(tái)中，煤礦應(yīng)急用戶的作業(yè)特征往往會(huì)發(fā)生變化，隨機(jī)會(huì)出現(xiàn)及時(shí)性要求高的作業(yè)提交到系統(tǒng)中，并沒有固有規(guī)律可循，因此非常有必要根據(jù)用戶的作業(yè)特征對(duì)調(diào)度器的相關(guān)參數(shù)進(jìn)行調(diào)整。具體的反饋系統(tǒng)設(shè)計(jì)見圖4所示。

圖4 CMEC-MMS-Scheduler反饋系統(tǒng)

在圖4中反饋機(jī)制主要包括兩個(gè)核心模塊：參數(shù)統(tǒng)計(jì)模塊和反饋機(jī)制模塊。將獲得的平均到達(dá)率和平均服務(wù)率這兩個(gè)核心參數(shù)的實(shí)際值傳給反饋機(jī)制模塊，根據(jù)CMEC-MMS調(diào)度算法模型計(jì)算出平均逗留時(shí)間和平均隊(duì)長(zhǎng)的理論值并與實(shí)際值進(jìn)行對(duì)比，將具有較大平均逗留時(shí)間和平均隊(duì)長(zhǎng)的作業(yè)調(diào)度到有槽位數(shù)的資源池服務(wù)窗口執(zhí)行。文中采用LATE調(diào)度算法來(lái)解決異構(gòu)環(huán)境問(wèn)題而導(dǎo)致的作業(yè)運(yùn)行效率問(wèn)題。

3.3 平均隊(duì)長(zhǎng)對(duì)比驗(yàn)證

本節(jié)通過(guò)多次不同的實(shí)驗(yàn)來(lái)對(duì)平均隊(duì)長(zhǎng)做驗(yàn)證，使用3種類型的作業(yè)來(lái)做測(cè)試：Wordcount、Tera Sort、Pi。這里也使用一個(gè)隨機(jī)函數(shù)random（）來(lái)模擬生成和實(shí)際環(huán)境類似的優(yōu)先級(jí)情況，分別做多次實(shí)驗(yàn)，每次實(shí)驗(yàn)時(shí)作業(yè)數(shù)目不斷增加，然后計(jì)算平均隊(duì)長(zhǎng)，實(shí)驗(yàn)對(duì)比結(jié)果如圖5所示。

圖5 3種調(diào)度器的平均隊(duì)長(zhǎng)

從圖5可以看出，F(xiàn)IFO調(diào)度器中作業(yè)的平均隊(duì)長(zhǎng)基本是線性增加的，而對(duì)于FAIR Scheduler和文中的CMEC-MMSScheduler調(diào)度器來(lái)說(shuō)，在CMEC-MMS中，雖然只有一個(gè)排隊(duì)隊(duì)列但是有多個(gè)資源池窗口，也可以將3個(gè)作業(yè)同時(shí)調(diào)度到3個(gè)資源池窗口中分別執(zhí)行，因此平均隊(duì)長(zhǎng)也為0。當(dāng)作業(yè)數(shù)目增加到18時(shí)，F(xiàn)IFO、FAIR和CMEC-MMS-這3種調(diào)度器的作業(yè)平均隊(duì)長(zhǎng)分別為27、17和12，可以看出，CMEC-MMS的平均隊(duì)長(zhǎng)比FIFO和FAIR Scheduler分別減少48%和29%。

4 結(jié) 論

文中通過(guò)分析經(jīng)典作業(yè)調(diào)度算法的優(yōu)缺點(diǎn)，結(jié)合煤礦應(yīng)急云多用戶及異構(gòu)環(huán)境的特征，提出基于排隊(duì)論M/M/S模型，設(shè)計(jì)出一種基于排隊(duì)論的帶有反饋機(jī)制的動(dòng)態(tài)云作業(yè)調(diào)度算法CMEC-MMS-Scheduler算法，提高了煤礦應(yīng)急云平臺(tái)作業(yè)調(diào)度的高效性和公平性，通過(guò)平均隊(duì)長(zhǎng)對(duì)比驗(yàn)證表明該算法在云作業(yè)調(diào)度中相對(duì)于經(jīng)典算法具有較好的處理性能和負(fù)載平衡能力。

［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］排隊(duì)理論［EB/OL］.http://wiki.mbalib.com/wiki/排隊(duì)論.

［5］司守奎，徐珂文，李日華.數(shù)學(xué)建模算法大全［D］.煙臺(tái)：海軍航空學(xué)院，2012.

［6］劉賽，李緒蓉，萬(wàn)麟瑞等.云環(huán)境下資源調(diào)度模型研究［J］.計(jì)算機(jī)工程與科學(xué)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 稿件編號(hào)：201510086

朱洪雷（1970—），男，山東濟(jì)南人，高級(jí)技師。研究方向：變電站運(yùn)維技術(shù)。