基于計算機動態任務分配表的負載均衡新算法

方文英

杭州萬向職業技術學院,浙江杭州310023

基于計算機動態任務分配表的負載均衡新算法

方文英

杭州萬向職業技術學院,浙江杭州310023

隨著計算速度的飛速發展，并行計算系統中，任務調度是解決多任務多資源情況下的最有效辦法，但是目前常見的任務調度問題是一個NP-Hard問題，在任分配的負載均衡上還存在不足之處。本文通過改進并設計一個動態的負載均衡Work-stealing算法，來加強計算機集群動態任務分配過程中的效率，使得各個任務能夠有條不紊的進行，從而提高整個計算機系統的資源利用率和整體性能。

任務調度;負載均衡;動態任務分配表;work-stealing算法

1 計算機動態任務調度基本概念和算法

在云計算框架中，影響計算機性能的是任務的調度問題。經過大量研究者的研究表明，云計算或并行計算中的任務調度問題是公認的復雜度較大的NP-Hard問題。在眾多任務調度算法中，效果最好的是基于負載均衡的調度算法，負載均衡是提高并行計算性能和計算機系統資源利用率的關鍵技術[1]。在計算機任務調度與分配過程中，主要分為調度模型和調度算法兩個關鍵點。選擇好的模型與對應算法，可以更好的進行任務調度的負載均衡處理。

1.1 調度模型

常見的動態任務分配表的調度模型分為分布式和集中式任務調度模型。基于分布式原型設計出的動態任務分配管理器，并投入實際任務調度使用的模型系統有Yarn，Falkon，Gearman等系統[2]。以上三個調度模型能夠非常好的適應各種調度算法，以保證整個系統的負載均衡模式。其中，Gearman模型是目前最常用的一種調度模型，在該模型上的各種負載均衡算法都有很好的應用。

1.2 調度算法

目前，基于負載均衡的調度算法研究主要分為兩類[3]：(1)靜態漸變傳播和交流算法，通過相連節點不斷均衡達到整個系統負載均衡；(2)動態負載均衡共享算法，通過隨機選擇多個節點進行均衡以達到最后的負載均衡，不強調節點相連。

本文主要針對目前較為常見的動態負載均衡算法進行研究，如今研究較多的動態負載均衡算法包括，隨機算法、輪詢算法、最小負載優先算法以及任務竊取算法等。本文著重分析Work-stealing任務竊取算法。

2 Work-stealing任務竊取算法

2.1 Work-stealing算法基本過程

Work-stealing[4]算法通過基于任務竊取的方式進行整體系統的負載均衡。該算法的竊取策略通過一種范式的方式均衡分配任務量，能夠及時發現沒有充分利用資源的計算節點，并從另一些處于繁忙計算的節點中解放一些任務給空閑狀態中的計算節點使用，從整體架構上看，這樣的策略可以使系統任務負載均衡。

Work-stealing算法中每個處理器都擁有一個雙端隊列，且可以看成是一個調用棧，從底部插入就緒空閑狀態的線程，等到其他處理器竊取任務的時候，從頂端刪除該線程。可以將該隊列命名為任務調度竊取棧，如圖1所示。

圖1 任務調度竊取棧Fig.1 Task scheduling steal stack

當Work工作端發現負載不均衡的時候，將調用Work-stealing算法完成任務的竊取，將竊取到的任務從竊取棧中彈出，給竊取端使用。基本過程包括：

(1)發現負載不均衡并想要竊取任務的服務器被設置成一個竊取端。

(2)當待竊取端請求中心任務調度器需要竊取任務，中心調度器發來可以被竊取的處理器的相關信息，竊取端首先查詢每個處理器管理的竊取棧，若棧非空，那么取出棧頂元素作為竊取的服務器。

(3)若竊取棧為空，竊取端則會嘗試隨機選擇另一個處理機進行竊取。通過不斷的迭代尋找，直到尋找到可以竊取對應任務的處理機，然后訪問該處理機并竊取處理不完的任務放進自己的任務隊列中，根據隊列規則依次執行任務。

2.2 Work-stealing算法三種竊取任務數量策略

任務數量選擇策略上，傳統的Work-stealing算法提供了三種不錯的計算策略，分別是加法級數策略、乘法級數策略和二分法級數策略。

(1)加法級數策略：當需要確定竊取任務的數量的時候，采取加法級數的策略分析當前所需要的任務數，隨著不斷改變處理機，任務數隨著加法級數增加。

(2)乘法級數策略：當需要確定竊取任務的數量的時候，采取乘法級數的策略分析當前所需要的任務數，隨著不斷改變處理機，任務數隨著乘法級數增加。

(3)二分法級數策略：當需要確定竊取任務的數量的時候，首先統計獲得的處理機的總隊列任務，然后選擇處理總隊列中的一半任務。

三種算法策略適用于不同的場合，以下是各種策略的對比表格，如表1所示。

表1 三種竊取任務數量策略比較Table 1 Comparison among three steeling tasks

2.3 Work-stealing算法兩種竊取任務時機策略

Work-stealing算法在竊取時機選擇策略主要有兩種，主要包括節點空閑時的任務竊取和節點快要空閑時的任務竊取策略。

2.3.1 節點空閑的時候進行任務竊取當需要進行任務竊取的時候，處理機首先向中心任務調度服務器提出竊取任務請求。中心任務調度服務器查詢各個處理機的當前狀態，并返回處于滿負荷狀態下的處理機，這樣需要執行竊取的處理機就可以進行竊取操作，改善那些處于滿負荷狀態下的處理機。

2.3.2 節點快要空閑的時候進行任務竊取某節點在就緒隊列中正在執行任務，但是該任務快要執行完成了，這時候進行任務竊取的請求。同時，請求過程也與節點空閑時候進行任務竊取的過程相同。

實際情況下，以上兩種策略各有優缺點，視具體情況選擇不同的算法策略。

3 改進的Work-stealing任務竊取算法

上文中介紹了傳統Work-stealing任務竊取算法使用的竊取任務數量和竊取任務時機策略，這些策略能夠很好的解決并行計算系統中的負載均衡問題。但是，到目前為止，該算法的所有策略研究都僅限于靜態的某幾個單一策略的組合，不能夠很好的體現并行系統的時序性。

本文的改進策略是根據設定竊取時機的不同，每當需要進行任務竊取的時候，就開始啟動Work-stealing算法，并選擇相應的可以進行竊取的處理機，并在該處理機上執行竊取任務的操作。本文將負載最大的處理機作為備選的待竊取任務處理機，本文改進的算法是最大負載優先竊取算法。

3.1 改進算法流程

過竊取時機的確定，本文將需要竊取任務的處理機設置為“竊取機”，當被設置為“竊取機”之后，竊取機向任務調度中心服務器請求任務竊取，服務器首先會執行動態的負載均衡算法進行選擇，挑選出目前負載最大的或者次大的等多個候選處理機作為“候選機”，候選機的選擇如下：

(1)任務調度中心服務器輪詢現有隊列中的各個處理機狀態，通過計算每個處理機的最大任務隊列的長度，比較選出結果最大的處理機，將該處理機作為候選機，然后將竊取機相關信息通過進程間通信返回給竊取機。

(2)通過上步中的竊取機信息進行任務的竊取。由于進程間通信的延遲緣故，在竊取機接收到候選機的進程號的時候，該進程的具體信息需要延遲一段時間才能傳播過來，這時候竊取機對其進行簡單的預竊取工作。對于竊取任務的數量，本文則根據當前傳播過來的候選機的任務數量做出最終決定，從候選機的就緒任務隊列中彈出目前需要的任務數量，直到被竊取的任務數量達到為止。任務竊取成功，轉(3)，否則，轉(4)。

(3)當前任務竊取已經成功，這時候需要動態更新目前保存在任務調度中心服務器的各個處理機的負載情況。

(4)當前任務竊取失敗，說明了所有處理機的任務都已經完成了，目前不存在可以進行竊取的任務了。

(5)竊取機從候選機中竊取到了相應數量的任務，并執行這些任務。

(6)算法結束，系統中目前的任務全部執行完成。

3.2 改進算法流程

本文改進的算法是最大負載優先的Work-stealing任務竊取算法。概算能夠根據當前各個處理機的任務量的多少來決定如何分配竊取任務。根據3.1節中提到的算法步驟可以得到本文算法的流程圖，如圖2所示。

圖2 本文改進算法流程圖Fig.2 Flow chart of the improved algorithm in this paper

其中，竊取時機調度算法細節如圖3所示。在處理機需要竊取多少任務的數量確定流程上，如圖4所示。

圖3 竊取時機調度算法流程圖Fig.3 Flow chart of Scheduling algorithm for stealing time

圖4 竊取任務數量流程圖Fig.4 Flow chart of stealing tasks

3.3 改進算法與傳統Work-stealing算法實驗對比

本文通過搭建一個原型系統測試本文改進算法與傳統Work-stealing算法。在原型系統中創建了10臺服務端，每個服務端最高負載量為10個任務。在傳統算法中，分別對三種竊取任務數量策略和兩種竊取任務時機策略進行實驗驗證。驗證結果如下表2所示。

表2 傳統算法與改進算法比較Table 2 Comparison between the traditional and improved algorithms

從上表中可以看出，本文改進算法的優勢在于，由于是通過動態不斷改變竊取任務量的，所以本文算法的任務量較為平均，負載較為均衡。另外，本文算法能夠快速確定竊取任務數量和時機，時間復雜度低。

4 結論

本文通過簡要分析和介紹常見的任務調度模型和任務竊取算法，著重分析了Work-stealing算法竊取策略。通過最大負載優先策略對傳統Work-stealing進行改進，不但改善了傳統算法在動態實時變化系統中的不足之處，而且通過快速選擇竊取任務數量和竊取任務時機，改進算法的時間復雜度低，有較強的實時負載均衡能力。

[1]Wickremasinghe B,Calheiros RN,Buyya R.Cloudanalyst:A cloudSim-based visual modeller for analyzing cloud computing environments and applications[C]//24th IEEE International Conference onAdvanced Information NetworkingApplications.Australia:IEEE,2010:446-452

[2]Casanova H,Dongarra J.Net Solve:A network server for solving computational science problems[J].International Journal of SuppercomputerApplications and High Performance Computing,1997,11(3):212-223

[3]Zhao Y,Raicu I,Foster I,et al.Realizing fast,scalable and reliable scientific computations in grid environments[M]//Gird computingresearchprogress.NewYork:Novapublisher,2008

[4]Blumofe RD,Leiserson CE.Scheduling multi-threaded computations by work stealing[J].JACM,1999,46(5):720-748

An Improved Algorithm for Load Balance Based on the Dynamic Task Scheduling List of Computer System

FANG Wen-ying
Hangzhou Wanxiang Polytechnic,Hangzhou 310023,China

With the development of computer science,the task scheduling method is the most efficient method for managing multitask and resources in a parallel computing system,but the problem of how to schedule tasks is a NP-Hard problem,the balance of scheduling has some shortcomings.In this article,we designed an improved dynamic task scheduling work-stealing method to strengthen the efficient of task scheduling in computers cluster and make a balance among all tasks so as to improve the resource use ratio and performance of whole computer system.

Task scheduling;load balance;dynamic task scheduling list;work-stealing algorithm

TP391

A

1000-2324(2015)05-0779-04

2014-08-20

2014-09-04

方文英(1976-),女,浙江杭州人,本科,講師,主要研究方向為計算機應用.E-mail:136520276@qq.com