基于主機性能度量的異構集群作業調度算法

王超 陳剛 黃剛 王彪

摘要：傳統經典作業度算法在集群應用中實現簡單、執行效率高，但在異構集群環境下由于缺乏在線節點運行狀態動態反饋能力和負載均衡能力，降低了計算資源利用率和系統吞吐率。為解決上述問題，設計了一種在異構集群環境下基于主機性能度量的作業負載均衡調度算法，該算法通過收集集群中在線節點的狀態信息和作業響應時間遴選出可信節點集合，計算出各可信節點的HPM值，利用負載均衡運算規則生成候選的作業分配節點集合，最終按照預先設計的優先原則把不同作業分配至各計算節點，并更新各節點運行狀態。實驗結果表明，在異構集群環境下調度同類型作業時，該算法在總完成時間和負載均衡性能等指標上均優于傳統經典算法。

關鍵詞：異構集群;主機性能度量;負載均衡;作業調度

中圖分類號：TP301文獻標志碼：A文章編號：1008-1739（2021）08-67-7

0引言

集群是多臺相互獨立的計算機，通過高速網絡互聯形成一個整體系統后，對外提供服務并對集群本身加以管理。集群運行過程的作業調度策略對集群資源利用率起著關鍵作用[1]，調度策略的優劣決定了集群中作業完成的效率。作業調度算法大致分為相互依賴和相互獨立2種算法。前者算法缺陷明顯，工程應用不多，后者算法因實現簡單，大多數集群管理系統都在采用。目前在國內外廣泛應用的相互獨立的經典作業調度算法中，主要包括先來先到服務（First Come First Service，FCFS）、Min-Min算法和基于優先級調度（Priority）等[2]。

常見的算法還包括輪詢調度算法、最小鏈接算法、遺傳算法、模擬退火算法等，但是輪詢調度算法和最小鏈接算法，沒有考慮各服務節點的性能差異[13]，遺傳算法和模擬退火算法適應于對復雜問題的優化，時效性較差[14]。在異構集群環境下，由于各節點計算機性能差異較大，上述算法的缺陷顯得更為明顯。為提升對異構集群資源的利用率，本文提出了主機性能度量（Host Performance Measurement，HPM）的概念，對集群各節點計算機的性能進行量化，并設計了一種基于主機性能度量的作業負載均衡調度（Host Performance Measurement Load Balancing，HPMLB）算法。該算法主要通過度量主機性能和判斷作業響應時間容忍度實現動態的HPMLB，由集群的調度節點根據集群各節點的HPM信息，結合作業響應狀態，依據負載均衡調度策略，將請求分配到集群中的各個計算節點，被派發作業的計算節點將接收請求并進行作業處理。該算法采用分層設計理念，使得作業調度層與計算執行層相分離，實現了對異構集群環境下具有相同功能不同實現的計算作業的調度。

1問題建模

在集群作業調度中，有一個節點作為調度節點，完成對所有作業的計算資源調度與分配，各計算節點完成業務計算。系統整體調度與管理流程如下：

①集群節點的網絡代理軟件接收作業請求命令;

②集群調度節點獲取調度狀態;

③集群調度節點的負載均衡調度器根據負載均衡調度算法進行調度計算和作業派發;

④受理作業計算節點進行具體的計算處理，同時根據作業執行情況更新本機狀態;

⑤各集群節點通過集群狀態同步機制動態實現各節點服務器狀態同步。

針對上述流程，本文設計的HPMLB算法主要思想是：

①通過HPM、執行工作列表（Executive Job List，EJL）和作業響應時間容忍度來動態地描述集群各節點當前負載情況;

②由集群調度節點根據集群各節點的HPM和EJL等關鍵信息，結合作業響應狀態，依據負載均衡調度策略，將請求分配到集群中各計算節點;

③各計算節點中的作業組織流程負責接受請求并組織作業執行器進行作業處理;

④各計算節點實時更新和對外發布本機的HPM和EJL等信息。

作業調度總體流程如圖1所示。

整個作業調度由集群中的調度節點完成，當進行HPMLB時，調度節點首先收集集群中在線節點并篩選出可信節點。然后計算各可信節點的HPM值，根據負載均衡運算規則生成候選集合。最后，依據同等條件下的優先原則進行作業分派，分派完成后進行各節點狀態更新。

為準確描述上述過程，給出集群節點性能、EJL和網絡狀態信息等概念的定義：

②EJL具體內容如表1所示。

③集群節點狀態信息（The Cluster Node Status information，CNS）：各集群節點服務器維護本機的狀態以及本機與其余節點的狀態信息，如表2所示。

2算法設計

2.1生成可信節點

（1）收集在線節點

集群各節點都保存集群狀態信息列表，包含本節點與集群其他所有節點當前的網絡狀態情況，并以固定周期△輪詢檢測更新整個集群的狀態信息，其檢測方式為集群中各節點以固定周期△循環接收集群節點的狀態信息和第三方心跳;接收調度節點信號，確定調度節點的狀態;完成節點狀態信息的同步與更新;調度節點根據心跳檢測和集群節點的狀態信息，生成集群在線節點的集合A。

（2）篩選可信節點

在生成的集群在線節點集合A中，調度節點查詢集合A中各個的IGHOST_INFO[].mainstatus值，若該值為1，則表示該對應的節點與調度節點通信正常，若為0，則表示與調度節點通信狀態異常，將其中值為1的生成與調度節點通信正常的節點集合B;

然后篩選出滿足作業響應時間容忍度的節點，生成可信節點集合C，根據式（3）進行本節點與集合B中節點的網絡路徑計算，獲取本地的當前時間，然后獲取本節點接收到的最近一次該發送的節點心跳時間，計算出該與調度節點的系統路徑長度。

作業響應時間容忍度Dpt作為系統常數進行配置，通過式（5）進行作業響應狀態運算。（）=1表示作業響應正常，（）=0表示作業響應超時，并將值為1的放在集合C中。

2.2作業調度

調度節點在生成的可信節點集合C中，計算HPM值，選取HPM值最小的節點集合生成候選集合D。在候選集合生成后，按如下原則進行作業分配：

①若系統滿負荷，即HPM值為Mhpm，作業拒絕;

②若候選節點唯一，即集合D中的元素唯一，則作業直接派發給該;

③若候選節點不唯一，即集合D中的元素不唯一，則選取值最大的進行派發。

詳細處理流程如圖2所示。

①獲取調度請求;

②獲取節點計算機的狀態信息;

③查詢集群狀態列表，獲取其為在線狀態的計算機節點集合A;

④在集合A中查詢與調度節點網絡狀態正常的計算機節點集合B;

⑤在集合B中遴選出滿足（）=1的集合C，其中作業響應的容忍時間Dpt一般設置為3△;

⑥在集合C中計算并選擇HPM值最小的集合D;

⑦判斷集合D的元素個數是否為1，若為1，則將該“+調度請求”作為調度請求結果對外發出，否則將集合中“最大值的+調度請求”作為調度請求結果對外發出;若集合D中各對應的計算機的HPM值>Mhpm（系統允許的最大負荷0<≤1）時，置為MAX_HOSTNUM+1;

⑧更新各節點當前的值。

2.3狀態動態同步

HPMLB算法在進行作業調度時，為了及時獲取集群各節點的動態負載情況以及對整個集群系統的集中管控，設計了集群狀態動態同步機制，集群各節點實時收集更新本節點狀態，并將本節點狀態對外發出，同時接收其余節點狀態信息，將接收到的其他節點狀態信息更新到本機。其同步及發布內容有：維護本節點作業執行狀態;維護本節點HPM值;對外發布工作列表數據;更新本節點保存的其余節點發布的狀態信息;維護本節點與其余節點的網絡狀態，若本節點與某一節點的節點網絡狀態函數nets （）的值為0，則將本節點與該節點之間的網絡狀態設置為超時;對外發布本節點狀態信息。

2.4整體算法描述

根據以上設計思路，本節給出了HPMLB算法的整體描述，其處理過程主要包括選取生成在線可信節點的集合，并計算節點的HPM值，選取最小HPM值的最大進行作業分派。

3算法分析

選取5臺服務器構建集群，設定集群整體性能，即總計算能力固定。針對單一作業類型，不同作業數量集合，對HPMLB算法、FCFS算法和Min-Min算法從作業總完成時間和節點負載均衡情況進行分析。

3.1作業總完成時間

衡量作業調度器性能的標準之一，總的作業完成時間越小，說明該作業調度器作業處理速度越快，反之越慢。針對HPMLB算法、FCFS算法和Min-Min算法，設置4組規模不同的單一作業集合，選取5臺服務器構建集群，在總計算能力固定的情況下，分為各節點服務器計算能力相同和計算能力2種不同情況對作業總完成時間進行統計。

（1）節點計算能力相同

現假定集群每個節點的計算能力為可并行執行30個作業，則整個集群總的計算能力為并行執行150個作業。其計算資源分配如表3所示。

設置每個作業耗時20 s，作業按均勻分布到達，選取4組不同規模的作業集合，分別為50，100，700，1 000，作業規模包括小于系統并行作業數量和大于系統并行作業數量的情況，統計整個作業集合的總完成時間，結果如圖3所示。

從圖3可以看出，當作業類型一致，在同構集群中FCFS，HPMLB總作業完成時間相當，優于Min-Min算法。Min-Min算法耗費時間多的原因在于其計時限量等待需要耗費一定時間，并在每個作業分配完畢后需遍歷和更新作業的期望完成時間，因此隨著作業量的增大，其耗費的時間越長。

（2）節點計算能力不同

在節點計算能力不同的情況下，構建異構集群，每臺計算機性能是不一致的，即每個節點，，三個參數值配置不同，，1，2三個參數值配置相同，現模擬異構集群下計算資源分配如表4所示。

上述作業集作業的總完成時間如圖4所示。

從圖4可以看出，在各節點性能差異較大的異構集群中，當作業規模數小于系統并行作業數量時，HPMLB、FCFS和Min-Min三種算法的總完成時間相當，當作業規模數大于系統并行作業數量時，HPMLB作業總時間明顯優于FCFS和Min-Min算法，而且隨著作業規模的不斷增加，差距越發明顯。在HPMLB算法中，作業調度器能夠實時獲取各節點服務器的動態負載，能夠較準確地把作業分配給能夠立即執行的節點服務器，從而大大節省了作業的等待時間。

同時，對3種算法針對2種不同的服務器集群作業調度時間做了比較，發現HPMLB算法對不同的集群環境適應性最好，在2種集群環境下作業總完成時間相當。其次是Min-Min算法，在2種集群環境下作業總完成時間有所變化，但是變化幅度不大，FCFS算法適應性最差。結果如圖5所示。

綜上所述，3種算法都會隨著作業數量的增加，總時間呈上升趨勢。HPMLB算法對不同集群環境適應性最好，Min-Min算法性能次之，FCFS算法性能最差。

當作業規模小于集群可并行運行的最大作業數時，3種算法作業總完成時間相當，當作業規模大于集群可并行運行的最大作業個數時，HPMLB算法的總完成時間明顯小于Min-Min算法和FCFS算法的總完成時間。

3.2節點負載均衡情況

負載均衡是指作業調度到各節點計算機上時，確保大多數節點計算機有作業運行，即充分利用集群計算資源。由于FCFS算法只是靜態地把先來先到的作業按節點順序依次分配給各節點計算機，因此這里不分析該算法的負載均衡性，只對HPMLB算法和Min-Min算法的節點負載均衡情況進行分析比較。

依據表4的計算資源構建異構集群，針對單一類型作業，在集群每個節點的計算能力和集群總體計算能力固定的情況下，當整個集群系統未達到滿載時，設置不同規模的單一作業集合，考慮2種作業調度算法下系統的負載均衡情況。

為減少負載均衡情況的計算量，假定所有作業的執行時間滿足整個作業集被分配完畢后，沒有作業運行結束。此時，集群每個節點的負載情況均可用當前執行的作業數與當前節點能承擔的最大作業數之比來衡量，即用HPM值來進行衡量。

從圖6和圖7可以看出，Min-Min算法優先將作業分配給性能好的服務器，導致整個集群各節點負載不均衡，出現了SOCAS05節點已經滿負荷運行，而SOCAS01仍處在空閑無作業執行的狀態。而HPMLB算法在不同規模的作業集合下，整個集群各節點的負載情況相對均衡，未出現空置服務器情況。通過在同一作業規模下，利用2種算法調度集群各節點負載情況的方差統計情況，比較2種調度算法的負載均衡性能。方差值越小，均衡性越好，結果如圖8所示。

從圖8可以看出，HPMLB算法的負載均衡性在不同作業規模下，其負載均衡性均優于Min-Min算法。

當作業數大于系統的總負載作業數時，Min-Min算法會導致集群中某些節點超載，某些節點空閑的情況，而HPMLB算法由于在實時收集各服務器動態的負載情況，當節點服務器作業運行結束后，該節點最新負載情況會被調度器動態感知。因此，當作業規模過大時，在負載均衡性方面，HPMLB算法優于Min-Min算法。

綜上所述，HPMLB算法在異構集群下，針對同一作業類型，從作業總完成時間以及節點的負載均衡性方面均優于FCFS和Min-Min算法。

4結束語

本文根據異構集群特點，提出了一種基于HPM的HPMLB算法。實驗結果表明，HPMLB算法在異構集群環境下，對同類型作業的調度性能在總完成時間和負載均衡性上均優于FCFS和Min-Min算法。該算法在準實時性應用設計中具有一定的通用性，已用于航天測控中心軌道計算分析平臺系統，為航天器在軌安全管理和穩定運行提供了有效保障。

參考文獻

[1] KHAN K H， QURESHI K， ABD-EL-BARR M. An Efficient Grid Scheduling Strategy for Data Parallel Applications[J].J Supercomput，2014，68（3）：1487-1502.

[2]宋俊輝，馮巖.負載均衡的分布式系統任務調度優化算法[J].吉林大學學報（理學版），2017，55（2）：383-387.

[3] LATIP R， IDRIS Z. Highest Response Ratio Next （HRRN） vs First Come First Served （FCFS） Scheduling Algorithm in Grid Environment[J].Software Engineering and Computer Systems， 2011，11（1）：689-691.

[4]杜玉霞，劉方愛，郭磊.Min-Min調度算法的研究與改進[J].計算機工程與應用，2010，46（24）：107-109.

[5]王文豪，嚴云洋.周靜波.基于負載均衡的Min-Min作業調度算法優化[J].南京理工大學學報，2015，39（4）：398-404.

[6]姜凱華，韓銳，孫鵬，等.基于Min-Min算法的智能終端服務遷移技術研究[J].網絡新媒體技術，2020，9（4）：37-40.

[7] HUANKAI C，WANG F，HELIAN N.User-priority Guided Min-Min Scheduling Algorithm for Load Balancing in Cloud Computing[C]//In： Proceedings of the 2013 National Conference on Parallel Computing Technologies（ PARCOMPTECH）.Bangalore：IEEE，2013：1-8.

[8]王釗，劉釗遠.一種改進的流媒體集群動態負載均衡調度算法[J].計算機與數字工程，2018，46（2）：241-246.

[9]劉斌.基于云計算中的任務調度算法研究[D].長春：長春理工大學，2019.

[10] MAHESWARAN M， SIEGEL HJ.A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems[C]//Proceedings Seventh Heterogeneous Computing Workshop（HCW98）. Orlando： IEEE，1998： 59-69.

[11] AMIN S，MOHAMED O，HAMIDAH I，et al. New Method for Scheduling Heterogeneous Multi-installment Systems[J]. Future Generation Computer Systems，2012，28（8）：1205-1216.

[12]王曉萍，孟坤.異構分布式系統的可分任務作業調度算法[J].小型微型計算機系統，2015，36（4）：797-800.

[13]張臘，劉淑芬，韓璐.基于負載均衡的作業調度算法[J].吉林大學學報（理學版），2014，52（4）：769-773.

[14]朱曉敏，陸佩忠.異構集群系統中安全關鍵實時應用調度研究[J].計算機學報，2010，33（12）：2364-2377.