分布式網(wǎng)格作業(yè)調(diào)度模型研究

分布式網(wǎng)格作業(yè)調(diào)度模型研究

0網(wǎng)格資源調(diào)度問(wèn)題的提出網(wǎng)格技術(shù)有效整合了廣泛、分散和異構(gòu)資源，提供了大量的計(jì)算資源、數(shù)據(jù)資源、信息資源、存儲(chǔ)資源、硬件資源等，用于處理科學(xué)計(jì)算、電子商務(wù)、工程制造等領(lǐng)域的應(yīng)用問(wèn)題。面對(duì)巨大的網(wǎng)格計(jì)算資源,我們需要有效加以利用,因此我們將要面臨并研究的主要問(wèn)題之一就是如何對(duì)廣域范圍內(nèi)分布、異構(gòu)、動(dòng)態(tài)的資源進(jìn)行合理調(diào)度。作為調(diào)度的目標(biāo)之一,負(fù)載平衡是計(jì)算網(wǎng)格的重要特性。我們知道,簡(jiǎn)單的負(fù)載平衡策略可以有效提高計(jì)算性能。對(duì)網(wǎng)格資源調(diào)度進(jìn)行的研究中,通常涉及到資源發(fā)現(xiàn)、資源監(jiān)控、資源聚類(lèi)、任務(wù)分配,任務(wù)調(diào)度。這里主要討論的是在資源聚類(lèi)基礎(chǔ)上,進(jìn)行的調(diào)度模型和負(fù)載平衡調(diào)度的研究。文獻(xiàn)提出了一種面向網(wǎng)格計(jì)算的機(jī)器選擇算法,用于主機(jī)資源的聚類(lèi),為網(wǎng)格資源組織和管理提供了一種有效的方法,提出了異構(gòu)環(huán)境下基于通信密集應(yīng)用和計(jì)算密集應(yīng)用的聚類(lèi)算法。根據(jù)此類(lèi)算法生成的虛擬集群作為我們將要研究的調(diào)度問(wèn)題的節(jié)點(diǎn)。文獻(xiàn)提出的網(wǎng)格計(jì)算資源調(diào)度的三層模式試圖解決網(wǎng)格計(jì)算中的資源調(diào)度問(wèn)題。但是它的三級(jí)調(diào)度模式層次間的通信會(huì)影響到調(diào)度系統(tǒng)的整體性能,并且第一級(jí)的集中式調(diào)度節(jié)點(diǎn)可能形成單故障點(diǎn)。這也是本文要解決的問(wèn)題之一。文獻(xiàn)中的傳統(tǒng)擴(kuò)散算法,每個(gè)節(jié)點(diǎn)只能與其周?chē)苯舆B接的節(jié)點(diǎn)平衡負(fù)載,通過(guò)多次循環(huán)迭代實(shí)現(xiàn)系統(tǒng)的負(fù)載平衡,這樣的負(fù)載平衡如果用于網(wǎng)格環(huán)境是不合適的,因?yàn)槊鎸?duì)廣域分布的網(wǎng)格,迭代的次數(shù)將極大降低負(fù)載平衡的效率,增強(qiáng)負(fù)載擴(kuò)散速度也在本文中給出了一個(gè)解決方案。本文首先說(shuō)明了負(fù)載平衡的相關(guān)概念,并描述本文需要的計(jì)算網(wǎng)格模型,負(fù)載信息采集策略,和負(fù)載轉(zhuǎn)移策略。然后提出了基于負(fù)載平衡的調(diào)度系統(tǒng)模型,以及相應(yīng)組件功能,給出了負(fù)載平衡算法。最后總結(jié)了以上工作并說(shuō)明將繼續(xù)進(jìn)行的工作。1負(fù)載負(fù)荷平衡1.1負(fù)載平衡的實(shí)現(xiàn)在計(jì)算網(wǎng)格中,當(dāng)經(jīng)過(guò)一段時(shí)間運(yùn)行后,某些結(jié)點(diǎn)分配的任務(wù)很多(重載節(jié)點(diǎn)),而另外一些結(jié)點(diǎn)卻相對(duì)空閑(輕載節(jié)點(diǎn)),產(chǎn)生負(fù)載不均衡現(xiàn)象。在一些計(jì)算網(wǎng)格的應(yīng)用中,尤其是在異構(gòu)資源的網(wǎng)格環(huán)境中,負(fù)載的不平衡性越發(fā)明顯,本文的應(yīng)用中,會(huì)出現(xiàn)1:50的負(fù)載不均衡。負(fù)載不均衡導(dǎo)致系統(tǒng)嚴(yán)重的低效運(yùn)行,因此,實(shí)現(xiàn)負(fù)載平衡是保證整個(gè)計(jì)算網(wǎng)格效率的前提。負(fù)載平衡問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化難題,一般分為靜態(tài)負(fù)載平衡和動(dòng)態(tài)負(fù)載平衡兩種。靜態(tài)負(fù)載平衡由于本身局限性,不適用于網(wǎng)格的動(dòng)態(tài)變化環(huán)境,因此本文主要研究動(dòng)態(tài)負(fù)載平衡。動(dòng)態(tài)負(fù)載平衡通過(guò)分析系統(tǒng)各節(jié)點(diǎn)實(shí)時(shí)負(fù)載信息,動(dòng)態(tài)地將任務(wù)在各個(gè)結(jié)點(diǎn)之間進(jìn)行分配和轉(zhuǎn)移以調(diào)整系統(tǒng)中各節(jié)點(diǎn)負(fù)載分布不均勻性,所以動(dòng)態(tài)負(fù)載平衡更能反映分布式系統(tǒng)的實(shí)際情況,適用于計(jì)算網(wǎng)格。1.2以資源聚類(lèi)產(chǎn)生的廣域節(jié)點(diǎn)為中心的網(wǎng)絡(luò)化分布式調(diào)度為了建立我們需要的網(wǎng)格系統(tǒng)模型,我們可以使用基于網(wǎng)絡(luò)性能的主機(jī)資源聚類(lèi)。它的思想是根據(jù)網(wǎng)格應(yīng)用對(duì)鏈路狀態(tài)(帶寬、延遲等)的QoS要求進(jìn)行資源劃分,要求資源集合內(nèi)部主機(jī)間連接為高帶寬、低延遲,而不同資源集合主機(jī)間的連接是相對(duì)低速的。通過(guò)此類(lèi)資源聚類(lèi)方法,在全局范圍內(nèi),我們可以將網(wǎng)格抽象為若干個(gè)廣域節(jié)點(diǎn)組成的分布系統(tǒng),進(jìn)行資源的管理和調(diào)度。每一個(gè)廣域節(jié)點(diǎn)是資源聚類(lèi)產(chǎn)生的一個(gè)節(jié)點(diǎn)集合。定義1廣域節(jié)點(diǎn),指通過(guò)資源聚類(lèi)產(chǎn)生的一個(gè)資源節(jié)點(diǎn)集合。所有廣域節(jié)點(diǎn)集合組成網(wǎng)格計(jì)算系統(tǒng)定義2每一個(gè)廣域節(jié)點(diǎn)內(nèi)部都有自己的資源管理和調(diào)度節(jié)點(diǎn),我們稱(chēng)之為廣域節(jié)點(diǎn)的作業(yè)管理調(diào)度節(jié)點(diǎn),文中簡(jiǎn)稱(chēng)為調(diào)度節(jié)點(diǎn).。調(diào)度節(jié)點(diǎn)之間存在直截通信連接的我們稱(chēng)之為臨近節(jié)點(diǎn)。通過(guò)這種方式,網(wǎng)格系統(tǒng)被分為兩層,底層是通過(guò)資源聚類(lèi)產(chǎn)生的一個(gè)節(jié)點(diǎn)集合Ni,是一個(gè)局域網(wǎng)格,高層是將各個(gè)局域網(wǎng)格連接起來(lái)形成一個(gè)整體的網(wǎng)格系統(tǒng)G。每個(gè)局域網(wǎng)格系統(tǒng)的調(diào)度方法可以根據(jù)自身特點(diǎn)使用傳統(tǒng)的分布式調(diào)度方法進(jìn)行任務(wù)分配和調(diào)度,本文討論的是更高層次的負(fù)載平衡問(wèn)題,即在各個(gè)局域網(wǎng)格之間負(fù)載不均衡的情況下,進(jìn)行負(fù)載平衡。負(fù)載平衡主要涉及3個(gè)方面的問(wèn)題:(1)信息采集策略;(2)負(fù)載轉(zhuǎn)移策略;(3)負(fù)載平衡算法。負(fù)載平衡算法是我們研究的重點(diǎn),將在后面章節(jié)中重點(diǎn)討論。1.3pu利用的假設(shè)在進(jìn)行負(fù)載平衡的調(diào)度中,需要了解各廣域節(jié)點(diǎn)的負(fù)載信息,作為衡量負(fù)載轉(zhuǎn)移目標(biāo)節(jié)點(diǎn)的負(fù)載輕重狀況的參數(shù)。因此定義3負(fù)載信息定義:{,}={CPU總體性能,CPU利用率}。假設(shè):輕負(fù)載<%30R中等負(fù)載=%60R重負(fù)載>80%R。在廣域網(wǎng)絡(luò)進(jìn)行信息傳輸網(wǎng)絡(luò)延遲相對(duì)較大,為了減少網(wǎng)絡(luò)通信所帶來(lái)的負(fù)載,本文的信息采集策略采用負(fù)載變化時(shí)采集負(fù)載信息的方式。當(dāng)廣域節(jié)點(diǎn)負(fù)載波動(dòng)超過(guò)一定范圍,它的調(diào)度節(jié)點(diǎn)才將采集到的負(fù)載信息傳輸給主調(diào)度節(jié)點(diǎn),這樣可以大量減少負(fù)載信息傳遞開(kāi)銷(xiāo)。所以,各調(diào)度節(jié)點(diǎn)的負(fù)載信息發(fā)送方式描述如下if(系統(tǒng)負(fù)載利用率<=中等負(fù)載and負(fù)載波動(dòng)大于5%)發(fā)送系統(tǒng)負(fù)載信息給負(fù)載平衡調(diào)度系統(tǒng)負(fù)載信息采集節(jié)點(diǎn);1.4采用作業(yè)轉(zhuǎn)移算法負(fù)載平衡過(guò)程需要進(jìn)行負(fù)載轉(zhuǎn)移,由于進(jìn)程遷移不僅難以在網(wǎng)格環(huán)境中的異構(gòu)結(jié)點(diǎn)間實(shí)現(xiàn),而且其開(kāi)銷(xiāo)也十分龐大,甚至抵消負(fù)載平衡所帶來(lái)的性能提高。因此,采用作業(yè)轉(zhuǎn)移算法,即只對(duì)已經(jīng)分配給廣域節(jié)點(diǎn)但未開(kāi)始執(zhí)行的作業(yè)進(jìn)行再分配,并且所有作業(yè)最多進(jìn)行一次再分配,這樣有效減輕負(fù)載平衡系統(tǒng)可能產(chǎn)生的“顛簸”現(xiàn)象。該方法可以自動(dòng)適應(yīng)Internet環(huán)境下的資源不確定性,可以不借助進(jìn)程遷移而實(shí)現(xiàn)低開(kāi)銷(xiāo)的任務(wù)再分配。2資源規(guī)劃模型2.1從調(diào)度節(jié)點(diǎn)的監(jiān)控在各個(gè)廣域節(jié)點(diǎn)的作業(yè)管理調(diào)度節(jié)點(diǎn)之間,通過(guò)選舉算法產(chǎn)生一個(gè)主調(diào)度節(jié)點(diǎn),主要用于收集全局范圍的負(fù)載信息,監(jiān)控其它調(diào)度節(jié)點(diǎn)有效性。主調(diào)度節(jié)點(diǎn)產(chǎn)生以后,它指定一個(gè)從調(diào)度節(jié)點(diǎn),并監(jiān)控從調(diào)度節(jié)點(diǎn)的有效性,以便在從節(jié)點(diǎn)失效時(shí),重新指定從調(diào)度節(jié)點(diǎn)。從調(diào)度節(jié)點(diǎn)的任務(wù)是,周期性監(jiān)控主調(diào)度節(jié)點(diǎn),并和主調(diào)度節(jié)點(diǎn)交換全局負(fù)載信息,在主調(diào)度節(jié)點(diǎn)發(fā)生故障的情況下快速接替主調(diào)度節(jié)點(diǎn)的位置并實(shí)施主調(diào)度節(jié)點(diǎn)的功能。主從節(jié)點(diǎn)之間的這種互相監(jiān)控的機(jī)制,有效保證了動(dòng)態(tài)負(fù)載平衡系統(tǒng)中的全局負(fù)載信息收集的有效性,增強(qiáng)系統(tǒng)的可靠性。網(wǎng)格系統(tǒng)模型G={1,2,…,,…,,…,},表示主調(diào)度節(jié)點(diǎn),表示從調(diào)度節(jié)點(diǎn)。如圖1所示,其中,

表示調(diào)度節(jié)點(diǎn)。立方體表示廣域節(jié)點(diǎn),云狀圖表示其它的廣域節(jié)點(diǎn)。2.2主調(diào)度節(jié)點(diǎn)信息搜尋算法主調(diào)度節(jié)點(diǎn):初始化時(shí),主調(diào)度節(jié)點(diǎn)組播信息給系統(tǒng)中各個(gè)調(diào)度節(jié)點(diǎn),表明自己是主調(diào)度節(jié)點(diǎn),告知其它調(diào)度節(jié)點(diǎn)將負(fù)載信息按照信息采集策略發(fā)送給自己。根據(jù)各調(diào)度節(jié)點(diǎn)返回信息指定一個(gè)從調(diào)度節(jié)點(diǎn),并啟動(dòng)后臺(tái)進(jìn)程,監(jiān)控從節(jié)點(diǎn)的有效性。系統(tǒng)運(yùn)行時(shí),在負(fù)責(zé)本地作業(yè)管理調(diào)度工作的同時(shí),接收其它調(diào)度節(jié)點(diǎn)傳來(lái)的當(dāng)前負(fù)載信息數(shù)據(jù),并將全局范圍調(diào)度節(jié)點(diǎn)的負(fù)載信息周期性發(fā)送給從節(jié)點(diǎn),以便從結(jié)點(diǎn)在適當(dāng)時(shí)機(jī)作為主調(diào)度節(jié)點(diǎn)工作;如果有其它調(diào)度節(jié)點(diǎn)因本地負(fù)載過(guò)重,發(fā)出資源請(qǐng)求到主調(diào)度節(jié)點(diǎn),主調(diào)度節(jié)點(diǎn)根據(jù)算法1選擇當(dāng)前全局負(fù)載最輕的節(jié)點(diǎn)位置和負(fù)載信息給請(qǐng)求節(jié)點(diǎn)。算法1主調(diào)度節(jié)點(diǎn)信息查找算法從調(diào)度節(jié)點(diǎn):從調(diào)度節(jié)點(diǎn)作為調(diào)度節(jié)點(diǎn),它本身也具備同其它調(diào)度節(jié)點(diǎn)一樣的本地作業(yè)管理調(diào)度功能。在被指定為從調(diào)度節(jié)點(diǎn)時(shí),從調(diào)度節(jié)點(diǎn)主要負(fù)責(zé)監(jiān)控主調(diào)度節(jié)點(diǎn)的有效性,并接受主調(diào)度節(jié)點(diǎn)傳遞的全局范圍負(fù)載信息。當(dāng)發(fā)現(xiàn)主調(diào)度節(jié)點(diǎn)失效時(shí),從節(jié)點(diǎn)向系統(tǒng)中所有調(diào)度節(jié)點(diǎn)組播信息,通知主調(diào)度節(jié)點(diǎn)失效,自己已經(jīng)接替成為新的主調(diào)度節(jié)點(diǎn),并接受全局范圍調(diào)度節(jié)點(diǎn)傳送來(lái)的各地負(fù)載信息。同時(shí)指定新的從調(diào)度節(jié)點(diǎn),行使主節(jié)點(diǎn)職能。其它調(diào)度節(jié)點(diǎn):調(diào)度節(jié)點(diǎn)通過(guò)取得相關(guān)節(jié)點(diǎn)負(fù)載信息,判斷任務(wù)轉(zhuǎn)移的目的節(jié)點(diǎn),完成全局負(fù)載平衡調(diào)度任務(wù),具體算法在下一節(jié)中給出。3調(diào)度節(jié)點(diǎn)負(fù)載重負(fù)載當(dāng)廣域節(jié)點(diǎn)負(fù)載過(guò)重時(shí),其調(diào)度節(jié)點(diǎn)同時(shí)向臨近節(jié)點(diǎn)和主調(diào)度節(jié)點(diǎn)發(fā)出負(fù)載轉(zhuǎn)移請(qǐng)求后,根據(jù)算法2描述的負(fù)載轉(zhuǎn)移方法,根據(jù)返回信息的到達(dá)順序,檢查相關(guān)調(diào)度節(jié)點(diǎn)的返回信息(一般臨近節(jié)點(diǎn)有較短網(wǎng)絡(luò)延遲),確定這些廣域節(jié)點(diǎn)是否可以減緩本地負(fù)載壓力,并且在其接受負(fù)載轉(zhuǎn)移后自身負(fù)載維持在正常負(fù)載狀態(tài)。如果滿足條件,則進(jìn)行負(fù)載轉(zhuǎn)移調(diào)度;否則繼續(xù)等待,直到滿足要求的調(diào)度節(jié)點(diǎn)返回信息,系統(tǒng)進(jìn)行負(fù)載轉(zhuǎn)移,將負(fù)載向周?chē)鷶U(kuò)散,或者轉(zhuǎn)移到負(fù)載最輕的位置。算法2調(diào)度節(jié)點(diǎn)負(fù)載平衡算法調(diào)度節(jié)點(diǎn)負(fù)載過(guò)重時(shí)通過(guò)獲取相關(guān)廣域節(jié)點(diǎn)的負(fù)載信息,判斷并決定負(fù)載轉(zhuǎn)移的目標(biāo)節(jié)點(diǎn)。通過(guò)采用這樣的方式,主調(diào)度節(jié)點(diǎn)作為一個(gè)全局負(fù)載信息采集節(jié)點(diǎn),存儲(chǔ)著各廣域節(jié)點(diǎn)的實(shí)時(shí)負(fù)載信息,并負(fù)責(zé)查找最輕負(fù)載節(jié)點(diǎn)。負(fù)載平衡的功能則分別由各個(gè)調(diào)度節(jié)點(diǎn)自身來(lái)完成,相對(duì)于一般集中式調(diào)度節(jié)點(diǎn)負(fù)責(zé)調(diào)度信息收集以及進(jìn)行任務(wù)調(diào)度,我們可以效減少了一般集中式調(diào)度節(jié)點(diǎn)的負(fù)載平衡調(diào)度負(fù)擔(dān)。在一般的分布式調(diào)度算法中,收集其它廣域節(jié)點(diǎn)實(shí)時(shí)負(fù)載信息的通信復(fù)雜度為O(n(n-1)),而這個(gè)算法的通信復(fù)雜度為O(n+1),和集中式調(diào)度算法的O(n-1)有相同的數(shù)量級(jí),卻通過(guò)主從調(diào)度節(jié)點(diǎn)的實(shí)現(xiàn)機(jī)制,具有了和分布式負(fù)載平衡算法類(lèi)似的可靠性。由于臨近廣域節(jié)點(diǎn)網(wǎng)絡(luò)延遲小,有效保證負(fù)載優(yōu)先轉(zhuǎn)移至臨近節(jié)點(diǎn);而且在臨近節(jié)點(diǎn)重負(fù)載的情況下,負(fù)載快速擴(kuò)散至全局最輕負(fù)載節(jié)點(diǎn)。通過(guò)這種方式,系統(tǒng)負(fù)載擴(kuò)散到更大范圍,更快轉(zhuǎn)移到全局最輕負(fù)載的廣域節(jié)點(diǎn),加速負(fù)載平衡速度,是一種有效的負(fù)載平衡方法。4負(fù)載平衡調(diào)度算法本文提出了一種分布式調(diào)度模型,通過(guò)主從調(diào)度節(jié)點(diǎn)之間的互相監(jiān)控,保證全局負(fù)載信息收集的有效性,使負(fù)載平衡系統(tǒng)具有一定的可靠性,更