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

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

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

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