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

關(guān)鍵詞：任務(wù)分配? 負(fù)載均衡? Work-Stealing算法

中圖分類號：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1672-3791（2019）04（b）-0013-02

1? 和任務(wù)調(diào)度的動態(tài)化相關(guān)的概念

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

1.1 調(diào)度模型

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

1.2 調(diào)度算法

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

2? 任務(wù)竊取算法

2.1 實(shí)現(xiàn)任務(wù)竊取有關(guān)的過程

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

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

2.2 任務(wù)竊取算法的任務(wù)數(shù)量策略

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

2.3 工作竊取算法的時機(jī)選擇

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

2.3.1 與空閑節(jié)點(diǎn)有關(guān)的竊取

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

2.3.2 和空閑節(jié)點(diǎn)有關(guān)的任務(wù)竊取

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

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

3? 改進(jìn)型Work-Stealing算法

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

3.1 相關(guān)算法的流程

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

第一，任務(wù)調(diào)度中心對服務(wù)器之中已經(jīng)開始進(jìn)行輪候的各個處理機(jī)的狀態(tài)進(jìn)行問詢，了解每一個可以處理的任務(wù)的最大隊(duì)列可能性，通過對隊(duì)列任務(wù)進(jìn)行比較選擇一個最為適當(dāng)?shù)奶幚頇C(jī)種類，將這種類型的處理機(jī)中的一個選擇為輪候的處理機(jī)，在此之后將竊取的相關(guān)信息通過進(jìn)程信息系統(tǒng)反饋給竊取機(jī)。

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

3.2 如何對算法進(jìn)行改進(jìn)

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

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

3.3 實(shí)驗(yàn)數(shù)據(jù)方面的對比

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

4? 結(jié)語

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

參考文獻(xiàn)

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

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

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