[發(fā)明專利]基于自頂向下任務(wù)分級的云工作流任務(wù)調(diào)度方法

在審

• 申請?zhí)枺?/td>: 201710315904.7
• 申請日: 2017-05-08
• 公開（公告）號: CN107133091A
• 公開（公告）日: 2017-09-05
• 發(fā)明（設(shè)計(jì)）人: 張小慶
• 申請（專利權(quán)）人: 武漢輕工大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06N3/00;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及云計(jì)算技術(shù)領(lǐng)域，特別是一種基于自頂向下任務(wù)分級的云工作流任務(wù)調(diào)度方法。

背景技術(shù)

云計(jì)算以軟硬件虛擬化技術(shù)為支撐，可以通過互聯(lián)網(wǎng)向用戶提供動態(tài)可擴(kuò)展的服務(wù)，其可提供的服務(wù)類型包括：軟件即服務(wù)SaaS、基礎(chǔ)設(shè)施即服務(wù)IaaS和平臺即服務(wù)PaaS。由于其商業(yè)化的特征和市場為導(dǎo)向的商業(yè)模型，用戶在使用諸如計(jì)算、存儲和網(wǎng)絡(luò)等云服務(wù)時通常是有償付費(fèi)的，使用模型類似于日常生活中使用的水、電、煤氣等資源。除此之外，云服務(wù)的提供必須以滿足用戶服務(wù)質(zhì)量QoS為最終目標(biāo)。云計(jì)算環(huán)境中的工作流調(diào)度問題即是實(shí)現(xiàn)各個相互關(guān)聯(lián)的工作流任務(wù)與可用云資源間的映射問題，調(diào)度目標(biāo)需要滿足用戶定義的目標(biāo)函數(shù)。然而，工作流調(diào)度本身是NP問題，多項(xiàng)式時間內(nèi)無法找到其最優(yōu)化。

工作流調(diào)度算法涉及兩種類型：盡力服務(wù)調(diào)度和QoS約束調(diào)度。盡力服務(wù)調(diào)度算法主要是最小化工作流調(diào)度時間為目標(biāo)，而未考慮資源訪問代價，主要應(yīng)用于網(wǎng)格計(jì)算環(huán)境中，代表性算法有min-min、max-min和suffrage等。而網(wǎng)格計(jì)算環(huán)境與目前的商業(yè)云計(jì)算環(huán)境具有明顯的不同，包括：1、云資源是按需動態(tài)提供的，用戶對資源類型和數(shù)量的選擇是較為靈活的，而網(wǎng)格環(huán)境中的資源類型、數(shù)量或使用時間都是比較固定的；2、云環(huán)境中的資源使用均是有償付費(fèi)的，且資源的定價模型根據(jù)資源類型的不同而不同，因此，任務(wù)執(zhí)行代價將是必須考慮的要素，而網(wǎng)格環(huán)境中的任務(wù)調(diào)度通常只側(cè)重于執(zhí)行效率的優(yōu)化問題。而QoS約束調(diào)度算法則可以定義滿足不同需求和QoS的調(diào)度目標(biāo)。云計(jì)算具有商業(yè)化特征，比較執(zhí)行時間，其資源使用代價在調(diào)度過程中更是不可忽視的要素，因此，更適合以QoS約束調(diào)度進(jìn)行優(yōu)化。

現(xiàn)有QoS約束調(diào)度中，多以滿足用戶截止時間或預(yù)算約束進(jìn)行任務(wù)調(diào)度優(yōu)化，代表性算法有關(guān)鍵路徑算法IC-PCP、增強(qiáng)IC-PCP算法EIPR、分割均衡時間算法PBTS和改進(jìn)異質(zhì)最早完成時間算法BHEFT。以上算法的不足之處在于：忽略了云資源提供的動態(tài)彈性特征以及資源性能和代價異構(gòu)的特征，均無法直接應(yīng)用于云計(jì)算環(huán)境中工作流調(diào)度優(yōu)化。因此，需要尋找一種適用于云計(jì)算環(huán)境，結(jié)合任務(wù)特征和資源特征的云工作流調(diào)度QoS方法。

發(fā)明內(nèi)容

本發(fā)明通過自頂向下的任務(wù)分級，得到初始的任務(wù)執(zhí)行序列，使得調(diào)度方案的初始種群個體更加多樣化，能夠?qū)崿F(xiàn)滿足截止時間和預(yù)算約束的工作流執(zhí)行代價最優(yōu)化調(diào)度。

為了實(shí)現(xiàn)上述目的，本發(fā)明所采用的方法是：

步驟一：初始化工作流任務(wù)和主機(jī)資源相關(guān)參數(shù)、執(zhí)行時間ECT矩陣和執(zhí)行代價ECC矩陣；

步驟二：計(jì)算工作流中所有任務(wù)的自頂向下分級；

步驟三：根據(jù)任務(wù)的自頂向下分級數(shù)的降序排列依次分配任務(wù)至可用主機(jī)資源，以此產(chǎn)生初始種群的第一個遺傳個體；

步驟四：通過隨機(jī)將任務(wù)分配至可用主機(jī)資源的方式產(chǎn)生剩余種群個體，每個個體使用二維方式編碼，即一個種群個體為一種工作流任務(wù)調(diào)度方案（主機(jī)號，任務(wù)執(zhí)行序列）；

步驟五：如果不滿足遺傳終止條件，則繼續(xù)執(zhí)行以下步驟；否則，終止執(zhí)行；

步驟六：根據(jù)個體適應(yīng)度函數(shù)評估種群個體的適應(yīng)度；

步驟七：利用輪盤賭選擇策略從種群中選擇父親個體；

步驟八：在所有父親個體上利用交叉操作產(chǎn)生新的子個體；

步驟九：在新產(chǎn)生的子個體上應(yīng)用變異操作產(chǎn)生新的子個體；

步驟十：根據(jù)適應(yīng)度函數(shù)評估每個子個體；

步驟十一：增加有效子個體，產(chǎn)生新種群；

步驟十二：返回步驟五，直到遺傳終止。

與傳統(tǒng)的云計(jì)算環(huán)境中工作流的調(diào)度方法相比，本發(fā)明具有以下優(yōu)點(diǎn)：1、將用戶定義的截止時間和預(yù)算約束引入云工作流調(diào)度問題中，通過這種多約束方式使用工作流調(diào)度更適應(yīng)于云環(huán)境的商業(yè)化特征；2、改變了傳統(tǒng)工作流調(diào)度方法只注重執(zhí)行時間的優(yōu)化，忽略了工作流執(zhí)行代價優(yōu)化的局限性；3、通過工作流結(jié)構(gòu)中任務(wù)的特定位置，以自頂向下分級方式定義了任務(wù)的調(diào)度優(yōu)先級，以此產(chǎn)生了更加合理和更多樣性的遺傳種群個體；4、通過更簡單的方式定義了種群個體的編碼方式，能夠直接從編碼染色體中解碼出任務(wù)的調(diào)度方案；5、設(shè)計(jì)了互換變異和替代變異兩種形式的個體變異操作，進(jìn)一步豐富了種群個體；6、在適應(yīng)度函數(shù)設(shè)計(jì)中兼顧考慮了時間因素和代價因素，并以此為標(biāo)準(zhǔn)，得到滿足截止時間和預(yù)算約束的代價最小化的調(diào)度方法。

附圖說明

圖1為本發(fā)明的工作流結(jié)構(gòu)示意圖。

圖2為本發(fā)明的主機(jī)資源結(jié)構(gòu)圖。

圖3為本發(fā)明的基于自頂向下任務(wù)分級的一種調(diào)度結(jié)果圖。