面向可靠性的網(wǎng)格工作流調(diào)度模型與算法研究.pdf

1、隨著網(wǎng)格技術(shù)的發(fā)展和應(yīng)用，研究重點已經(jīng)從實現(xiàn)網(wǎng)格系統(tǒng)各核心組件及其基本功能逐漸轉(zhuǎn)向如何保障網(wǎng)格提供非平凡的服務(wù)質(zhì)量(QoS)?？煽啃跃褪欠浅Ｖ匾腝oS指標之一。隨著網(wǎng)格應(yīng)用領(lǐng)域的不斷擴展和深入，網(wǎng)格可靠性問題成為制約網(wǎng)格技術(shù)全面應(yīng)用的重要因素。然而，由于網(wǎng)格系統(tǒng)本身的復雜性、動態(tài)性和異構(gòu)性，使得網(wǎng)格可靠性難以得到充分保障。近年來，研究者不僅針對網(wǎng)格系統(tǒng)的可靠性建模、評估、分析技術(shù)展開研究，而且在網(wǎng)格系統(tǒng)架構(gòu)的搭建、網(wǎng)格資源管理和任務(wù)調(diào)

2、度等方面也開始融入可靠性方面的內(nèi)容。網(wǎng)格工作流已逐漸成為網(wǎng)格環(huán)境中設(shè)計大規(guī)?？茖W應(yīng)用的典型范式，其調(diào)度問題是網(wǎng)格工作流中關(guān)鍵問題之一，直接影響網(wǎng)格工作流是否能夠成功、高效地執(zhí)行。因此，面向可靠性的網(wǎng)格工作流調(diào)度研究具有良好理論價值和實用意義。
　　 網(wǎng)格的動態(tài)性和自治性等特征給工作流的成功、高效運行帶來了巨大挑戰(zhàn)，為了有效保障和提高網(wǎng)格環(huán)境中任務(wù)執(zhí)行的可靠性能與性能，本文基于對網(wǎng)格系統(tǒng)中不同層面可靠性研究的深入分析，針對網(wǎng)格工作

3、流調(diào)度所面臨的難點和挑戰(zhàn)，重點研究高效的網(wǎng)格工作流調(diào)度機制以及提高工作流執(zhí)行可靠性的策略，論文的主要工作和創(chuàng)新包括：
　　 (1)研究并提出了基于M/M/N型可修排隊系統(tǒng)的網(wǎng)格資源可靠性評估模型及相應(yīng)的動態(tài)網(wǎng)格工作流調(diào)度模型
　　 針對網(wǎng)格資源會發(fā)生失效并以一定概率進行恢復的情況，采用M/M/N型可修排隊系統(tǒng)建立了一個多集群環(huán)境中網(wǎng)格資源的可靠性和動態(tài)處理能力的綜合評估模型。通過模型求解得到各資源站點的穩(wěn)態(tài)可用度、平均隊

4、長等指標，據(jù)此估算各資源站點上的任務(wù)平均排隊等待時間。該模型綜合考慮了網(wǎng)格資源可能失效以及各資源站點的動態(tài)負載情況，更加符合網(wǎng)格系統(tǒng)的實際情況。基于所提出的資源可靠性評估模型，研究提出了一個排隊時間感知的動態(tài)網(wǎng)格工作流調(diào)度模型并設(shè)計了相應(yīng)的動態(tài)網(wǎng)格工作流調(diào)度算法(QTADGWS)。該算法采用基于列表的調(diào)度方式，通過最大化程度重疊工作流任務(wù)的數(shù)據(jù)傳輸時間和排隊等待時間來獲取最優(yōu)性能。仿真實驗結(jié)果表明相較HEFT、CPOP算法，QTADGW

5、S算法在完成時間和任務(wù)平均等待時間等方面能有更好的性能。
　　 (2)提出了用戶截止時間約束下的可靠工作流調(diào)度算法
　　 針對多集群網(wǎng)格環(huán)境，采用Markov過程對資源站點的處理單元進行可用性建模，并結(jié)合隨機服務(wù)模型描述網(wǎng)格資源的動態(tài)負載壓力和動態(tài)處理能力。提出了工作流截止時間滿意度的概念，并基于資源的可用性和動態(tài)服務(wù)模型，給出了工作流截止時間滿意度的計算方法。基于最大截止時間滿意度優(yōu)先的思想，將工作流全局截止時間劃分問

6、題描述為一個約束下的非線性規(guī)劃問題并通過已有方法求解，進而提出了一種截止時間滿意度增強的工作流調(diào)度算法(DSESAW)。仿真實驗結(jié)果驗證了該算法在網(wǎng)格環(huán)境的適應(yīng)性和用戶截止時間保障方面的有效性。
　　 (3)針對實際網(wǎng)格環(huán)境提出了自適應(yīng)工作流調(diào)度機制和可靠性增強策略
　　 針對實際的網(wǎng)格環(huán)境-Open Science Grid(OSG)，基于工作流系統(tǒng)Swift，提出了一個多階段網(wǎng)格工作流調(diào)度機制，主要包括資源站點發(fā)現(xiàn)、

7、資源站點初始評估以及資源站點動態(tài)評估和選擇。通過基于時間序列的性能預測值評估各資源站點的初始性能，提出了一個基于網(wǎng)格資源站點自適應(yīng)評分機制的選擇算法。為了提高工作流執(zhí)行的可靠性并盡可能縮短執(zhí)行時間，設(shè)計了一個增量式的任務(wù)副本策略，并采用各資源站點任務(wù)排隊等待時間的經(jīng)驗累積分布函數(shù)圖來優(yōu)化任務(wù)副本的設(shè)置參數(shù)。在OSG中完成的大量實驗結(jié)果表明，所提出的算法和策略能夠有效減小工作流調(diào)度長度和作業(yè)拒絕率。引入多階段工作流調(diào)度機制及優(yōu)化策略后，能