[發(fā)明專利]一種云環(huán)境下BoT任務(wù)的快速調(diào)度方法

在審

• 申請?zhí)枺?/td>: 201711023219.3
• 申請日: 2017-10-27
• 公開（公告）號: CN107908466A
• 公開（公告）日: 2018-04-13
• 發(fā)明（設(shè)計）人: 孫晉;張毅;董韻;冒晶晶;孫露露;何愛清;張華旭;龔炎
• 申請（專利權(quán)）人: 南京理工大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 南京理工大學(xué)專利中心32203
• 代理人: 薛云燕

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

本發(fā)明涉及云計算技術(shù)領(lǐng)域，特別是一種云環(huán)境下BoT任務(wù)的快速調(diào)度方法。

背景技術(shù)

云計算旨在通過互聯(lián)網(wǎng)將可用資源(包括計算資源、平臺資源和應(yīng)用資源)以服務(wù)的形式提供給用戶。用戶以“用多少、付多少”的方式使用這些資源。因此，云計算特別適合處理那些需要大量計算資源的任務(wù)。

Bag-of-Tasks(BoT)任務(wù)是一類包含多個可并行處理作業(yè)的任務(wù)。BoT任務(wù)是指包含多個可并行處理作業(yè)的任務(wù)，廣泛存在于計算機視頻、圖片處理、蒙特卡羅仿真的科學(xué)和工程領(lǐng)域。事實上，很多用戶(包括企業(yè)或者機構(gòu))都已有一些有限資源的計算設(shè)備(可稱為私有云)，但是不能高效調(diào)度BoT任務(wù)使得最大完工時間(即makespan)最小化。

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

本發(fā)明的目的在于提供一種云環(huán)境下BoT任務(wù)的快速調(diào)度方法，從而快速有效地確定每個作業(yè)的開始時間并最小化makespan。

實現(xiàn)本發(fā)明目的的技術(shù)解決方案為：一種云環(huán)境下BoT任務(wù)的快速調(diào)度方法，步驟如下：

步驟1，信息讀取：讀取BoT任務(wù)的所有參數(shù)；

步驟2，作業(yè)調(diào)度：基于讀取的參數(shù)，確定所有作業(yè)的開始時間；

步驟3，作業(yè)執(zhí)行：按照步驟2的結(jié)果執(zhí)行各個作業(yè)。

進一步地，所述BoT任務(wù)的所有參數(shù)包括：所有BoT任務(wù)中各作業(yè)的處理時間，各任務(wù)所需的VM類型。

進一步地，所述基于讀取的參數(shù)，確定所有作業(yè)的開始時間，所采用的作業(yè)調(diào)度方法如下：

假設(shè)一個私有云CP₀，私有云提供了k個VM類型，分別為VM₁,VM₂,…,VM_k；

每個VM_q都用兩個配置參數(shù)來描述：該VM所能提供的CPU數(shù)量CPU_q和內(nèi)存的數(shù)量Mem_q，q＝1,2,…,k；

一共有n個BoT任務(wù)a₁,a₂,…,a_n，每個任務(wù)a_i包含T_i個作業(yè)用一個參數(shù)x_iq表示a_i是否需要VM_q，如果需要則x_iq＝1；否則，x_iq＝0；每個作業(yè)的處理時間為r_ij，其中i＝1,2,…,n,j＝1,2,…,T_i；

時間軸以1小時的粒度離散化，私有云最大CPU數(shù)量和內(nèi)存數(shù)量分別表示為CPU^*和Mem^*，即在時間軸上的任何一點私有云上所消耗的資源不能超過CPU^*和Mem^*；

設(shè)任務(wù)a_i的完工時間為c_i，時間軸的最大時間戳S＝max_{i＝1,2,…,n}c_i；設(shè)c_ij為作業(yè)t_ij的完工時間，故有：

若作業(yè)t_ij的開始時間為st_ij，那么c_ij如下：

c_ij＝st_ij+r_ij (2)

定義決策變量z_ijs，i＝1,2,…,n,j＝1,2,…,T_i,s＝0,1,…,S；z_ijs＝1表明作業(yè)t_ij的開始時間為s，否則z_ijs＝0，把作業(yè)t_ij的開始時間描述成整數(shù)規(guī)劃問題，即Minimize the makespan(C_max)：

C_max＝max_{i＝1,2,…,n}c_i (3)

s.t.

上述作業(yè)調(diào)度方法從作業(yè)的失敗時刻的下一時刻起確定作業(yè)的開始時間，需要結(jié)合私有云最大CPU數(shù)量CPU^*和內(nèi)存數(shù)量Mem^*，且滿足公式(3)～(5)的約束。

進一步地，作業(yè)調(diào)度方法具體如下：