云環(huán)境下基于失效感知的工作流調(diào)度算法研究.pdf

1、近年來(lái)，由于云計(jì)算的快速發(fā)展，大規(guī)模的云計(jì)算數(shù)據(jù)中心在全球各地被廣泛建立。隨著對(duì)云計(jì)算關(guān)注度的提高，云計(jì)算的功能(functionality)和復(fù)雜度(complexity)被研究人員廣泛研究。在云環(huán)境中，為了在滿(mǎn)足服務(wù)質(zhì)量的前提下，盡可能的降低服務(wù)成本，實(shí)現(xiàn)用戶(hù)和服務(wù)提供商雙方最大化收益問(wèn)題而引入了“云工作流”。通過(guò)將工作流技術(shù)與云計(jì)算相結(jié)合，一方面其可以將原先復(fù)雜的應(yīng)用需求按照業(yè)務(wù)邏輯進(jìn)行抽象定義和分解，對(duì)任務(wù)和資源進(jìn)行再次整理和靈

2、活配置，從而提高服務(wù)質(zhì)量;另一方面其可以實(shí)現(xiàn)任務(wù)自動(dòng)調(diào)度、任務(wù)監(jiān)控和資源分配的優(yōu)化與管理，因此可以大幅提高任務(wù)的執(zhí)行效率，能有效地提高云計(jì)算服務(wù)的質(zhì)量，減少執(zhí)行任務(wù)的費(fèi)用開(kāi)銷(xiāo)。
　　針對(duì)云工作流的調(diào)度問(wèn)題，不同的研究人員從完工時(shí)間最小化、執(zhí)行成本最低化、任務(wù)完成率最大化等多方面展開(kāi)研究。雖然當(dāng)前存在很多云工作流的調(diào)度方法，但都沒(méi)有針對(duì)云計(jì)算資源失效而建立調(diào)度模型，從而有效的規(guī)避和減少失效事件對(duì)云環(huán)境下工作流任務(wù)調(diào)度結(jié)果的影響。而在

3、云計(jì)算環(huán)境中，資源失效是不可避免的。由于資源失效將直接帶來(lái)系統(tǒng)性能降低、程序執(zhí)行提前終止甚至數(shù)據(jù)丟失等問(wèn)題，最終導(dǎo)致更多的任務(wù)不能在截止期內(nèi)完成、違約率增高，嚴(yán)重影響到云計(jì)算的可靠性和穩(wěn)定性，大大降低了服務(wù)質(zhì)量（Quality of Service，QoS）。同時(shí)由于工作流的各個(gè)任務(wù)之間存在時(shí)序約束和數(shù)據(jù)依賴(lài)。因此在工作流執(zhí)行的過(guò)程當(dāng)中，一旦某一個(gè)資源節(jié)點(diǎn)出現(xiàn)失效情況，不但導(dǎo)致此任務(wù)需要重新執(zhí)行，有可能整個(gè)工作流任務(wù)都需要重新執(zhí)行，嚴(yán)重

4、影響到云計(jì)算的效率，浪費(fèi)大量的計(jì)算資源。
　　基于當(dāng)前云計(jì)算環(huán)境下失效預(yù)測(cè)機(jī)制的國(guó)內(nèi)、外研究現(xiàn)狀和發(fā)展趨勢(shì)，結(jié)合云計(jì)算調(diào)度優(yōu)化特點(diǎn)，本文首先提出了基于失效感知的工作流調(diào)度模型，在調(diào)度過(guò)程中引入了失效預(yù)測(cè)機(jī)制和任務(wù)再調(diào)度策略，調(diào)度在滿(mǎn)足截止期要求的基礎(chǔ)上以最大化任務(wù)的完成率為目標(biāo)。在任務(wù)調(diào)度過(guò)程中，為工作流的每一個(gè)任務(wù)生成子截止時(shí)間。根據(jù)資源失效預(yù)測(cè)模型，當(dāng)所選的資源節(jié)點(diǎn)在任務(wù)的子截止期前發(fā)生失效時(shí)，提前把任務(wù)遷移到另一個(gè)可以順利完

5、成該任務(wù)的節(jié)點(diǎn)上，從而有效地規(guī)避資源失效對(duì)任務(wù)執(zhí)行帶來(lái)的影響，且在任務(wù)遷移過(guò)程中盡量把關(guān)鍵路徑任務(wù)分配到同一個(gè)性能較高的虛擬機(jī)上以減少任務(wù)之間數(shù)據(jù)傳輸?shù)拈_(kāi)銷(xiāo)，縮短完工時(shí)間，提高任務(wù)的完成率。然后對(duì)失效感知的工作流調(diào)度模型中的各個(gè)模塊功能進(jìn)行了詳細(xì)說(shuō)明，在此基礎(chǔ)上對(duì)失效預(yù)測(cè)機(jī)制、工作流模型和資源模型進(jìn)行定義，最后對(duì)模型進(jìn)行具體實(shí)現(xiàn)，給出了基于失效感知的工作流調(diào)度算法(BFGA)。該算法基于遺傳算法進(jìn)行改進(jìn)，算法中提出了新穎的三元組編碼方式

6、，在種群初始化過(guò)程中，采用隨機(jī)生成和使用已經(jīng)證明是有效的算法相結(jié)合的方式生成個(gè)體，以達(dá)到兼顧種群多樣性的目的。同時(shí)設(shè)計(jì)了符合工作流特點(diǎn)的交叉和變異方法，在個(gè)體進(jìn)行交叉變異之后又引入了調(diào)整算子對(duì)部分結(jié)果進(jìn)行局部微調(diào)，以避免陷入局部最優(yōu)，有效提高了收斂的速度。
　　通過(guò)CloudSim云計(jì)算仿真平臺(tái)對(duì)提出的模型和算法進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)借助不同類(lèi)型工作流應(yīng)用和改變仿真環(huán)境參數(shù)的方法進(jìn)行。通過(guò)與GA算法進(jìn)行對(duì)比，驗(yàn)證了算法的有效性。實(shí)驗(yàn)證

7、明BFGA算法相對(duì)一般的GA算法由于采用三元組的編碼方式，初始化種群采用了多種生成個(gè)體的方法，豐富了種群個(gè)體的多樣性，且在種群進(jìn)化過(guò)程中增加了調(diào)整算子，使其具有更好的收斂速度。其次，從失效預(yù)測(cè)準(zhǔn)確率、工作流任務(wù)數(shù)量、失效節(jié)點(diǎn)比率三個(gè)方面來(lái)驗(yàn)證BFGA算法與GA算法、First-fit算法、Pessimistic Best-fit算法以及不考慮失效的普通算法對(duì)任務(wù)調(diào)度的影響。實(shí)驗(yàn)證明當(dāng)失效預(yù)測(cè)準(zhǔn)確率大于50％時(shí)，BFGA算法相比其他算法具