[發明專利]基于EDA-GA混合算法的云計算多目標任務調度方法

在審

• 申請號: 201811316114.1
• 申請日: 2018-11-07
• 公開（公告）號: CN109491761A
• 公開（公告）日: 2019-03-19
• 發明（設計）人: 龐善臣;李文好
• 申請（專利權）人: 中國石油大學（華東）
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/48;G06F9/50;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.基于EDA-GA混合算法的云計算多目標任務調度方法，其特征在于，云用戶提交的任務具有多樣性與差異性，而且云計算資源具有異步性和動態性。本發明根據以上信息，得到一個合理的任務處理隊列，并根據系統的多個目標對任務進行有效調度，從而找到一種最優化的任務調度方案。主要包括以下部分：

A、分析系統的整體架構和目標，并對云計算的任務調度機制建立模型；

B、設計一種合理的任務隊列排列方法；

C、設計一種面向云計算多目標任務調度的EDA-GA混合算法。

2.根據權利要求1所述的基于EDA-GA混合算法的云計算多目標任務調度方法，其特征在于，所述的部分A中，從系統目標、約束條件等方面對云計算系統進行分析，并對任務調度機制建立模型。云計算任務調度的目標包括降低用戶任務完成時間、滿足用戶SLA要求、保持負載均衡、提高資源利用率等。在進行任務調度時，當云系統收到用戶提交的任務后，它采用批處理方式處理任務，該步驟是由任務管理器進行管理，任務管理器可以按照用戶要求決定最終的任務處理隊列。同時，資源管理器可以實時獲得當前虛擬機資源的計算能力、利用率等。在得到任務管理器與資源管理器的相關信息以后，調度器開始任務調度工作，調度時需要滿足一定的約束條件，如一個任務只能在一臺虛擬機上執行且僅被執行一次，任務需要根據任務管理器中形成的任務隊列順序依次進行調度。

3.根據權利要求1所述的基于EDA-GA混合算法的云計算多目標任務調度方法，其特征在于，所述的部分B中，由于云計算用戶的大量增加，用戶向云計算系統提交的任務量快速增長，并且這些任務具有一些自身的特性，如任務的種類可能屬于計算密集型、內存密集型或I/O密集型。而且云計算中資源是異構的，不同計算資源之間存在差異，因此任務在不同虛擬機資源上執行的時間會不同。同時，任務具有用戶設定的截止時間和優先級兩個特性。根據以上三種任務特性，首先得到任務在所有可用虛擬機資源上的執行效果差，再結合截止時間、優先級兩個屬性，設計合理的權重公式得到每個任務的權重，最后依據權重值的大小對任務進行排序，從而形成最終的任務處理隊列。具體步驟如下：

①根據任務管理器以及資源管理器，獲得任務大小和當前所有虛擬機資源的計算能力，并計算任務在虛擬機上的執行時間矩陣，計算公式如下：

假設用戶提交的任務總數量為n，創建的虛擬機總數量為m，所以ETC矩陣是n×m，T_i表示任務i的大小，S_j表示虛擬機j的計算速度；

②根據①中計算得到的任務執行時間矩陣，求出該任務的平均執行時間和最小執行時間，計算公式如下：

T_min＝min(ETC(n,0),ETC(n,1),…,ETC(n,m-1))

③利用AMM(AverageMinusMinimum)算法原理，將該任務的平均執行時間減去最小執行時間得到一個差值，該差值即為執行效果差Q(i)，差值越大的任務應盡可能越早地被調度到更合適的虛擬上，從而避免因調度不合適而引起整體完成時間的增加，計算公式如下：

Q(i)＝T_avg(i)-T_min(i)

④利用設計的權重公式，將任務的執行效果差、截止時間、優先級代入公式中進行計算，得到該任務的權重值，計算公式如下：

其中，和都是用來將任務的執行效果差和截止時間量化到與任務優先級相同的范圍中；DL(i)表示任務i的截止完成時間，TDL表示所有任務中的最大截止完成時間；P(i)表示任務i的優先級，用0到9之間的整數進行標注，數字越小，代表優先級越高。

α，β，γ為權重參數值，且α+β+γ＝1。本發明的目標之一是降低用戶任務完成時間、滿足用戶SLA要求，而用戶SLA要求在本發明中是根據截止時間進行約束的。因此，α與β的權重值相對γ較大，分別設置為0.4，0.4，γ設置為0.2。

⑤根據所有任務的權重值大小，按照從小到大的順序對任務進行排列，形成最終的任務處理隊列。權重值越小，代表該任務應越早被調度。

4.根據權利要求1所述的基于EDA-GA混合算法的云計算多目標任務調度方法，其特征在于，所述的部分C中，任務調度器根據全局資源管理器中提供的各個虛擬機的負載、利用率、計算速度等信息，以及任務管理器提供的任務處理隊列，將請求的任務調度至合適的虛擬機上。根據系統目標，設計了三種子種群，每個子種群具有自己的調度策略，具體如下：

①完成時間優先-子種群(T-FP)：該種群以完成時間最短為調度目標，當接收到某個任務時，計算該任務在所有可用虛擬機資源上的完成時間，完成時間為等待時間和處理時間之和，然后將該任務調度到具有最短完成時間的虛擬機上；

②利用率優先-子種群(U-FP)：該種群以提高虛擬機的資源利用率為目標，當接收到某個任務時，獲得當前時刻所有虛擬機的資源利用率，然后將任務調度到具有最小資源利用率的虛擬機上；

③學習-子種群(L-FP)：通過抽樣啟發式進行初始化，通過完成時間優先-子種群和利用率優先-子種群的優秀解進行更新，并利用適應度函數進行評估，通過迭代方式逐漸接近最優解。

本發明的EDA-GA混合算法，在算法前期，三種子種群根據自身目標，利用EDA算法的概率模型實現任務到虛擬機的分配，然后對每個子種群中的個體進行適應度評估，將適應度值高的優秀個體選擇出來，建立概率模型并進行采樣，產生新的解。進而利用GA算法，對新產生的解編碼，并以一定的概率進行交叉和變異操作，最后再進行適應度評估，以一定比例保留滿足目標的優秀解，與EDA階段的優秀解進行組合，形成新的子種群。最后對三種子種群進行更新，得到每個子種群的局部最優解，利用局部最優解來更新全局最優解，反復迭代，最終輸出滿足系統多個目標的最優解。

其中，本發明的目標函數定義為如下公式：

CompleteTime為整體完成時間，DBL為整體系統的負載均衡度。

和是權重系數，代表了任務完成時間和負載均衡在系統目標中所占的比重，本發明中由于兩個目標都較為重要，因此將其都設置為0.5。

GValue的值越大，表示該調度方案在降低用戶任務完成時間、提高資源利用率、保持系統負載均衡方面的效果越好。

基于EDA-GA混合算法的云計算多目標任務調度方法的具體步驟如下：

Step1：接收用戶的任務請求；

Step2：基于任務特性，根據所設計的權重公式計算各個任務的權重值，依據權重值的大小按順序對任務進行排列，形成最終的任務處理隊列；

Step3：初始化整體種群的規模，并按照1:2:1的比例，將整體種群劃分為完成時間優先子種群、學習-子種群和利用率優先-子種群；

Step4：對每個子種群進行初始化，按照各自種群的調度目標，將任務隊列中的任務調度到合適的虛擬機上；

Step5：按照三個子種群各自的目標函數，對種群中的個體進行評估，保留一定比例的優秀個體；

Step6：完成時間優先子種群和利用率優先-子種群交換彼此的優秀個體，學習-子種群接收其他兩個子種群的優秀個體；

Step7：根據交換后得到的新種群，利用EDA算法，建立概率模式，并利用輪盤賭方法進行采樣，產生出新的個體，并根據整體目標函數進行適應度評估，保留一定數量的優秀個體；

Step8：將Step7中得到的新個體利用GA算法，通過編碼、交叉、變異等步驟產生新的個體，并進行適應度評估，保留一定數量的優秀個體；

Step9：將Step7和Step8中篩選出來的優秀個體結合，形成新的子種群，并進行適應度評估，得到各個子種群的局部最優解；

Step10：根據局部最優解獲得全局最優解；

Step11：三個子種群根據更新公式進行更新，并進行下一次迭代；

Step12：判斷是否滿足終止條件，若滿足，則輸出全局最優解；若不滿足，則跳轉到Step5。