截止日期約束的云中資源調(diào)度成本優(yōu)化算法

摘要：隨著越來越多的工作流應(yīng)用程序部署在云端，如何在滿足工作流截止期限約束的前提下優(yōu)化資源調(diào)度成本成為一個熱門研究領(lǐng)域。本文提出了一種截止日期約束的成本優(yōu)化（CODC） 算法。首先，合并工作流任務(wù)以減少不同實例之間的數(shù)據(jù)傳輸開銷。其次，關(guān)注父任務(wù)和子任務(wù)對當(dāng)前任務(wù)優(yōu)先級的影響，并考慮任務(wù)的子截止日期未被滿足的情況，以選擇最早完成任務(wù)執(zhí)行的實例。最后，在5 種工作流上與現(xiàn)有算法進行對比。與3 種對照算法相比，CODC 算法具有更低的工作流執(zhí)行成本。

關(guān)鍵詞：云計算；資源調(diào)度；截止日期約束；任務(wù)實例映射；成本優(yōu)化

中圖分類號：TP311 文獻標(biāo)志碼：A

云計算（Cloud Computing） 是將物理設(shè)備抽象為虛擬資源，以互聯(lián)網(wǎng)為媒介向用戶提供的一種新型分布式計算模式[1]。受益于服務(wù)器不斷提升的處理能力以及高速網(wǎng)絡(luò)的低延遲，用戶能夠隨時隨地通過服務(wù)接口動態(tài)地獲得可擴展的便捷資源，并根據(jù)實際使用量進行付費，而不需要大量的前期投資。成本優(yōu)化是云資源調(diào)度的重要考慮因素之一，它試圖在滿足服務(wù)質(zhì)量（Quality of Service， QoS） 的同時獲得最小的調(diào)度成本，然而任務(wù)之間的依賴約束使得可調(diào)度條件變得更加復(fù)雜[2]，QoS 的要求也間接地提高了在任務(wù)響應(yīng)時間和執(zhí)行成本之間尋找平衡的難度。因此，設(shè)計一種有效的資源調(diào)度方法來均衡任務(wù)執(zhí)行的時間和成本變得日益重要。

針對此問題，Chen 等[3] 提出了一種實時任務(wù)調(diào)度算法，旨在減少工作流響應(yīng)時間、降低執(zhí)行成本并提高服務(wù)實例的資源利用率。該算法基于任務(wù)的最早開始時間為任務(wù)分配調(diào)度優(yōu)先級，并根據(jù)任務(wù)的最晚完成時間將任務(wù)分配到合適的租賃實例上。Toussi 等[4] 提出了一種分而治之的調(diào)度算法，將工作流分為多個子工作流，針對每個子工作流的關(guān)鍵路徑上的任務(wù)選擇滿足截止日期和最低執(zhí)行成本的服務(wù)資源，并將關(guān)鍵路徑上的任務(wù)從工作流中刪除。王旖旎[5] 提出了一種主動響應(yīng)式工作流調(diào)度算法，在新工作流到達時將當(dāng)前所有工作流的就緒任務(wù)進行混合調(diào)度以滿足期限約束，并優(yōu)先選擇具有最小調(diào)度成本的計算資源。Ahmad 等[6] 提出了一種截止日期感知的啟發(fā)式算法，通過工作流最短執(zhí)行時間確定其截止日期，并實時監(jiān)控資源池動態(tài)，為工作流任務(wù)分配執(zhí)行成本最低的虛擬實例。張艮山等[7] 提出了一種期限預(yù)算雙重約束的工作流調(diào)度算法，根據(jù)工作流結(jié)構(gòu)特征對其進行分層處理，將任務(wù)劃分為若干個互不關(guān)聯(lián)的任務(wù)包，以提高調(diào)度過程中的并行程度。

盡管上述方法考慮了工作流任務(wù)之間的數(shù)據(jù)依賴關(guān)系，但未進行任務(wù)合并以降低數(shù)據(jù)傳輸成本，并忽略了父任務(wù)對于當(dāng)前任務(wù)優(yōu)先級的影響。此外，它們很少關(guān)注任務(wù)子截止日期未被滿足的情況。為了克服上述方法的不足，本文提出了一種截止日期約束的成本優(yōu)化（CODC） 算法，包括4 個調(diào)度階段：任務(wù)合并、任務(wù)優(yōu)先級分配、任務(wù)子截止日期分配和租賃實例選擇。CODC 算法的主要優(yōu)勢如下：

（1）明確云工作流任務(wù)合并條件，將滿足條件的任務(wù)進行合并，以減少不同實例之間的數(shù)據(jù)傳輸開銷；

（2）關(guān)注父任務(wù)以及子任務(wù)對于當(dāng)前任務(wù)優(yōu)先級的影響，給出優(yōu)化任務(wù)優(yōu)先級分配過程；

（3）設(shè)計每個任務(wù)的子截止日期，將工作流中的任務(wù)分離，以便在子截止日期的約束下分別調(diào)度任務(wù)，并選擇最早完成當(dāng)前任務(wù)執(zhí)行的實例。