馮復(fù)劍

(江蘇第二師范學(xué)院,南京 210013)

近年來隨著科學(xué)研究越來越依賴于海量數(shù)據(jù)集的分析和分布式資源的使用,科學(xué)工作流[1-3]得到了巨大的發(fā)展.通過管理分析的復(fù)雜性、在分布式資源上執(zhí)行必要的計算、收集分析結(jié)果的信息以及記錄和再現(xiàn)科學(xué)分析等手段,科學(xué)工作流管理系統(tǒng)提供了一個輔助科學(xué)發(fā)現(xiàn)過程的環(huán)境,加速了科學(xué)進(jìn)步的步伐.

商業(yè)云因其高彈性、專用軟硬件基礎(chǔ)設(shè)施和按需付費的成本模型等特性[4-6],已經(jīng)成為進(jìn)行大規(guī)模科學(xué)分析的支撐平臺.通過各種云服務(wù),可以促進(jìn)工作流的執(zhí)行.其執(zhí)行過程中,需要考慮一個或多個QoS 約束,常見的為時間-成本優(yōu)化.工作流調(diào)度的時間-成本優(yōu)化是一個難題,國內(nèi)外學(xué)者已從不同方面展開了研究并取得了豐富的成果[7-15].一些綜述文章[16-18]對其進(jìn)行了較完整的闡述,這里就不再一一回顧.為了簡潔起見,僅描述本文解決的問題.

現(xiàn)有的科學(xué)工作流調(diào)度算法多基于有向無環(huán)圖(Directed Acyclic Graph,DAG)建模,僅對工作流結(jié)構(gòu)中的順序和“與”結(jié)構(gòu)適用,并不支持“或”結(jié)構(gòu).這限制了算法的使用范圍和性能.文獻(xiàn)[12]提出,可以將“或”結(jié)構(gòu)轉(zhuǎn)換成“與”結(jié)構(gòu)進(jìn)行處理.這是不合理的,違背了工作流語義.對于“或”結(jié)構(gòu)中的支路每個流程實例只會選擇其中一條,而“與”結(jié)構(gòu)的所有支路都是同時執(zhí)行的,兩者是不可以直接轉(zhuǎn)換的.正因為未考慮“或”結(jié)構(gòu),現(xiàn)有的算法存在以下不足:

(1) 同一層活動分配相同的截止期限不合理

逆向分層調(diào)度算法[12](Deadline Bottom Level,DBL)以及基于此而改進(jìn)的算法中,認(rèn)為同一層的所有活動具有相同的截止期限.圖1為一個簡單的基于逆向分層的工作流實例,圖中活動節(jié)點的上方數(shù)字表示選擇最快執(zhí)行服務(wù)所需要消耗的時間.活動1 完成后,根據(jù)輸出條件選擇執(zhí)行支路{2,3,4}或者支路{5}.依據(jù)DBL 算法求得每個活動的時間區(qū)間如表1.活動5 的時間區(qū)間為[4,27],所以可選服務(wù)的耗時范圍為[7,23],假定其執(zhí)行最慢的服務(wù)耗時23 個單位時間.基于滿足截止期限的前提下選擇最低成本的原則,工作流在實例執(zhí)行過程中若選擇支路{5}將會調(diào)用執(zhí)行時間最長的服務(wù),因此將消耗掉額外16 個單位的時間.由此 帶來兩個問題:

圖1 一個簡單的工作流實例

表1 DBL 活動時間區(qū)間

① 活動5 本可以在時間點11 時刻即可結(jié)束,則活動6 將提前16 個單位時間開始,在不改變后續(xù)活動既定調(diào)度方案的情況下,將使得整個工作流提前16 個單位時間結(jié)束；

② 將額外消耗的16 個單位時間分配給后續(xù)未開始的活動,從而獲得更優(yōu)的執(zhí)行方案.

當(dāng)這兩種情況下帶來的效益遠(yuǎn)遠(yuǎn)大于單個活動5 優(yōu)化帶來的效益時,DBL 對截止期限的分配存在弊端.

(2) 松弛時間優(yōu)化未同時考慮活動控制結(jié)構(gòu)和服務(wù)效益

當(dāng)給定的工作流截止期限大于算法計算得出的截止期限時,工作流存在松弛時間.為了提高效益,需要將這部分時間資源合理地分配給能夠帶來費用優(yōu)化的活動.表2為圖1工作流實例中部分活動對應(yīng)的候選服務(wù)列表.

表2 候選服務(wù)列表

假設(shè)現(xiàn)有2 個單位的工作流松弛時間,由于只有活動{5,6}有多個候選的服務(wù),因此只需要對這兩個活動進(jìn)行優(yōu)化.根據(jù)文獻(xiàn)[13]提出的寬裕時間有效分配算法(Slack-time Effective Allocation,SEA),活動5,6 的鄰服務(wù)級差性價比分別為1 和0.5,因此將松弛時間全部分配給活動5.基于“或”結(jié)構(gòu)的特性,若工作流實際執(zhí)行過程中選擇活動5 所在的支路是小概率事件,此時分配的松弛時間將不會帶來費用優(yōu)化,從而導(dǎo)致時間資源的浪費.

(3) 其它問題

文獻(xiàn)12 中定理2 認(rèn)為BLmin≥LCT,其中:BLmin是按照逆向分組后求得的工作流最小完工時間,LCT為最小關(guān)鍵路徑法計算的完工時間.該定理不成立,因為BLmin和LCT均根據(jù)每個活動的最快服務(wù)求得,若BLmin＞LCT表示同一工作流在活動執(zhí)行者相同的條件下通過兩種不同方法得到不同的完工時間,這是不合理的.

為了解決以上的不足,本文提出一種新的調(diào)度算法,充分考慮工作流控制結(jié)構(gòu)中的順序、“與”和“或”結(jié)構(gòu),并分別從靜態(tài)調(diào)度和動態(tài)監(jiān)控兩個階段對截止期限的分配進(jìn)行討論.

1 模型和相關(guān)概念

1.1 工作流模型

定義1.工作流的DAG 模型是一個二元組 〈N,E〉,其中:N={1,2,3,4,···,n|n∈N?}表示所有的活動集；是活動之間的邏輯關(guān)系.

為了討論方便,下面給出一些變量的定義及其數(shù)學(xué)表達(dá)式:

(1)S(i):活動i的 候選服務(wù)集合,其大小為L(i).

(2)S(i)j:活動i的 第j個候選服務(wù).

(3)T(i)j:S(i)j所需的處理時間和數(shù)據(jù)傳輸時間之和.

(4)C(i)j:S(i)j對應(yīng)的服務(wù)費用和數(shù)據(jù)傳輸成本之和.

(5)D(i):活動i的截止期限.

(6)TS(i) :活動i的松弛時間,當(dāng)選定S(i)j后有:D(i)=T(i)j+TS(i).

(7)pred(i)/succ(i):活動i的前驅(qū)/后繼.

為了排除網(wǎng)絡(luò)等其它客觀環(huán)境的影響,假設(shè)云服務(wù)供應(yīng)商能夠提供無限數(shù)量的實例訪問,且不同存儲服務(wù)之間的帶寬基本相同.

1.2 關(guān)鍵活動優(yōu)先級

為了敘述方便,下面給出一些符號的語義:

(1)CP:工作流的最長執(zhí)行路徑,即關(guān)鍵路徑.

(2)CP(i) :活動i是關(guān)鍵活動.

(3)CPs(i)/CPand(i)/CPor(i):關(guān)鍵活動.i.處于順序支路/“與”支路/“或”支路,同步活動為關(guān)鍵活動,且在順序支路上.

定義2.關(guān)鍵活動優(yōu)先級(Critical Activity Priority,CAP),反應(yīng)活動時間-成本優(yōu)化對整個流程性能提升的影響程度.優(yōu)先級越高,表示活動的優(yōu)化帶來的影響越大,反之越小.

關(guān)鍵活動按照其所處控制結(jié)構(gòu)的不同,相應(yīng)的優(yōu)先級不同.下面分別對3 種拓?fù)浣Y(jié)構(gòu)進(jìn)行闡述.

(1) “與”支路

“與”控制結(jié)構(gòu)中的每條支路需要在同步活動處等待,當(dāng)關(guān)鍵活動獲得額外的時間資源后,將延長所在支路的執(zhí)行時間,進(jìn)而影響整個控制塊中每條支路的運行.因此,“與”支路上單個關(guān)鍵活動的優(yōu)化將會提升整個“與”控制結(jié)構(gòu)的性能.

(2) 順序支路

順序支路上的關(guān)鍵活動,對其分配額外的時間資源只會優(yōu)化該活動本身,并不會波及其它活動.

(3) “或”支路

由于“或”結(jié)構(gòu)在實例運行之前無法確定選擇哪條支路,因此,對“或”支路上的關(guān)鍵活動分配額外的時間資源有可能無法帶來效益.

綜上所述,可以得到關(guān)鍵活動的優(yōu)先級為:CAP(CPand(i))＞CAP(CPs(i))＞CAP(CPor(i)).

2 調(diào)度算法

本文按照如下步驟解決調(diào)度問題:

步驟1 尋找工作流的最小關(guān)鍵路徑.

步驟2 查詢可用時隙,根據(jù)每個任務(wù)的局部最優(yōu)解生成最優(yōu)調(diào)度計劃.

步驟3 實時監(jiān)控流程實例的運行狀態(tài).

接下來詳細(xì)陳述步驟2-3,關(guān)鍵路徑的尋找通過文獻(xiàn)[19]提出的方法實現(xiàn).

2.1 松弛時間分配策略

定義3.服務(wù)效益比(Service Benefit Ratio,SBR),衡量服務(wù)替換所帶來效益的大小,其計算公式為:

式(1)中的m、n分別表示第m、n個候選服務(wù).

對優(yōu)先級相同的活動集合A,基于服務(wù)效益比的松弛時間分配算法(Slack Time Allocation Based on SBR,STABSBR)如下:

算法1.STABSBR 算法輸入:A ,?i∈A 具 有相同的活動優(yōu)先級；松弛時間TS；輸出:{TS(i)}；Begin 1 計算 A 中每個活動i 的下一個候選服務(wù)(S (i)按照成本降序排列)與當(dāng)前選擇服務(wù)的Δ C(i)m,n,Δ T(i)m,n,SBR(i)m,n；2 while(A ≠?)3 {4從 A 中去除所有Δ T(i)m,n＞TS 的活動,并按照SBR(i)m,n降序、ΔT(i)m,n 升序排列得到B ；5 if (B≠?)6 {7 TS(B(0))=ΔT(B(0)),TS=TS-TS(B(0))；8 將活動 B (0)移 出 A；9 }10 }End

該算法能夠?qū)⑷诸~外的時間資源合理的在活動之間進(jìn)行分配,從而產(chǎn)生最優(yōu)的調(diào)度方案.假設(shè)現(xiàn)有順序串聯(lián)的兩個活動1 和2,其候選服務(wù)集分別為S(1)={(T,C)}={(5,9),(8,8)},S(2)={(T,C)}={(6,10),(8,8)},且根據(jù)工作流執(zhí)行時間下界求得其松弛時間為TS(WF)=3.從前面的分析可以知道,因此,給活動2 分配兩個單位的松弛時間,即選擇第2 個候選服務(wù)作為執(zhí)行服務(wù).剩余的1 個單位時間資源由于無法提供給活動1 以滿足其最低的時間增量,將不再繼續(xù)優(yōu)化.

2.2 靜態(tài)調(diào)度

靜態(tài)調(diào)度需要考慮活動的拓?fù)浣Y(jié)構(gòu),由關(guān)鍵活動優(yōu)先級可知對于順序和“或”結(jié)構(gòu)松弛時間的再分配只影響單個活動,而“與”結(jié)構(gòu)會影響到整個控制塊.因此,需 要對“與”結(jié)構(gòu)進(jìn)行單獨說明.

圖2 “與”控制結(jié)構(gòu)

以圖2所示的“與”控制結(jié)構(gòu)為例,branch(1),branch(2)...branch(i)分別表示每條支路,假設(shè)branch(i)是子關(guān)鍵路徑.現(xiàn)根據(jù)松弛時間分配策略為某個關(guān)鍵活動m分 配了 ΔT的松弛時間,則可求得“與”控制塊新的截止期限為(D(branch(i))+ΔT),因此其他非關(guān)鍵路徑支路獲得的松弛時間為(D(branch(i))+ΔT-D(branch(n))),1 ≤n≤i-1.此時,可在每條支路內(nèi)部按照松弛時間分配策略再對調(diào)度進(jìn)行調(diào)整.

考慮工作流控制結(jié)構(gòu)的靜態(tài)調(diào)度算法(Static Scheduling Considering Workflow Control Structure,SSCWCS)如下:

算法2.SSCWCS 算法輸入:〈 N,E〉,D (WF)；輸出:D (i)；Begin 1 為每個活動選擇執(zhí)行最快的服務(wù),以此求得工作流的關(guān)鍵路徑CP,并計算其執(zhí)行時間下界D (CP)min；2 if (D (WF)＜D(CP)min )3 {4 提醒管理者需要修改 D (WF)；5 }6 else if(D (WF)＞D(CP)min)7 {8 計算工作流的松弛時間TS=D(WF)-D(CP)min；

9 將關(guān)鍵活動按照拓?fù)浣Y(jié)構(gòu)分類,分別求得；for(i=0;i＜4;i++)B=[{CPand(i)},{CPs(i)},{CPor(i)},{N-({CPand(i)}∪{CPs(i)}∪{CPor(i)})}]10 11 {12 將 分別代入算法1 進(jìn)行優(yōu)化；13 }B(0)≠?A=B(i),TS 14 if ()15 {16 計算“與”關(guān)鍵支路新的截止期限 D (branch(CPand))′并將其作為整個控制塊新的截止期限；for(i=0;i＜length(and);i++)17 18 {19 if ()20 {21 TS(branch(i))=D(branch(CPand))′-D(branch(i)),按照算法1 對該支路進(jìn)行調(diào)優(yōu)；22 }23 }24 }25 }Endbranch(i)≠branch(CPand)

2.3 動態(tài)監(jiān)控

由于“或”結(jié)構(gòu)在流程定義階段無法確定實際運行過程中所選擇的支路,因此靜態(tài)調(diào)度并未對非關(guān)鍵路徑支路和關(guān)鍵路徑支路設(shè)置相同的截止期限.這就需要在執(zhí)行過程中,為“或”結(jié)構(gòu)設(shè)置監(jiān)測點,根據(jù)選擇的支路動態(tài)的為后續(xù)未執(zhí)行的活動重新生成調(diào)度方案.

通過為每個“或”分支活動設(shè)置監(jiān)測點,進(jìn)而監(jiān)聽該活動的結(jié)束事件,并根據(jù)輸出條件判斷后續(xù)所選擇的支路.若選擇的是關(guān)鍵路徑支路,則不更改現(xiàn)有的調(diào)度方案,否則對其進(jìn)行優(yōu)化.“或”結(jié)構(gòu)動態(tài)監(jiān)控優(yōu)化算法(OR Dynamic Monitoring,ORDM)如下.

算法3.ORDM 算法輸入:〈 N,E〉,D (WF)；輸出:D (i)；Begin 1 找出所有的“或”控制結(jié)構(gòu),并設(shè)置“或”分支活動 ior_split為監(jiān)測點；2 監(jiān)聽ior_split 的 結(jié)束事件,記錄其完成時間TF(ior_split),并根據(jù)輸出條件判定后續(xù)選擇的支路branch；3 if (branch=branch(CP))4 {5 按照靜態(tài)調(diào)度方案對活動進(jìn)行調(diào)度；6 }7 else 8 {9 根據(jù)當(dāng)前的調(diào)度方案求得未完成活動的關(guān)鍵路徑CP′及其需要消耗的時間D (CP′)；

10 D (WF)′=D(WF)-TF(ior_split)；11 分別將CP=CP′,D (CP)min=D(CP′),D (WF)=D(WF)′代入算法2,對未完成的活動進(jìn)行調(diào)優(yōu)；12 }End

算法3 動態(tài)監(jiān)控“或”結(jié)構(gòu)的執(zhí)行情況,規(guī)避了為所有“或”分支分配相同截止期限而造成效益無法最大化的情況的出現(xiàn).本文提出的動態(tài)監(jiān)控思路同樣適合于流程執(zhí)行過程中出現(xiàn)的簡單異常,如服務(wù)的延遲、異常導(dǎo)致服務(wù)不可用.此時,可以把異常節(jié)點至結(jié)束活動的拓?fù)洚?dāng)作是新的工作流,并按照算法3 中步驟8-12 重新調(diào)度.其它復(fù)雜的異常處理將是下一步研究的對象.

3 實例

本章對前文提出的調(diào)度方法進(jìn)行實例應(yīng)用.圖3是虛擬科學(xué)分析過程的DAG 模型,表3是模型中每個活動對應(yīng)的候選服務(wù)集合,時間單位為分鐘(min),費用單位為人民幣(￥).設(shè)定工作流的開始時間為0,截止期限為110.

圖3 工作流DAG 模型

表3 活動候選服務(wù)集合

3.1 關(guān)鍵路徑時間下界

每個活動選擇耗時最短的服務(wù)的條件下,按照如下步驟求得關(guān)鍵路徑執(zhí)行時間的下界.

(1) “與”結(jié)構(gòu)

T(3,4)min=T(3)min+T(4)min=6+10=16,T(5)min=12,T(3,4)min＞T(5)min,因此關(guān)鍵路徑為活動3,4.

(2) “或”結(jié)構(gòu)

T(8)min=5,T(9)min=15,T(9)min＞T(8)min,所以關(guān)鍵支路為活動9.

順序活動處于關(guān)鍵路徑上,因此整個工作流的關(guān)鍵路徑由活動1,2,3,4,6,7,9,10,11 組成,其執(zhí)行時間下界為D(CP)min=T(1)min+T(2)min+T(3,4)min+T(6)min+T(7)min+T(9)min+T(10)min+T(11)min=94.

3.2 松弛時間分配

工作流的松弛時間TS(WF)=D(WF)-D(CP)min=110-94=16.將關(guān)鍵活動按照所處的控制結(jié)構(gòu)分類得到 {CPand(i)}={3,4},{CPs(i)}={1,2,6,7,10,11},{CPor(i)}={9}.根據(jù)算法2 分配松弛時間.

(1) “與”關(guān)鍵活動

活動3 只有一個候選服務(wù),已經(jīng)是最優(yōu)方案；活動4 的 ΔT=5 ＜16,所以其可以獲得5 個單位的額外時間,此時工作流的剩余松弛時間TS(WF)=16-5=11.

(2) 順序關(guān)鍵活動

同步活動6,7 只有單個候選服務(wù),所以{ΔT}={ΔT(1),ΔT(2),ΔT(10),ΔT(11)}={2,2,4,8},{S BR}={0.5,0.5,0.5,1}.因此活動11 將優(yōu)先獲得8 個單位的時間資源,此時工作流剩余的松弛時間為3 個單位.活動1,2 的服務(wù)替換產(chǎn)生相同的效益,因此給活動1 分配2 個單位時間.

經(jīng)過上述的步驟,工作流剩余1 個單位的松弛時間,無法滿足其它活動更換服務(wù)所需的最小時間變量,且又因為調(diào)整過后的“與”控制結(jié)構(gòu)中活動5 沒有可替換的服務(wù),調(diào)優(yōu)結(jié)束.工作流優(yōu)化過后的調(diào)度方案如表4所示.

表4 活動執(zhí)行服務(wù)

3.3 動態(tài)監(jiān)控

活動7 處設(shè)置監(jiān)測點,TF(7)=T(1,2,3,4,6,7)=75,根據(jù)其輸出條件判斷活動8 所在的支路被選中,此時活動8,10,11 組成了新的工作流WF′.其松弛時間TS=D(WF)-TF(7)-T(8,10,11)=110-75-24=11,ΔT(8)=2,ΔT(10)=4,易知活動8,10 均可分得對應(yīng)的額外時間資源,即選擇成本最低的服務(wù).

4 結(jié)束語

為了更好地解決云環(huán)境下科學(xué)工作流調(diào)度過程中的時間-成本優(yōu)化問題,在DAG 模型中增加了對工作流“或”控制結(jié)構(gòu)的支持,并提出了關(guān)鍵活動優(yōu)先級的概念,此舉彌補了現(xiàn)有基于DAG 的調(diào)度算法無法支持“或”結(jié)構(gòu)的不足；同時,給出了活動的松弛時間分配策略,并基于此提出了云環(huán)境下科學(xué)工作流的調(diào)度算法,該方法由靜態(tài)調(diào)度和動態(tài)監(jiān)控組成.最后通過虛擬的科學(xué)分析過程對上述的算法進(jìn)行了說明和應(yīng)用.