[發明專利]一種基于分段排序及標準差調整因子的云計算任務調度方法

有效

• 申請號: 201710458109.3
• 申請日: 2017-06-16
• 公開（公告）號: CN107357652B
• 公開（公告）日: 2020-10-23
• 發明（設計）人: 高欣;王萍;趙兵;賈慶軒;王睿;梁躍
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/48;H04L29/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明實施例提供了一種基于分段排序及標準差調整因子的云計算任務調度方法，包括：基于任務的獨立性和異構的硬件計算節點，建立任務調度數學模型，確定預期執行矩陣ETC；利用動態規劃的多階段決策組合優化方法，計算各個任務的平均預期執行時間，并以此為依據將任務進行分段，使長時間執行的任務可以優先執行，縮短執行時間；在各個分段中，計算每個任務在各個計算節點下運行時間的標準差，然后根據其大小，將標準差大的任務優先調度到最短完成時間的計算節點上，從而減少任務等待時間。根據本發明實施例提供的技術方案，可以實現提高任務調度的效率，縮短時間跨度，確保負載均衡。

【技術領域】

本發明涉及數據處理技術領域，尤其涉及一種基于分段排序及標準差調整因子的云計算任務調度方法。

【背景技術】

任務調度算法是云計算技術的核心，它直接決定著整個系統的運行效率。一般意義上調度是任務與任務處理器的一種映射。云計算系統中資源種類眾多，提供服務效率不一，規模巨大，怎樣更有效利用云計算系統中的資源一直是一個核心關注熱點。選擇合適的任務調度算法有助于提高云計算的處理效率、減少成本等。

傳統調度算法包括輪詢、隨機、hash算法等，但由于算法簡單，操作方便，比較適用于短任務，任務數較少的同構環境，對于異構計算環境來說有許多不足，從而造成時間跨度(makespan)增大。經典啟發式算法包括min-min算法、sufferage算法、遺傳、蟻群法。遺傳、蟻群算法的復雜度較高，min-min算法以最快的速度減少調度中的任務，以盡量縮短所有任務的完成時間，但min-min算法會使系統負載不均衡，并導致makespan較大。Max-min算法首先調度長任務，一定程度上能夠使負載平衡趨于均衡，但該算法缺陷是，沒有考慮任務的執行頻率。與min-min算法先調度短任務不同的是，seg-min-min算法在調度前先對任務按長度排序，執行時間長的任務段較早被調度，且被調度到處理能力強的機器上在執行長任務的同時能執行若干短任務，這樣任務的整體執行時間可能只由長任務來決定，而長任務又被分配到了執行該任務的最佳資源上，所以會使總的任務執行時間縮短，但是一味地優先調度長任務，會造成短任務停滯等待，甚至負載均衡度大大降低。

【發明內容】

基于上述，本發明提出一種基于分段排序及標準差調整因子的云計算任務調度方法?；谌蝿盏莫毩⑿院彤悩嫷挠布嬎愎濣c，建立任務調度數學模型，確定預期執行矩陣ETC；利用動態規劃的多階段決策組合優化方法，計算各個任務的平均預期執行時間，并以此為依據將任務進行分段，使長時間執行的任務可以優先執行，縮短執行時間；在各個分段中，計算每個任務在各個計算節點下預期運行時間的標準差，然后根據其大小，將標準差大的任務優先調度到最短完成時間的計算節點上，從而減少任務等待時間。

以往算法對任務執行時間考慮不足，單純追求當前局部最優，給全局性能帶來了負面影響。在一個給定的計算環境上任務執行時間是存在差異的。有的在不同的計算環境上差異大些，有的差異小些。對執行時間差異大的任務，差異越大按以往的算法帶來的負面影響越大。針對表1的一個示例，對以往算法進行改進，可以一定程度上提高性能，彌補不足，結果對比如圖2所示。本發明的優點在于：從任務之間相互獨立、長度長短不一等特點出發，根據ETC矩陣，采取相應的調度策略?；趧討B規劃思想，利用多階段決策的組合優化方法，根據分段和標準差來規劃每個任務的調度問題，從全局角度出發，不僅考慮當前任務，也考慮下一步的調度，使得總體的時間跨度縮短，同時也兼顧提高了負載均衡性，提高對計算資源的利用率。

表1任務與機器執行時間示例