分布式系統負載平衡調度模型研究

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