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

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

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

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

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

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

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

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

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

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