劉素芹, 張 千, 王俊爽

(中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院, 青島 266580)

1 引言

集群資源進(jìn)行調(diào)度成為影響集群性能的重要因素之一[1]. 文獻(xiàn)傳統(tǒng)的調(diào)度算法先來(lái)先服務(wù)算法(First Come First Serve, FCFS)等傳統(tǒng)的調(diào)度算法難以滿(mǎn)足大規(guī)模異構(gòu)集群對(duì)資源調(diào)度的需求[2–4], 尤其是負(fù)載均衡問(wèn)題更為突出[5,6], 蟻群算法 (Ant Colony Optimization,ACO)等仿生型智能調(diào)度算法受到越來(lái)越多的關(guān)注.

國(guó)內(nèi)外學(xué)者對(duì)蟻群算法在集群調(diào)度中的應(yīng)用做了一定的研究[7,8], 認(rèn)為其分布并行性、健壯性、可擴(kuò)展性都比較適合于集群調(diào)度, 但是蟻群算法沒(méi)有充分考慮資源與作業(yè)的匹配度和負(fù)載均衡問(wèn)題, 導(dǎo)致集群的整體性能不能得以充分發(fā)揮, 所以需要對(duì)蟻群算法深入研究并加以改進(jìn), 以進(jìn)一步提高集群調(diào)度的性能.

2 蟻群算法及在集群調(diào)度中的應(yīng)用

2.1 蟻群算法原理

蟻群算法[8]是由意大利學(xué)者于1991年首先提出的一種具有群體智能的仿生優(yōu)化算法, 借鑒生物界中螞蟻在覓食過(guò)程中總能找到最短路徑的思想. 蟻群算法用螞蟻行走的路徑軌跡求解問(wèn)題的最優(yōu)解, 螞蟻的每條路徑軌跡代表所求問(wèn)題的一種解, 所有的螞蟻都在解空間中獨(dú)立地搜索, 當(dāng)螞蟻在行進(jìn)過(guò)程中遇見(jiàn)尚未經(jīng)過(guò)的路口時(shí), 就從該路口延伸出的路徑中隨機(jī)地選擇一條尚未走過(guò)的路徑繼續(xù)前進(jìn), 同時(shí)釋放與該路徑長(zhǎng)度有關(guān)的信息素增強(qiáng)該路徑的被選概率, 該路徑長(zhǎng)度越短, 釋放的信息素就越多. 當(dāng)后來(lái)的螞蟻再次經(jīng)過(guò)該路口時(shí), 就選擇信息素濃度高的路徑, 同時(shí)釋放更多的信息素, 形成正反饋機(jī)制. 同時(shí)引入信息素?fù)]發(fā)機(jī)制,避免殘留信息素太多使啟發(fā)信息失去參考價(jià)值的現(xiàn)象.蟻群算法的這種自催化行為不需要外界提供其他的信息, 應(yīng)用起來(lái)比較簡(jiǎn)單, 現(xiàn)已在旅行商問(wèn)題、組合優(yōu)化問(wèn)題、二次分配問(wèn)題等領(lǐng)域得到了良好的發(fā)展.

2.2 蟻群算法用于集群調(diào)度的策略

用蟻群算法解決集群調(diào)度問(wèn)題的策略[9,10]為:

(1) 設(shè)組成蟻群的螞蟻數(shù)量為M, 每只螞蟻均可獨(dú)立求得一組作業(yè)調(diào)度方案.

(2) 集群系統(tǒng)初始化, 集群中所有節(jié)點(diǎn)都需提供自身的CPU個(gè)數(shù)及每個(gè)CPU的處理能力等參數(shù), 為每個(gè)節(jié)點(diǎn)設(shè)置初始信息素.

(3) 異構(gòu)集群系統(tǒng)中的管理節(jié)點(diǎn)在每個(gè)調(diào)度周期開(kāi)始前就開(kāi)始收集各節(jié)點(diǎn)的資源信息:

① 若有新節(jié)點(diǎn)加入集群, 就為這個(gè)新加入集群的節(jié)點(diǎn)根據(jù)它所提供的CPU個(gè)數(shù)及處理能力等參數(shù)設(shè)置初始信息素;

② 若集群中有節(jié)點(diǎn)因故障等原因掉線(xiàn), 則將該掉線(xiàn)節(jié)點(diǎn)作停用標(biāo)記;

③ 若集群中作停用標(biāo)記的節(jié)點(diǎn)恢復(fù), 就重新為該節(jié)點(diǎn)設(shè)置啟用標(biāo)志;

④ 集群中作業(yè)調(diào)度結(jié)束后, 依據(jù)作業(yè)的完成情況修改節(jié)點(diǎn)的信息素: 成功則獎(jiǎng)勵(lì), 失敗則懲罰.

(4) 螞蟻個(gè)體根據(jù)概率公式隨機(jī)選擇一個(gè)可用的計(jì)算節(jié)點(diǎn)作為第一個(gè)作業(yè)分配的節(jié)點(diǎn), 并且依據(jù)信息素計(jì)算出轉(zhuǎn)移概率的大小, 按順序決定下一個(gè)作業(yè)分配的節(jié)點(diǎn). 重復(fù)此步驟, 直到所有的作業(yè)分配完成.

(5) 調(diào)度策略的優(yōu)化目標(biāo)是所有任務(wù)的總體執(zhí)行代價(jià)最小和系統(tǒng)資源的負(fù)載平衡性最優(yōu).

當(dāng)一個(gè)螞蟻找到一種調(diào)度方案后, 就計(jì)算該調(diào)度方案的執(zhí)行時(shí)間和負(fù)載均衡性. 當(dāng)所有螞蟻都找到調(diào)度方案后, 比較每個(gè)調(diào)度方案的執(zhí)行時(shí)間和負(fù)載均衡性, 并以此修改各相關(guān)路徑的信息素. 選擇任務(wù)完成時(shí)間最短和負(fù)載均衡性最優(yōu)的一組資源為最優(yōu)方案.

2.3 信息素更新帶來(lái)的問(wèn)題

在蟻群算法中, 信息素的更新非常重要, 集群系統(tǒng)直接根據(jù)信息素更新后的大小決定下一個(gè)作業(yè)選擇該集群節(jié)點(diǎn)的概率. 蟻群算法的信息素更新公式如式(1)和式(2):

從公式(1)和公式(2)可以看到, 信息素的更新方式有時(shí)會(huì)帶來(lái)以下兩方面的問(wèn)題:

(1) 作業(yè)需求與集群節(jié)點(diǎn)資源性能不匹配

從公式(2)中螞蟻根據(jù)作業(yè)完成情況釋放信息素可以看出, 作業(yè)成功完成, 就對(duì)該集群節(jié)點(diǎn)進(jìn)行獎(jiǎng)勵(lì);作業(yè)完成失敗, 就對(duì)該集群節(jié)點(diǎn)進(jìn)行懲罰. 但這種情況并沒(méi)有考慮作業(yè)需求和集群節(jié)點(diǎn)資源性能的匹配問(wèn)題,很可能會(huì)出現(xiàn)小作業(yè)在大資源上執(zhí)行的這種“大炮打蚊子”式的性能不匹配的問(wèn)題.

(2) 集群各節(jié)點(diǎn)之間負(fù)載不均衡

公式(1)中信息素?fù)]發(fā)系數(shù)ρ通常是固定的常數(shù),也即各集群節(jié)點(diǎn)上的信息素?fù)]發(fā)程度相同. 但集群各節(jié)點(diǎn)的性能不同, 作業(yè)又是隨機(jī)到達(dá)的, 系統(tǒng)運(yùn)行一段時(shí)間后, 很可能會(huì)出現(xiàn)集群各節(jié)點(diǎn)之間負(fù)載不均衡的情況.

3 對(duì)蟻群算法的改進(jìn)

針對(duì)信息素更新中存在的問(wèn)題對(duì)蟻群算法進(jìn)行改進(jìn), 稱(chēng)之為該進(jìn)型蟻群算法 (Improved ACO, IACO)算法, 這種改進(jìn)包括兩個(gè)方面: 一方面引入性能匹配因子提高性能匹配度, 把這種算法稱(chēng)為 P M-A C O(Performance Matching-ACO); 另一方面引入負(fù)載均衡因子優(yōu)化負(fù)載均衡, 把這種算法稱(chēng)為L(zhǎng)B-ACO (Load Balance-ACO).

3.1 PM-ACO算法

為了使得分配的資源和作業(yè)的需求更好的匹配,達(dá)到物盡其用, 從而更好的發(fā)揮集群的整體性能, 進(jìn)行資源調(diào)度時(shí), 根據(jù)作業(yè)的需求計(jì)算每個(gè)作業(yè)到各個(gè)集群節(jié)點(diǎn)的匹配程度, 引入性能匹配因子 λij. λij即用戶(hù)作業(yè)i所需資源與集群空閑節(jié)點(diǎn)j擁有資源的匹配度.

其中,realExetime表示作業(yè)的實(shí)際運(yùn)行時(shí)間,estimatedTime表示作業(yè)的預(yù)期運(yùn)行時(shí)間, 作業(yè)對(duì)資源的需求與集群節(jié)點(diǎn)所擁有資源越接近, 性能匹配因子λij也就越小.

引入性能匹配因子后, 螞蟻根據(jù)作業(yè)完成情況釋放信息素的公式(4)和公式(5)如下:

其中,λij為性能匹配因子,λ0為匹配度閾值為信息素增量,c為獎(jiǎng)勵(lì)因子或懲罰因子,k為所需計(jì)算資源.

當(dāng)作業(yè)在資源節(jié)點(diǎn)上執(zhí)行完成后, 計(jì)算作業(yè)與該集群節(jié)點(diǎn)的性能匹配因子λij的值, 并把λij的值與匹配度閾值作比較. 如果λij的值小于匹配度閾值, 信息素調(diào)節(jié)因子就取獎(jiǎng)勵(lì)因子, 增大該資源節(jié)點(diǎn)的信息素濃度,使得此資源節(jié)點(diǎn)被選中的概率增大. 如果λij的值大于匹配度閾值, 信息素調(diào)節(jié)因子就取懲罰因子, 減小資源節(jié)點(diǎn)的信息素濃度, 使得此資源節(jié)點(diǎn)被選中的概率降低. 這樣, 對(duì)于資源處理能力需求小的作業(yè)就可能選擇更匹配的處理能力低的集群節(jié)點(diǎn). 隊(duì)列后面對(duì)資源處理能力需求大的作業(yè)也就會(huì)到處理能力高的集群節(jié)點(diǎn)上去執(zhí)行, 從而較好地解決了資源與作業(yè)不匹配的問(wèn)題.

3.2 LB-ACO算法

在蟻群算法中, 揮發(fā)系數(shù)的大小直接影響著算法的收斂速度. 揮發(fā)系數(shù)較小時(shí), 計(jì)算節(jié)點(diǎn)的信息素較大,算法收斂的也較快. 為了滿(mǎn)足蟻群算法作業(yè)調(diào)度中負(fù)載均衡的要求, 系統(tǒng)需要不斷的檢測(cè)計(jì)算節(jié)點(diǎn)的負(fù)載及其作業(yè)完成情況. 為了保證負(fù)載均衡, 我們需要把各計(jì)算節(jié)點(diǎn)負(fù)載完成率的差值控制在一個(gè)較小的閾值之內(nèi). 為了動(dòng)態(tài)的調(diào)整蟻群算法的揮發(fā)系數(shù), 提高負(fù)載均衡性能, 引入負(fù)載均衡因子, 表達(dá)如公式(6)所示:

其中,Ta表示計(jì)算節(jié)點(diǎn)成功完成的任務(wù)數(shù),Tf表示該計(jì)算節(jié)點(diǎn)已經(jīng)接收的所有任務(wù)總數(shù).Tf一定時(shí),Ta越大,計(jì)算節(jié)點(diǎn)成功完成的任務(wù)數(shù)越多,ωi也越小, 表明計(jì)算節(jié)點(diǎn)的作業(yè)完成率越高;Ta越小, 計(jì)算節(jié)點(diǎn)成功完成的任務(wù)數(shù)越少,ωi也就越大, 表明計(jì)算節(jié)點(diǎn)的作業(yè)完成率越低.

引入負(fù)載均衡因子后, 集群節(jié)點(diǎn)殘留信息素改變?nèi)绻?7)所示:

其中,ω0為負(fù)載均衡因子的初始閾值.

在為作業(yè)選擇集群節(jié)點(diǎn)時(shí), 需要計(jì)算該集群節(jié)點(diǎn)的負(fù)載均衡因子ωi的值, 并將ωi的值與初始閾值ω0作比較. 若ωi小于初始閾值時(shí), 應(yīng)該減小揮發(fā)系數(shù),增大集群節(jié)點(diǎn)的信息素值, 使該集群節(jié)點(diǎn)被選概率增大, 作業(yè)分配收斂于此資源節(jié)點(diǎn); 反之, 若ωi大于初始閾值時(shí), 應(yīng)該增大揮發(fā)系數(shù), 減小計(jì)算節(jié)點(diǎn)的信息素值,使該集群節(jié)點(diǎn)被選概率降低, 使算法的全局搜索能力增強(qiáng), 以便找到更加匹配的資源.

3.3 IACO用于集群調(diào)度的實(shí)現(xiàn)方案

改進(jìn)后的蟻群算法應(yīng)用于異構(gòu)集群系統(tǒng)進(jìn)行資源調(diào)度的實(shí)現(xiàn)方案如圖1所示.

圖1 IACO 用于集群調(diào)度的實(shí)現(xiàn)方案

調(diào)度開(kāi)始前, 異構(gòu)集群系統(tǒng)中的管理節(jié)點(diǎn)就開(kāi)始收集各節(jié)點(diǎn)的資源信息素信息. 若有新節(jié)點(diǎn)加入, 則對(duì)該節(jié)點(diǎn)進(jìn)行初始化. 集群系統(tǒng)對(duì)每組作業(yè)調(diào)度時(shí), 都需要?jiǎng)?chuàng)建一個(gè)新的蟻群. 蟻群中的每個(gè)螞蟻找到一種調(diào)度方案后, 就計(jì)算該調(diào)度方案的執(zhí)行時(shí)間和負(fù)載均衡性. 當(dāng)所有螞蟻都找到調(diào)度方案后, 比較每個(gè)調(diào)度方案的執(zhí)行時(shí)間和負(fù)載均衡性, 并以此修改各相關(guān)路徑的信息素. 選擇任務(wù)完成時(shí)間最短和負(fù)載均衡性最高的一組資源為最優(yōu)方案.

4 實(shí)驗(yàn)結(jié)果及分析

為了對(duì)改進(jìn)的蟻群算法在集群調(diào)度中的應(yīng)用效果進(jìn)行測(cè)試, 在100個(gè)節(jié)點(diǎn)的異構(gòu)集群上對(duì)真實(shí)的地震資料進(jìn)行處理, 調(diào)度算法分別采用先來(lái)先服務(wù)算法FCFS、蟻群算法ACO、引入性能匹配因子的PMACO算法、引入負(fù)載均衡因子的LB-ACO算法和最終改進(jìn)的蟻群算法IACO, 主要對(duì)處理時(shí)間和CPU平均利用率進(jìn)行對(duì)比, 實(shí)驗(yàn)結(jié)果如圖2和圖3所示.

圖2 處理時(shí)間比較

圖3 各節(jié)點(diǎn) CPU 平均利用率對(duì)比

從實(shí)驗(yàn)結(jié)果可以看出, 蟻群算法ACO考慮到資源和作業(yè)的實(shí)際情況, 比傳統(tǒng)的先來(lái)先服務(wù)算法FCFS有明顯的優(yōu)勢(shì); 引入性能匹配因子后的PMACO算法解決了“大炮打蚊子”的問(wèn)題, 使得性能有所改進(jìn), 但負(fù)載均衡問(wèn)題沒(méi)有解決; LB-ACO算法考慮了負(fù)載均衡問(wèn)題, 但還有可能存在“大炮打蚊子”現(xiàn)象;IACO較好地解決了這兩方面的問(wèn)題, 不論是處理時(shí)間還是CPU利用率均有明顯提高.

由此可見(jiàn), 傳統(tǒng)的蟻群算法應(yīng)用于集群調(diào)度時(shí)確實(shí)存在資源匹配和負(fù)載均衡的問(wèn)題, 在這兩個(gè)方面進(jìn)行改進(jìn)后能夠較好地提高集群的調(diào)度性能.

5 結(jié)論

傳統(tǒng)調(diào)度算法已經(jīng)難以滿(mǎn)足大規(guī)模異構(gòu)集群的作業(yè)的調(diào)度, 蟻群算法比較適合于集群中的作業(yè)調(diào)度, 但是, 傳統(tǒng)的蟻群算法在作業(yè)匹配和負(fù)載均衡方面還存在問(wèn)題, 改進(jìn)的蟻群算法IACO較好地解決了這一問(wèn)題, 有效地提高了集群調(diào)度的性能.