基于鏈網(wǎng)模型的動(dòng)態(tài)負(fù)載均衡研究

基于鏈網(wǎng)模型的動(dòng)態(tài)負(fù)載均衡研究

分布式網(wǎng)絡(luò)系統(tǒng)（cs）是由兩個(gè)或兩個(gè)以上的網(wǎng)絡(luò)或通信線路連接到網(wǎng)絡(luò)或通信線路的兩個(gè)或兩個(gè)系統(tǒng)組成的系統(tǒng)。分布式計(jì)算是基于消息傳輸（又稱節(jié)點(diǎn)）的計(jì)算模型。投資少、靈活可靠。這為用戶提供了一種基于事務(wù)發(fā)送的有效手段來(lái)實(shí)現(xiàn)高性能和并行計(jì)算的有效途徑，因此它被廣泛用于分布系統(tǒng)。由于每個(gè)節(jié)點(diǎn)的處理能力不同，當(dāng)系統(tǒng)執(zhí)行該部分時(shí)，每個(gè)節(jié)點(diǎn)分配了許多任務(wù)（稱為加載），而其他節(jié)點(diǎn)是空的（稱為加載或慢加載）。為了避免這種情況，應(yīng)采取負(fù)荷平衡措施。負(fù)載均衡(LoadBalancing)即設(shè)法對(duì)已分配給各個(gè)結(jié)點(diǎn)的任務(wù)進(jìn)行重新調(diào)度,并通過(guò)進(jìn)程遷移(又稱為任務(wù)遷移),使各結(jié)點(diǎn)負(fù)載大致相同,這樣能大大提高分布式并行系統(tǒng)的工作效率及性能.但目前的研究大都集中在均衡策略的理論上,對(duì)實(shí)現(xiàn)模型的研究很少.為此,作者構(gòu)建了幾種負(fù)載均衡實(shí)現(xiàn)模型,并研究了其相應(yīng)的實(shí)現(xiàn)算法.1創(chuàng)造約束結(jié)論s在所討論的模型中,相關(guān)的數(shù)據(jù)結(jié)構(gòu)主要有:a.WS:表示結(jié)點(diǎn)S上還未計(jì)算執(zhí)行的任務(wù)集;b.RS:表示結(jié)點(diǎn)S上的已經(jīng)執(zhí)行完的任務(wù)集;c.HS:表示結(jié)點(diǎn)S上等待執(zhí)行結(jié)果即正在執(zhí)行的任務(wù)集.結(jié)點(diǎn)S可用布爾函數(shù)busy(S)和free(S)來(lái)記錄本結(jié)點(diǎn)的狀態(tài),若busy(S)為true,則表示結(jié)點(diǎn)S處于忙狀態(tài);若free(S)為true,則表示結(jié)點(diǎn)S處于空閑狀態(tài).當(dāng)busy(S)與free(S)皆為false時(shí),表示結(jié)點(diǎn)S處于正常狀態(tài),即負(fù)載處于輕載與超載之間的狀態(tài).在所討論的模型中,統(tǒng)一用send(*,*,*)表示任務(wù)發(fā)送,receive(*,*,*)表示任務(wù)的接收.其中,前2個(gè)參數(shù)表示發(fā)送的源結(jié)點(diǎn)和目的結(jié)點(diǎn),第3個(gè)參數(shù)表示發(fā)送或接收的任務(wù).2任務(wù)的整體遷移負(fù)載均衡模型中要解決的核心問(wèn)題有2個(gè):a.什么時(shí)候進(jìn)行任務(wù)的遷移;b.怎樣進(jìn)行任務(wù)的遷移,也就是說(shuō)如何確定發(fā)生了遷移.在下述模型中,把請(qǐng)求遷出任務(wù)的結(jié)點(diǎn)稱為發(fā)送結(jié)點(diǎn)(sender),而請(qǐng)求遷入任務(wù)的結(jié)點(diǎn)稱為接收結(jié)點(diǎn)(receiver).2.1監(jiān)控系統(tǒng)的調(diào)用和切換的速率為了確定1個(gè)結(jié)點(diǎn)在某一時(shí)刻是發(fā)送結(jié)點(diǎn)還是接收結(jié)點(diǎn),必須對(duì)該結(jié)點(diǎn)的負(fù)載情況進(jìn)行評(píng)估.通?？蓮囊韵聨讉€(gè)方面考慮:a.CPU隊(duì)列的長(zhǎng)度(如進(jìn)程的數(shù)目);b.某段時(shí)間內(nèi)CPU隊(duì)列的平均長(zhǎng)度;c.可用內(nèi)存的大小;d.上、下文切換的速率;e.系統(tǒng)調(diào)用的速率;f.CPU的利用率.T.Kunz通過(guò)研究認(rèn)為,使用不同的因子,效率差別較大.使用最簡(jiǎn)單的因子(如CPU隊(duì)列的長(zhǎng)度)就可獲得較高的效率,所以,在所討論的模型中,就以CPU隊(duì)列的長(zhǎng)度作為評(píng)價(jià)一個(gè)體現(xiàn)結(jié)點(diǎn)負(fù)載狀況的最重要標(biāo)準(zhǔn),根據(jù)每個(gè)結(jié)點(diǎn)的局部任務(wù)隊(duì)列中數(shù)據(jù)結(jié)構(gòu)的任務(wù)數(shù)或任務(wù)負(fù)載來(lái)決定該結(jié)點(diǎn)的負(fù)載狀態(tài).如果存在新任務(wù)w,則任務(wù)處理算法為Ws=Ws∪{w};Num(Ws)=Num(Ws)+Num(w).2.2b.門限策略通常,判斷1個(gè)結(jié)點(diǎn)在某一時(shí)刻是發(fā)送結(jié)點(diǎn)還是接收結(jié)點(diǎn)的方法有2種:a.相對(duì)遷移策略——根據(jù)收集的系統(tǒng)負(fù)載信息,按負(fù)載的大小對(duì)各結(jié)點(diǎn)排隊(duì),把該時(shí)刻負(fù)載較重的稱為發(fā)送結(jié)點(diǎn),較輕的稱為接收結(jié)點(diǎn).b.門限策略(或稱為閾值策略)——每個(gè)結(jié)點(diǎn)有各自的負(fù)載上限MaxLoad和負(fù)載下限MinLoad,當(dāng)結(jié)點(diǎn)的負(fù)載低于下限MinLoad時(shí),該結(jié)點(diǎn)為接收結(jié)點(diǎn);當(dāng)結(jié)點(diǎn)的負(fù)載高于上限MaxLoad時(shí),該結(jié)點(diǎn)為發(fā)送結(jié)點(diǎn);當(dāng)結(jié)點(diǎn)的負(fù)載處于上限MaxLoad和下限MinLoad之間時(shí),則該結(jié)點(diǎn)工作正常.這里涉及的模型均采用門限策略.此外,在遷移任務(wù)時(shí),均采用代價(jià)小、效率高的非搶占式任務(wù)遷移,即遷移的任務(wù)都是尚未執(zhí)行的.3源控制回歸模型負(fù)載動(dòng)態(tài)均衡步驟通常包括:a.各個(gè)結(jié)點(diǎn)間負(fù)載信息收集;b.根據(jù)所收集的負(fù)載信息進(jìn)行決策;c.實(shí)現(xiàn)任務(wù)在各結(jié)點(diǎn)之間的遷移.結(jié)合這3個(gè)步驟,提出幾個(gè)模型.在定位每次均衡調(diào)度的源結(jié)點(diǎn)或目的結(jié)點(diǎn)時(shí),可選擇首次適應(yīng)算法或最佳適應(yīng)算法.在所討論的模型中,使用的是首次適應(yīng)算法,即以每次所找到的第1個(gè)符合要求的結(jié)點(diǎn)作為源結(jié)點(diǎn)或目的結(jié)點(diǎn),它的主要優(yōu)點(diǎn)是盡量減少平均調(diào)度檢測(cè)時(shí)間,盡早啟動(dòng)調(diào)度,以執(zhí)行結(jié)點(diǎn)上的任務(wù).3.1鏈模型該模型綜合了目前流行的發(fā)送者驅(qū)動(dòng)和接收者驅(qū)動(dòng)策略,即要么由發(fā)送者,要么由接收者向相鄰結(jié)點(diǎn)逐一提出接收或發(fā)送請(qǐng)求.3.1.1鏈?zhǔn)侥Ｐ椭薪Y(jié)論的增刪Linear-list=(D,R).其中:D={ai|ai∈D0,I=1,2,…,n,n≥0};R={N},N={<ai-1,ai>|ai-1,ai∈D0,i=2,3,…,n};D0為某個(gè)數(shù)據(jù)對(duì)象.關(guān)系N是一個(gè)序偶的集合,它表示線性模型中結(jié)點(diǎn)之間的相鄰關(guān)系,即ai-1的處理順序領(lǐng)先于ai,ai的處理順序領(lǐng)先于ai+1.在鏈?zhǔn)侥Ｐ椭?稱ai-1是ai的直接前驅(qū)結(jié)點(diǎn),ai+1是ai的直接后繼結(jié)點(diǎn).鏈?zhǔn)侥Ｐ偷倪壿嫿Y(jié)構(gòu)如圖1所示.鏈?zhǔn)侥Ｐ椭?各結(jié)點(diǎn)僅和其相鄰結(jié)點(diǎn)(稱為前相鄰結(jié)點(diǎn)和后相鄰結(jié)點(diǎn))交互,將鏈?zhǔn)侥Ｐ偷囊欢硕x為頭結(jié)點(diǎn),則稱另一端的結(jié)點(diǎn)為尾結(jié)點(diǎn).頭結(jié)點(diǎn)僅有后相鄰結(jié)點(diǎn),而尾結(jié)點(diǎn)僅有前相鄰結(jié)點(diǎn).對(duì)鏈?zhǔn)侥Ｐ椭械钠渌Y(jié)點(diǎn)來(lái)說(shuō),與其相鄰的靠近頭結(jié)點(diǎn)的結(jié)點(diǎn)稱為前相鄰結(jié)點(diǎn),靠近尾結(jié)點(diǎn)的結(jié)點(diǎn)稱為后相鄰結(jié)點(diǎn).各結(jié)點(diǎn)中只需保持相鄰前后結(jié)點(diǎn)的位置信息.由于各結(jié)點(diǎn)僅與其相鄰的前后結(jié)點(diǎn)發(fā)生交互,所以,在鏈?zhǔn)侥Ｐ椭羞M(jìn)行動(dòng)態(tài)的增刪是很方便的,只需改變相應(yīng)的結(jié)點(diǎn)的后相鄰結(jié)點(diǎn)和前相鄰結(jié)點(diǎn)的信息,可很靈活、方便地進(jìn)行系統(tǒng)的擴(kuò)充和縮小.3.1.2尋找當(dāng)代網(wǎng)絡(luò)/wac為真實(shí)鏈?zhǔn)侥Ｐ筒捎幂喸兎?按照串行方式與其他結(jié)點(diǎn)交互,采用命令驅(qū)動(dòng)策略(發(fā)送者驅(qū)動(dòng)或接收者驅(qū)動(dòng)).在鏈?zhǔn)侥Ｐ椭?各結(jié)點(diǎn)只需知道自己的動(dòng)態(tài)負(fù)載狀況,而不需知道其他結(jié)點(diǎn)的動(dòng)態(tài)負(fù)載情況.當(dāng)某一結(jié)點(diǎn)被確定為發(fā)送者或接收者時(shí),該結(jié)點(diǎn)逐個(gè)請(qǐng)求鏈?zhǔn)侥Ｐ椭衅渌Y(jié)點(diǎn)找尋滿足要求的點(diǎn).a.鏈?zhǔn)侥Ｐ途馑惴?(sender-initiated):busy:if(Num(Hs)≥MaxLoad){busy(s)=true;尋找前驅(qū)和后繼結(jié)點(diǎn)中free(i)為true的結(jié)點(diǎn)i;}if(存在結(jié)點(diǎn)i使得free(i)=true){send(s,i,w);Ws=Ws-{w};if(Num(Hs)≥MaxLoad){gotobusy;}else{if((Num(Hs)<MaxLoad)and(Num(Hs)≥MinLoad)){busy(s)=false;正常工作;}if(Num(Hs)<MinLoad){free(s)=true;}}}else{wait(p);//waitingforpmilliseconds.gotobusy;}b.鏈?zhǔn)侥Ｐ途馑惴?(receiver-initiated):free:if(Num(Hs)<MinLoad){free(s)=true;尋找前驅(qū)和后繼結(jié)點(diǎn)中busy(i)為true的結(jié)點(diǎn)i;}if(存在結(jié)點(diǎn)i使得busy(i)=true){receive(i,s,w);Ws=Ws+{w};if(Num(Hs)<MaxLoad){gotofree;}else{if((Num(Hs)<MaxLoad)and(Num(Hs)≥MinLoad)){free(s)=false;正常工作;}if(Num(Hs)≥MaxLoad){busy(s)=true;}}}else{wait(p);gotofree;}3.1.3模式1,2鏈?zhǔn)侥Ｐ妥畲蟮膬?yōu)點(diǎn)是簡(jiǎn)單,時(shí)間復(fù)雜度僅為O(n)(n為模型中結(jié)點(diǎn)總數(shù)),它不需要相互交換負(fù)載信息,沒(méi)有過(guò)多額外開銷,通訊延遲也較小.采用鏈?zhǔn)侥Ｐ途馑惴?時(shí),沒(méi)有過(guò)重負(fù)載的忙結(jié)點(diǎn),不會(huì)被空閑鄰結(jié)點(diǎn)所打擾;采用鏈?zhǔn)侥Ｐ途馑惴?時(shí),負(fù)載平衡的許多工作由空閑結(jié)點(diǎn)來(lái)完成,沒(méi)有給忙結(jié)點(diǎn)增加許多額外的負(fù)擔(dān).其缺點(diǎn)是可靠性較差,1個(gè)結(jié)點(diǎn)崩潰會(huì)影響整個(gè)系統(tǒng)的正常運(yùn)行;同時(shí),當(dāng)結(jié)點(diǎn)總數(shù)n很大時(shí),在系統(tǒng)重載(即系統(tǒng)中大多數(shù)結(jié)點(diǎn)都重載)時(shí)采用鏈?zhǔn)侥Ｐ途馑惴?,或在系統(tǒng)輕載(即系統(tǒng)中大多數(shù)結(jié)點(diǎn)都輕載)時(shí)采用鏈?zhǔn)侥Ｐ途馑惴?,效率較低.所以,鏈?zhǔn)侥Ｐ瓦m用于結(jié)點(diǎn)數(shù)不太大的中小型分布式系統(tǒng).3.2網(wǎng)絡(luò)模型考慮到鏈?zhǔn)侥Ｐ偷娜秉c(diǎn),作者進(jìn)一步提出了以綜合二者優(yōu)點(diǎn)的混合驅(qū)動(dòng)策略為基礎(chǔ)的網(wǎng)狀模型.3.2.1無(wú)序隊(duì)x,ynetwork=(V,R).其中:V={x|x∈dataobject},R={VR},VR={(x,y)|P(x,y)∧(x,y∈V)}.無(wú)序隊(duì)(x,y)表示結(jié)點(diǎn)x和y相連;x,y互為鄰接點(diǎn).網(wǎng)狀模型的邏輯結(jié)構(gòu)如圖2所示.在網(wǎng)狀模型中,各結(jié)點(diǎn)中記載有若干相鄰結(jié)點(diǎn)的位置及負(fù)載信息,每次當(dāng)結(jié)點(diǎn)的負(fù)載狀態(tài)發(fā)生變化時(shí),則由該結(jié)點(diǎn)向相鄰結(jié)點(diǎn)進(jìn)行廣播,使各相鄰結(jié)點(diǎn)更新各自所記錄的該負(fù)載狀態(tài)發(fā)生變化的結(jié)點(diǎn)負(fù)載情況.3.2.2u3000鄰接病點(diǎn)的均衡在網(wǎng)狀模型中每個(gè)結(jié)點(diǎn)都有若干個(gè)鄰接結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)都采用并行方法(如廣播)進(jìn)行交互.在網(wǎng)狀模型中,采用狀態(tài)變化驅(qū)動(dòng)策略,即結(jié)點(diǎn)僅在負(fù)載狀況發(fā)生變化時(shí),才向其他結(jié)點(diǎn)報(bào)告(廣播)最新的狀態(tài)信息.而每個(gè)結(jié)點(diǎn)根據(jù)各自的運(yùn)行能力事先確立了負(fù)載上限(Maxload)和負(fù)載下限(Minload),輕載的結(jié)點(diǎn)從相鄰的超載的結(jié)點(diǎn)中接收超載任務(wù)執(zhí)行.所以,在該模型中,每個(gè)結(jié)點(diǎn)都具有記錄鄰接結(jié)點(diǎn)負(fù)載狀態(tài)信息及相互間任務(wù)傳遞情況的一組屬性.網(wǎng)狀模型均衡算法如下:if負(fù)載發(fā)生變化{向相鄰結(jié)點(diǎn)廣播自己的負(fù)載;load-changed:if(Num(Hs)>Maxload){Ws=WsU{w};}if(Num(Hs)<MaxLoad)and(Num(Hs)≥MinLoad){正常執(zhí)行;Num(Hs)=Num(Hs)-Num(Rs);}if((Num(Hs)<MinLoad){if(Ws≠Φ){get(w);Ws=Ws-{w};Gotoload-changed;}else{根據(jù)自己所接收到的鄰接結(jié)點(diǎn)的負(fù)載情況if有超載結(jié)點(diǎn){從超載結(jié)點(diǎn)接收任務(wù);Hs=HsU{w};Num(Hs)=Num(Hs)+Num(w);Gotoload-changed;}else{等待直到有新任務(wù)(自身的或再次廣播之后的)};}}}3.2.3執(zhí)行需求決策時(shí),實(shí)體網(wǎng)狀模型具有良好的可靠性,即使有數(shù)個(gè)結(jié)點(diǎn)崩潰也不會(huì)造成整個(gè)系統(tǒng)工作癱瘓,并且對(duì)于大規(guī)模并行計(jì)算問(wèn)題,當(dāng)每個(gè)結(jié)點(diǎn)均處于忙狀態(tài)時(shí),幾乎不需要額外調(diào)度開銷.當(dāng)算法中的任務(wù)請(qǐng)求不能滿足時(shí),并不需要反復(fù)請(qǐng)求,而是記錄請(qǐng)求任務(wù)的結(jié)點(diǎn)號(hào),以后產(chǎn)生新任務(wù)時(shí),就把該任務(wù)發(fā)送到該空閑的結(jié)點(diǎn)上,這樣就避免了對(duì)鄰接結(jié)點(diǎn)的反復(fù)打擾,減少了通訊開銷,因而網(wǎng)狀模型更適宜于大中型分布式系統(tǒng).但是,在較壞情況下(即在大型分布式系統(tǒng)中網(wǎng)絡(luò)通訊條件不太好時(shí)),結(jié)點(diǎn)間的通訊延遲可能使各結(jié)點(diǎn)記錄的負(fù)載狀況與真實(shí)情況不同,使用這樣的過(guò)時(shí)信息決策,必然導(dǎo)致效率降低.為此,采用結(jié)合鏈?zhǔn)侥Ｐ团c網(wǎng)狀模型的鏈網(wǎng)模型.3.3鏈網(wǎng)模型的改進(jìn)上述2種模型都并不完善,對(duì)評(píng)定系統(tǒng)優(yōu)越性的幾條要求(有效性,穩(wěn)定性,可靠性,用戶透明性和通用性)都不能較好地滿足,為此,綜合并改進(jìn)鏈?zhǔn)侥Ｐ团c網(wǎng)狀模型得到鏈網(wǎng)模型,它對(duì)于前述幾點(diǎn)要求都能較好地滿足.3.3.1中心網(wǎng)點(diǎn)內(nèi)無(wú)結(jié)論在由許多結(jié)點(diǎn)組成的分布式系統(tǒng)中,若干結(jié)點(diǎn)(視結(jié)點(diǎn)性能而定)組成一個(gè)小局域網(wǎng),即每個(gè)小局域網(wǎng)是一個(gè)包含幾個(gè)結(jié)點(diǎn)元素的結(jié)點(diǎn)集,一個(gè)分布式系統(tǒng)中的所有結(jié)點(diǎn)分屬于不同的小局域網(wǎng)(結(jié)點(diǎn)集),任一結(jié)點(diǎn)必須屬于并且僅屬于某一小局域網(wǎng)(結(jié)點(diǎn)集),即各結(jié)點(diǎn)集間沒(méi)有交集.每個(gè)結(jié)點(diǎn)僅和該結(jié)點(diǎn)所屬局域網(wǎng)內(nèi)結(jié)點(diǎn)平衡.在各局域網(wǎng)內(nèi),各以1個(gè)結(jié)點(diǎn)作為信息中心結(jié)點(diǎn),當(dāng)各自負(fù)載狀況發(fā)生變化時(shí),局域網(wǎng)內(nèi)其他結(jié)點(diǎn)主動(dòng)向信息中心匯報(bào)情況,并從該中心獲取同一局域網(wǎng)內(nèi)其他結(jié)點(diǎn)負(fù)載情況;各局域網(wǎng)內(nèi)的信息中心結(jié)點(diǎn)以鏈?zhǔn)浇Y(jié)構(gòu)相連.鏈網(wǎng)模型邏輯結(jié)構(gòu)如圖3所示.在鏈網(wǎng)模型中,僅信息中心結(jié)點(diǎn)需要記錄處于相同局域網(wǎng)內(nèi)的其他非信息中心結(jié)點(diǎn)的負(fù)載信息,而各非信息中心結(jié)點(diǎn)僅需知道信息中心結(jié)點(diǎn)的位置.當(dāng)某一非信息中心結(jié)點(diǎn)負(fù)載發(fā)生變化時(shí),將負(fù)載信息向信息中心匯報(bào)即可.若負(fù)載變化后該非信息中心結(jié)點(diǎn)空閑,則按信息中心記載的信息從忙結(jié)點(diǎn)接收任務(wù).這樣,每次的負(fù)載變化不需打擾相鄰結(jié)點(diǎn),也不被相鄰結(jié)點(diǎn)打擾,提高了整個(gè)系統(tǒng)的效率.而各信息中心的聯(lián)系可視分布式系統(tǒng)的規(guī)模采用不同的模式.若系統(tǒng)規(guī)模相對(duì)較小,則各信息中心的聯(lián)系可采用鏈?zhǔn)侥Ｐ?若系統(tǒng)規(guī)模較大(即結(jié)點(diǎn)數(shù)為一極大值),則各信息中心的聯(lián)系又可采用鏈網(wǎng)模型,依此類推.3.3.2個(gè)人客觀條件負(fù)載信息報(bào)告鏈網(wǎng)模型中的均衡算法分為非信息中心處理算法和信息中心處理算法.信息中心僅作為信息集散地,具體的調(diào)度和操作是由非信息中心結(jié)點(diǎn)根據(jù)信息中心結(jié)點(diǎn)的記錄來(lái)進(jìn)行的,具體到任務(wù)的調(diào)度是由空閑非信息中心結(jié)點(diǎn)完成,這樣不會(huì)增加忙結(jié)點(diǎn)的負(fù)擔(dān).非信息中心信息處理算法如下:if負(fù)載發(fā)生變化{向信息中心匯報(bào)負(fù)載情況;if負(fù)載處于上下限之間{執(zhí)行任務(wù);有任務(wù)執(zhí)行完畢則向信息中心匯報(bào)負(fù)載情況;}if負(fù)載超過(guò)上限{超載任務(wù)等待他結(jié)點(diǎn)調(diào)入;向信息中心匯報(bào)負(fù)載情況,告之超載狀態(tài);}if負(fù)載低于下