隨着大規模並行分佈處理系統，特別是網絡工作站集群的廣泛應用。如何採取有效的調度策略來平衡各節點的負載，從而提高整個系統資源的利用率，已成為人們的研究熱點。集群具有可擴展性、 高可用性、高性能、高性價比等優點，作為存儲區域網的存儲設備具有天生的優勢。隨着PC機的發展，硬盤的價格越來越低，其存儲容量越來越大，每台PC機也可配置多塊硬盤，且可擴充能力極高，作為集群中的節點管理也相當方便，並具有一定的計算能力。如何採取有效的調度策略來平衡各節點的負載，從而提高整個系統資源的利用率，成為研究的重點。

1 負載均衡的目標

1. 要保持所有處理機處於忙碌狀態，而不是保證他們平分負載
2. 提供最短的平均任務響應時間
3. 具有一定的自適應性，能適於變化的負載
4. 是可靠的，避免負載的輕重跳躍，避免處理機抖動，減少不必要的通訊開銷

2 影響分佈式系統性能的因素

主要有這些因素影響着分佈式系統的性能：網絡延遲、數據通信效能、CU處理能力、任務的分割、無法預算處理時間、任務的顛簸等等。我們在尋求分佈式計算調度算法時，就是有針對性的以解決這些問題為目的，從各個角度，不同側面，利用一種或者集中方法結合起來的形式，從而達到最優解，使得系統效率相對最高。

3 幾種基本的調度算法

獲得網絡負載均衡有幾個基本的方法，這些方法可以結合使用，形成更高級的算法，以下是幾種基本的方法：

3.1 輪轉法

輪轉算法是所有算法中最簡單也最容易實現的一種方法，輪轉法簡單地在一串節點中線性輪轉，平衡器將新請求發給節點表中的下一個節點。如此連續下去。這個算法在DNS域名輪詢中被廣泛使用。但是簡單應用輪轉法DNS轉換，可能造成持續訪問同一節點，從而干擾正常的網絡負載平衡，使網絡平衡系統無法高效工作。輪轉法典型適用於集群中所有節點的處理能力和性能均相同的情況，在實際應用中，一般將它與其他簡單方法聯合使用時比較有效。

3.2 加權法

加權算法根據節點的優先級或權值來分配負載。權值是基於各節點能力的假設或估計值。加權方法只能與其它方法結合使用，是它們一個很好的補充。

3.3 散列法

散列法也叫哈希法（Hash），通過單射不可逆的Hash函數，按照某種規則將網絡請求發往集群節點。與簡單加權法相似。

3.4 最少連接法

針對TCP連接進行在最少連接法中，管理節點記錄目前所有活躍連接，把下一個新的請求發給當前含有最少連接數的節點。缺陷是某些應用層會話要消耗更多的系統資源，儘管集群中連接數平衡了，但是處理量可能差別很大，連接數無法反映出真實的應用負載。

3.5 最低缺失法

在最低缺失法中，管理節點長期記錄到各節點的請求情況，把下個請求發給歷史上處理請求最少的節點。與最少連接法不同的是，最低缺失記錄過去的連接數而不是當前的連接數。

3.6 最快響應法

管理節點記錄自身到每一個集群節點的網絡響應時間，並將下一個到達的連接請求分配給響應時間最短的節點。在大多數基於LAN的集群中，最快響應算法工作的並不是很好，大多數與以太網連接的現代系統，有部分負載時，可在1ms或更短時間內響應，這使得這種方法沒有意義。

4 幾種高級的調度算法

4.1 基於遺傳算法的分佈式任務調度策略

1. 符號串表示
   符號串表示必須能夠唯一地表示搜索空間中的所有搜索節點。對於多處理器調度問題，一個有效的調度必須滿足下列條件：（一）調度任務之間的先後關係；（二）完整性和唯一性條件（每一個任務都在調度中出現且出現一次）。監控任務表是滿足這種條件的可行方法，每個表對應於一個處理器上運行的監控任務子集。一個調度的描述如下圖所示。

1. 起始群體
   在遺傳算法的每一次迭代中，必須維持一個符號串的群體。起始的符號串群體通常是隨機生成的。假定以下條件：在調度中每個處理器上的任務都按高度升序排列於表中。這樣可以保證低高度的任務優先執行，保證算法的有效性。有時高度排序條件並不是充分條件，在此前提下，高度的定義被修正以減小這種情況出現的可能性。
2. 適應度函數
   對於MSP，適應度函數需要考慮吞吐量、完成時間以及處理器的使用等因素。而對上面問題，適應度函數僅取決於調度的完成時間。一個調度完成時間定義為任務圖中所有任務執行完成所用的時間，這個使時間最小的調度就是最優調度。
3. 遺傳操作
   （一）交叉如果交叉截點的選取使得每個交叉截點兩側任務的高度都是不同的，並且交叉截點前面最近任務的高度都是一樣的，則新生成的符號串一定有效。（二）繁殖繁殖操作通過從舊的群體中選取適應度值最大的符號串來構成新的群體。選取的準則為：具有較高適應度值的符號串應有較多的機會在下一代中存活。這是因為「好的」的符號串具有較高的適應度值並應被保留到下一代。（三）突變對於MSP，突變由隨機變換兩個高度相同的任務來實現突變算法如下：1、隨機選取一個任務T1；2、比較高度，找出符號串中高度相同的任務T2；3、交換任務，通過在調度中交換任務T1和T2來生成一個新的符號串；4、突變操作用突變概率來控制，這一算法在一個符號串上使用突變操作以生成一個新的符號串。（5）完整的遺傳算法問題求解的完整遺傳算法如下：Genetic-Algorithm（）{調用調度生成算法N次並將生成的符號串存入Group；Do{計算Group中每個符號串的適應度值；調用繁殖算法；令BESTSIRING為Group中適應值最大的符號串；For（i=1 ; i<=GroupNum/2; i++）{從Group中取出兩個符號串並以概率P¬1調用交叉操作；if（交叉操作發生）將生成的符號串加入Temp；else將原符號串加入Temp；}對Temp中的每一個符號串，以概率P2調用突變算法；if（突變操作發生）將新生成的符號串加入NewGroup；else將原符號串加入NewGroup；用BESTSIRNG取代Group中適應度值最小的符號串；}while（算法尚未滿足收斂準則）；}

4.2 蟻群算法求解分佈式系統任務分配問題

1. 基本蟻群算法
   Dorigo

   首先提出了蟻群算法。蟻群算法是模仿真實的蟻群行為而提出的一種模擬進化算法。螞蟻個體之間是通過一種稱之為信息素的物質進行信息傳遞，從而能相互協作，完成複雜的任務。螞蟻在運動過程中，能夠在它所經過的路徑上留下信息素，而且螞蟻在運動過程中能夠感知這種物質的存在及其強度，並以此指導自己的運動方向，螞蟻傾向於朝着該物質強度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現出一種信息正反饋現象：某一路徑上走過的螞蟻越多，則後來者選擇該路徑的概率就越大。螞蟻個體之間就是通過這種信息素的交流，搜索到一條從蟻巢到食物源的可能的較短路徑。蟻群算法的步驟可簡要地表述為：①設置所有參數，信息素痕迹初始化；②每隻螞蟻根據狀態轉移規則建立一個完整的解，狀態轉移規則主要取決於信息素和啟發式信息；③更新信息素。這3 個過程重複直到滿足終止條件。

2. 蟻群算法求解任務分配問題
   在用於任務分配問題求解的蟻群算法中，每一個人工螞蟻是具有下述特性的智能體：當它選擇把任務指派給處理器時，它會在連接上留下一種稱為痕迹的物質(等價於信息素)；它以一定的概率為一指定任務選擇處理器，該概率為在連接, 上的啟發式信息和的痕迹量的函數；在構造一個完整的解時，已經被處理的任務被加以禁止，所有分配到處理器的任務的KOP需求如果超過該處理器的能力限制，則該處理器也被禁止，如此重複直到所有的任務都已被處理器處理為止。該啟發式算法使用由只螞蟻組成的群體來一步步地進行解的構造。每隻螞蟻代表建立解的一個獨立過程，這個過程分兩步來完成：①螞蟻選擇將要被分配的任務；②對每個已經選擇的任務，分配處理器執行它。若干螞蟻過程之間通過信息素值來交換信息，合作求解並不斷優化。所有任務均被處理器處理完意味着螞蟻建立解過程的結束。

4.3 一種自適應的分佈式調度策略

1. 總體結構圖
   系統結構如圖1所示，前端的共享介質型集線器(前端HUB)作為集群的單一入口點，藉助於集線器的共享介質特徵，使得所有房間集群的數據包都能被內部節點的同構網卡接收並傳往它們各自的數據鏈路層。集群內部所有服務節點都配備兩塊網卡，上端網卡綁定一個對外的公共IP地址(VIP)，以實現集群的單一IP映像；每個下端網卡配備一個內部1P地址，負責和集群管理控制台進行交互和發送數據包到外部網關。控制台節點機負責管理和監視各個服務節點的工作狀態。
2. 調度原理
   該系統的調度原理如圖2所示。其基本思想是在連接請求建立的初期，根據各個Server節點負載狀況對TCP連接的第二次握手信號進行一定的延時，使得當前負載最輕的節點總是最

先響應客戶端的連接請求。通常根據連接請求內容和服務類型的不同，各個Server節點的工作負載往往表現出不均衡性，而且這種不均衡性是難以避免的，也是隨時間不斷變化的。本策略正是利用這種不均衡性，根據負載的動態變化來自動進行調度，在各個Server節點間達到一種自適應的平衡。而且不需要節點間相互通訊，因此實現簡單，開銷更小。

其工作原理描述如下:

1. t1時刻，客戶端訪間集群服務器，給VIP發SYN請求，準備建立連接；
2. SYN包到達前端HUB後，以廣播的形式發送到各個Server節點的同構網卡；
3. 駐留在各個Server上的調度處理模塊收到SYN請求後，根據自身的負載情況(由負載收集模塊給出)對該請求進行一定的延時.負載中的Server節點延時大，負載輕的Server節點延時小，使得負載較輕的Server節點先發第二次握手信號(即SYN十ACK包)。如在LoadA<LoadB的情況下DelayA<DelayB，於是A的回應先發出；
4. t2時刻，Load較小的ServerA節點的應答信息達到客戶端，於是客戶端給VIP發送第三次握手信號；
5. t3時刻，Load較大的ServerB節點的應答信息到達客戶端，由於t3>t2，客戶端已經收到A的應答，TCP協議棧會自動丟棄B的應答；
6. 第三次握手信號經由前端HUB到達各個Server節點，包過濾模塊檢查該應答信號的ACK序列號是否與自身的初始序列號一致，即判斷NACK和(NISN+1)是否相等，如果相等，則允許通過；否則向上層TCP協議棧發送一個RST數據包以撤銷該連接。圖示中ServerA將建立起連接，ServerB
   將撤銷連接，從而選擇當前負載較輕的ServerA為新來的請求服務。