基于主機(jī)性能度量的異構(gòu)集群作業(yè)調(diào)度算法

王超 陳剛 黃剛 王彪

摘要：傳統(tǒng)經(jīng)典作業(yè)度算法在集群應(yīng)用中實(shí)現(xiàn)簡(jiǎn)單、執(zhí)行效率高，但在異構(gòu)集群環(huán)境下由于缺乏在線節(jié)點(diǎn)運(yùn)行狀態(tài)動(dòng)態(tài)反饋能力和負(fù)載均衡能力，降低了計(jì)算資源利用率和系統(tǒng)吞吐率。為解決上述問(wèn)題，設(shè)計(jì)了一種在異構(gòu)集群環(huán)境下基于主機(jī)性能度量的作業(yè)負(fù)載均衡調(diào)度算法，該算法通過(guò)收集集群中在線節(jié)點(diǎn)的狀態(tài)信息和作業(yè)響應(yīng)時(shí)間遴選出可信節(jié)點(diǎn)集合，計(jì)算出各可信節(jié)點(diǎn)的HPM值，利用負(fù)載均衡運(yùn)算規(guī)則生成候選的作業(yè)分配節(jié)點(diǎn)集合，最終按照預(yù)先設(shè)計(jì)的優(yōu)先原則把不同作業(yè)分配至各計(jì)算節(jié)點(diǎn)，并更新各節(jié)點(diǎn)運(yùn)行狀態(tài)。實(shí)驗(yàn)結(jié)果表明，在異構(gòu)集群環(huán)境下調(diào)度同類型作業(yè)時(shí)，該算法在總完成時(shí)間和負(fù)載均衡性能等指標(biāo)上均優(yōu)于傳統(tǒng)經(jīng)典算法。

關(guān)鍵詞：異構(gòu)集群;主機(jī)性能度量;負(fù)載均衡;作業(yè)調(diào)度

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2021）08-67-7

0引言

集群是多臺(tái)相互獨(dú)立的計(jì)算機(jī)，通過(guò)高速網(wǎng)絡(luò)互聯(lián)形成一個(gè)整體系統(tǒng)后，對(duì)外提供服務(wù)并對(duì)集群本身加以管理。集群運(yùn)行過(guò)程的作業(yè)調(diào)度策略對(duì)集群資源利用率起著關(guān)鍵作用[1]，調(diào)度策略的優(yōu)劣決定了集群中作業(yè)完成的效率。作業(yè)調(diào)度算法大致分為相互依賴和相互獨(dú)立2種算法。前者算法缺陷明顯，工程應(yīng)用不多，后者算法因?qū)崿F(xiàn)簡(jiǎn)單，大多數(shù)集群管理系統(tǒng)都在采用。目前在國(guó)內(nèi)外廣泛應(yīng)用的相互獨(dú)立的經(jīng)典作業(yè)調(diào)度算法中，主要包括先來(lái)先到服務(wù)（First Come First Service，F(xiàn)CFS）、Min-Min算法和基于優(yōu)先級(jí)調(diào)度（Priority）等[2]。

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

1問(wèn)題建模

在集群作業(yè)調(diào)度中，有一個(gè)節(jié)點(diǎn)作為調(diào)度節(jié)點(diǎn)，完成對(duì)所有作業(yè)的計(jì)算資源調(diào)度與分配，各計(jì)算節(jié)點(diǎn)完成業(yè)務(wù)計(jì)算。系統(tǒng)整體調(diào)度與管理流程如下：

①集群節(jié)點(diǎn)的網(wǎng)絡(luò)代理軟件接收作業(yè)請(qǐng)求命令;

②集群調(diào)度節(jié)點(diǎn)獲取調(diào)度狀態(tài);

③集群調(diào)度節(jié)點(diǎn)的負(fù)載均衡調(diào)度器根據(jù)負(fù)載均衡調(diào)度算法進(jìn)行調(diào)度計(jì)算和作業(yè)派發(fā);

④受理作業(yè)計(jì)算節(jié)點(diǎn)進(jìn)行具體的計(jì)算處理，同時(shí)根據(jù)作業(yè)執(zhí)行情況更新本機(jī)狀態(tài);

⑤各集群節(jié)點(diǎn)通過(guò)集群狀態(tài)同步機(jī)制動(dòng)態(tài)實(shí)現(xiàn)各節(jié)點(diǎn)服務(wù)器狀態(tài)同步。

針對(duì)上述流程，本文設(shè)計(jì)的HPMLB算法主要思想是：

①通過(guò)HPM、執(zhí)行工作列表（Executive Job List，EJL）和作業(yè)響應(yīng)時(shí)間容忍度來(lái)動(dòng)態(tài)地描述集群各節(jié)點(diǎn)當(dāng)前負(fù)載情況;

②由集群調(diào)度節(jié)點(diǎn)根據(jù)集群各節(jié)點(diǎn)的HPM和EJL等關(guān)鍵信息，結(jié)合作業(yè)響應(yīng)狀態(tài)，依據(jù)負(fù)載均衡調(diào)度策略，將請(qǐng)求分配到集群中各計(jì)算節(jié)點(diǎn);

③各計(jì)算節(jié)點(diǎn)中的作業(yè)組織流程負(fù)責(zé)接受請(qǐng)求并組織作業(yè)執(zhí)行器進(jìn)行作業(yè)處理;

④各計(jì)算節(jié)點(diǎn)實(shí)時(shí)更新和對(duì)外發(fā)布本機(jī)的HPM和EJL等信息。

作業(yè)調(diào)度總體流程如圖1所示。

整個(gè)作業(yè)調(diào)度由集群中的調(diào)度節(jié)點(diǎn)完成，當(dāng)進(jìn)行HPMLB時(shí)，調(diào)度節(jié)點(diǎn)首先收集集群中在線節(jié)點(diǎn)并篩選出可信節(jié)點(diǎn)。然后計(jì)算各可信節(jié)點(diǎn)的HPM值，根據(jù)負(fù)載均衡運(yùn)算規(guī)則生成候選集合。最后，依據(jù)同等條件下的優(yōu)先原則進(jìn)行作業(yè)分派，分派完成后進(jìn)行各節(jié)點(diǎn)狀態(tài)更新。

為準(zhǔn)確描述上述過(guò)程，給出集群節(jié)點(diǎn)性能、EJL和網(wǎng)絡(luò)狀態(tài)信息等概念的定義：

②EJL具體內(nèi)容如表1所示。

③集群節(jié)點(diǎn)狀態(tài)信息（The Cluster Node Status information，CNS）：各集群節(jié)點(diǎn)服務(wù)器維護(hù)本機(jī)的狀態(tài)以及本機(jī)與其余節(jié)點(diǎn)的狀態(tài)信息，如表2所示。

2算法設(shè)計(jì)

2.1生成可信節(jié)點(diǎn)

（1）收集在線節(jié)點(diǎn)

集群各節(jié)點(diǎn)都保存集群狀態(tài)信息列表，包含本節(jié)點(diǎn)與集群其他所有節(jié)點(diǎn)當(dāng)前的網(wǎng)絡(luò)狀態(tài)情況，并以固定周期△輪詢檢測(cè)更新整個(gè)集群的狀態(tài)信息，其檢測(cè)方式為集群中各節(jié)點(diǎn)以固定周期△循環(huán)接收集群節(jié)點(diǎn)的狀態(tài)信息和第三方心跳;接收調(diào)度節(jié)點(diǎn)信號(hào)，確定調(diào)度節(jié)點(diǎn)的狀態(tài);完成節(jié)點(diǎn)狀態(tài)信息的同步與更新;調(diào)度節(jié)點(diǎn)根據(jù)心跳檢測(cè)和集群節(jié)點(diǎn)的狀態(tài)信息，生成集群在線節(jié)點(diǎn)的集合A。

（2）篩選可信節(jié)點(diǎn)

在生成的集群在線節(jié)點(diǎn)集合A中，調(diào)度節(jié)點(diǎn)查詢集合A中各個(gè)的IGHOST_INFO[].mainstatus值，若該值為1，則表示該對(duì)應(yīng)的節(jié)點(diǎn)與調(diào)度節(jié)點(diǎn)通信正常，若為0，則表示與調(diào)度節(jié)點(diǎn)通信狀態(tài)異常，將其中值為1的生成與調(diào)度節(jié)點(diǎn)通信正常的節(jié)點(diǎn)集合B;

然后篩選出滿足作業(yè)響應(yīng)時(shí)間容忍度的節(jié)點(diǎn)，生成可信節(jié)點(diǎn)集合C，根據(jù)式（3）進(jìn)行本節(jié)點(diǎn)與集合B中節(jié)點(diǎn)的網(wǎng)絡(luò)路徑計(jì)算，獲取本地的當(dāng)前時(shí)間，然后獲取本節(jié)點(diǎn)接收到的最近一次該發(fā)送的節(jié)點(diǎn)心跳時(shí)間，計(jì)算出該與調(diào)度節(jié)點(diǎn)的系統(tǒng)路徑長(zhǎng)度。

作業(yè)響應(yīng)時(shí)間容忍度Dpt作為系統(tǒng)常數(shù)進(jìn)行配置，通過(guò)式（5）進(jìn)行作業(yè)響應(yīng)狀態(tài)運(yùn)算。（）=1表示作業(yè)響應(yīng)正常，（）=0表示作業(yè)響應(yīng)超時(shí)，并將值為1的放在集合C中。

2.2作業(yè)調(diào)度

調(diào)度節(jié)點(diǎn)在生成的可信節(jié)點(diǎn)集合C中，計(jì)算HPM值，選取HPM值最小的節(jié)點(diǎn)集合生成候選集合D。在候選集合生成后，按如下原則進(jìn)行作業(yè)分配：

①若系統(tǒng)滿負(fù)荷，即HPM值為Mhpm，作業(yè)拒絕;

②若候選節(jié)點(diǎn)唯一，即集合D中的元素唯一，則作業(yè)直接派發(fā)給該;

③若候選節(jié)點(diǎn)不唯一，即集合D中的元素不唯一，則選取值最大的進(jìn)行派發(fā)。

詳細(xì)處理流程如圖2所示。

①獲取調(diào)度請(qǐng)求;

②獲取節(jié)點(diǎn)計(jì)算機(jī)的狀態(tài)信息;

③查詢集群狀態(tài)列表，獲取其為在線狀態(tài)的計(jì)算機(jī)節(jié)點(diǎn)集合A;

④在集合A中查詢與調(diào)度節(jié)點(diǎn)網(wǎng)絡(luò)狀態(tài)正常的計(jì)算機(jī)節(jié)點(diǎn)集合B;

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

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

⑦判斷集合D的元素個(gè)數(shù)是否為1，若為1，則將該“+調(diào)度請(qǐng)求”作為調(diào)度請(qǐng)求結(jié)果對(duì)外發(fā)出，否則將集合中“最大值的+調(diào)度請(qǐng)求”作為調(diào)度請(qǐng)求結(jié)果對(duì)外發(fā)出;若集合D中各對(duì)應(yīng)的計(jì)算機(jī)的HPM值>Mhpm（系統(tǒng)允許的最大負(fù)荷0<≤1）時(shí)，置為MAX_HOSTNUM+1;

⑧更新各節(jié)點(diǎn)當(dāng)前的值。

2.3狀態(tài)動(dòng)態(tài)同步

HPMLB算法在進(jìn)行作業(yè)調(diào)度時(shí)，為了及時(shí)獲取集群各節(jié)點(diǎn)的動(dòng)態(tài)負(fù)載情況以及對(duì)整個(gè)集群系統(tǒng)的集中管控，設(shè)計(jì)了集群狀態(tài)動(dòng)態(tài)同步機(jī)制，集群各節(jié)點(diǎn)實(shí)時(shí)收集更新本節(jié)點(diǎn)狀態(tài)，并將本節(jié)點(diǎn)狀態(tài)對(duì)外發(fā)出，同時(shí)接收其余節(jié)點(diǎn)狀態(tài)信息，將接收到的其他節(jié)點(diǎn)狀態(tài)信息更新到本機(jī)。其同步及發(fā)布內(nèi)容有：維護(hù)本節(jié)點(diǎn)作業(yè)執(zhí)行狀態(tài);維護(hù)本節(jié)點(diǎn)HPM值;對(duì)外發(fā)布工作列表數(shù)據(jù);更新本節(jié)點(diǎn)保存的其余節(jié)點(diǎn)發(fā)布的狀態(tài)信息;維護(hù)本節(jié)點(diǎn)與其余節(jié)點(diǎn)的網(wǎng)絡(luò)狀態(tài)，若本節(jié)點(diǎn)與某一節(jié)點(diǎn)的節(jié)點(diǎn)網(wǎng)絡(luò)狀態(tài)函數(shù)nets （）的值為0，則將本節(jié)點(diǎn)與該節(jié)點(diǎn)之間的網(wǎng)絡(luò)狀態(tài)設(shè)置為超時(shí);對(duì)外發(fā)布本節(jié)點(diǎn)狀態(tài)信息。

2.4整體算法描述

根據(jù)以上設(shè)計(jì)思路，本節(jié)給出了HPMLB算法的整體描述，其處理過(guò)程主要包括選取生成在線可信節(jié)點(diǎn)的集合，并計(jì)算節(jié)點(diǎn)的HPM值，選取最小HPM值的最大進(jìn)行作業(yè)分派。

3算法分析

選取5臺(tái)服務(wù)器構(gòu)建集群，設(shè)定集群整體性能，即總計(jì)算能力固定。針對(duì)單一作業(yè)類型，不同作業(yè)數(shù)量集合，對(duì)HPMLB算法、FCFS算法和Min-Min算法從作業(yè)總完成時(shí)間和節(jié)點(diǎn)負(fù)載均衡情況進(jìn)行分析。

3.1作業(yè)總完成時(shí)間

衡量作業(yè)調(diào)度器性能的標(biāo)準(zhǔn)之一，總的作業(yè)完成時(shí)間越小，說(shuō)明該作業(yè)調(diào)度器作業(yè)處理速度越快，反之越慢。針對(duì)HPMLB算法、FCFS算法和Min-Min算法，設(shè)置4組規(guī)模不同的單一作業(yè)集合，選取5臺(tái)服務(wù)器構(gòu)建集群，在總計(jì)算能力固定的情況下，分為各節(jié)點(diǎn)服務(wù)器計(jì)算能力相同和計(jì)算能力2種不同情況對(duì)作業(yè)總完成時(shí)間進(jìn)行統(tǒng)計(jì)。

（1）節(jié)點(diǎn)計(jì)算能力相同

現(xiàn)假定集群每個(gè)節(jié)點(diǎn)的計(jì)算能力為可并行執(zhí)行30個(gè)作業(yè)，則整個(gè)集群總的計(jì)算能力為并行執(zhí)行150個(gè)作業(yè)。其計(jì)算資源分配如表3所示。

設(shè)置每個(gè)作業(yè)耗時(shí)20 s，作業(yè)按均勻分布到達(dá)，選取4組不同規(guī)模的作業(yè)集合，分別為50，100，700，1 000，作業(yè)規(guī)模包括小于系統(tǒng)并行作業(yè)數(shù)量和大于系統(tǒng)并行作業(yè)數(shù)量的情況，統(tǒng)計(jì)整個(gè)作業(yè)集合的總完成時(shí)間，結(jié)果如圖3所示。

從圖3可以看出，當(dāng)作業(yè)類型一致，在同構(gòu)集群中FCFS，HPMLB總作業(yè)完成時(shí)間相當(dāng)，優(yōu)于Min-Min算法。Min-Min算法耗費(fèi)時(shí)間多的原因在于其計(jì)時(shí)限量等待需要耗費(fèi)一定時(shí)間，并在每個(gè)作業(yè)分配完畢后需遍歷和更新作業(yè)的期望完成時(shí)間，因此隨著作業(yè)量的增大，其耗費(fèi)的時(shí)間越長(zhǎng)。

（2）節(jié)點(diǎn)計(jì)算能力不同

在節(jié)點(diǎn)計(jì)算能力不同的情況下，構(gòu)建異構(gòu)集群，每臺(tái)計(jì)算機(jī)性能是不一致的，即每個(gè)節(jié)點(diǎn)，，三個(gè)參數(shù)值配置不同，，1，2三個(gè)參數(shù)值配置相同，現(xiàn)模擬異構(gòu)集群下計(jì)算資源分配如表4所示。

上述作業(yè)集作業(yè)的總完成時(shí)間如圖4所示。

從圖4可以看出，在各節(jié)點(diǎn)性能差異較大的異構(gòu)集群中，當(dāng)作業(yè)規(guī)模數(shù)小于系統(tǒng)并行作業(yè)數(shù)量時(shí)，HPMLB、FCFS和Min-Min三種算法的總完成時(shí)間相當(dāng)，當(dāng)作業(yè)規(guī)模數(shù)大于系統(tǒng)并行作業(yè)數(shù)量時(shí)，HPMLB作業(yè)總時(shí)間明顯優(yōu)于FCFS和Min-Min算法，而且隨著作業(yè)規(guī)模的不斷增加，差距越發(fā)明顯。在HPMLB算法中，作業(yè)調(diào)度器能夠?qū)崟r(shí)獲取各節(jié)點(diǎn)服務(wù)器的動(dòng)態(tài)負(fù)載，能夠較準(zhǔn)確地把作業(yè)分配給能夠立即執(zhí)行的節(jié)點(diǎn)服務(wù)器，從而大大節(jié)省了作業(yè)的等待時(shí)間。

同時(shí)，對(duì)3種算法針對(duì)2種不同的服務(wù)器集群作業(yè)調(diào)度時(shí)間做了比較，發(fā)現(xiàn)HPMLB算法對(duì)不同的集群環(huán)境適應(yīng)性最好，在2種集群環(huán)境下作業(yè)總完成時(shí)間相當(dāng)。其次是Min-Min算法，在2種集群環(huán)境下作業(yè)總完成時(shí)間有所變化，但是變化幅度不大，F(xiàn)CFS算法適應(yīng)性最差。結(jié)果如圖5所示。

綜上所述，3種算法都會(huì)隨著作業(yè)數(shù)量的增加，總時(shí)間呈上升趨勢(shì)。HPMLB算法對(duì)不同集群環(huán)境適應(yīng)性最好，Min-Min算法性能次之，F(xiàn)CFS算法性能最差。

當(dāng)作業(yè)規(guī)模小于集群可并行運(yùn)行的最大作業(yè)數(shù)時(shí)，3種算法作業(yè)總完成時(shí)間相當(dāng)，當(dāng)作業(yè)規(guī)模大于集群可并行運(yùn)行的最大作業(yè)個(gè)數(shù)時(shí)，HPMLB算法的總完成時(shí)間明顯小于Min-Min算法和FCFS算法的總完成時(shí)間。

3.2節(jié)點(diǎn)負(fù)載均衡情況

負(fù)載均衡是指作業(yè)調(diào)度到各節(jié)點(diǎn)計(jì)算機(jī)上時(shí)，確保大多數(shù)節(jié)點(diǎn)計(jì)算機(jī)有作業(yè)運(yùn)行，即充分利用集群計(jì)算資源。由于FCFS算法只是靜態(tài)地把先來(lái)先到的作業(yè)按節(jié)點(diǎn)順序依次分配給各節(jié)點(diǎn)計(jì)算機(jī)，因此這里不分析該算法的負(fù)載均衡性，只對(duì)HPMLB算法和Min-Min算法的節(jié)點(diǎn)負(fù)載均衡情況進(jìn)行分析比較。

依據(jù)表4的計(jì)算資源構(gòu)建異構(gòu)集群，針對(duì)單一類型作業(yè)，在集群每個(gè)節(jié)點(diǎn)的計(jì)算能力和集群總體計(jì)算能力固定的情況下，當(dāng)整個(gè)集群系統(tǒng)未達(dá)到滿載時(shí)，設(shè)置不同規(guī)模的單一作業(yè)集合，考慮2種作業(yè)調(diào)度算法下系統(tǒng)的負(fù)載均衡情況。

為減少負(fù)載均衡情況的計(jì)算量，假定所有作業(yè)的執(zhí)行時(shí)間滿足整個(gè)作業(yè)集被分配完畢后，沒有作業(yè)運(yùn)行結(jié)束。此時(shí)，集群每個(gè)節(jié)點(diǎn)的負(fù)載情況均可用當(dāng)前執(zhí)行的作業(yè)數(shù)與當(dāng)前節(jié)點(diǎn)能承擔(dān)的最大作業(yè)數(shù)之比來(lái)衡量，即用HPM值來(lái)進(jìn)行衡量。

從圖6和圖7可以看出，Min-Min算法優(yōu)先將作業(yè)分配給性能好的服務(wù)器，導(dǎo)致整個(gè)集群各節(jié)點(diǎn)負(fù)載不均衡，出現(xiàn)了SOCAS05節(jié)點(diǎn)已經(jīng)滿負(fù)荷運(yùn)行，而SOCAS01仍處在空閑無(wú)作業(yè)執(zhí)行的狀態(tài)。而HPMLB算法在不同規(guī)模的作業(yè)集合下，整個(gè)集群各節(jié)點(diǎn)的負(fù)載情況相對(duì)均衡，未出現(xiàn)空置服務(wù)器情況。通過(guò)在同一作業(yè)規(guī)模下，利用2種算法調(diào)度集群各節(jié)點(diǎn)負(fù)載情況的方差統(tǒng)計(jì)情況，比較2種調(diào)度算法的負(fù)載均衡性能。方差值越小，均衡性越好，結(jié)果如圖8所示。

從圖8可以看出，HPMLB算法的負(fù)載均衡性在不同作業(yè)規(guī)模下，其負(fù)載均衡性均優(yōu)于Min-Min算法。

當(dāng)作業(yè)數(shù)大于系統(tǒng)的總負(fù)載作業(yè)數(shù)時(shí)，Min-Min算法會(huì)導(dǎo)致集群中某些節(jié)點(diǎn)超載，某些節(jié)點(diǎn)空閑的情況，而HPMLB算法由于在實(shí)時(shí)收集各服務(wù)器動(dòng)態(tài)的負(fù)載情況，當(dāng)節(jié)點(diǎn)服務(wù)器作業(yè)運(yùn)行結(jié)束后，該節(jié)點(diǎn)最新負(fù)載情況會(huì)被調(diào)度器動(dòng)態(tài)感知。因此，當(dāng)作業(yè)規(guī)模過(guò)大時(shí)，在負(fù)載均衡性方面，HPMLB算法優(yōu)于Min-Min算法。

綜上所述，HPMLB算法在異構(gòu)集群下，針對(duì)同一作業(yè)類型，從作業(yè)總完成時(shí)間以及節(jié)點(diǎn)的負(fù)載均衡性方面均優(yōu)于FCFS和Min-Min算法。

4結(jié)束語(yǔ)

本文根據(jù)異構(gòu)集群特點(diǎn)，提出了一種基于HPM的HPMLB算法。實(shí)驗(yàn)結(jié)果表明，HPMLB算法在異構(gòu)集群環(huán)境下，對(duì)同類型作業(yè)的調(diào)度性能在總完成時(shí)間和負(fù)載均衡性上均優(yōu)于FCFS和Min-Min算法。該算法在準(zhǔn)實(shí)時(shí)性應(yīng)用設(shè)計(jì)中具有一定的通用性，已用于航天測(cè)控中心軌道計(jì)算分析平臺(tái)系統(tǒng)，為航天器在軌安全管理和穩(wěn)定運(yùn)行提供了有效保障。

參考文獻(xiàn)

[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]宋俊輝，馮巖.負(fù)載均衡的分布式系統(tǒng)任務(wù)調(diào)度優(yōu)化算法[J].吉林大學(xué)學(xué)報(bào)（理學(xué)版），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調(diào)度算法的研究與改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（24）：107-109.

[5]王文豪，嚴(yán)云洋.周靜波.基于負(fù)載均衡的Min-Min作業(yè)調(diào)度算法優(yōu)化[J].南京理工大學(xué)學(xué)報(bào)，2015，39（4）：398-404.

[6]姜?jiǎng)P華，韓銳，孫鵬，等.基于Min-Min算法的智能終端服務(wù)遷移技術(shù)研究[J].網(wǎng)絡(luò)新媒體技術(shù)，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]王釗，劉釗遠(yuǎn).一種改進(jìn)的流媒體集群動(dòng)態(tài)負(fù)載均衡調(diào)度算法[J].計(jì)算機(jī)與數(shù)字工程，2018，46（2）：241-246.

[9]劉斌.基于云計(jì)算中的任務(wù)調(diào)度算法研究[D].長(zhǎng)春：長(zhǎng)春理工大學(xué)，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]王曉萍，孟坤.異構(gòu)分布式系統(tǒng)的可分任務(wù)作業(yè)調(diào)度算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36（4）：797-800.

[13]張臘，劉淑芬，韓璐.基于負(fù)載均衡的作業(yè)調(diào)度算法[J].吉林大學(xué)學(xué)報(bào)（理學(xué)版），2014，52（4）：769-773.

[14]朱曉敏，陸佩忠.異構(gòu)集群系統(tǒng)中安全關(guān)鍵實(shí)時(shí)應(yīng)用調(diào)度研究[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（12）：2364-2377.