方文英

杭州萬(wàn)向職業(yè)技術(shù)學(xué)院,浙江杭州310023

基于計(jì)算機(jī)動(dòng)態(tài)任務(wù)分配表的負(fù)載均衡新算法

方文英

杭州萬(wàn)向職業(yè)技術(shù)學(xué)院,浙江杭州310023

隨著計(jì)算速度的飛速發(fā)展，并行計(jì)算系統(tǒng)中，任務(wù)調(diào)度是解決多任務(wù)多資源情況下的最有效辦法，但是目前常見(jiàn)的任務(wù)調(diào)度問(wèn)題是一個(gè)NP-Hard問(wèn)題，在任分配的負(fù)載均衡上還存在不足之處。本文通過(guò)改進(jìn)并設(shè)計(jì)一個(gè)動(dòng)態(tài)的負(fù)載均衡Work-stealing算法，來(lái)加強(qiáng)計(jì)算機(jī)集群動(dòng)態(tài)任務(wù)分配過(guò)程中的效率，使得各個(gè)任務(wù)能夠有條不紊的進(jìn)行，從而提高整個(gè)計(jì)算機(jī)系統(tǒng)的資源利用率和整體性能。

任務(wù)調(diào)度;負(fù)載均衡;動(dòng)態(tài)任務(wù)分配表;work-stealing算法

1 計(jì)算機(jī)動(dòng)態(tài)任務(wù)調(diào)度基本概念和算法

在云計(jì)算框架中，影響計(jì)算機(jī)性能的是任務(wù)的調(diào)度問(wèn)題。經(jīng)過(guò)大量研究者的研究表明，云計(jì)算或并行計(jì)算中的任務(wù)調(diào)度問(wèn)題是公認(rèn)的復(fù)雜度較大的NP-Hard問(wèn)題。在眾多任務(wù)調(diào)度算法中，效果最好的是基于負(fù)載均衡的調(diào)度算法，負(fù)載均衡是提高并行計(jì)算性能和計(jì)算機(jī)系統(tǒng)資源利用率的關(guān)鍵技術(shù)[1]。在計(jì)算機(jī)任務(wù)調(diào)度與分配過(guò)程中，主要分為調(diào)度模型和調(diào)度算法兩個(gè)關(guān)鍵點(diǎn)。選擇好的模型與對(duì)應(yīng)算法，可以更好的進(jìn)行任務(wù)調(diào)度的負(fù)載均衡處理。

1.1 調(diào)度模型

常見(jiàn)的動(dòng)態(tài)任務(wù)分配表的調(diào)度模型分為分布式和集中式任務(wù)調(diào)度模型?；诜植际皆驮O(shè)計(jì)出的動(dòng)態(tài)任務(wù)分配管理器，并投入實(shí)際任務(wù)調(diào)度使用的模型系統(tǒng)有Yarn，F(xiàn)alkon，Gearman等系統(tǒng)[2]。以上三個(gè)調(diào)度模型能夠非常好的適應(yīng)各種調(diào)度算法，以保證整個(gè)系統(tǒng)的負(fù)載均衡模式。其中，Gearman模型是目前最常用的一種調(diào)度模型，在該模型上的各種負(fù)載均衡算法都有很好的應(yīng)用。

1.2 調(diào)度算法

目前，基于負(fù)載均衡的調(diào)度算法研究主要分為兩類(lèi)[3]：(1)靜態(tài)漸變傳播和交流算法，通過(guò)相連節(jié)點(diǎn)不斷均衡達(dá)到整個(gè)系統(tǒng)負(fù)載均衡；(2)動(dòng)態(tài)負(fù)載均衡共享算法，通過(guò)隨機(jī)選擇多個(gè)節(jié)點(diǎn)進(jìn)行均衡以達(dá)到最后的負(fù)載均衡，不強(qiáng)調(diào)節(jié)點(diǎn)相連。

本文主要針對(duì)目前較為常見(jiàn)的動(dòng)態(tài)負(fù)載均衡算法進(jìn)行研究，如今研究較多的動(dòng)態(tài)負(fù)載均衡算法包括，隨機(jī)算法、輪詢算法、最小負(fù)載優(yōu)先算法以及任務(wù)竊取算法等。本文著重分析Work-stealing任務(wù)竊取算法。

2 Work-stealing任務(wù)竊取算法

2.1 Work-stealing算法基本過(guò)程

Work-stealing[4]算法通過(guò)基于任務(wù)竊取的方式進(jìn)行整體系統(tǒng)的負(fù)載均衡。該算法的竊取策略通過(guò)一種范式的方式均衡分配任務(wù)量，能夠及時(shí)發(fā)現(xiàn)沒(méi)有充分利用資源的計(jì)算節(jié)點(diǎn)，并從另一些處于繁忙計(jì)算的節(jié)點(diǎn)中解放一些任務(wù)給空閑狀態(tài)中的計(jì)算節(jié)點(diǎn)使用，從整體架構(gòu)上看，這樣的策略可以使系統(tǒng)任務(wù)負(fù)載均衡。

Work-stealing算法中每個(gè)處理器都擁有一個(gè)雙端隊(duì)列，且可以看成是一個(gè)調(diào)用棧，從底部插入就緒空閑狀態(tài)的線程，等到其他處理器竊取任務(wù)的時(shí)候，從頂端刪除該線程?？梢詫⒃撽?duì)列命名為任務(wù)調(diào)度竊取棧，如圖1所示。

圖1 任務(wù)調(diào)度竊取棧Fig.1 Task scheduling steal stack

當(dāng)Work工作端發(fā)現(xiàn)負(fù)載不均衡的時(shí)候，將調(diào)用Work-stealing算法完成任務(wù)的竊取，將竊取到的任務(wù)從竊取棧中彈出，給竊取端使用。基本過(guò)程包括：

(1)發(fā)現(xiàn)負(fù)載不均衡并想要竊取任務(wù)的服務(wù)器被設(shè)置成一個(gè)竊取端。

(2)當(dāng)待竊取端請(qǐng)求中心任務(wù)調(diào)度器需要竊取任務(wù)，中心調(diào)度器發(fā)來(lái)可以被竊取的處理器的相關(guān)信息，竊取端首先查詢每個(gè)處理器管理的竊取棧，若棧非空，那么取出棧頂元素作為竊取的服務(wù)器。

(3)若竊取棧為空，竊取端則會(huì)嘗試隨機(jī)選擇另一個(gè)處理機(jī)進(jìn)行竊取。通過(guò)不斷的迭代尋找，直到尋找到可以竊取對(duì)應(yīng)任務(wù)的處理機(jī)，然后訪問(wèn)該處理機(jī)并竊取處理不完的任務(wù)放進(jìn)自己的任務(wù)隊(duì)列中，根據(jù)隊(duì)列規(guī)則依次執(zhí)行任務(wù)。

2.2 Work-stealing算法三種竊取任務(wù)數(shù)量策略

任務(wù)數(shù)量選擇策略上，傳統(tǒng)的Work-stealing算法提供了三種不錯(cuò)的計(jì)算策略，分別是加法級(jí)數(shù)策略、乘法級(jí)數(shù)策略和二分法級(jí)數(shù)策略。

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

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

(3)二分法級(jí)數(shù)策略：當(dāng)需要確定竊取任務(wù)的數(shù)量的時(shí)候，首先統(tǒng)計(jì)獲得的處理機(jī)的總隊(duì)列任務(wù)，然后選擇處理總隊(duì)列中的一半任務(wù)。

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

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

2.3 Work-stealing算法兩種竊取任務(wù)時(shí)機(jī)策略

Work-stealing算法在竊取時(shí)機(jī)選擇策略主要有兩種，主要包括節(jié)點(diǎn)空閑時(shí)的任務(wù)竊取和節(jié)點(diǎn)快要空閑時(shí)的任務(wù)竊取策略。

2.3.1 節(jié)點(diǎn)空閑的時(shí)候進(jìn)行任務(wù)竊取當(dāng)需要進(jìn)行任務(wù)竊取的時(shí)候，處理機(jī)首先向中心任務(wù)調(diào)度服務(wù)器提出竊取任務(wù)請(qǐng)求。中心任務(wù)調(diào)度服務(wù)器查詢各個(gè)處理機(jī)的當(dāng)前狀態(tài)，并返回處于滿負(fù)荷狀態(tài)下的處理機(jī)，這樣需要執(zhí)行竊取的處理機(jī)就可以進(jìn)行竊取操作，改善那些處于滿負(fù)荷狀態(tài)下的處理機(jī)。

2.3.2 節(jié)點(diǎn)快要空閑的時(shí)候進(jìn)行任務(wù)竊取某節(jié)點(diǎn)在就緒隊(duì)列中正在執(zhí)行任務(wù)，但是該任務(wù)快要執(zhí)行完成了，這時(shí)候進(jìn)行任務(wù)竊取的請(qǐng)求。同時(shí)，請(qǐng)求過(guò)程也與節(jié)點(diǎn)空閑時(shí)候進(jìn)行任務(wù)竊取的過(guò)程相同。

實(shí)際情況下，以上兩種策略各有優(yōu)缺點(diǎn)，視具體情況選擇不同的算法策略。

3 改進(jìn)的Work-stealing任務(wù)竊取算法

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

本文的改進(jìn)策略是根據(jù)設(shè)定竊取時(shí)機(jī)的不同，每當(dāng)需要進(jìn)行任務(wù)竊取的時(shí)候，就開(kāi)始啟動(dòng)Work-stealing算法，并選擇相應(yīng)的可以進(jìn)行竊取的處理機(jī)，并在該處理機(jī)上執(zhí)行竊取任務(wù)的操作。本文將負(fù)載最大的處理機(jī)作為備選的待竊取任務(wù)處理機(jī)，本文改進(jìn)的算法是最大負(fù)載優(yōu)先竊取算法。

3.1 改進(jìn)算法流程

過(guò)竊取時(shí)機(jī)的確定，本文將需要竊取任務(wù)的處理機(jī)設(shè)置為“竊取機(jī)”，當(dāng)被設(shè)置為“竊取機(jī)”之后，竊取機(jī)向任務(wù)調(diào)度中心服務(wù)器請(qǐng)求任務(wù)竊取，服務(wù)器首先會(huì)執(zhí)行動(dòng)態(tài)的負(fù)載均衡算法進(jìn)行選擇，挑選出目前負(fù)載最大的或者次大的等多個(gè)候選處理機(jī)作為“候選機(jī)”，候選機(jī)的選擇如下：

(1)任務(wù)調(diào)度中心服務(wù)器輪詢現(xiàn)有隊(duì)列中的各個(gè)處理機(jī)狀態(tài)，通過(guò)計(jì)算每個(gè)處理機(jī)的最大任務(wù)隊(duì)列的長(zhǎng)度，比較選出結(jié)果最大的處理機(jī)，將該處理機(jī)作為候選機(jī)，然后將竊取機(jī)相關(guān)信息通過(guò)進(jìn)程間通信返回給竊取機(jī)。

(2)通過(guò)上步中的竊取機(jī)信息進(jìn)行任務(wù)的竊取。由于進(jìn)程間通信的延遲緣故，在竊取機(jī)接收到候選機(jī)的進(jìn)程號(hào)的時(shí)候，該進(jìn)程的具體信息需要延遲一段時(shí)間才能傳播過(guò)來(lái)，這時(shí)候竊取機(jī)對(duì)其進(jìn)行簡(jiǎn)單的預(yù)竊取工作。對(duì)于竊取任務(wù)的數(shù)量，本文則根據(jù)當(dāng)前傳播過(guò)來(lái)的候選機(jī)的任務(wù)數(shù)量做出最終決定，從候選機(jī)的就緒任務(wù)隊(duì)列中彈出目前需要的任務(wù)數(shù)量，直到被竊取的任務(wù)數(shù)量達(dá)到為止。任務(wù)竊取成功，轉(zhuǎn)(3)，否則，轉(zhuǎn)(4)。

(3)當(dāng)前任務(wù)竊取已經(jīng)成功，這時(shí)候需要?jiǎng)討B(tài)更新目前保存在任務(wù)調(diào)度中心服務(wù)器的各個(gè)處理機(jī)的負(fù)載情況。

(4)當(dāng)前任務(wù)竊取失敗，說(shuō)明了所有處理機(jī)的任務(wù)都已經(jīng)完成了，目前不存在可以進(jìn)行竊取的任務(wù)了。

(5)竊取機(jī)從候選機(jī)中竊取到了相應(yīng)數(shù)量的任務(wù)，并執(zhí)行這些任務(wù)。

(6)算法結(jié)束，系統(tǒng)中目前的任務(wù)全部執(zhí)行完成。

3.2 改進(jìn)算法流程

本文改進(jìn)的算法是最大負(fù)載優(yōu)先的Work-stealing任務(wù)竊取算法。概算能夠根據(jù)當(dāng)前各個(gè)處理機(jī)的任務(wù)量的多少來(lái)決定如何分配竊取任務(wù)。根據(jù)3.1節(jié)中提到的算法步驟可以得到本文算法的流程圖，如圖2所示。

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

其中，竊取時(shí)機(jī)調(diào)度算法細(xì)節(jié)如圖3所示。在處理機(jī)需要竊取多少任務(wù)的數(shù)量確定流程上，如圖4所示。

圖3 竊取時(shí)機(jī)調(diào)度算法流程圖Fig.3 Flow chart of Scheduling algorithm for stealing time

圖4 竊取任務(wù)數(shù)量流程圖Fig.4 Flow chart of stealing tasks

3.3 改進(jìn)算法與傳統(tǒng)Work-stealing算法實(shí)驗(yàn)對(duì)比

本文通過(guò)搭建一個(gè)原型系統(tǒng)測(cè)試本文改進(jìn)算法與傳統(tǒng)Work-stealing算法。在原型系統(tǒng)中創(chuàng)建了10臺(tái)服務(wù)端，每個(gè)服務(wù)端最高負(fù)載量為10個(gè)任務(wù)。在傳統(tǒng)算法中，分別對(duì)三種竊取任務(wù)數(shù)量策略和兩種竊取任務(wù)時(shí)機(jī)策略進(jìn)行實(shí)驗(yàn)驗(yàn)證。驗(yàn)證結(jié)果如下表2所示。

表2 傳統(tǒng)算法與改進(jìn)算法比較Table 2 Comparison between the traditional and improved algorithms

從上表中可以看出，本文改進(jìn)算法的優(yōu)勢(shì)在于，由于是通過(guò)動(dòng)態(tài)不斷改變竊取任務(wù)量的，所以本文算法的任務(wù)量較為平均，負(fù)載較為均衡。另外，本文算法能夠快速確定竊取任務(wù)數(shù)量和時(shí)機(jī)，時(shí)間復(fù)雜度低。

4 結(jié)論

本文通過(guò)簡(jiǎn)要分析和介紹常見(jiàn)的任務(wù)調(diào)度模型和任務(wù)竊取算法，著重分析了Work-stealing算法竊取策略。通過(guò)最大負(fù)載優(yōu)先策略對(duì)傳統(tǒng)Work-stealing進(jìn)行改進(jìn)，不但改善了傳統(tǒng)算法在動(dòng)態(tài)實(shí)時(shí)變化系統(tǒng)中的不足之處，而且通過(guò)快速選擇竊取任務(wù)數(shù)量和竊取任務(wù)時(shí)機(jī)，改進(jìn)算法的時(shí)間復(fù)雜度低，有較強(qiáng)的實(shí)時(shí)負(fù)載均衡能力。

[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-),女,浙江杭州人,本科,講師,主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用.E-mail:136520276@qq.com