[發(fā)明專利]基于EDA-GA混合算法的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201811316114.1
• 申請(qǐng)日: 2018-11-07
• 公開（公告）號(hào): CN109491761A
• 公開（公告）日: 2019-03-19
• 發(fā)明（設(shè)計(jì)）人: 龐善臣;李文好
• 申請(qǐng)（專利權(quán)）人: 中國石油大學(xué)（華東）
• 主分類號(hào): G06F9/455
• 分類號(hào): G06F9/455;G06F9/48;G06F9/50;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明提出了一種基于EDA?GA混合算法的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法。本發(fā)明基于云用戶所提交任務(wù)的多樣性與差異性，以及云計(jì)算資源的異步性，通過對(duì)任務(wù)特性進(jìn)行分析與計(jì)算，最終形成一個(gè)合理的任務(wù)處理隊(duì)列。基于EDA?GA混合算法，以降低任務(wù)完成時(shí)間、提高資源利用率、保持系統(tǒng)負(fù)載均衡為目標(biāo)，對(duì)任務(wù)進(jìn)行合理調(diào)度。本發(fā)明提供的任務(wù)調(diào)度方法，能夠在云計(jì)算環(huán)境下對(duì)用戶提交的任務(wù)進(jìn)行合理有效的調(diào)度，滿足系統(tǒng)多個(gè)目標(biāo)需求。

技術(shù)領(lǐng)域

本發(fā)明涉及云計(jì)算領(lǐng)域，特別涉及基于EDA-GA混合算法的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法。

背景技術(shù)

在信息化的今天，隨著用戶數(shù)量和需求的日益增加以及互聯(lián)網(wǎng)的不斷擴(kuò)大，云計(jì)算應(yīng)運(yùn)而生，它是在并行計(jì)算、網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展而來的。云計(jì)算與其他計(jì)算技術(shù)相比較，具有很多獨(dú)特的優(yōu)點(diǎn)，主要包括三個(gè)方面：一是按需服務(wù)的可擴(kuò)展性，能夠考慮到用戶特定的約束和要求；二是靈活性，能夠通過持續(xù)控制資源及其優(yōu)化來支持；三是虛擬化，是將用戶與物理基礎(chǔ)設(shè)施分離的工具。云計(jì)算技術(shù)已經(jīng)滲透到當(dāng)前各類社會(huì)領(lǐng)域中，廣泛應(yīng)用于電信、電子政務(wù)、制造、教育科研、醫(yī)療等領(lǐng)域，例如，以我國微云以及百度云為代表的存儲(chǔ)云為廣大用戶提供了可靠安全的數(shù)據(jù)存儲(chǔ)服務(wù)、安全備份、歸檔管理以及記錄服務(wù)，為應(yīng)用資源主體提供了極大的便利。伴隨著云計(jì)算技術(shù)的快速發(fā)展與廣泛應(yīng)用，其優(yōu)勢(shì)功能越發(fā)明顯，逐步邁向成熟應(yīng)用的階段。

任務(wù)調(diào)度是云計(jì)算的關(guān)鍵技術(shù)之一，任務(wù)調(diào)度是在滿足用戶需求以及提高云系統(tǒng)性能的前提下，將用戶提交的任務(wù)合理地分配到虛擬機(jī)上。任務(wù)調(diào)度算法是用戶與云服務(wù)提供商之間的紐帶，好的任務(wù)調(diào)度調(diào)度算法不僅能保證用戶得到較好的用戶體驗(yàn)，滿足用戶對(duì)于便捷、安全、人性化的要求，而且能夠?yàn)樵品?wù)提供商降低能耗和運(yùn)營(yíng)成本，平衡系統(tǒng)負(fù)載，提高資源利用率，從而促進(jìn)云計(jì)算的良好發(fā)展。

目前，傳統(tǒng)任務(wù)調(diào)度方法具有一定的缺陷，例如，只能實(shí)現(xiàn)單個(gè)目標(biāo)，無法滿足用戶與云系統(tǒng)的多個(gè)目標(biāo)需求。同時(shí)，基于云計(jì)算的任務(wù)調(diào)度問題已經(jīng)被證明屬于NP完全問題。因此，設(shè)計(jì)一種滿足多個(gè)目標(biāo)的任務(wù)調(diào)度方法具有重要的實(shí)際意義和理論意義。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有方法的缺陷，本發(fā)明提出了一種基于EDA-GA混合算法的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法。該方法基于用戶任務(wù)的多樣性與差異性以及云計(jì)算資源的異步性與動(dòng)態(tài)性，設(shè)計(jì)一種決定任務(wù)處理隊(duì)列的方法以確定任務(wù)調(diào)度順序，進(jìn)而設(shè)計(jì)一種滿足降低任務(wù)完成時(shí)間、符合用戶SLA要求、提高資源利用率、保持系統(tǒng)負(fù)載均衡等多個(gè)目標(biāo)的任務(wù)調(diào)度方法。

基于EDA-GA混合算法的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法，可以分為以下幾個(gè)部分：

A、分析系統(tǒng)的整體架構(gòu)和目標(biāo)，并對(duì)云計(jì)算中的任務(wù)調(diào)度機(jī)制建立模型；

B、設(shè)計(jì)一種合理的任務(wù)隊(duì)列排列方法；

C、設(shè)計(jì)一種面向云計(jì)算多目標(biāo)任務(wù)調(diào)度的EDA-GA混合算法。

部分A中，從系統(tǒng)目標(biāo)、約束條件等方面對(duì)云計(jì)算系統(tǒng)進(jìn)行分析，并對(duì)任務(wù)調(diào)度機(jī)制建立模型。本發(fā)明中，云計(jì)算任務(wù)調(diào)度的目標(biāo)包括降低任務(wù)完成時(shí)間、滿足用戶SLA要求、保持負(fù)載均衡、提高資源利用率等。在進(jìn)行任務(wù)調(diào)度時(shí)，當(dāng)云系統(tǒng)收到用戶提交的任務(wù)后，它采用批處理方式處理任務(wù)，該步驟是由任務(wù)管理器進(jìn)行管理，任務(wù)管理器可以按照用戶要求決定最終的任務(wù)處理隊(duì)列。同時(shí)，資源管理器可以實(shí)時(shí)獲得當(dāng)前虛擬機(jī)資源的計(jì)算能力、利用率等。在得到任務(wù)管理器與資源管理器的相關(guān)信息以后，調(diào)度器開始任務(wù)調(diào)度工作。調(diào)度時(shí)需要滿足一定的約束條件，比如，一個(gè)任務(wù)只能在一臺(tái)虛擬機(jī)上執(zhí)行且僅被執(zhí)行一次，任務(wù)需要根據(jù)任務(wù)管理器中形成的任務(wù)隊(duì)列順序依次進(jìn)行調(diào)度等。約束函數(shù)具體如下：

min{TFT},max{TU}

TFT≥FT_i,i＝1,...,n (4)