[發(fā)明專利]一種云環(huán)境下的工作流調(diào)度與數(shù)據(jù)分配方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201711468801.0
• 申請(qǐng)日: 2017-12-28
• 公開（公告）號(hào): CN108182109B
• 公開（公告）日: 2021-08-31
• 發(fā)明（設(shè)計(jì)）人: 陳羽中;黃啟成;郭文忠
• 申請(qǐng)（專利權(quán)）人: 福州大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/50;H04L29/08
• 代理公司: 福州元?jiǎng)?chuàng)專利商標(biāo)代理有限公司 35100
• 代理人: 蔡學(xué)俊

1.一種云環(huán)境下的工作流調(diào)度與數(shù)據(jù)分配方法，其特征在于，包括如下步驟：

步驟A：獲取云平臺(tái)當(dāng)前的工作流；

步驟B：根據(jù)調(diào)度模型計(jì)算工作流中每個(gè)任務(wù)的高度，并按照高度升序排列任務(wù)；

步驟C：使用粒子群優(yōu)化算法，每個(gè)粒子表示一種工作流調(diào)度與數(shù)據(jù)分配方案，以工作流的執(zhí)行時(shí)間以及執(zhí)行成本為優(yōu)化目標(biāo)，獲得全局最優(yōu)的粒子編碼；

步驟D：將全局最優(yōu)的粒子編碼解碼成工作流調(diào)度與數(shù)據(jù)分配方案并輸出；

所述步驟B中，計(jì)算工作流中每個(gè)任務(wù)的高度并按照高度升序排列任務(wù)，包括以下步驟：

步驟B1：構(gòu)造工作流的有向無(wú)環(huán)圖G，方法為：

工作流由n個(gè)相互依賴的任務(wù)T＝{T₁,T₂,…,T_n}構(gòu)成，采用有向無(wú)環(huán)圖G＝(V,E)表示，其中V表示節(jié)點(diǎn)集合，V＝T，E表示邊集合，E＝{e_ij|T_i∈T∧T_j∈T∧T_i∈pred(T_j)}；其中任務(wù)T_j的直接前驅(qū)任務(wù)的集合表示為pred(T_j)，直接后續(xù)任務(wù)的集合表示為succ(T_j)，只有當(dāng)pred(T_j)中的任務(wù)全部執(zhí)行完成并且數(shù)據(jù)傳輸?shù)饺蝿?wù)T_j所在的虛擬機(jī)時(shí)，任務(wù)T_j才開始執(zhí)行，沒有前驅(qū)任務(wù)的任務(wù)節(jié)點(diǎn)稱為開始任務(wù)T_entry，沒有后繼任務(wù)的任務(wù)節(jié)點(diǎn)稱為結(jié)束任務(wù)T_exit；T_i∈pred(T_j)表示任務(wù)T_i是任務(wù)T_j的直接前驅(qū)任務(wù)，即任務(wù)T_j是任務(wù)T_i的直接后繼任務(wù)，任務(wù)T_j依賴于任務(wù)T_i；e_ij表示任務(wù)T_i和任務(wù)T_j間的邊，e_ij的值代表任務(wù)T_i需傳輸給任務(wù)T_j的數(shù)據(jù)量大小；

步驟B2：從工作流的開始任務(wù)T_entry出發(fā)，遍歷工作流的有向無(wú)環(huán)圖G，計(jì)算每個(gè)任務(wù)T_i的初始高度Height_init(T_i)；其中，任務(wù)T_i的初始高度Height_init(T_i)的計(jì)算方法如下：

步驟B3：從工作流的結(jié)束任務(wù)T_exit出發(fā)，遍歷工作流的有向無(wú)環(huán)圖G，計(jì)算每個(gè)任務(wù)T_i的高度Height(T_i)；其中，任務(wù)T_i的高度Height(T_i)的計(jì)算方法如下：

其中，表示產(chǎn)生位于區(qū)間范圍內(nèi)的隨機(jī)整數(shù)；

通過(guò)計(jì)算工作流中每個(gè)任務(wù)T_i的高度Height(T_i)，從而確定任務(wù)T_i執(zhí)行的順序，然后根據(jù)任務(wù)的高度升序排列，構(gòu)成任務(wù)的拓?fù)漤樞颍擁樞蚴潜３秩蝿?wù)之間優(yōu)先級(jí)約束的線性順序；

步驟B4：根據(jù)每個(gè)任務(wù)T_i的高度Height(T_i)，按照高度升序排列任務(wù)，構(gòu)成任務(wù)的拓?fù)漤樞颍?/p>

所述步驟C中，使用粒子群優(yōu)化算法，以工作流的執(zhí)行時(shí)間以及執(zhí)行成本為優(yōu)化目標(biāo)，獲得全局最優(yōu)的粒子編碼，包括以下步驟：

步驟C1：初始化粒子群，設(shè)置粒子群算法參數(shù)，包括粒子數(shù)量、慣性因子、認(rèn)知能力因子、社會(huì)學(xué)習(xí)因子、迭代次數(shù)、種群規(guī)模、粒子維數(shù)、粒子速度控制范圍；其中，初始化粒子群，粒子的編碼方式如下：

X_i＝{x_i,1,x_i,2,…,x_i,N}是粒子群X中的第i個(gè)粒子，表示工作流調(diào)度問(wèn)題的第i個(gè)調(diào)度方案，N是工作流所包含的元素?cái)?shù)量，工作流元素包括構(gòu)成工作流的任務(wù)和數(shù)據(jù)，X_i的每一維表示工作流元素與服務(wù)節(jié)點(diǎn)的映射關(guān)系，x_i,j的值表示該工作流元素所在的虛擬機(jī)的序號(hào)，即將工作流的第j個(gè)元素分配到序號(hào)為x_i,j的虛擬機(jī)，虛擬機(jī)的序號(hào)的取值范圍為[1,m]，m為云平臺(tái)中的虛擬機(jī)節(jié)點(diǎn)數(shù)；

步驟C2：計(jì)算粒子群中每個(gè)粒子的適應(yīng)度值，根據(jù)粒子的適應(yīng)度值，記錄個(gè)體歷史最優(yōu)粒子和種群最優(yōu)粒子；其中，粒子群中粒子的適應(yīng)度值的計(jì)算方法如下：

fitness＝α.T_total+β.C_total

其中，α、β表示權(quán)重系數(shù)，T_total表示工作流執(zhí)行的時(shí)間代價(jià)，C_total表示工作流執(zhí)行的成本代價(jià)，具體定義如下：

C_total＝Cost_exe(G)+Cost_tx(G)

其中，工作流執(zhí)行的時(shí)間代價(jià)T_total定位為從用戶提交一個(gè)工作流到獲得執(zhí)行結(jié)果的總時(shí)間，即結(jié)束任務(wù)T_exit的完成時(shí)間工作流執(zhí)行的成本代價(jià)C_total包括工作流的任務(wù)處理代價(jià)Cost_exe(G)和數(shù)據(jù)傳輸代價(jià)Cost_tx(G)；

工作流執(zhí)行的時(shí)間代價(jià)T_total的計(jì)算方法如下：

首先定義工作流中的任務(wù)T_i的任務(wù)開始時(shí)間和任務(wù)完成時(shí)間分別為ST_i和FT_i，則ST_i定義如下：

其中VM(T_i)表示任務(wù)T_i所分配的虛擬機(jī)的序號(hào)，表示和任務(wù)T_i分配到同一個(gè)虛擬機(jī)(即VM(T_k)＝VM(T_i))且是最晚先于任務(wù)T_i被虛擬機(jī)調(diào)度執(zhí)行的任務(wù)T_k(即T_k→T_j)的任務(wù)完成時(shí)間；表示傳輸任務(wù)T_i所需的全部數(shù)據(jù)所需的時(shí)間；TRT_ji為任務(wù)T_j存在任務(wù)T_i所需的數(shù)據(jù)D_ji時(shí)的數(shù)據(jù)傳輸時(shí)間，定義如下：

其中，VM(T_j)表示任務(wù)T_j所分配的虛擬機(jī)的序號(hào)，VM(D_ji)表示數(shù)據(jù)D_ji所放置的虛擬機(jī)的序號(hào)，表示任務(wù)T_j所分配的虛擬機(jī)與數(shù)據(jù)D_ji所放置的虛擬機(jī)之間的鏈路帶寬；表示數(shù)據(jù)D_ji所放置的虛擬機(jī)與任務(wù)T_i所分配的虛擬機(jī)之間的鏈路帶寬；

根據(jù)ST_i的定義，F(xiàn)T_i定義為：

其中為任務(wù)T_i在虛擬機(jī)vm_j上被調(diào)度執(zhí)行后的執(zhí)行時(shí)間；

根據(jù)上述定義，當(dāng)一個(gè)工作流的任務(wù)被調(diào)度之后，工作流的執(zhí)行時(shí)間就等于結(jié)束任務(wù)T_exit的完成時(shí)間，即：

工作流的任務(wù)處理代價(jià)Cost_exe(G)的計(jì)算方法如下：

其中，VM(T_i)表示任務(wù)T_i分配的虛擬機(jī)的序號(hào)，表示任務(wù)T_i在分配的虛擬機(jī)VM(T_i)上的處理代價(jià)，工作流的任務(wù)處理代價(jià)Cost_exe(G)即為構(gòu)成工作流的各個(gè)任務(wù)的處理代價(jià)之和；的具體定義如下：

假定VM(T_i)＝j(luò)，則

其中，DS_i表示任務(wù)T_i的數(shù)據(jù)大小，PS_j表示虛擬機(jī)vm_j的處理能力，RC_j表示虛擬機(jī)vm_j的租賃費(fèi)用；

工作流執(zhí)行過(guò)程中各個(gè)任務(wù)間的數(shù)據(jù)傳輸代價(jià)Cost_tx(G)的計(jì)算方法如下：

其中VM(T_i)表示任務(wù)T_i分配的虛擬機(jī)的序號(hào)，VM(D_ij)表示數(shù)據(jù)D_ij所放置的虛擬機(jī)的序號(hào)，D_ij是任務(wù)間的數(shù)據(jù)傳輸矩陣D中的元素，表示任務(wù)T_i和任務(wù)T_j之間需要傳輸?shù)臄?shù)據(jù)的大小，單位為MB，數(shù)據(jù)傳輸矩陣D定義如下：

表示任務(wù)T_i所分配的虛擬機(jī)節(jié)點(diǎn)與數(shù)據(jù)D_ij所放置的虛擬機(jī)節(jié)點(diǎn)之間的數(shù)據(jù)鏈路的租賃價(jià)格，單位是$/MB；表示數(shù)據(jù)D_ij所放置的虛擬機(jī)節(jié)點(diǎn)與任務(wù)T_j所分配的虛擬機(jī)節(jié)點(diǎn)之間的數(shù)據(jù)鏈路的租賃價(jià)格；

步驟C3：根據(jù)更新策略，更新每個(gè)粒子的速度和位置，并計(jì)算更新后的粒子適應(yīng)度值；其中，粒子位置的更新方法如下：

對(duì)于任務(wù)和虛擬機(jī)的分配問(wèn)題，需要把粒子的位置轉(zhuǎn)化為虛擬機(jī)節(jié)點(diǎn)的序號(hào)，因此在對(duì)粒子的位置進(jìn)行更新時(shí)，采用取整的方法對(duì)粒子的位置進(jìn)行離散值的轉(zhuǎn)換：

其中，表示對(duì)實(shí)數(shù)x_ij向下取整；

步驟C4：判斷是否滿足最大迭代次數(shù)，是則輸出全局最優(yōu)粒子編碼，結(jié)束迭代，否則返回步驟C2，繼續(xù)迭代。