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

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

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

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

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

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

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

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