一個網格服務工作流的動態調度算法
2008-12-31 00:00:00李超朱巧明李培峰馬峰明
計算機應用研究 2008年11期
（1.蘇州大學 計算機學院，江蘇 蘇州 215006； 2.江蘇省計算機信息處理技術重點實驗室，江蘇 蘇州 215006）
摘要：針對服務網格環境中資源的動態性，提出了一種并行調度算法PGSWA（parallel grid service workflow scheduling），該算法引入了性能預測模型和并行就緒隊列來預測下一段時間資源的性能并使得成員服務能夠并行執行。實驗證明，該算法能較好地縮短工作流的執行時間，提高工作流的執行性能。
關鍵詞：網格服務工作流； 動態調度； 性能預測模型； 并行隊列
中圖分類號：TP3016文獻標志碼：A
文章編號：1001-3695(2008)11-3285-03
Dynamic scheduling algorithm for grid service workflow
LI Chao1，2， ZHU Qiao-ming1， LI Pei-feng1，2， MA Feng-ming1，2
(1.School of Computer Science Technology， Soochow University， Suzhou Jiangsu 215006， China； 2.Key Laboratory of Computer Information Processing Technology of Jiangsu Province， Suzhou Jiangsu 215006， China)
Abstract:Considering the dynamics of resources in the service-oriented grid environment， this paper proposed a novel sche-duling algorithm PGSWA(parallel grid service workflow scheduling) to solve such problem. The algorithm introduced the performance prediction model and parallel ready queue into the scheduling to predict the resource performance and run services in parallel. The experiment results show that it can reduce the executing time of workflow， and improve its performance.
Key words：grid service workflow; dynamic scheduling; performance prediction model; parallel queue
在服務網格環境中，所有的資源包括計算、通信和存儲等都是以服務的形式存在。同時，工作流作為實現網格中資源協同工作的一項重要技術手段，將網格中的多個服務包裝成一個更大粒度的服務部署在網格中，供其他服務或上層的應用訪問，來解決復雜的科學和商業應用。
網格服務工作流可以看成是一組成員服務的集合，服務之間存在著時序或因果的約束條件，并最終完成一個特定的目標。它與傳統的工作流之間具有很大的差別，如基于虛擬組織的工作方式；網格資源的動態性導致網格的計算和處理能力隨時間變化，應用性能估計困難；資源異構以及跨管理域等。
調度是網格工作流中重要的課題，并且網格工作流調度不同于一般的任務調度，在調度時不僅要考慮為任務選擇一個最佳的資源，還要考慮各個任務之間的時序或因果的約束條件，以及協調各個任務的執行來獲取最終的執行結果[1]。
本文提出了一種新的網格服務工作流調度算法。算法引入了性能預測模型能夠較好地預測下一段時間資源的性能；引入了就緒隊列和并行就緒隊列來提高任務執行之間的并行性；考慮資源可靠性，一定程度上保證了工作流的順利執行。
1相關工作
在已有的網格資源調度算法中，主要側重于解決網格作業與網格資源間的調度問題。文獻[2]提出了一種基于經濟學模型的優化調度模型，其目的是在資源提供者和使用者間建立交易，以盡可能低的費用滿足資源使用者進行計算任務的最低要求；文獻[3]采用了一種基于Class Ad匹配的集中式方案，以形成資源調度器；文獻[4]提供了一個高度結構化的可擴展的調度方案。但是這些調度方案未能從網格服務的角度考慮網格服務工作流的調度。
文獻[5，6]提出了一種基于遺傳算法的網格服務工作流調度算法，從不同側面改進了遺傳算法，克服了傳統遺傳算法收斂性差和早熟收斂的缺陷，提高了資源選擇的效率。但是卻沒有考慮服務網格環境中資源的動態性和可靠性，而且沒有考慮任務之間的并行性。文獻[7]通過對網格工作流中應用程序優先級進行定義，可以使用優先級調度算法來保證優先級較高的網格工作流應用程序能夠被優先調度和運行，但它也同樣沒有考慮到任務之間的并行執行，導致執行效率比較低。
通過具體的實驗和模擬實驗驗證，本文提出的調度算法能夠有效地預測資源節點的性能，協助調度器獲得合理的調度方案；通過引入關鍵網格服務和并行就緒隊列提高了成員服務之間執行的并行性，縮短了工作流的執行時間，提高了工作流的執行性能。
2網格服務工作流調度模型
21工作流執行模型
工作流系統的核心部件是工作流引擎。它首先解析工作流描述文件，根據抽象的工作流定義，獲取包含的成員服務及成員服務之間的依賴關系，這些依賴關系不僅包括數據傳輸依賴，還包括控制依賴。
獲取了所需的成員服務和依賴關系之后，系統就會將滿足執行約束的任務放到就緒隊列中，等待系統調度器為其選擇一個服務資源并執行。工作流執行模型如圖1所示。
從圖1可以看出，工作流執行模型由有向無環圖（directed acyclic graphs，DAG）管理器和調度器組成。DAG管理器主要負責監視任務的執行，基于任務之間的事件及依賴關系來動態更新就緒隊列。調度器主要為就緒隊列中的任務選擇一個最佳的服務資源，并且傳送控制信息和數據信息到服務資源所在的節點，并驅動服務的執行。
22網格服務工作流動態調度模型
網格調度作為網格資源與網格用戶之間的橋梁，是網格資源管理系統的重要組成部分。網格調度系統一方面收集大量的可用的資源信息；另一方面根據用戶的性能需求將合適的資源分配給應用。根據GGF網格調度研究小組，網格調度器負責：a)發現應用的可用資源；b)選擇合適的資源；c)執行作業。簡而言之，網格調度是由排序和映射組成，排序是根據網格應用的優先級決定網格作業執行的順序，映射是一個選擇合適資源并將其分配給應用的過程，為獲得最佳的應用執行性能，每次映射之前都應該進行性能評估。
221服務節點性能的預測模型
從GIS（grid information services）上獲取每個節點的服務資源列表，并采用每隔一段時間重新獲取的方式來保證每次都能夠較為準確地獲取資源信息。
節點的性能是動態變化的，通過綜合考慮CPU、CPU負載、內存、網絡負載以及節點上等待隊列的長度這些因素來考查一個節點的性能。通過大量的實驗，并對實驗結果進行回歸統計處理，得出了用來預測某個節點性能的預測模型。
Mp(ni)=α×ni_cload-β×ni_nload-δ×ni_c-γ×ni_m+η×ni_tnum+ε(1)
其中：α、β、δ、γ、η是性能因子，分別代表了CPU負載、網絡負載、CPU、內存及節點上等待隊列長度影響節點性能所占的比重；ε為隨機誤差，均值為零的正態分布隨機變量；ni表示第i個資源節點，且1≤i≤n；n為所有節點的數目。
采用的數學模型是嶺回歸統計，嶺統計是一種理論上有較大影響并得以廣泛應用的估計方法。對于線性回歸模型，回歸系數b的嶺估計定義為
b∧(k)=(XTX+kI)-1XTy(2)
用b的嶺統計建立的回歸方程稱為嶺回歸方程。其中k＞0稱為嶺系數。式(1）中的矩陣X和y都經過中心化和標準化交換。嶺估計隨k（峰系數）值改變而改變，若記b∧i(k)為b∧(k)的第i個分量，當k在[0，+∞)上變化時，b∧(k)的圖像稱為嶺跡。
選擇k值的嶺跡法是：將b∧1(k)，b∧2(k)，…，b∧m(k)的嶺跡畫在同一個圖上，根據嶺跡的變化趨勢選擇k值，使得各個回歸系數的嶺估計大體上穩定，并且各個回歸嶺系數估計的符號比較合理。
通過在MATLAB中進行回歸，發現在k取0.6時，各個回歸系數的嶺估計比較穩定，因此將k設為0.6。
為了驗證一個預測模型是否合理，是否可以進行較為準確的預測。要對其進行檢驗，最常用的方法是顯著性檢驗，也稱F檢驗。其中統計量計算公式如下：
F=[∑ni=1(i-y)2]/[m∑ni=1(yi-i)2/(n-m-1)](3)
在給定的顯著性水平α下，把計算出的F分布表中查得的自由度為(m，n-m-1)的Fα值相比，若F≥Fα，則可以認為因變量y與自變量x1，x2，…，xm間線性相關關系是顯著的，所建回歸預測模型有效可用。
根據實驗數據和式（1）（2），計算得出F的值為5.553 6。在α取0.95時，F0.95(6，425-6-1)=2.120 3，滿足F≥Fα，證明預測模型是有效的。
獲取了節點的性能值，就可根據各個節點的性能值生成一個按性能值非遞減排列的資源列表。
222資源的可靠性定義
利用Re(ni)代表資源節點ni的可靠性，只有當資源的可靠性達到一定標準時才會有可能成為候選資源，表示為在該資源上能成功運行某服務的概率。因此對于用戶而言，體現了資源安全可靠執行服務的概率。采用式(4)計算：
Re(ni)=α×succsin-1+β×1/(n-1)∑n-1k=1succsik(4)
其中：succsik=1ni上si運行成功0ni上si運行失敗
表示了在資源ni上運行服務si是否成功，α、β是權重因子且α+β=1，分別代表了最近一次執行情況和歷史執行情況所占的比重。
同樣，利用Re(si)來代表服務資源si的可靠性，其計算式為
Re(si)=×succsin-1+β×1/(n-1)∑n-1k=1succsik（5）
其中:succsik=1si執行成功0si執行失敗代表了si是否執行成功。有了每個si的可靠性約束，調度器在選擇資源時就可以根據Re(si)的大小來篩選服務資源。
223服務估計執行時間的定義
Test(si，ni)用來表示服務si在節點ni上的估計執行時間，計算式為
Tnest(si，ni)=λTn-1est(si，ni)+(1-λ)[Tn-1exc(si，ni)+βn-1](6)
βn=1/(n-1)(∑nk=1Tkexc(si，ni)-(∑nk=1Tkexc(si，ni))2/n)（7）
λ=Texc/Test(Test＞2Texc)
1-Texc/Test(Texc＜Test≤T2Texc)
Test/Texc(Test≤Texc)（8）
其中：Tnest(si，ni)表示si在資源ni上第n次執行時的估計執行時間，βn是標準方差，反映了在該資源上執行該服務實例的歷史變動情況。λTn-1est(si，ni)代表了前一次的估計執行時間對當前執行時間的影響，(1-λ)[Tn-1exc(si，ni)+βn-1]則代表了歷史執行情況對當前執行時間估計的影響。λ是根據最近一次的估計時間和執行時間動態確定的，用于控制這兩部分對目前時間估計的影響力，并且λ的取值是動態確定的，更加適應了網格環境的動態性。
23就緒隊列和并行就緒隊列
就緒隊列中的任務是可以執行的活動。在工作流執行時，工作流中的活動單元（即處于就緒狀態的成員服務）可能被分成n個就緒隊列，筆者用{RL1，RL2，…，RLn}代表執行時的n個就緒隊列。n的大小和每個就緒隊列中的活動單元是在運行時確定的。每個就緒隊列中活動單元之間是獨立的，并可以并行執行，不同就緒隊列中的活動單元根據約束條件可能并行或串行執行，如圖2所示。
如圖2所示，RLi和RLj只能串行的執行，因為只有RLi和RLj存在著序列約束。如果A3能夠在A2之前執行完，則RLj和RLk可以部分并行執行。
工作流開始執行的時間用Ts表示，結束時間用Te表示。分析可知，工作流的執行時間取決于就緒隊列的執行和就緒隊列之間的并行度。并行度越高，則執行效率越高。為了定義并行就緒隊列，首先引入關鍵成員服務CGS（critical grid ser-vice）。
231關鍵服務成員的定義
假設L代表RLk的長度，假設Si，k表示就緒隊列RLk中Si服務，若滿足如下性質，則將其定義為關鍵網格服務CGS。
TCGS=max{Tsi，kest｜1≤k≤L}。其中Tsi，kest是RLk中si的估計執行時間。
由上可知，CGS的執行時間的快慢決定了所在就緒隊列RLk的執行時間的快慢，在一定意義上也就決定了整個工作流的執行時間快慢。
232并行就緒隊列的定義
通過定義并行就緒隊列，就可以確定哪些就緒隊列可以并行執行，從而提高工作流任務的執行效率，縮短工作流的執行時間。
引入隊列的開始執行時間TRLksta和執行結束時間TRLkend，定義如下：
TRLkend=TRLksta+TCGS(9)
對開始時間和結束時間進行了粗略的計算。其中TCGS表示關鍵服務的估計執行時間，利用式（6）計算獲得。
如果RLi和RLj滿足下式，則表明兩個就緒隊列是可以并行執行的。
(TRLjsta≤TRLista＜TRLjend)∨(TRLjsta＜TRLiend≤TRLjend)∨
(TRLista≤TRLjsta＜TRLiend)∨(TRLista＜TRLjend≤TRLiend)
（10）
24算法實現
根據上述的分析和定義，針對服務工作流調度問題，提出并行調度算法——PGSWA（parallel grid service workflow sche-duling）算法。該算法描述如下：
輸入：工作流應用{A1，A2，…，An}，資源節點可靠性閾值NC，服務資源可靠性閾值SC；
輸出：成員服務與服務資源間的映射關系；
a）獲取就緒隊列{RL1，RL2，…，RLn}，并獲取每個隊列的關鍵任務；
b）通過式（11）計算來獲取并行隊列；
c）根據系統設定的NC來篩選篩選資源節點；
d）通過預測模型獲取可用資源節點的性能值；
e）根據需求考慮就緒隊列中成員服務的時間和成本約束，根據設定的SC，為處于就緒狀態的成員服務分配最佳的可用的服務資源。
3實驗驗證
在已有的網格調度算法中，最短作業最快資源（SJFR）[8]和最長作業最快資源（LJFR）[8]是兩種常用算法，前者可以獲得較短的總體作業執行時間，但會導致長作業執行時間很長；而后者雖然避免了長作業餓死，但作業執行的總體時間也比較長。
為了驗證PGSWA算法的性能，提交的工作流由1～20個成員服務組成，每次實驗時提交5～10個工作流，記錄每種情況下工作流的平均執行時間。實驗環境為：一個主機作為調度節點，八個性能不同的主機作為資源節點，并且每個節點上都部署了分詞服務、人名識別服務、地名識別服務、機構名識別服務和詞性標注服務。實驗結果如圖3所示。
實驗表明，基于PGSWA算法的工作流的執行時間低于SJFR算法和LJFR算法產生的執行時間。當工作流包含的成員服務較少時，三種算法的執行時間相差不大，這主要是因為處于就緒狀態的任務較少，任務區分度較小。隨著成員服務數量的增加，PGSWA由于考慮了任務之間的并行執行，能獲得較好的執行性能。
此外，為了驗證調度算法的性能，通過在GridSim中進行模擬實驗與FCFS、LJFR、SJFR調度算法進行了比較，并設置了五種不同的工作流結構，每種工作流由5～50個成員服務組成。在實驗中設定了10個資源節點，每個節點包含一樣的服務資源列表。兩種調度算法的實驗結果如圖4所示。
由圖4可知，在模擬環境中，PGSWA算法表現出較好的性能，執行時間均小于FCFS、LJFR和SJFR算法下的平均執行時間。工作流的成員服務數量比較少的情況下，幾種算法下工作流的執行時間相差不大；當成員服務的數量超過30時，執行時間出現了較大的區別，主要是由于PGSWA算法考慮了服務就緒隊列中服務之間執行的并行性，使得滿足條件的服務能夠并行的執行，從而提高了執行效率。
4結束語
針對服務網格環境下的網格工作流調度，本文提出了一種新型的工作流調度模型，通過引入性能預測模型，較好地預測資源的性能；通過引入并行就緒隊列，提高了任務之間的并行執行。通過實驗驗證，該調度模型能夠較好地縮短工作流的執行時間，保證工作流的順利執行。但該調度方法僅僅考慮了資源的性能和可靠性，沒有考慮用戶的QoS[9]以及系統多層次的QoS；而且調度方法中還沒有提出一種較好的容錯機制來保障工作流的安全執行。這些將是下一步研究的重點和難點問題。
參考文獻：
［1］ZHU Qiao-ming， LI Pei-feng， GONG Zheng-xian，et al. ADJSA: An adaptable dynamic job scheduling approach based on historical information[C]//Proc of the 2nd International Conference on Scalable Information Systems. 2007:201-207.
[2]BUYYA R， ABRAMSON D， GIDDY J. An economy driven resource management architecture for a global computational power grid[C]//Proc of Int’l Conf on Parallel and Distributed Processing Techniques and Applications. 2000:259-264.
[3]FREY J， TANNENBAUM T， FOSTER I，et al. Condor-G: a computation management agent for multi-institutional grids[J].Cluster Computing，2002，5(3):237-246.
[4]CHAPIN S， KARPOVICH J， GRMSHAW A. The Legion resource mana-gement system[C]//Proc of the 5th Workshop on Job Scheduling Strategies for Parallel Processing. 2000:123-128.
[5]DONG Fang-peng， SELIM G. An adaptive double-layer workflow scheduling approach for grid computing[C]//Proc of the 21st International Symposium on High Performance Computing Systems and Applications. Washington DC:IEEE Computer Society， 2007:156-163.
[6]TRETOLA G，ZIMEO E.Activity pre-scheduling in grid workflows[C]//Proc of the 15th Euromicro International Conference on Parallel，Distributed and Network-based Processing. Washington DC:IEEE Computer Society， 2007:245-253.
[7]劉洋，桂小林，徐玉文. 網格工作流中基于優先級的調度方法研究[J].西安交通大學學報， 2006，40(4):411-414.
[8]ABRAHAM A， BUYYA R. Nature’s heuristics for scheduling jobs on computational grids[C]//Proc ofthe 8th Int’l Conf on Advanced Computing and Communication. 2000:301-308.
[9]YUAN Ying-chun， LI Xiao-ping， WANG Qian. Dynamic heuristics for time and cost reduction in grid workflows[M].Berlin:Springer-Verlag， 2007:499-508.
[10]郭文彩，楊揚. 基于遺傳算法的網格服務工作流調度的研究[J].計算機應用， 2006，26(1):54-56.
[11]王勇，胡春明，杜宗霞. 服務質量感知的網格工作流調度[J].軟件學報， 2006，17(11):2341-2351.
