分布式系統(tǒng)負(fù)載平衡調(diào)度模型研究

分布式系統(tǒng)負(fù)載平衡調(diào)度模型研究

分布式系統(tǒng)可以方便地處理大型計(jì)算問題。它的優(yōu)點(diǎn)是系統(tǒng)資源的可用性、規(guī)模的可擴(kuò)展性和共存性。如何有效地實(shí)現(xiàn)分布式系統(tǒng)資源的管理和調(diào)度是充分挖掘系統(tǒng)并行潛力的關(guān)鍵因素。通常，一個(gè)分布式系統(tǒng)需要同時(shí)處理多個(gè)任務(wù)，而每個(gè)計(jì)算結(jié)點(diǎn)需要同時(shí)處理多個(gè)進(jìn)程，這就需要通過調(diào)度與分配算法來實(shí)現(xiàn)任務(wù)的優(yōu)化分配，以有效地減小平均響應(yīng)時(shí)間，降低執(zhí)行時(shí)的額外開銷等。因此，負(fù)載平衡就成為改善分布式系統(tǒng)性能的重要手段，它的一個(gè)重要目標(biāo)是提高系統(tǒng)性能，縮短用戶任務(wù)的平均響應(yīng)時(shí)間；它的另一個(gè)重要目標(biāo)是均勻地、充分地利用整個(gè)系統(tǒng)的資源。這兩個(gè)目標(biāo)是一致的，資源的使用越平衡，任務(wù)的響應(yīng)時(shí)間就越短。通常，負(fù)載平衡調(diào)度方法分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩種。國(guó)內(nèi)外對(duì)此已進(jìn)行了許多研究，出現(xiàn)了多種算法。解決靜態(tài)負(fù)載平衡的方法主要有：模擬退火算法、遺傳算法、啟發(fā)式方法、基于圖論的方法等。解決動(dòng)態(tài)負(fù)載平衡的方法主要包括以下幾種：基于隨機(jī)選擇任務(wù)移動(dòng)結(jié)點(diǎn)的概率調(diào)度算法、根據(jù)負(fù)載變化而基于梯度模型的調(diào)度算法、自適應(yīng)的近鄰契約算法等。影響負(fù)載平衡調(diào)度問題的因素很多，各個(gè)調(diào)度算法的實(shí)現(xiàn)方法也各不相同。Kim提出的調(diào)度模型將負(fù)載平衡調(diào)度過程分為以下四個(gè)階段：負(fù)載估算、負(fù)載平衡收益性決策、任務(wù)轉(zhuǎn)移和任務(wù)選擇。文獻(xiàn)中的調(diào)度模型考慮了以下因素：調(diào)度時(shí)間、調(diào)度的源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)、調(diào)度任務(wù)的選擇。文獻(xiàn)研究了基于多處理機(jī)的任務(wù)調(diào)度模型Pk|fix|Cmax，并在此基礎(chǔ)上提出了一個(gè)更接近實(shí)際的負(fù)載平衡調(diào)度模型，該模型是以下五個(gè)元素的集合：處理機(jī)系統(tǒng)、任務(wù)集實(shí)例、處理機(jī)約束集、任務(wù)之間的約束集和調(diào)度的評(píng)價(jià)指標(biāo)，但是該文獻(xiàn)并沒有對(duì)各元素作詳細(xì)的描述。本文在深入研究各種負(fù)載平衡調(diào)度算法和調(diào)度模型的基礎(chǔ)上，綜合考慮影響負(fù)載平衡調(diào)度問題的各個(gè)因素，給出了一個(gè)負(fù)載平衡調(diào)度問題的一般模型的形式化描述，即將負(fù)載平衡調(diào)度問題的一般模型用四元組<E,T,L,S>來表示。其中：因子E(Environment）：表示分布式系統(tǒng)的網(wǎng)絡(luò)環(huán)境；因子T(Task）：表示用戶提交的任務(wù)屬性；因子L(Load）：表示系統(tǒng)的負(fù)載評(píng)價(jià)；因子S(Strategy）：表示系統(tǒng)所采用的調(diào)度策略。1分布式系統(tǒng)結(jié)構(gòu)設(shè)計(jì)定義1分布式網(wǎng)絡(luò)調(diào)度環(huán)境因子E是一個(gè)三元組（DS,SE,SG）。其中：分布式系統(tǒng)DS(DistributedSystem）：表示分布式系統(tǒng)的物理網(wǎng)絡(luò)結(jié)構(gòu)；負(fù)載平衡調(diào)度環(huán)境SE(SchedulingEnvironment）：表示負(fù)載平衡調(diào)度結(jié)點(diǎn)的邏輯拓?fù)浣Y(jié)構(gòu)；調(diào)度組SG(SchedulingGroup）：參與某項(xiàng)調(diào)度活動(dòng)的計(jì)算結(jié)點(diǎn)所組成的集合。1.1同構(gòu)性和拓?fù)浣Y(jié)構(gòu)分布式系統(tǒng)DS(DistributedSystem），是由一組根據(jù)通訊協(xié)議物理聯(lián)接、地理分布工作站組成的相互協(xié)作、資源共享的網(wǎng)絡(luò)系統(tǒng)，組成DS的工作站稱為節(jié)點(diǎn)。節(jié)點(diǎn)很難做到必須是同構(gòu)的，從功能上可以區(qū)分為圖形工作站、科學(xué)計(jì)算工作站、I/O工作站、數(shù)據(jù)庫(kù)工作站、WEB工作站等，從性能上可以區(qū)分為單處理機(jī)工作站、多處理機(jī)工作站、r-處理機(jī)工作站等。但是同構(gòu)DS由于其便于調(diào)度、便于管理的優(yōu)點(diǎn)，在某些場(chǎng)合常常得到特殊應(yīng)用。DS除了需要描述各節(jié)點(diǎn)的功能與性能特性之外，還要描述節(jié)點(diǎn)之間物理意義上的拓?fù)浣Y(jié)構(gòu)。不同的拓?fù)浣Y(jié)構(gòu)對(duì)負(fù)載平衡調(diào)度算法有很大的影響，文獻(xiàn)討論了2維網(wǎng)格、4維超立方、線性陣列等不同結(jié)構(gòu)對(duì)梯度策略、發(fā)送者驅(qū)動(dòng)策略、接收者驅(qū)動(dòng)策略、集中式調(diào)度策略和基于預(yù)測(cè)的調(diào)度策略等不同負(fù)載平衡調(diào)度算法的影響。1.2載平衡調(diào)度環(huán)境在負(fù)載平衡調(diào)度過程中，根據(jù)節(jié)點(diǎn)之間的協(xié)作協(xié)議、任務(wù)性質(zhì)與功能對(duì)應(yīng)關(guān)系（例如，WEB服務(wù)類任務(wù)通常由WEB工作站處理）以及負(fù)載平衡調(diào)度策略的差異，分布式系統(tǒng)重新構(gòu)成邏輯意義上的圖的拓?fù)浣Y(jié)構(gòu)，即負(fù)載平衡調(diào)度環(huán)境SE(SchedulingEnvironment）,SE上的節(jié)點(diǎn)稱為結(jié)點(diǎn)。負(fù)載平衡調(diào)度環(huán)境的拓?fù)浣Y(jié)構(gòu)是一個(gè)無向圖SE=（N,E），其中N為結(jié)點(diǎn)集，E為SE的邏輯邊集。若將DS也表示成無向圖，則圖SE滿足下面性質(zhì)：(1）無向圖SE是無向圖DS的子圖；(2）無向圖SE是連通圖。所有負(fù)載平衡調(diào)度策略均在負(fù)載平衡調(diào)度環(huán)境SE上進(jìn)行討論，典型的SE圖結(jié)構(gòu)有普通無向圖、Mesh圖、Hypercube圖和層次結(jié)構(gòu)圖等。在參考了以上幾種經(jīng)典的分布式系統(tǒng)模型的基礎(chǔ)上，綜合靜態(tài)和動(dòng)態(tài)兩種負(fù)載平衡策略，提出了一個(gè)基于層次結(jié)構(gòu)的混合調(diào)度策略模型，如圖1所示，該模型具有更優(yōu)越的性能。1.3參與調(diào)度活動(dòng)的程序負(fù)載平衡調(diào)度活動(dòng)（即執(zhí)行一次負(fù)載平衡調(diào)度算法）稱為調(diào)度事件S＿Event，調(diào)度事件S＿Event是一個(gè)二元組（SG,SA）。其中，調(diào)度組SG(SchedulingGroup）是由參與調(diào)度事件S＿Event的所有SE結(jié)點(diǎn)組成的集合，SA為調(diào)度事件S＿Event執(zhí)行的調(diào)度算法（SchedulingAlgorithm）。調(diào)度組中的結(jié)點(diǎn)充任兩類角色（角色指結(jié)點(diǎn)在參與調(diào)度活動(dòng)過程中所承擔(dān)的責(zé)任和該發(fā)揮的作用），即一個(gè)調(diào)度服務(wù)器SS(SchedulingServer）和若干調(diào)度成員SM(SchedulingMembers），調(diào)度服務(wù)器SS是負(fù)載平衡調(diào)度事件S＿Event的啟動(dòng)者，調(diào)度成員SM是S＿Event的參與者。調(diào)度組是負(fù)載平衡調(diào)度活動(dòng)的基本單位，根據(jù)每次調(diào)度活動(dòng)動(dòng)態(tài)生成，負(fù)責(zé)處理具體的調(diào)度事件。由于對(duì)于同一個(gè)分布式系統(tǒng)，不同的調(diào)度策略會(huì)得到不同的負(fù)載平衡調(diào)度環(huán)境拓?fù)浣Y(jié)構(gòu)，與此同時(shí)，在調(diào)度過程中，參與負(fù)載平衡調(diào)度活動(dòng)的工作站類型與數(shù)目也各不相同，因此上述節(jié)點(diǎn)、結(jié)點(diǎn)與角色三個(gè)概念之間具有如下關(guān)系：(1）節(jié)點(diǎn)是物理上的概念，表示分布式系統(tǒng)中的工作站。結(jié)點(diǎn)與角色都是邏輯上的概念，指在負(fù)載平衡調(diào)度問題空間中（表示成圖的拓?fù)浣Y(jié)構(gòu)），參與負(fù)載平衡調(diào)度活動(dòng)的實(shí)體（On-tology）。(2）節(jié)點(diǎn)、結(jié)點(diǎn)和角色都是靜態(tài)的概念。結(jié)點(diǎn)擔(dān)任一定的角色，使用相關(guān)資源和信息協(xié)作完成各項(xiàng)調(diào)度活動(dòng)。角色是結(jié)點(diǎn)在完成一項(xiàng)調(diào)度活動(dòng)時(shí)所具有的權(quán)利與責(zé)任集合。(3）角色和結(jié)點(diǎn)之間的綁定是動(dòng)態(tài)的。同一個(gè)結(jié)點(diǎn)在不同調(diào)度事件中可以擔(dān)任不同的角色。在同一個(gè)調(diào)度事件中，一個(gè)角色（指調(diào)度成員）可以由多個(gè)結(jié)點(diǎn)擔(dān)任，一個(gè)結(jié)點(diǎn)也可以同時(shí)擔(dān)任多個(gè)角色（既是調(diào)度服務(wù)器又是調(diào)度成員）。2任務(wù)提交方式定義2用戶任務(wù)因子T是一個(gè)三元組（TT,TM,TC）。其中：任務(wù)類型TT(TaskType）：表示由用戶提交的任務(wù)的類型；任務(wù)提交方式TM(TasksubmittingManner）：表示用戶提交任務(wù)的方式；任務(wù)約束TC(TaskConstaints）：表示任務(wù)的結(jié)構(gòu)特征與求解性能要求。2.1靜態(tài)多媒體數(shù)據(jù)用戶提交的服務(wù)請(qǐng)求類型是多種多樣的，按照對(duì)處理器、網(wǎng)絡(luò)和I/O的資源要求，可以簡(jiǎn)單的將它們分為兩個(gè)不同類別，以便應(yīng)用不同的處理策略：(1）靜態(tài)請(qǐng)求：例如普通的文本、圖像等靜態(tài)多媒體數(shù)據(jù)，它們對(duì)處理器負(fù)載影響不大，造成的磁盤I/O負(fù)載與文檔的大小成正比，主要對(duì)網(wǎng)絡(luò)I/O造成壓力。(2）動(dòng)態(tài)請(qǐng)求：更為常見的請(qǐng)求常常需要結(jié)點(diǎn)進(jìn)行預(yù)處理，例如搜尋數(shù)據(jù)庫(kù)、壓縮解壓多媒體文件等，這些請(qǐng)求需要相當(dāng)大的處理器和磁盤I/O資源。2.2動(dòng)態(tài)遷移任務(wù)轉(zhuǎn)移在結(jié)點(diǎn)收到任務(wù)請(qǐng)求后，根據(jù)某種連接調(diào)度算法，將任務(wù)盡可能均勻地分配到各個(gè)結(jié)點(diǎn)，實(shí)現(xiàn)前期的負(fù)載平衡。但結(jié)點(diǎn)的負(fù)載往往無法通過單一的指標(biāo)（如連接數(shù)或響應(yīng)時(shí)間等）來靜態(tài)地確定，只有任務(wù)被結(jié)點(diǎn)執(zhí)行之后負(fù)載的大小才能實(shí)際地顯現(xiàn)出來，故上述的平衡往往是某種形式上的平衡，不能作為負(fù)載平衡的最終目標(biāo)，這就需要?jiǎng)討B(tài)地將某些結(jié)點(diǎn)（如負(fù)載較重的結(jié)點(diǎn)）上的任務(wù)轉(zhuǎn)移至另外一些結(jié)點(diǎn)（如負(fù)載較輕的結(jié)點(diǎn)）上去執(zhí)行，使各個(gè)結(jié)點(diǎn)的負(fù)載進(jìn)一步在實(shí)際環(huán)境中盡可能均勻。通過分析結(jié)點(diǎn)的實(shí)時(shí)負(fù)載信息，動(dòng)態(tài)地將任務(wù)在各結(jié)點(diǎn)之間進(jìn)行調(diào)整或轉(zhuǎn)移，如果結(jié)點(diǎn)可以接受任務(wù)，就將任務(wù)轉(zhuǎn)移到該結(jié)點(diǎn)，甚至可以將正在執(zhí)行的任務(wù)轉(zhuǎn)移到其他相對(duì)空閑的結(jié)點(diǎn)（此時(shí)稱為遷移）。該思路又分為搶占式和非搶占式兩類：(1）搶占式：轉(zhuǎn)移一個(gè)已經(jīng)部分執(zhí)行的任務(wù)，該操作的代價(jià)通常是非常昂貴的，因?yàn)槭占蝿?wù)的狀態(tài)信息非常困難。這些狀態(tài)信息包括：虛擬內(nèi)存的映像、進(jìn)程控制塊、I/O緩沖區(qū)、文件指針等。故搶占式任務(wù)遷移開銷較大。(2）非搶占式：進(jìn)行任務(wù)轉(zhuǎn)移時(shí)只針對(duì)還未執(zhí)行的任務(wù)，不涉及任務(wù)狀態(tài)信息的搜集、轉(zhuǎn)移。2.3子任務(wù)的分解分布并行計(jì)算任務(wù)一般分為兩種模式：一種是基本模式，即將一個(gè)大計(jì)算量的任務(wù)分解為一些相互獨(dú)立的子任務(wù)，在一組工作站上并行執(zhí)行，最后將子任務(wù)結(jié)果匯集為總的結(jié)果；另一種為協(xié)作模式，即在計(jì)算過程中，子任務(wù)間需要同步，交換中間結(jié)果，因而要求基本上同時(shí)開始，并以同樣速度執(zhí)行。3負(fù)載狀態(tài)的修正定義3負(fù)載評(píng)價(jià)因子L是一個(gè)五元組（LP,fl,LT,LS，α）。其中：負(fù)載參數(shù)LP(LoadParameter）：表示影響系統(tǒng)或工作站結(jié)點(diǎn)負(fù)載的因素；負(fù)載函數(shù)fl(LoadFunction）：表示系統(tǒng)或工作站結(jié)點(diǎn)負(fù)載大小的計(jì)算函數(shù)；負(fù)載閾值LT(LoadThreshold）：表示系統(tǒng)或工作站結(jié)點(diǎn)的負(fù)載閾值；負(fù)載狀態(tài)LS(LoadState）：表示系統(tǒng)或工作站結(jié)點(diǎn)的負(fù)載狀態(tài)；負(fù)載狀態(tài)修正因子α（loadstatemodifyingfactor）：表示調(diào)節(jié)系統(tǒng)或工作站結(jié)點(diǎn)的負(fù)載狀態(tài)的因子。設(shè)R為實(shí)數(shù)集，則它們滿足：L：(fl(LP）,LT）→LS。3.1負(fù)載指標(biāo)比較負(fù)載平衡調(diào)度工作的一個(gè)重要目標(biāo)是提高系統(tǒng)性能，縮短用戶任務(wù)的平均響應(yīng)時(shí)間。而一個(gè)作業(yè)的響應(yīng)時(shí)間依賴于其所運(yùn)行的主機(jī)上的負(fù)載。負(fù)載越重，其運(yùn)行時(shí)間越長(zhǎng)。因而，理想的負(fù)載指標(biāo)應(yīng)與作業(yè)響應(yīng)時(shí)間有一種單調(diào)關(guān)系。一個(gè)可以正確反映當(dāng)前系統(tǒng)負(fù)載情況的負(fù)載指標(biāo)對(duì)一個(gè)成功的動(dòng)態(tài)負(fù)載平衡系統(tǒng)來說至關(guān)重要。理想的、真正能夠體現(xiàn)系統(tǒng)負(fù)載情況的負(fù)載指標(biāo)應(yīng)當(dāng)滿足以下條件：(1）測(cè)量開銷低，這意味著可以頻繁測(cè)量以確保信息最新；(2）能體現(xiàn)所有競(jìng)爭(zhēng)資源上的負(fù)載；(3）各個(gè)負(fù)載指標(biāo)在測(cè)量及控制上相互獨(dú)立。Ferrari建議使用各種資源隊(duì)列長(zhǎng)度的線性組合作為負(fù)載指標(biāo)，但其條件是假定系統(tǒng)處于穩(wěn)定狀態(tài)，并且要求資源的排隊(duì)規(guī)則是FCFS。不過實(shí)際系統(tǒng)往往難以完全滿足這些條件。Zhou建議使用各種CPU隊(duì)列長(zhǎng)度作為負(fù)載指標(biāo)，他發(fā)現(xiàn)CPU隊(duì)列長(zhǎng)度和磁盤隊(duì)列長(zhǎng)度分別與CPU類作業(yè)和I/O類作業(yè)有密切關(guān)系，但資源隊(duì)列長(zhǎng)度與資源利用率并沒有緊密的關(guān)系。Bonomi等人使用處理機(jī)上活動(dòng)的進(jìn)程數(shù)的瞬時(shí)信息和周期搜集到的平均CPU運(yùn)行隊(duì)列等信息的組合作為負(fù)載指標(biāo)，并且進(jìn)行了實(shí)際測(cè)量，性能上有所改進(jìn)，但仍不能正確反映資源利用率。Kunz通過實(shí)驗(yàn)比較了運(yùn)行隊(duì)列任務(wù)數(shù)、系統(tǒng)調(diào)用的速率、CPU進(jìn)程切換率、CPU利用率、空閑內(nèi)存大小和1min內(nèi)負(fù)載平均值6個(gè)單項(xiàng)指標(biāo)，以及它們的”或”及”與”組合，發(fā)現(xiàn)其中效果最好的是單項(xiàng)指標(biāo)中的運(yùn)行隊(duì)列任務(wù)數(shù)，任何其它單項(xiàng)指標(biāo)或其組合都不比它好。綜上所述，影響負(fù)載的因素非常復(fù)雜，衡量分布式系統(tǒng)或工作站結(jié)點(diǎn)的負(fù)載的參數(shù)包括任務(wù)到達(dá)數(shù)、任務(wù)離開數(shù)、瞬時(shí)隊(duì)列長(zhǎng)度、平均隊(duì)列長(zhǎng)度、平均響應(yīng)時(shí)間、平均伸展系數(shù)（任務(wù)從到達(dá)到離開的時(shí)間與在此階段收到的服務(wù)時(shí)間之比）、CPU利用率、未完成的工作量、可用資源（如內(nèi)存等）情況、交付任務(wù)的要求等，分別用x1,x2,x3,x4,x5,x6,x7,x8,x9，…表示，則LP可表示如下：在上述這些參數(shù)中，有些信息是得不到或不準(zhǔn)確的。國(guó)際上現(xiàn)有的負(fù)載平衡系統(tǒng)多使用運(yùn)行隊(duì)列任務(wù)數(shù)作為負(fù)載指標(biāo)，因?yàn)樗容^容易獲得，而且它與多數(shù)作業(yè)響應(yīng)時(shí)間有密切的關(guān)系。為簡(jiǎn)單起見，大多數(shù)負(fù)載平衡系統(tǒng)將任務(wù)隊(duì)列中的任務(wù)數(shù)作為描述負(fù)載的唯一參數(shù)，事實(shí)上，如果采集過多參數(shù)，則會(huì)因增加額外開銷而得不到所希望的性能改善。3.2負(fù)載函數(shù)的描述負(fù)載函數(shù)fl:LP→R。將任務(wù)隊(duì)列中的任務(wù)數(shù)作為描述負(fù)載的唯一參數(shù)時(shí)，負(fù)載函數(shù)可以簡(jiǎn)單地描述成該式中，x表示系統(tǒng)或工作站結(jié)點(diǎn)，既可以是一臺(tái)計(jì)算機(jī)，也可以是一個(gè)分布式系統(tǒng)，函數(shù)TQ(x）表示x的任務(wù)隊(duì)列，|TQ(x）表示任務(wù)隊(duì)列TQ(x）中的任務(wù)數(shù)。3.3系統(tǒng)或工作站點(diǎn)負(fù)載狀態(tài)負(fù)載閾值LT是一個(gè)序偶<β1，β2>，其中，β1，β2∈R,0<β1≤β2。負(fù)載狀態(tài)集LS={‘NL’，‘LL’，‘SL’，‘HL’}，‘NL’、‘LL’、‘SL’、‘HL’分別表示空載（NullLoad）、輕載（LightLoad）、適載（SuitableLoad）和重載（HighLoad）。根據(jù)兩個(gè)閾值β1與β2，可以將系統(tǒng)或工作站結(jié)點(diǎn)的負(fù)載狀態(tài)劃分為空載、輕載、適載和重載等四種類型。用下列的函數(shù)表示：當(dāng)β1=β2時(shí)，表示只有一個(gè)負(fù)載閾值，此時(shí)負(fù)載狀態(tài)集不再設(shè)置適載狀態(tài)，往往將非重載稱為適載。3.4動(dòng)態(tài)調(diào)整負(fù)載閾值負(fù)載狀態(tài)修正因子α∈R用來修正負(fù)載閾值LT，表示參與調(diào)度的工作站結(jié)點(diǎn)的一種自主性，它可以根據(jù)環(huán)境負(fù)載情況動(dòng)態(tài)調(diào)整負(fù)載閾值，當(dāng)α≠0時(shí)，它表示一種自適應(yīng)負(fù)載平衡調(diào)度策略。設(shè)序偶集即Ω={<β1-α，β2-α>，<β1-α，β2>，<β1-α，β2+α>，<β1，β2-α>，<β1，β2>，<β1，β2+α>，<β1+α，β2-α>，<β1+α，β2>，<β1+α，β2+α>}，則LT∈Ω。4分布式調(diào)度環(huán)境定義4調(diào)度策略S是一個(gè)四元組（SD,ST,SF,SC）。其中：調(diào)度域SD(SchedulingDomain）：表示分布式網(wǎng)絡(luò)調(diào)度環(huán)境；調(diào)度類型ST(SchedulingType）：表示負(fù)載平衡調(diào)度策略的類型；調(diào)度構(gòu)架SF(SchedulingFramework）：表示調(diào)度策略的基本構(gòu)架；調(diào)度約束SC(SchedulingConstraint）：表示調(diào)度策略的約束條件。4.1網(wǎng)絡(luò)計(jì)算服務(wù)在分布式網(wǎng)絡(luò)環(huán)境中，對(duì)于用戶來說，參與負(fù)載平衡調(diào)度工作、為用戶提供網(wǎng)絡(luò)計(jì)算服務(wù)的工作站資源是透明的，通常情況下，為用戶提供服務(wù)的只是部分工作站資源，它們通過負(fù)載平衡策略共同為用戶提供網(wǎng)絡(luò)計(jì)算服務(wù)，以達(dá)到均衡資源、最短時(shí)間內(nèi)響應(yīng)用戶的目的。稱這部分工作站為調(diào)度域SD。4.2動(dòng)態(tài)負(fù)載平衡調(diào)度模型調(diào)度類型區(qū)分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度兩種。靜態(tài)負(fù)載平衡問題就是將任務(wù)均勻分配給各工作站，此時(shí)工作站的任務(wù)量、任務(wù)間的通信量都為定值，不隨時(shí)間變化。靜態(tài)負(fù)載平衡調(diào)度策略的優(yōu)點(diǎn)是可以得到最優(yōu)負(fù)載平衡結(jié)果，其缺點(diǎn)是在現(xiàn)實(shí)網(wǎng)絡(luò)環(huán)境中很難做到。另外，因?yàn)殪o態(tài)調(diào)度服務(wù)器需要掌握各工作站的實(shí)時(shí)負(fù)載變化情況，所以它適于處理工作站故障等異常情況，但隨著系統(tǒng)規(guī)模的增大，靜態(tài)負(fù)載平衡調(diào)度效率快速下降。動(dòng)態(tài)負(fù)載平衡通過分析系統(tǒng)的實(shí)時(shí)負(fù)載信息，動(dòng)態(tài)地將任務(wù)在各個(gè)結(jié)點(diǎn)之間進(jìn)行分配和調(diào)整以適應(yīng)實(shí)時(shí)分布式系統(tǒng)中負(fù)載分布的不均勻性，所以動(dòng)態(tài)負(fù)載平衡更能反映分布式系統(tǒng)的實(shí)際情況。但其缺點(diǎn)也十分明顯，動(dòng)態(tài)負(fù)載平衡調(diào)度結(jié)果只能得到部分的平衡，并且參與調(diào)度的系統(tǒng)也是局部的。另外，動(dòng)態(tài)調(diào)度策略通常忽略了工作站可能出現(xiàn)故障的情況，而在大規(guī)模分布式系統(tǒng)中，系統(tǒng)的不穩(wěn)定是難以避免的。此外，動(dòng)態(tài)負(fù)載平衡調(diào)度也往往忽略了任務(wù)之間的通信量，這樣在通信量較大的分布式系統(tǒng)中將增大整個(gè)系統(tǒng)的負(fù)載，進(jìn)而造成整個(gè)系統(tǒng)的不穩(wěn)定。按照負(fù)載平衡調(diào)度活動(dòng)的啟動(dòng)者劃分，動(dòng)態(tài)負(fù)載平衡調(diào)度可以分為發(fā)送者驅(qū)動(dòng)算法、接收者驅(qū)動(dòng)算法和雙向驅(qū)動(dòng)算法三種類型。在發(fā)送者驅(qū)動(dòng)算法中，當(dāng)一個(gè)結(jié)點(diǎn)超載時(shí)，它作為發(fā)送者嘗試將任務(wù)發(fā)送給一個(gè)輕載結(jié)點(diǎn)（接收者）。與發(fā)送者驅(qū)動(dòng)算法相反，接收者驅(qū)動(dòng)算法是當(dāng)一個(gè)結(jié)點(diǎn)的負(fù)載狀態(tài)變成輕載時(shí)，它作為接收者嘗試從重載結(jié)點(diǎn)接收一個(gè)任務(wù)。雙向驅(qū)動(dòng)算法兼有上述兩種算法的優(yōu)點(diǎn)，當(dāng)系統(tǒng)整體負(fù)載較輕時(shí)，調(diào)用發(fā)送者驅(qū)動(dòng)算法容易發(fā)現(xiàn)輕載結(jié)點(diǎn)；當(dāng)系統(tǒng)整體負(fù)載較重時(shí)，調(diào)用接收者驅(qū)動(dòng)算法則容易發(fā)現(xiàn)重載結(jié)點(diǎn)。它的不足在于，如果在系統(tǒng)負(fù)載較重時(shí)使用發(fā)送者驅(qū)動(dòng)算法容易造成系統(tǒng)不穩(wěn)定。一個(gè)較好的解決辦法是采用自適應(yīng)算法，合理設(shè)置閾值，及時(shí)掌握系統(tǒng)的負(fù)載狀態(tài)信息。根據(jù)靜態(tài)負(fù)載平衡調(diào)度與動(dòng)態(tài)負(fù)載平衡調(diào)度的這些特點(diǎn)，在文獻(xiàn)中提出了一種分層負(fù)載平衡調(diào)度模型。此模型是靜態(tài)調(diào)度與動(dòng)態(tài)調(diào)度的混合模型，也是一種通用模型，當(dāng)層次結(jié)構(gòu)自底向上縮為單層扁平結(jié)構(gòu)時(shí)，它退化為靜態(tài)調(diào)度模型，當(dāng)層次結(jié)構(gòu)自頂向下塌為單層扁平結(jié)構(gòu)時(shí)，它退化為動(dòng)態(tài)調(diào)度模型，如圖1所示。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的動(dòng)態(tài)調(diào)度與靜態(tài)調(diào)度相比，分層負(fù)載平衡調(diào)度系統(tǒng)具有較好的問題求解效率。4.3配置框架f調(diào)度構(gòu)架指負(fù)載平衡調(diào)度算法的四個(gè)組成部分：轉(zhuǎn)移策略、選擇策略、定位策略和信息策略，它們組成負(fù)載平衡調(diào)度活動(dòng)的整個(gè)生命周期。(1）閾值設(shè)置位置在調(diào)度活動(dòng)的生命周期中，轉(zhuǎn)移策略決定調(diào)度組中的結(jié)點(diǎn)是否處于合適的狀態(tài)來參與任務(wù)轉(zhuǎn)移工作，充當(dāng)任務(wù)轉(zhuǎn)移的發(fā)送者或者接收者角色。一種普遍認(rèn)可的轉(zhuǎn)移策略是閾值策略：參照3.3節(jié)，當(dāng)某結(jié)點(diǎn)完成一個(gè)任務(wù)使其負(fù)載小于閾值β1時(shí)，就將該結(jié)點(diǎn)確定為接收者；當(dāng)某結(jié)點(diǎn)從用戶或者其它結(jié)點(diǎn)接收新任務(wù)，使其負(fù)載大于閾值β2時(shí)，就將該結(jié)點(diǎn)確定為發(fā)送者。此時(shí)稱β1為接收閾值，β2是發(fā)送閾值。閾值設(shè)置要適當(dāng)，如果閾值設(shè)置過低，負(fù)載量被人為提高；如果閾值設(shè)置過高，結(jié)點(diǎn)事實(shí)上已經(jīng)支持過重的計(jì)算，但表面上仍顯得空閑。這種方法也稱絕對(duì)轉(zhuǎn)移策略，與之相對(duì)的為相對(duì)轉(zhuǎn)移策略，即在調(diào)度組中，確定相對(duì)于其它結(jié)點(diǎn)負(fù)載最輕的結(jié)點(diǎn)為接收者，相對(duì)于其它結(jié)點(diǎn)負(fù)載最重的結(jié)點(diǎn)為發(fā)送者。(2）選擇合適的轉(zhuǎn)移任務(wù)在調(diào)度活動(dòng)的生命周期中，選擇策略在轉(zhuǎn)移策略之后啟動(dòng)。一旦轉(zhuǎn)移策略確定了發(fā)送者之后，選擇策略負(fù)責(zé)從該結(jié)點(diǎn)選擇一個(gè)待轉(zhuǎn)移任務(wù)，如果選擇策略找不到合適的轉(zhuǎn)移任務(wù)，則該結(jié)點(diǎn)就不再被認(rèn)為是發(fā)送者。最簡(jiǎn)單的選擇策略方法是選擇導(dǎo)致該結(jié)點(diǎn)成為發(fā)送者的新任務(wù)作為轉(zhuǎn)移任務(wù)，此時(shí)任務(wù)轉(zhuǎn)移的開銷較小。選擇策略要考慮以下幾個(gè)因素：轉(zhuǎn)移的額外開銷盡量小，被選擇的任務(wù)應(yīng)該足夠大，以值得花去額外開銷。(3）共享負(fù)載的輪詢策略定位策略主要選擇待轉(zhuǎn)移任務(wù)的接收者。在靜態(tài)調(diào)度算法中，由調(diào)度服務(wù)器負(fù)責(zé)定位、收集系統(tǒng)信息，發(fā)送者從調(diào)度服務(wù)器獲得系統(tǒng)信息來確定接收者。在動(dòng)態(tài)調(diào)度算法中，一