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

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

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

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

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

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

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