[發(fā)明專利]一種基于穩(wěn)定匹配博弈理論的工作流調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011329163.6
• 申請(qǐng)日: 2020-11-24
• 公開（公告）號(hào): CN112306642B
• 公開（公告）日: 2022-10-14
• 發(fā)明（設(shè)計(jì)）人: 賈兆紅;潘磊;唐俊
• 申請(qǐng)（專利權(quán)）人: 安徽大學(xué)
• 主分類號(hào): G06F9/455
• 分類號(hào): G06F9/455
• 代理公司: 合肥市浩智運(yùn)專利代理事務(wù)所(普通合伙) 34124
• 代理人: 張祥

本發(fā)明提供了一種基于穩(wěn)定匹配博弈理論的工作流調(diào)度方法，包括以下步驟：步驟A：輸入工作流的DAG圖，虛擬機(jī)池V＝{VM₀,VM₁,…,VM_m?1}，以及CCR數(shù)值；步驟B：計(jì)算每個(gè)任務(wù)的rank值，選擇每一層中具有最大rank值的任務(wù)加入關(guān)鍵路徑任務(wù)集合CP；步驟C：基于穩(wěn)定匹配博弈理論將任務(wù)分配到虛擬機(jī)上，得到調(diào)度方案；步驟D：優(yōu)化調(diào)度方案，遍歷所有任務(wù)，將使當(dāng)前任務(wù)開始時(shí)間提前的前驅(qū)節(jié)點(diǎn)復(fù)制到當(dāng)前任務(wù)所在的虛擬機(jī)上。本發(fā)明的優(yōu)點(diǎn)在于：基于關(guān)鍵路徑和任務(wù)復(fù)制的兩種局部?jī)?yōu)化策略有效地減少了工作流的最大完工時(shí)間，綜合考慮了任務(wù)的公平性問(wèn)題，能夠提高客戶滿意度。

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

本發(fā)明涉及工作流調(diào)度技術(shù)領(lǐng)域，尤其涉及一種基于穩(wěn)定匹配博弈理論的工作流調(diào)度方法。

背景技術(shù)

云計(jì)算提供了一種新的資源交付和服務(wù)提供模式，它可以提供各種各樣的計(jì)算和資源服務(wù)如服務(wù)器，存儲(chǔ)容量，cpu等以及在整個(gè)網(wǎng)絡(luò)上運(yùn)行的電子商務(wù)、社交網(wǎng)絡(luò)等應(yīng)用服務(wù)。為了利用云計(jì)算服務(wù)模式的資源優(yōu)勢(shì)，大力節(jié)約投資成本，擺脫資源受地域和時(shí)間的限制，我們可以將任何工作任務(wù)都放在云計(jì)算環(huán)境下執(zhí)行，例如，已經(jīng)被廣泛研究的工作流任務(wù)。工作流即是一系列相互銜接、自動(dòng)執(zhí)行的業(yè)務(wù)活動(dòng)或任務(wù)。我們將放置在云計(jì)算環(huán)境下的工作流，稱之為云工作流。像高能量物理學(xué)，引力波學(xué)，地理學(xué)，生物信息學(xué)，天文學(xué)等科學(xué)應(yīng)用中的任務(wù)都是基于集中控制的，且數(shù)據(jù)之間存在著較強(qiáng)的相互依賴的關(guān)系。由于云計(jì)算環(huán)境下需要最大程度的滿足用戶QoS(Quality of Service，服務(wù)質(zhì)量)的需求，所以在云環(huán)境下研究工作流任務(wù)調(diào)度算法的意義重大。工作流任務(wù)調(diào)度策略的選取將會(huì)對(duì)云計(jì)算的效率和性能產(chǎn)生重要的影響，不恰當(dāng)?shù)恼{(diào)度策略不但會(huì)造成資源的浪費(fèi)而且還滿足不了用戶對(duì)QoS的需求，從而使云資源提供商和云服務(wù)使用者都不能達(dá)到自己的目標(biāo)。

目前，大多數(shù)云工作流調(diào)度算法都關(guān)注于最小化整個(gè)工作流的總成本或最大完工時(shí)間等共同目標(biāo)。然而在現(xiàn)實(shí)中，如視頻監(jiān)控、對(duì)象追蹤、人臉識(shí)別等工作流，各個(gè)子任務(wù)都有各自的目標(biāo)，比如最小響應(yīng)時(shí)間或最快處理速度等。對(duì)于一些調(diào)度算法，如果總是將當(dāng)前最優(yōu)資源(如最大帶寬、最快處理速度等)按照優(yōu)先級(jí)分配給任務(wù)，如公開號(hào)為CN103838627A的發(fā)明專利公開的一種基于工作流吞吐量最大化的工作流調(diào)度方法，以及公開號(hào)為CN103914754A的發(fā)明專利公開的一種工作流的任務(wù)調(diào)度方法、多工作流調(diào)度方法及其系統(tǒng)均是基于優(yōu)先級(jí)完成工作流的調(diào)度的，而且更關(guān)注多個(gè)工作流的處理順序，可能會(huì)使部分任務(wù)不能滿足客戶要求，從而造成不公平分配。資源的不公平分配會(huì)導(dǎo)致一些任務(wù)目標(biāo)的滿意度顯著下降，從而影響客戶對(duì)云服務(wù)的滿意度。因此，在考慮工作流全局目標(biāo)的同時(shí)，也需要考慮其內(nèi)部各個(gè)任務(wù)之間的公平性。如何在保證任務(wù)公平性的前提下，最小化工作流的完工時(shí)間有重要意義。

博弈論(Game Theory，GT)主要研究理性決策者之間的戰(zhàn)略互動(dòng)，廣泛應(yīng)用于邏輯學(xué)、系統(tǒng)科學(xué)等各個(gè)領(lǐng)域。考慮到均衡任務(wù)的可靠性，Yang等提出了一種基于合作博弈模型的任務(wù)調(diào)度算法，在保證效率的同時(shí)降低了算法的復(fù)雜度。為了解決網(wǎng)格計(jì)算中的任務(wù)調(diào)度問(wèn)題，Gao等將網(wǎng)格負(fù)載均衡問(wèn)題視為非合作博弈模型，提出了一種基于GT的網(wǎng)格代價(jià)最小化算法。實(shí)驗(yàn)結(jié)果表明，基于博弈的算法具有較好的解決任務(wù)調(diào)度問(wèn)題的能力。Wang等提出了一種基于動(dòng)態(tài)博弈模型的多目標(biāo)工作流調(diào)度算法，以最小化最大完工時(shí)間和總成本，最大化異構(gòu)云虛擬機(jī)之間的工作負(fù)載分配的系統(tǒng)公平性。Sujana等將多目標(biāo)工作流調(diào)度問(wèn)題定義為在兩個(gè)約束條件下的最小化執(zhí)行時(shí)間和經(jīng)濟(jì)成本的雙目標(biāo)序列合作博弈模型。盡管GT在解決工作流調(diào)度問(wèn)題上有一定的優(yōu)勢(shì)，但在現(xiàn)有的研究中，考慮任務(wù)公平性問(wèn)題的研究仍然很少，而且現(xiàn)有算法的效果和處理速度依然不能滿足所有用戶的需求。

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

本發(fā)明所要解決的技術(shù)問(wèn)題在于提供一種基于GT模型中的穩(wěn)定匹配博弈理論進(jìn)行工作流調(diào)度的方法，以解決現(xiàn)有技術(shù)未考慮任務(wù)公平性的問(wèn)題，同時(shí)最小化工作流的完工時(shí)間。

本發(fā)明是通過(guò)以下技術(shù)方案解決上述技術(shù)問(wèn)題的：一種基于穩(wěn)定匹配博弈理論的工作流調(diào)度方法，包括以下步驟：