實(shí)例密集型商務(wù)工作流任務(wù)調(diào)度與分配策略研究.pdf

1、隨著電子商務(wù)的迅速發(fā)展，商業(yè)和政府機(jī)構(gòu)通常需要處理大量的服務(wù)請求，這些服務(wù)請求通常是一個個較小的業(yè)務(wù)流程，需要在有限制的時間內(nèi)完成處理，為有時序限制的實(shí)例密集型商務(wù)工作流。當(dāng)前商業(yè)領(lǐng)域的數(shù)據(jù)量越來越大，如何確保在時序限制內(nèi)大量實(shí)例密集型業(yè)務(wù)流程的實(shí)時完成已成為對服務(wù)質(zhì)量具有挑戰(zhàn)性的問題，因?yàn)槿魏蔚臅r間延誤都會造成諸如用戶滿意度、經(jīng)濟(jì)損失甚至是處罰等嚴(yán)重的后果。云計算的迅速發(fā)展為商務(wù)工作流的處理帶來了很大的機(jī)遇，然而，由于云服務(wù)的動態(tài)特性

2、，缺少服務(wù)質(zhì)量管理策略成為其大范圍部署的嚴(yán)重障礙。對于當(dāng)今利用云計算資源的軟件系統(tǒng)來說，對有時序限制的大量處理過程提供滿意的服務(wù)質(zhì)量是一個關(guān)鍵的研究問題。考慮這些復(fù)雜的實(shí)例密集型商務(wù)流程，確保在有時間限制的范圍內(nèi)按時完成所有任務(wù)的調(diào)度對服務(wù)質(zhì)量的提高有很大的影響;對所有任務(wù)的運(yùn)行狀況進(jìn)行有效的監(jiān)控，提高任務(wù)分配的效率和可靠性，對于商業(yè)應(yīng)用來說則是個很重要的標(biāo)準(zhǔn)。
　　本文主要的研究工作概況如下：
　　(1)本文首先提出了幾種

3、調(diào)度模型，粗粒度、細(xì)粒度、資源池調(diào)度通用模型和理論最短執(zhí)行時間調(diào)度模型。由于商業(yè)流程通常是一個較小的工作流實(shí)例，每個實(shí)例的執(zhí)行時間通常在某一固定的區(qū)間內(nèi)。對于不同的實(shí)例，其起始和結(jié)束時間通常有一定的要求，并且不同的實(shí)例有時序關(guān)系，因此提出使用區(qū)間調(diào)度的思想來處理上述特性。商業(yè)流程中，由于不同的任務(wù)存在著時序依賴關(guān)系，可以很好的利用區(qū)間調(diào)度方法將多個任務(wù)分配至不同處理器上執(zhí)行，為商務(wù)工作流程的并行化調(diào)度提供基礎(chǔ)。
　　(2)在區(qū)間調(diào)

4、度基礎(chǔ)上，利用有向無環(huán)圖（Directed Acyclic Graph，DAG）模型，考慮任務(wù)各自的時序限制，本文深入研究有多個串行和并行子活動的DAG任務(wù)實(shí)時調(diào)度。給出了一種有效的DAG任務(wù)調(diào)度模型，將調(diào)度任務(wù)分成串行和可并行調(diào)度部分，提取DAG任務(wù)的有效主路徑，然后對任務(wù)按有效主路徑并行展開，根據(jù)任務(wù)的執(zhí)行截止期限與其子活動的時序限制，提出DAG任務(wù)的拉伸調(diào)度策略，使多個任務(wù)調(diào)度時，盡可能減少對處理器資源的占用，保證其他任務(wù)能有效的

5、進(jìn)行調(diào)度，多個任務(wù)各自都可以滿足時序限制的要求。
　　(3)針對無單個任務(wù)響應(yīng)時限約束的流程，將商業(yè)任務(wù)完全拉伸后，本文提出一種動態(tài)優(yōu)先權(quán)調(diào)度策略(DPS)。主要基于Min-Min啟發(fā)式算法和貪心思想策略，將整個商務(wù)工作流的調(diào)度過程中的所有調(diào)度任務(wù)按使用的云處理器的數(shù)量進(jìn)行分批處理，對每批調(diào)度任務(wù)所需的調(diào)度時間進(jìn)行預(yù)測并排序，按任務(wù)所需的執(zhí)行時間，將不同執(zhí)行時長的任務(wù)賦予不同的優(yōu)先級，在調(diào)度過程中，保持各云處理器執(zhí)行狀態(tài)的一致性。

6、DPS算法的時間復(fù)雜度為O(m2n)，在效率上比Min-Min提高很多。通過與理論最短執(zhí)行時間相比，二者的比值能夠達(dá)到98.5％以上，特別是當(dāng)調(diào)度的數(shù)據(jù)量達(dá)到1，000，000個任務(wù)時，該比值能到達(dá)接近99.9％，充分證明了DPS算法對于大量任務(wù)是一個可以獲得接近最優(yōu)的調(diào)度算法。
　　(4)為了實(shí)現(xiàn)對大量商業(yè)流程的調(diào)度過程進(jìn)行監(jiān)控，判斷任務(wù)執(zhí)行是否會出現(xiàn)時序沖突，本文提出一種商務(wù)工作流調(diào)度過程監(jiān)控方案。沿著商務(wù)工作流執(zhí)行的時間軸將