基于排隊論的煤礦應急云作業調度模型研究

朱洪雷，劉丙偉，孟繁明

（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—），男，山東濟南人，高級技師。研究方向：變電站運維技術。