[發明專利]一種面向云計算平臺的任務調度方法有效
| 申請號： | 201711340244.4 | 申請日： | 2017-12-14 |
| 公開（公告）號： | CN108108225B | 公開（公告）日： | 2019-05-24 |
| 發明（設計）人： | 耿曉中;柯洪昌;于瀾;任斌;鮑杰;徐欣欣 | 申請（專利權）人： | 長春工程學院 |
| 主分類號： | G06F9/455 | 分類號： | G06F9/455;G06F9/48;H04L29/08 |
| 代理公司： | 北京市盛峰律師事務所 11337 | 代理人： | 席小東 |
| 地址： | 130012 *** | 國省代碼： | 吉林;22 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 虛擬機 任務優先級隊列 云計算平臺 云計算系統 任務調度 任務復制 結點 復制 負載均衡性 資源利用率 傳統算法 負載平衡 降序排列 開始階段 選擇階段 遍歷 放入 延遲 虛擬 調度 | ||
1.一種面向云計算平臺的任務調度方法，其特征在于，包括以下步驟：
步驟1，初始化任務調度隊列，計算每個任務的靜態優先級，按照靜態優先級降序排列任務，將任務依次放入任務優先級隊列中；
具體包括：
構建任務DAG圖；DAG圖由四元組G＝(T,E,W,C)構成，各成員定義如下：
(1)T表示DAG圖中的任務集合，共有n個任務，T＝{T1,T2,…,Tn}；
(2)E＝{Ei,j|Ti,Tj∈T}表示任務間通信邊的集合，Ei,j表示從任務Ti到任務Tj的一條有向邊；
(3)W是一個n*m矩陣，表示n個任務分別在m個虛擬機上的執行時間，m為虛擬機總數量；虛擬機集合P表示為：P＝{P1,P2,…,Pm}；
W(Ti,Pk)表示任務Ti在虛擬機Pk上的運行時間，Pk∈P；按照公式(1)計算任務Ti的平均運行時間
(4)C是任務間的通信開銷，C(Ei,j)表示有向邊Ei,j上的通信開銷，假設當兩個任務被分到同一虛擬機上時，任務間的通信開銷為0；
(5)任務Ti的前驅任務集合pred(Ti)表示為：pred(Ti)＝{Te|Ee,i∈E}；
任務Ti的后繼任務集合succ(Ti)表示為：succ(Ti)＝{Ts|Ei,s∈E}；
(6)假設DAG圖中只有一個起點，用Tstart表示；只有一個終點用Tend表示；
(7)按照如下公式(2)計算DAG圖中的每個任務Ti的靜態優先級rank(Ti)：
以Tend作為計算開始結點，以Tstart作為計算結束結點，按照從下向上，同層從左到右的原則，遍歷DAG圖中的所有任務結點，依次計算得到每個結點任務的靜態優先級；
步驟2，令i＝1；
步驟3，選擇任務Ti；
步驟4，令k＝1；
步驟5，按照公式(3)計算任務Ti在虛擬機Pk上的開始執行時間(st(Ti,Pk))：
其中：
任務Ti在虛擬機Pk上的開始執行時間(st(Ti,Pk))是指：任務Ti的所有前驅任務都被執行完，并且虛擬機Pk接收到任務Ti的所有前驅任務的執行結果時，任務Ti可以在Pk上開始運行的時間：
ava(Pk)表示虛擬機Pk的起始可用時間，指虛擬機Pk的就緒時間或最近分配到虛擬機Pk上的任務Ti的完成時間，表示為：ava(Pk)＝0或者ava(Pk)＝ct(Ti,Pk)；
ct(Te,Px)表示任務Ti的前驅任務在除虛擬機Pk外的其他對應虛擬機上的完成時間；
步驟6，將任務Ti的父任務結點按照靜態優先級值降序排列，構造得到父任務隊列；F為父任務隊列中父任務結點數量；父任務隊列Ti0表示為：Ti0＝{Ti-10,Ti-20,…,Ti-F0}；其中，Ti-10表示任務Ti的父任務隊列中靜態優先級最高的任務；Ti-20表示任務Ti的父任務隊列中靜態優先級次高的任務；Ti-F0表示任務Ti的父任務隊列中靜態優先級最低的任務；父任務隊列Ti0中任意一個父任務表示為Ti-f0；
步驟7，令f＝1；
步驟8，按照公式(4)計算虛擬機Pk相對于任務Ti的空閑時間slot(Ti,Pk)；其中，虛擬機Pk的空閑時間指虛擬機Pk已經處于就緒狀態，但任務Ti需要等待其前驅任務的執行結果，任務Ti在等待其前驅任務的執行結果的等待時間，即為，虛擬機Pk的空閑時間；
slot(Ti,Pk)＝st(Ti,Pk)-ava(Pk) (4)
步驟9，判斷Ti的父任務Ti-f0是否滿足以下規則：slot(Ti,Pk)≥W(Ti-f0,Pk)并且ct(Qf,Pk)<st(Ti,Pk)；而且父任務Ti-f0沒有在虛擬機Pk上執行過；其中，W(Ti-f0,Pk)代表父任務Ti-f0在虛擬機Pk上的運行時間；ct(Qf,Pk)表示父任務Ti-f0在虛擬機Pk上的完成時間；
如果滿足，則復制Ti-f0到虛擬機Pk的空閑時間slot(Ti,Pk)上，更新當前任務Ti的開始執行時間(st(Ti,Pk))和虛擬機Pk的空閑時間slot(Ti,Pk)；如果不滿足，執行步驟10；
步驟10，令f＝f+1；判斷f是否大于F，如果大于，則執行步驟11；如果不大于，則返回執行步驟9；
步驟11，任務Ti在虛擬機Pk上的完成時間等于任務Ti的開始執行時間加上任務Ti的執行時間，即：根據公式(5)計算Ti在Pk上的完成時間(ct(Ti,Pk))：
ct(Ti,Pk)＝st(Ti,Pk)+W(Ti,Pk) (5)
步驟12，令k＝k+1；判斷k是否大于m，如果大于，則執行步驟13；如果不大于，則返回執行步驟5；
步驟13，計算云計算系統的虛擬機負載平衡標準偏差Lk；
步驟14，根據用戶需求分配任務Ti到ct(Ti,Pk)+Lk值小的虛擬機上去執行；
步驟15，令i＝i+1；判斷i是否大于n，如果大于，則執行步驟16；如果不大于，則返回執行步驟3；
步驟16，輸出每個任務所分配的虛擬機；由虛擬機執行所分配的對應任務。
2.根據權利要求1所述的面向云計算平臺的任務調度方法，其特征在于，步驟13具體包括以下步驟：
步驟13.1，根據公式(6)計算虛擬機Pk的負載權值load(Pk)：
load(Pk)＝w1·r_cpu+w2·r_mem+w3·r_bw (6)
其中：r_cpu表示CPU利用率，r_mem表示內存利用率，r_bw表示網絡帶寬利用率；w1+w2+w3＝1，w1,w2,w3分別表示CPU、內存、帶寬的影響因子；
步驟13.2，根據公式(7)計算云計算系統的虛擬機平均負載loadave：
其中：load(Pk)表示虛擬機Pk的負載權值；
步驟13.3，根據公式(8)計算云計算系統的虛擬機負載平衡標準偏差Lk：
由此得到云計算系統的虛擬機負載平衡標準偏差Lk。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于長春工程學院，未經長春工程學院許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201711340244.4/1.html，轉載請聲明來源鉆瓜專利網。
