查道貴,許彩芳,陳 偉

(宿州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)信息系,安徽 宿州 234101)

基于云計(jì)算環(huán)境的任務(wù)調(diào)度算法探究

查道貴,許彩芳,陳 偉

(宿州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)信息系,安徽 宿州 234101)

云計(jì)算所展現(xiàn)的是“海量”的集群性資源池和極具伸縮性的動態(tài)彈性空間，并以其獨(dú)特的時(shí)代魅力吸引著科學(xué)發(fā)展的目光.相形之下，基于云計(jì)算環(huán)境的任務(wù)調(diào)度算法的研究，也越來越受到世人的關(guān)愛與推崇.

互聯(lián)網(wǎng)；云計(jì)算環(huán)境；任務(wù)調(diào)度；算法探究

所謂“云計(jì)算任務(wù)調(diào)度”，可簡單理解為“云計(jì)算環(huán)境下的任務(wù)調(diào)度”.因此，對云環(huán)境中“海量”資源，如何分配得當(dāng)、運(yùn)用“恰如其分”；對用戶的任務(wù)需求，如何調(diào)度有力,算法“卓有成效”，已成當(dāng)務(wù)之急.

1 “網(wǎng)格化”結(jié)算背景下云計(jì)算任務(wù)調(diào)度算法的“移植性”探討

基于網(wǎng)格結(jié)算與云計(jì)算的局部屬性的相似性，形近神似使其二者走得很近.

1.1 “ Min-min”算法的“先易后難”

“Min-min”算法作為貪心算法門類的一種形式， 志在計(jì)算可用資源的擇“易”避“難”.在海量的云計(jì)算信息數(shù)據(jù)池中做出取舍，傾向于執(zhí)行速度最快和最先能完成任務(wù)的計(jì)算資源，不失為典型的一種“先易后難”策略.該算法突出的優(yōu)勢在于“輕裝上陣”，尤其對服務(wù)要求質(zhì)量不高的用戶是一個(gè)工作階段性的突破，并能立竿見影.而伴隨云計(jì)算規(guī)模的逐漸擴(kuò)大，又置身于任務(wù)與日俱增，這種擇易避難的劣根性便暴露無遺.累積過多的優(yōu)質(zhì)資源無形當(dāng)中要面對負(fù)擔(dān)過重的任務(wù)壓力，最終成效也必然大打折扣.而空閑狀態(tài)下的其他資源被長期置于最后，對整體資源造成無謂的浪費(fèi).

1.2 “Max-min”算法的“能者多勞”

“ Max-min”可算作第二種貪心算法，難度與“Min-min”算法“殊途同歸”，基本保持一致.不同的是，“Max-min”在海量的云計(jì)算信息數(shù)據(jù)池中做出“能者多勞”的選擇，傾向于最大計(jì)算量與完成最晚時(shí)間的計(jì)算資源.“Max-min”算法有其進(jìn)步性的一面，緩解了 “Min-min”算法下負(fù)載不均的迫切性問題，也緩解了資源閑置的嚴(yán)重性難題，對資源利用率是一項(xiàng)促進(jìn)提高，但該算法存在一定的局限性，有其自適應(yīng)能力不強(qiáng)與拓展不力的弊端，尤其應(yīng)用的空間非常狹小.

1.3 “Suffer-age”算法的“末位淘汰”

“Suffer-age”可算作第三種貪心算法，難度也與前兩者基本一致.但不同的是，“Suffer-age”算法在海量云計(jì)算數(shù)據(jù)池中做出“末尾淘汰”的選擇.將任務(wù)完成時(shí)間的次小與最小差定義，以“Suffer-age” 值(任務(wù)執(zhí)行損失)做出算法取舍.任務(wù)調(diào)度中， 傾向于“Suffer-age”最大值.調(diào)度當(dāng)中，一旦子任務(wù)發(fā)生資源競爭，可根據(jù)“Suffer-age”值給予適時(shí)調(diào)度.

2 “簡練式”雛形模式中云計(jì)算任務(wù)調(diào)度算法的“借鑒性”研究

鑒于分布式集群計(jì)算有其大規(guī)?；渴鸱矫娴牧觿?，不少網(wǎng)絡(luò)公司圍繞整體系統(tǒng)的方便運(yùn)行做出努力.如 Google旗下的“Map/Reduce”以簡練易于移植著稱，它依托Map步驟將大型任務(wù)拆分n個(gè)子任務(wù)，子任務(wù)遵循分布式部署，進(jìn)一步分配到計(jì)算資源中實(shí)施“Reduce” 的具體步驟.等到各種計(jì)算執(zhí)行結(jié)束后，計(jì)算結(jié)果予以匯總輸出，而后進(jìn)行任務(wù)的總體處置.被廣泛化借鑒應(yīng)用于目前眾多的云計(jì)算平臺當(dāng)中，而其他調(diào)度算法共性下的特色也“各具風(fēng)采”.

2.1 “FIFO”調(diào)度算法的“先進(jìn)先出”

“FIFO”算法的亮點(diǎn)在于任務(wù)調(diào)度策略的“先進(jìn)先出”.對映射關(guān)系的確定是基于客戶需求任務(wù)的到達(dá)時(shí)間與優(yōu)先級別來通盤考慮的.在“FIFO”云計(jì)算中， 一旦計(jì)算資源呈現(xiàn)空閑狀態(tài)，馬上聯(lián)動起來的系統(tǒng)，則傾向于提交最早選擇，且優(yōu)先高于同類任務(wù)的選擇，分配執(zhí)行資源計(jì)算.“FIFO”算法突出特點(diǎn)則在于減少計(jì)算任務(wù)的調(diào)度策略，凸顯其算法簡練，具有應(yīng)用方便的優(yōu)勢.但缺點(diǎn)也同樣明顯.對大計(jì)算量、優(yōu)先級高的任務(wù)執(zhí)行的“偏愛”，造成小型任務(wù)遭遇云系統(tǒng)長時(shí)間內(nèi)備受冷落.同時(shí)，因其算法太過拘謹(jǐn)，遲滯現(xiàn)象明顯，往往對資源搶占與資源競爭等系統(tǒng)特殊性要求，無法形成靈活有力的策略支持.但也有改進(jìn)的余地，通過該算法的調(diào)度框架做出修改，即可讓任一應(yīng)用調(diào)度任務(wù)的策略傾斜“塵埃落定”.

2.2 公平調(diào)度算法的“資源均分”

“Fair Scheduling”“資源均分”設(shè)想，在于“Hadoop” 作業(yè)處理實(shí)現(xiàn)公平合理化.此種云計(jì)算的任務(wù)調(diào)度，其策略偏重于資源池內(nèi)的計(jì)算資源取向選擇，對等待狀態(tài)的任務(wù)序列“熟視無睹”，因而缺乏資源選擇的主動性.公平調(diào)度算法的突出特點(diǎn)，在于計(jì)算資源的均分、均攤.先將資源池進(jìn)行結(jié)構(gòu)歸屬劃分，不同的任務(wù)池各有不同歸屬，再以優(yōu)先的方式將各種屬性任務(wù)歸屬分配到相應(yīng)的任務(wù)池內(nèi),系統(tǒng)平均配給.同時(shí)，調(diào)度任務(wù)管理維護(hù)由任務(wù)池的分配系統(tǒng)一并擔(dān)負(fù)，池內(nèi)任務(wù)既能實(shí)現(xiàn)系統(tǒng)資源平等劃分、均攤使用，又可基于計(jì)算資源“平分天下”進(jìn)一步展開資源的競爭與搶占，以此達(dá)到強(qiáng)化優(yōu)勢的目的.此任務(wù)調(diào)度策略，其優(yōu)勢明顯在于對任務(wù)調(diào)度合理性、公平性給予很大程度的維護(hù)，避免了部分用戶因另類任務(wù)需求，而難以得到較好的體驗(yàn)性服務(wù)，以此形成云計(jì)算服務(wù)整體質(zhì)量的綜合提升.

2.3 能力調(diào)度算法的“比例分配”

能力調(diào)度算法以“Capacity-Scheduling”最為典型，于自身分布式集群計(jì)算當(dāng)中多有應(yīng)用.其任務(wù)調(diào)度策略尤以對比性能見長，策略中心在于數(shù)據(jù)可用性能資源的參數(shù)對比上，系統(tǒng)一旦接到客戶需求服務(wù)信息，響應(yīng)敏捷，眾多“Job-Queue”隊(duì)列群起而發(fā).數(shù)據(jù)中心結(jié)合參數(shù)對比，分別給予每隊(duì)“Job-Queue”隊(duì)列相應(yīng)比例資源的參數(shù)配比，落實(shí)管理任務(wù)職能，并落實(shí)好執(zhí)行相應(yīng)隊(duì)列中的任務(wù)角色.倘若某“Job-Queue”隊(duì)列對計(jì)算資源無配備“奢求”,原有資源歸屬即時(shí)為他隊(duì)列一并占用.而該隊(duì)列倘有任務(wù)需求變故發(fā)生,系統(tǒng)也迅速做出反應(yīng)，馬上將原有資源配備及時(shí)“歸位”,以方便隊(duì)列任務(wù)的再次執(zhí)行.依據(jù)這種措施的快捷性服務(wù)，避免了資源負(fù)載失衡與局部資源閑置問題的糾結(jié)，相對資源而言，其調(diào)度計(jì)算利用率有了質(zhì)的提高.但其主要問題也顯而易見，在于此能力調(diào)度算法的部分局限性，主要是不支持資源的搶占.對某項(xiàng)任務(wù)的執(zhí)行均為“單兵出擊”，只能專注于一件事情，只能等任務(wù)執(zhí)行結(jié)束后，才會再次執(zhí)行同隊(duì)列或他隊(duì)列的其他任務(wù).而對超限制的資源使用，系統(tǒng)亮點(diǎn)在于處置“果斷”，不再為超限“奢求”額外配給計(jì)算資源，以充分展示管理有序性，體現(xiàn)系統(tǒng)服務(wù)的公平合理.

3 “智能化”取向前景下云計(jì)算任務(wù)調(diào)度算法的“發(fā)展性”思考

縱觀云計(jì)算發(fā)展歷程，任務(wù)調(diào)度作為一種“NP”完全性問題，事關(guān)“聚類”的優(yōu)化組合，之前闡述的傳統(tǒng)“網(wǎng)格式”結(jié)算調(diào)度策略與前期“簡練式”雛形調(diào)度策略，在此問題上均存在諸多不足.近些年來，伴隨信息數(shù)據(jù)技術(shù)的萬象更新，逐步推出了啟發(fā)式“智能化”算法新思路，對解決任務(wù)調(diào)度關(guān)鍵性“取向”問題，做出了諸多“發(fā)展性”思考.

3.1 “直線距離”對接中，蟻群算法的“直接性”發(fā)展思考

目前蟻群算法中，其重要參數(shù)均來自于“周而復(fù)始”的大量重復(fù)性實(shí)驗(yàn)，而得出“直線距離”的最終結(jié)果,進(jìn)而加以確定.也就是說所得參數(shù)組合不可能一次成為最優(yōu)，并且可能難以滿足云計(jì)算環(huán)境下任務(wù)調(diào)度動態(tài)性的需求，“走彎路”既成事實(shí).針對這一狀況，胡偉華等做出了“以優(yōu)化算法求解蟻群算法的參數(shù)最佳組合”算法改進(jìn)研究.該算法基于資源歸屬與任務(wù)計(jì)算結(jié)合考慮，實(shí)現(xiàn)了蟻群算法相應(yīng)參數(shù)的靈活匹配，從而能夠?qū)⒇?fù)載均衡良好保持于云計(jì)算系統(tǒng)始終，并于服務(wù)要求上給予客戶充分性滿足，并滿足了等級服務(wù)要求[1].實(shí)驗(yàn)表明，“匠心獨(dú)具”的該算法，尋優(yōu)能力強(qiáng)且極具實(shí)時(shí)性，是一種卓有成效的調(diào)度算法.

3.2 “傳承裂變”演繹中，遺傳算法的“基因性”進(jìn)化思考

遺傳算法的特色在于基因仿真模型中的計(jì)算模型構(gòu)建，在于進(jìn)行“遺傳、變異”與交叉生物類仿真操作，在不斷演繹求解中更迭進(jìn)化，尋求進(jìn)化的更優(yōu)解.目前遺傳算法已廣泛應(yīng)用于多個(gè)領(lǐng)域，且解決效果形勢喜人.基于此，黃璐等人進(jìn)一步做出了“任務(wù)調(diào)度中將模擬退火算法與遺傳算法相結(jié)合”的改進(jìn)遺傳算法研究，依據(jù) “Metropolis” 模擬退火算法準(zhǔn)則，對個(gè)體準(zhǔn)入機(jī)制進(jìn)一步做出界定，在遺傳特性做出不丟失保證的基礎(chǔ)上，確保新個(gè)體的適時(shí)、足量介入，索求最優(yōu)調(diào)度方案，讓遺傳算法實(shí)現(xiàn)“種群進(jìn)化”成為可能[2]；李建鋒等提出了“雙適應(yīng)度函數(shù)”的概念，中心意圖在于建立“全部執(zhí)行任務(wù)時(shí)間與平均完成子任務(wù)時(shí)間”兩項(xiàng)標(biāo)準(zhǔn)，以服務(wù)“整體質(zhì)量與總體滿意度”為原則，進(jìn)而為云計(jì)算任務(wù)調(diào)度執(zhí)行效率提供保證，從而降低任務(wù)執(zhí)行總體時(shí)間，縮短平均完成子任務(wù)時(shí)間[3]；段衛(wèi)軍等做出了“QoS約束策略調(diào)度”研究，以適應(yīng)函數(shù)預(yù)測成本定義與完成時(shí)限，并在求解遺傳算子計(jì)算中搜索全局最優(yōu)方案，以蟻群算子融合度提高任務(wù)調(diào)度精確解.

3.3 “物以類聚”取舍中，粒子群算法的“擇優(yōu)性”導(dǎo)向思考

“Particle Swarm Optimization，PSO”粒子群算法，以一種啟發(fā)式搜索全局的優(yōu)化算法，從中求解事物發(fā)展規(guī)律.主要以“速度至位置”的模型展示粒子群算法的搜索路徑，解空間的每處候選解均以粒子單位形象化,并由適應(yīng)函數(shù)決策解的程度的優(yōu)劣[4].盡管該算法形式上對其種群性“全局搜索”策略有所保留，但其“速度至位置”模型操作的簡單性，賦予了求解便捷性優(yōu)勢，將復(fù)雜遺傳操作給予了“擇優(yōu)性”導(dǎo)向，如尤其特有記憶功能可以令其及時(shí)跟蹤種群“領(lǐng)頭雁”的最優(yōu)粒子.

截至目前，關(guān)于粒子群算法的“擇優(yōu)性”研究不斷.如封良良等人根據(jù)經(jīng)典粒子群算法提出了“雙適應(yīng)度函數(shù)”思路，實(shí)現(xiàn)總體任務(wù)執(zhí)行的時(shí)間降低，子任務(wù)平均完成的時(shí)間縮短[5]；沈愷濤等提出了以“改進(jìn)粒子群編碼”方式求解任務(wù)調(diào)度的策略；李靜梅等人提出了 “異構(gòu)多處理器”解決模式，通過整數(shù)矩陣“編碼”種群粒子，做出了極佳的“發(fā)展性”思考.

[1]胡偉華.基于改進(jìn)蟻群算法的云計(jì)算任務(wù)調(diào)度策略研究[D].杭州:杭州電子科技大學(xué),2013:21-35.

[2]黃璐.基于遺傳算法的云計(jì)算任務(wù)調(diào)度算法研究[D].廈門:廈門大學(xué),2014:21-30.

[3]李建鋒,彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用,2013,31(1):184-186.

[4]王登科.基于粒子群優(yōu)化與蟻群優(yōu)化的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(1):290-293.

[5]封良良,張?zhí)?賈振紅.云計(jì)算環(huán)境下基于粒子群的任務(wù)調(diào)度算法研究[J].計(jì)算機(jī)工程,2013,39(5):183-186.

On Task Scheduling Algorithm Based on Cloud Computing Environment

ZHA Dao-gui, XU Cai-fang, CHEN Wei

(Computer Information Department, Suzhou Vocational Technical College, Suzhou Anhui 234101, China)

Cloud computing is to show the massive cluster resource pool and the flexible dynamic elastic space to attract the attention of scientific development with its unique charm of the times. By contrast, researches of the task scheduling algorithm based on cloud computing environment are getting more and more popular.

internet; cloud computing environment; task scheduling; algorithm research

1673-2103(2017)02-0041-03

2017-01-03

安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目(KJ2016A778)；安徽省省級項(xiàng)目校企合作實(shí)踐教育基地重點(diǎn)項(xiàng)目(2015sjjd037)；安徽省高校優(yōu)秀青年人才支持計(jì)劃重點(diǎn)項(xiàng)目(gxyqZD2016586)

查道貴(1975-),男，安徽安慶人，講師，碩士，研究方向：計(jì)算機(jī)應(yīng)用.

TP301.6

A