異構(gòu)分布式系統(tǒng)中實時可任意切分任務調(diào)度算法

仝武寧, 劉道華, 李宏斌

(1. 陜西中醫(yī)藥大學 基礎醫(yī)學院, 陜西 咸陽 712046；2. 信陽師范學院 計算機與信息技術學院, 河南 信陽 464000)

0 引言

可分任務是一種可被切分成任意多個子任務的任務，且被切分成的子任務之間沒有依賴關系，可以在許多不同的處理機上同時處理.大量的文獻對可分任務進行了研究，且可分任務理論已經(jīng)被成功地應用于許多科學問題中，如：圖像處理、信號處理以及文本搜索等應用領域[1-3].在分布式系統(tǒng)中，任務調(diào)度策略的優(yōu)劣直接影響系統(tǒng)的性能，設計較優(yōu)的調(diào)度策略以提高系統(tǒng)的效率、用戶滿意度等是分布式系統(tǒng)中任務調(diào)度研究的主要目標.文獻[4]提出一種利用可分任務理論計算滿足實時可分任務完成截止時間約束時所需最少處理機的方法；文獻[5]提出了一種考慮處理器可用時間的實時可分任務調(diào)度算法.文獻[6]對文獻[5]中提出的算法進行了改進，得到了調(diào)度問題的精確解.文獻[7]將實施可分任務劃分成緊急任務和非緊急任務，然后根據(jù)不同的任務類型設計了不同的調(diào)度方案，以達到最大化接受率的目的.文獻[8]考慮任務對系統(tǒng)的最低需求，設計了一個考慮資源可用性的任務調(diào)度算法以提高資源的利用率.也有越來越多的文獻對實時可分任務進行了研究[9,10]，然而在已有的研究文獻中，都旨在最優(yōu)化資源利用率等單一目標，并沒有考慮優(yōu)化多個目標的資源調(diào)度.因此，本文針對異構(gòu)分布式環(huán)境下的實時可分任務調(diào)度問題進行了研究，為最大化服務收益、任務接受率以及最小化完成時間設計了有效的算法.

1 問題描述

本文采用星型網(wǎng)絡拓撲，即系統(tǒng)中包含有一個主處理機P0和N個從處理機P1,P2，…，PN.主處理機P0負責判斷是否接收用戶提交的任務以及將接受的任務分發(fā)給從處理機，P0和從處理機Pi(i=1,2,…，N)之間有進行通信的鏈路li，且通過通信鏈路li傳遞一個單位任務量所需要的時間為gi.從處理機Pi(i=1,2,…，N)負責接收和處理主處理機分配給它的任務，且該處理機處理一個單位任務量所需要的時間為wi.

本文研究的對象是可分任務，即任務可以被無限拆分，拆分后的子任務之間沒有任何依賴關系.對于任務Τj，用三元組來表示，即Τj=(aj,dj,αj)，其中aj和αj分別表示任務Τj的到達時間和任務量，dj是任務Τj相對完成截止時間，則任務Τj的絕對完成截止時間為aj+αj.用戶提交任務后，分布式系統(tǒng)可以根據(jù)用戶的任務量，任務的完成截止時間來確定任務的服務收益，用δj表示任務Τj的服務收益.

異構(gòu)分布式系統(tǒng)中具有完成截止時間的實時可分任務調(diào)度問題可以歸結(jié)為：當任務到來時，主處理機如何根據(jù)當前從處理機的狀態(tài)決定是否接受該任務，以使得一段時間內(nèi)服務收益和任務接受率最大；當用戶提交的任務被接受時，如何將該任務分配到不同的處理機上以使得任務的完成時間最短.因此，要解決該問題需要解決三個子問題：1)主處理機如何判斷用戶提交的任務是否可以被接受？2)任務被接受后，如果處理機處于忙的狀態(tài)，需要將接受的任務置于任務等待隊列中，如何確定任務等待隊列中任務的順序，以使得盡可能多的任務按時完成？3)任務按照何種策略被分配到處理機上以使得任務完成時間最短？

2 考慮服務收益的實時可分任務調(diào)度算法

2.1 任務接受規(guī)則與任務刪除策略

當用戶提交任務后，主處理機要根據(jù)從處理機的狀態(tài)以及任務等待隊列中的任務量來確定是否接受該任務，本文提出了一種同時考慮任務完成時間和任務的服務收益的策略以確定該任務是否被接受.當用戶提交的任務Τj同時滿足式(1)和式(2)時，該任務被拒絕，否則就接受該任務.

aj+dj

(1)

(2)

其中sj，tj和Q分別是任務Τj的預計開始時間、預計執(zhí)行時間和當前的任務等待隊列.任務Τj的預計開始時間由式(3)計算得到，本文采用改進的文獻[11]提出的方法計算任務的預計執(zhí)行時間，如式(4)所示.

(3)

(4)

當任務Τj被接受且滿足aj+dj

ηj=(sj+tj)-(aj+dj),

(5)

tQ={Τk|tk>ηj,Τk∈Q},

(6)

(7)

2.2 考慮服務收益的排序策略

當處理機都處于忙的狀態(tài)時，未進行處理的任務就加入到任務等待隊列中.任務的執(zhí)行順序會影響任務的完成時間、任務的接受率等，因此本文提出了一種綜合考慮任務完成時間和服務收益是排序策略，即通過式(8)計算任務等待隊列中任務的θj(j=1,2,…)，對任務等待隊列中任務按照θj(j=1,2,…,)值由小到大的順序進行排序.

(8)

其中0≤μ,ν≤1是兩個權(quán)重系數(shù)，且有μ+ν=1.經(jīng)過大量仿真實驗發(fā)現(xiàn)，當μ∈[0.58 0.67]時仿真結(jié)果更優(yōu)，因此在實驗中μ取0.6.

2.3 任務調(diào)度模型及算法

當有處理機空閑時就要取任務等待隊列中的任務分配給空閑的處理機以進行處理，如何有效地將任務分配到不同的處理機上以使任務的處理時間最短是需要解決的關鍵問題.式(9)給出了一個以最小化任務完成時間為目標的優(yōu)化模型.

(9)

(10)

(11)

(12)

算法1 任務調(diào)度算法框架

輸入：任務Τj,任務等待隊列Q；

輸出：任務Τj的調(diào)度方案；

If 任務Τj同時滿足式(1)和式(2) do

任務Τj被拒絕；

else

If 任務Τj滿足式(1)，不滿足式(2) do

If 任務等待隊列Q為空 do

任務Τj被拒絕；

else

根據(jù)式(5)—(7)確定要從任務等待隊列Q中刪除的任務；通過式(8)計算任務Τj的θj值，并將任務Τj插入到Q中；

end

else

通過式(8)計算任務Τj的θj值，并將任務Τi插入到Q中；

end

取出任務等待隊列Q中的第一個任務，表示為Τj′，根據(jù)(10)—(12)將Τj′分配到處理機上；

end.

3 實驗與分析

3.1 參數(shù)設置

3.2 評價指標

為評價算法的有效性，采用三種評價指標，分別為：接受率、服務收益率和任務完成時間，且三個指標的定義如下：

接受率:一段時間內(nèi)接受任務的任務量與用戶提交任務的任務量的比值，即

(13)

其中Ω和Nr分別是接受任務的集合和一段時間內(nèi)用戶提交任務的個數(shù).

服務收益率:一段時間內(nèi)接受任務的服務收益與用戶提交任務的服務收益的比值，即

(14)

任務完成時間:執(zhí)行完所有任務所需要的時間，即所有處理機結(jié)束執(zhí)行的時刻，定義為：

(15)

其中Ti是處理機Pi(1≤i≤N)結(jié)束執(zhí)行任務的時刻.

3.3 對比算法與實驗結(jié)果

為驗證算法的有效性，進行了3組對比實驗，每組實驗中有兩個對比算法，第一個對比算法是文獻[7]提出的算法，表示為E_RDLS，另一個是文獻[8]提出的R_RDLS算法，本文提出的算法表示為B_RDLS.

圖1給出了系數(shù)R變化時得到的任務接受率，圖2給出了系數(shù)R變化時得到的任務服務收益率，圖3給出了不同任務數(shù)量時得到的任務完成時間.

圖1 任務接受率隨R的變化情況Fig. 1 Acceptance ratio v.s. R

圖2 服務收益率隨R的變化情況Fig. 2 Benefit ratio v.s. R

圖3 任務完成時間Fig. 3 Makespan of Loads

3.4 實驗分析

圖1給出了任務接受率隨系數(shù)R變化的情況，顯然本文提出的B_RDLS算法在相同系數(shù)R的情況下得到比對比算法較高的接受率.當任務具有小的相對完成截止時間和大的任務量時，該任務就具有較大的服務收益，被接受的可能性就大，從而使得算法具有較高的接受率.當任務具有大的相對完成截止時間時，該任務被接受的可能性就大，因此也能提高算法的接受率.

由圖2中任務服務收益率隨系數(shù)R變化的情況可以得到：本文提出的B_RDLS算法在相同系數(shù)R的情況下得到比對比算法要高的服務收益率.服務收益大的任務容易被接受，當該任務不能按時完成時，采用從任務等待隊列中刪除任務的策略(刪除任務等待序列中服務收益較小且能夠使得當前被接受的任務按時完成的任務)，以盡可能地接受服務收益較高的任務，因此本文提出的算法在不同R的情況下可以得到比對比算法較高的服務收益率.

圖3給出了任務量由100到500變化時任務的完成時間變化情況.由圖3可以看出B_RDLS能夠得到比E_RDLS和R_RDLS算法更小的任務完成時間.優(yōu)先選擇處理速度快的處理機進行任務分配可以使得任務的完成時間減少.此外，設計的方法可以自動確定給不同處理機分配的任務量以實現(xiàn)處理機的無間隙處理任務，同樣可以減少不必要的時間消耗，因此本文的B_RDLS算法可以得到較小的任務完成時間.

4 結(jié)語

研究了異構(gòu)分布式系統(tǒng)中考慮服務收益的實時可分任務調(diào)度問題，設計了最大化任務服務收益的任務接受/拒絕規(guī)則以及從任務等待隊列中刪除任務的策略,以使得所有接受的任務能按時完成的同時,提高服務收益和任務接受率.為減小任務的完成時間，設計了綜合考慮任務服務收益和任務相對完成截止時間的排序策略、自適應地為處理機分配任務，使處理機無間隙地處理任務等方案，以減少任務的執(zhí)行時間.仿真實驗結(jié)果表明，設計的算法能夠得到比對比算法較高的任務接受率、服務收益率以及較小的任務完成時間.然而，算法中任務的排序策略中兩個參數(shù)會影響算法的性能，任務的不同，最優(yōu)的參數(shù)設置也不同.因此，如何只適應地確定出兩個參數(shù)的值或者給出更優(yōu)的任務排序策略是需要進一步研究的工作.