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

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

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