[發(fā)明專利]一種基于BP-Tabu搜索的云任務(wù)負(fù)載均衡調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201710491607.8
• 申請日: 2017-06-26
• 公開（公告）號: CN107329815B
• 公開（公告）日: 2020-08-04
• 發(fā)明（設(shè)計(jì)）人: 陸佳煒;李杰;盧成炳;徐俊;高飛;肖剛;周煥;高燕煦
• 申請（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/455;G06F9/50
• 代理公司: 杭州斯可睿專利事務(wù)所有限公司 33241
• 代理人: 王利強(qiáng)

1.一種基于BP-Tabu搜索的云任務(wù)負(fù)載均衡調(diào)度方法，其特征在于：包括以下步驟：

第一步：形式化描述云計(jì)算環(huán)境下的負(fù)載均衡任務(wù)調(diào)度問題，并給出對于云計(jì)算環(huán)境下各元素相關(guān)定義，包括：云任務(wù)T、虛擬機(jī)資源VM、執(zhí)行時間矩陣CT、任務(wù)調(diào)度方案P、任務(wù)最早完成時間makespan、總?cè)蝿?wù)最優(yōu)完成時間和負(fù)載均衡度LB_p；

第二步：基于貪心算法思想求得任務(wù)調(diào)度初始解，使用對時間貪心的算法，對任務(wù)調(diào)度初始解進(jìn)行求解，過程為：先通過計(jì)算獲得每個任務(wù)在相應(yīng)虛擬機(jī)資源上的最小完成時間列表，然后在這些最小完成時間中，選取出其中的最大值與最小值進(jìn)行組合，如果該任務(wù)組合對相對于其他任務(wù)組合對分配時間最優(yōu)，就完成任務(wù)資源分配；如果不是最優(yōu)，即將任務(wù)對分配給其他虛擬機(jī)資源；若任務(wù)對分配存在多種方案，挑選任務(wù)運(yùn)行數(shù)最少的虛擬機(jī)資源分配；

第三步：針對不同任務(wù)調(diào)度方案，根據(jù)虛擬機(jī)處理能力MIPS、指令的執(zhí)行成本以及延遲成本，定義虛擬機(jī)利用效益函數(shù)，用于衡量虛擬機(jī)的使用效益；根據(jù)虛擬機(jī)總利用效益，以及虛擬機(jī)的總負(fù)載平衡度，定義任務(wù)調(diào)度方案P下的優(yōu)值函數(shù)值B_p，用于衡量該任務(wù)調(diào)度方案的任務(wù)優(yōu)值，過程如下：

3.1、在任務(wù)調(diào)度方案P下，定義虛擬機(jī)vm_j當(dāng)前狀態(tài)下VMU_j為虛擬機(jī)vm_j的利用效益，vm_j為第j個虛擬機(jī)資源，j＝1,2,…,m，m為虛擬機(jī)數(shù)量，函數(shù)如下：

VMU_j＝vmu(α,DP,MIPS)

其中α為虛擬機(jī)處理指令的執(zhí)行成本，DP為處理指令的延遲成本；

3.2、定義n個不同任務(wù)調(diào)度到m個不同虛擬機(jī)上的平均負(fù)載，即總?cè)蝿?wù)最優(yōu)完成時間為即MI_i為任務(wù)t_i的總指令長度；假設(shè)，在任務(wù)調(diào)度方案P下，虛擬機(jī)總的負(fù)載均衡度虛擬機(jī)的負(fù)載VL_j為分配給第j個虛擬機(jī)vm_j所有任務(wù)的預(yù)期完成時間；定義該任務(wù)調(diào)度方案P下的優(yōu)值函數(shù)值B_p，用于衡量任務(wù)調(diào)度方案P的任務(wù)優(yōu)值，主要函數(shù)如下：

其中w₁，w₂為權(quán)重值，VMU為虛擬機(jī)利用效益和，LB_p為該任務(wù)調(diào)度方案下的負(fù)載均衡度；

第四步、結(jié)合貪心算法獲得的任務(wù)調(diào)度初始解，通過衡量包含效益值以及負(fù)載均衡度的優(yōu)值函數(shù)，得出基于Tabu搜索算法優(yōu)化后的任務(wù)調(diào)度分配策略。