[發明專利]一種云環境下截止期約束的科學工作流調度方法有效
| 申請號： | 201910693745.3 | 申請日： | 2019-07-30 |
| 公開（公告）號： | CN110609736B | 公開（公告）日： | 2021-04-20 |
| 發明（設計）人： | 鄧科峰;曹書錦;宋君強;任開軍;李小勇;任小麗;黃浩煒;周翱隆;張家灝 | 申請（專利權）人： | 中國人民解放軍國防科技大學 |
| 主分類號： | G06F9/48 | 分類號： | G06F9/48;G06F9/455 |
| 代理公司： | 長沙大珂知識產權代理事務所(普通合伙) 43236 | 代理人： | 伍志祥 |
| 地址： | 410003 湖*** | 國省代碼： | 湖南;43 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 一種 環境 截止 約束 科學 工作流 調度 方法 | ||
1.一種云環境下截止期約束的科學工作流調度方法，其特征在于，包括以下步驟：
步驟1，將任務集合T中的任務按照拓撲結構進行排序得到T′；
步驟2，為T′中的任務計算向上排序值；
步驟3，根據所述的向上排序值為中每個任務分配子截止期；
步驟4，將T′中任務根據子截止期的緊急情況進行排序；
步驟5，根據所述的排序先后次序為任務分配虛擬機；
步驟5中分配虛擬機包括以下步驟：
步驟501，若存在滿足任務ti子截止期的虛擬機集合{VM}，則將任務ti分配到開銷最小的虛擬機VMk；
步驟502，若不存在滿足ti子截止期的虛擬機，則選擇最快的虛擬機VMfast執行，并將超出截止期的時間σ算入后繼任務；
由此，獲得工作流初始調度方案S′和租用虛擬機集合R；
步驟6，對所述的初始調度方案S′進行優化，所述的優化包括虛擬機升級優化和虛擬機降級優化；
所述的虛擬機升級優化包括以下步驟：
步驟601，對每個虛擬機VMk∈R，將該虛擬機升級為VMk′，并重新計算該虛擬機上任務的執行時間，節約的時間開銷記為gaink；
步驟602，找到max{gaink,VMk∈R}，并重新計算VMk上的費用開銷newCost，若費用開銷優于原方案，則接受該虛擬機升級，否則繼續執行步驟601直到遍歷所有R集合內的虛擬機；
步驟603，得到新的調度方案S″；
所述的虛擬機降級優化包括以下步驟：
步驟604，在調度方案S″中，對每個虛擬機VMk∈R，將該虛擬機降級為VMk′，并重新計算該虛擬機上任務的執行時間，超出的時間開銷記為delay；
步驟605，重新計算每個虛擬機降級后的費用開銷newCost，找到max{mGain＝Costk-newCostk,VMk∈R}，其中Costk表示虛擬機VMk降級之前的費用開銷，newCostk表示虛擬機VMk降級之后的費用開銷；
步驟606，計算新的時間開銷newMakespan，若滿足截止期要求，接受該虛擬機降級，否則繼續執行步驟604直到遍歷所有R集合內的虛擬機；
步驟607，得到新的調度方案Schedule。
2.根據權利要求1所述的科學工作流調度方法，其特征在于，所述的向上排序值ranku(ti)的計算方法為：
其中，succ(ti)代表了ti的全部后繼任務；γj是通信開銷系數；dij是任務ti到任務tj的數據傳輸時間，若任務ti和任務tj均分配到同一虛擬機上，有dij＝0；是任務ti在最快虛擬機實例上的執行時間。
3.根據權利要求2所述的科學工作流調度方法，其特征在于，所述的任務ti子截止期subD(ti)分配方法為：
其中，tentry為科學工作流中的初始任務，ranku(tentry)為初始任務tentry的向上排序值，D為科學工作流的截止期。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于中國人民解放軍國防科技大學，未經中國人民解放軍國防科技大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201910693745.3/1.html，轉載請聲明來源鉆瓜專利網。
