基于計算機動態(tài)任務分配表的負載均衡新算法

摘? 要：計算機技術飛速發(fā)展的今天，在并行計算機系統之中，任務調度依舊是解決多資源配置的最有效方法之一，但是當前的任務調度依然存在著一些困境，其中的一個難題是NP-Hard問題，即和任務負載均衡相關的分配方法還存在調度方面的問題。該文提出了一個新的負載均衡的動態(tài)Work-Stealing新算法，通過這個新算法可以加強動態(tài)計算機集群之中任務分配的效率，幫助各種任務進行得更加順暢，以此幫助整個計算機系統提升資源的利用效率，并提升計算機系統的整體性能。該文首先對常見的任務調度模型進行分析，分析了任務調取算法的計算機制，著重對工作竊取算法的計算策略進行探討，通過快速地選擇竊取的時機和竊取的工作任務數量，可以實現復雜維度的算法，提升負載的實際均衡能力。

關鍵詞：任務分配? 負載均衡? Work-Stealing算法

中圖分類號：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1672-3791（2019）04（b）-0013-02

1? 和任務調度的動態(tài)化相關的概念

動態(tài)調度相關問題對于計算機的性能產生非常大的影響，特別是在云計算的框架之中。大量的學者在這個領域投入了研發(fā)，他們的研究結果表明，在并行計算和云計算的任務當中，進行調度和分配的時候，會遇到一些負載的問題，其中很多問題甚至屬于復雜的NP-Hard問題。負載均衡的算法和任務調度的算法有很大的關聯性，效果也是比較好的。負載均衡是一種提升并行計算之中計算機資源利用效率的最重要的技術。在對計算機資源進行調度和對計算任務進行分配的過程中，最關鍵的技術領域則是調度算法和調度模型。選擇最為恰當的調度模型和調度算法進行搭配，可以最大程度地實現任務調度的負載均衡處置。

1.1 調度模型

分布式模型和集中式模型是動態(tài)任務調度分配表中最為常見的兩種，動態(tài)任務管理器是在分布式原理的基礎上設計出來的，在實際調度操作的實收，投入到應用之中的調度方法有Gearman、Falkon等方法，這些方法都有很多的實際應用的例子。上述幾種調度模型均可以與其對應的基礎調度算法互相之間達到調和的效果，以此來保證系統運行方面的負載可以達到均衡，在這之中，尤其突出的是名為Gearman的調度模式。和這種模型有關的負載均衡運算可以得到良好的運用。

1.2 調度算法

和負載均衡有關的調度算法可以分為兩個大類：第一，靜態(tài)漸變的交流算法動態(tài)的傳播模式，動態(tài)的模式和靜態(tài)漸變的模式有細微的差異，突出表現在互相連接的節(jié)點方面，這些節(jié)點之間大都是運用均衡的方法實現系統負載的均衡。第二，動態(tài)共享均衡和均衡算法之間也有不同，常見的方法是通過幾個隨機分布的動態(tài)節(jié)點之間的均衡實現良好狀態(tài)的最終效果的動態(tài)負載均衡，為了達到這種狀態(tài)，各個負載節(jié)點之間通常不是鏈接緊密的。該文所研究的主要是動態(tài)均衡算法，現階段學術界議論比較多的是隨機輪訓算法、負載均衡算法、任務竊取算法等，任務竊取算法就是Work-Stealing算法。

2? 任務竊取算法

2.1 實現任務竊取有關的過程

任務竊取算法的實現基礎是在任務竊取的基礎方法之中，實現整個系統的負載均衡。任務竊取算法所要實現的價值，是均衡的任務分配，在進行任務分配的負載均衡的過程中，激發(fā)一些沒有被利用的空閑節(jié)點，從而使得一些并非處于繁忙工作狀態(tài)的節(jié)點可以解放出來部分空間，給那些空閑節(jié)點分配過去。從這種任務架構的內容上看，上述策略最終實現了任務之間的負載均衡。在進行任務截取的過程當中，相同的處理器之間可能有一些同樣的雙端隊列，通過這些隊列可以實現調用棧的隨機調用，可以嘗試在這些棧的底部插入部分棧程，如果遇到這樣的棧程，在任務竊取器工作的時候，底端的棧程就可以實現恢復，然后進行刪除，這樣隊列就會被認定為一個任務調度相關的棧。

當工作端發(fā)現負載出現不均的情況之時，需要運用任務竊取算法進行任務的竊取，并將竊取到的任務從竊取的棧之中彈出，將該棧給竊取端使用。這個步驟的基本操作為：第一，一個負載不均衡的服務器被設置為竊取端，并且設置其為想要竊取任務。第二，等待竊取請求的竊取端服務器等待接收竊取任務，等待中心調度器發(fā)來的可以竊取調度任務的信息，竊取端根據任務處理器發(fā)過來的信息詢問每一個處理器所控制的竊取棧，如果這個棧不是空的，那么就設置竊取棧之中的元素當作竊取的服務器。第三，如果竊取的棧是空的，竊取端就會隨機選擇另外一個處理器進行竊取，經過不斷地尋找迭代，最終選到可以竊取任務的處理器，之后對該處理器進行訪問，處理機所竊取的任務就會自動地加入到自身的隊列任務之中，任務隊列之間就可以隨機地完成分配的任務。

2.2 任務竊取算法的任務數量策略

在任務數量的選擇策略方面，傳統的任務竊取算法有3種進行數量計算的策略可供選擇，分別是乘數級別算法。二分法級數算法以及加法級數算法。第一，乘數級別算法。當已經明確竊取任務的數量的時候，乘數級別的算法對當前進行策略分析相關的任務數進行計算，對處理機不斷進行改變，任務的數量會呈現出乘數級別的增長。第二，二分級數方法。如果需要竊取的任務數量是特定的，遇到緊急的情況需要根據隊列統計的任務獲取處理機的工作量，對工作量進行簡單的計算，之后選擇總處理隊列之中的1/2的任務。第三，加法級數的方法。當確定需要竊取的任務數量之后，采用加法級數的策略會針對當前正在執(zhí)行的工作進行分析，隨后會根據加法技術的改變對任務機進行處理，所處理的任務數量根據加法級數逐步增加。上述3種方法在不同的場合均有所使用。

2.3 工作竊取算法的時機選擇

工作竊取算法在竊取的時間的選擇特點方面可以歸納成兩種策略分類，即對于空閑節(jié)點的竊取和對即將處于閑置狀態(tài)的節(jié)點的竊取。

2.3.1 與空閑節(jié)點有關的竊取

如果遇到和任務竊取相關的任務，第一步是服務器向處理機發(fā)出指令，命令任務機開始執(zhí)行任務竊取的動作，任務調度中心首先提出任務竊取的請求。和中心調度有關的服務器就會開始對各種機器的狀態(tài)進行調查，根據運行狀態(tài)下的機器的動態(tài)，給服務器反饋信息。這樣就選擇出了可以進行任務處理的處理機，任務竊取的處理機就可以進行任務的操作，實現任務的竊取。還有一些處于滿負荷運行狀態(tài)的任務處理機的工作狀態(tài)就會有所改變。

2.3.2 和空閑節(jié)點有關的任務竊取

如果某個正在執(zhí)行任務的節(jié)點執(zhí)行完了整個任務，這個時候就會接收到任務處理的請求，那么任務處理過程當中的空閑節(jié)點就會進行任務回程。

在實踐中運用的情況是，上述兩種選擇的策略都既有優(yōu)點又有缺點，還是會根據不同的算法對任務執(zhí)行的策略有所選擇。

3? 改進型Work-Stealing算法

之前已經論述過的工作竊取算法只是停留在比較原始的階段當中，與任務竊取算法有關的任務數量和任務的策略一般是比較傳統的類型，盡管這些策略在執(zhí)行方面已經有可能實現負載均衡的部分問題，但是到目前為止，很多算法的研究依然停留在與策略組合有關的階段，均是進行靜態(tài)的研究，這樣就無法實現和并行計算相關的時序性要求。

3.1 相關算法的流程

該文所研究的竊取算法的第一步需要確定一個處理機，同時將其稱為竊取機，竊取機在工作的時候，通過竊取所獲得的任務調度中心的請求不一樣，服務器主動根據負載的情況，將負載的運算結果報告給主機，服務器會根據負載的不同做出選擇，根據負載最優(yōu)的那個實現負載均衡。候選機的選擇有如下幾個步驟。

第一，任務調度中心對服務器之中已經開始進行輪候的各個處理機的狀態(tài)進行問詢，了解每一個可以處理的任務的最大隊列可能性，通過對隊列任務進行比較選擇一個最為適當的處理機種類，將這種類型的處理機中的一個選擇為輪候的處理機，在此之后將竊取的相關信息通過進程信息系統反饋給竊取機。

第二，經過上述步驟之后，竊取機可以收獲任務的授權，在處于進程之中的任務機器進行選擇，對于任務進程的調度而言有可能出現延遲的問題，如果竊取的任務和獲取信號的強弱有關，這些進程的信息獲取會在經過一定的時點時有適當延遲，經過一段時間之后才能夠轉播出現。竊取機會進行簡單的選擇操作，根據竊取的任務的數量進行分配選擇確定完成之后，到被竊取的數量最終達到最大的數量級別為止。

3.2 如何對算法進行改進

在筆者的研究過程中，改進型算法一般都是和工作竊取方法的任務匹配相關的，根據任務機的實際巡行狀態(tài)，可以對任務實現合理分配，上文論述過分配的步驟如何實現，和該文的流程處理有關聯。

竊取時機的算法細節(jié)為：第一步遍歷所有的處理機，選取數個初始化的處理機，將其設置為竊取處理機。在任務流程方面，第一步開始計算待竊取的任務數量，第二步對這些任務實現竊取并開始執(zhí)行。

3.3 實驗數據方面的對比

通過搭建原型系統對改進型工作竊取算法的實驗表明，原型系統當中的十天服務器客戶端，實現的任務負載最高紀錄為10臺，實現的負載任務量為10個，與傳統的計算方法相比，在傳統的計算方法當中，有3種和任務竊取密切關聯的任務組合策略，3種任務組合策略和2種隨機組合策略都有實驗對照組。對比的結果發(fā)現，改進型算法的優(yōu)勢特別大，其優(yōu)異表現在，可以進行不斷的動態(tài)改變，使得可以獲得的動態(tài)竊取的任務數量出現變動，和該文有關的動態(tài)竊取平衡算法實現了動態(tài)的均衡，負載的方面非常均衡，和該文研究有關的竊取數量和時機的選擇不算復雜。

4? 結語

計算機科學技術的飛速發(fā)展要求在并行計算的信息系統當中，通過任務調度的方法實現資源的有效配置，但是目前的技術在任務的均衡分配方面還存有不足。該文通過改進和設計一種動態(tài)均衡的工作竊取算法，實現任務分配的效率。該文通過對日常比較常見的竊取算法和任務調度模型進行分析，著重分析了任務竊取算法的工作策略，通過最大負載優(yōu)勢的傳統工作竊取算法的改進，可以完善這種算法對于動態(tài)變化系統的數據處理的改進要求，實現較強的實時均衡負載。

參考文獻

[1] 李坤.基于動態(tài)反饋機制的服務器負載均衡算法研究[J].電子科技，2015，28（9）：45-49.

[2] 向建軍，白欣，左繼章.一種用于實時集群的多任務負載均衡算法[J].計算機工程，2003（12）：36-38.

①作者簡介：王濤（1996，2—），男，漢族，湖北黃岡人，本科，研究方向：計算機科學與技術。