[發明專利]一種云環境下執行可靠性感知的并行任務調度方法

有效

• 申請號: 201710227551.5
• 申請日: 2017-04-10
• 公開（公告）號: CN107038070B
• 公開（公告）日: 2021-04-16
• 發明（設計）人: 張志鋒;曹潔;孫玉勝;張建偉;鄧璐娟;鄭倩;馬軍霞;桑永宣;趙曉君
• 申請（專利權）人: 鄭州輕工業學院
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;H04L29/08
• 代理公司: 河南廣文律師事務所 41124
• 代理人: 王自剛

一種云環境下執行可靠性感知的并行任務調度方法，涉及云計算技術領域，本發明針對用戶對并行任務有完成截止時間和執行可靠性的要求，根據云計算系統的計算資源和通信設備的故障率服從指數分布的特點，生成并行任務在云計算系統上執行的所有執行方案，將這些執行方案構建執行方案圖，基于執行方案圖，提出滿足并行任務完成截止時間要求的最大可靠性執行方案求解算法MREP，而且MREP算法切實可行，在并行任務執行可靠性、并行任務執行成功率和完成時間方面都表現出較好的性能。

【技術領域】

本發明涉及云計算技術領域，尤其是涉及一種云環境下執行可靠性感知的并行任務調度方法。

【背景技術】

公知的，由于云計算建立在大規模廉價的服務器集群上，導致計算節點軟硬件、通信鏈路極容易出現故障，即不同的計算節點和通信鏈路表現出不同的故障率，云計算是分布式計算、并行處理和網格計算的進一步發展，是基于互聯網的計算，能夠通過互聯網以按需、易擴展的方式提供硬件服務、基礎架構服務、平臺服務、軟件服務、存儲服務等的系統，在“云”中，集聚了大量的服務器、存儲設備和應用軟件，用戶通過訪問這些資源，就可以方便獲取自己所需要的服務，如數據訪問、特定計算服務等。

云計算整合了Internet上分布的、異構的各種資源，其資源性能千差萬別，軟硬件故障、網絡中斷都可以導致資源不能運行提交給它的任務，然而，現實中的有些重要應用，例如核電站、飛行控制、交通指揮調度等系統對計算任務的成功執行有著嚴格的要求，提高這些計算任務的執行成功率至關重要，由于計算資源計算速度、通信鏈路通信速度以及它們的故障率的不同，同一任務在不同計算資源上的執行成功率不同，對于任務之間存在優先級約束和數據依賴關系的并行任務來說，提高并行任務執行成功率的關鍵是制定有效的任務調度策略，確保任務高可靠執行已成為云計算當前研究的熱點，在云環境下，云用戶通常是按自己所實際獲得的服務質量對服務進行付費的，而服務的完成時間和可靠性是評估服務質量的兩個重要的評價標準，通常，云服務完成任務所用的時間越短、服務越可靠，費用越高，終端用戶出于計算成本的考慮，可在應用服務的完成時間和可靠性之間進行折中。

在多任務多機環境下，調度問題的實質是將m個任務分配到n個機器上執行，一般來說，調度問題屬于NP問題，很難找到最優解，因此，通常是尋求次優解，針對多機環境中的并行任務調度問題，通常的調度方法有：(1)表調度算法，基本思想是根據所有任務的優先級別進行排序，來構造一個調度列表，然后按某種策略把任務調度到處理機上執行，這類調度算法典型的有：HEFT(HeterogeneousEarliestFinish time)，，CPOP(Critical Path Ona Proeessor)，DLS(dynamic levelseheduling)等，與其它種類調度算法相比，表調度算法的時間復雜度相對較低，比較實用；(2)基于任務復制的調度算法，主要思想是將一個任務分別映射到兩個或多個處理機上執行，以降低該任務和關聯任務之間的通信開銷，前提是任務的冗余計算開銷要小于通信開銷，這類算法典型的有：DSH(Duplication SchedulingHeuristic)，CPFD(Critical Path Fast Duplication)等；(3)基于任務分簇的調度算法，基本思想是將同一個簇中的任務分配到同一個處理機上執行，避免了同一簇中任務之間的通信開銷，典型的算法是DSC(Dominant Sequence Clustering)算法；(4)非確定性調度算法，它主要是通過有導向的隨機選擇來搜索問題的解空間，以便獲取調度目標的近優解。