[發明專利]一種云環境下BoT任務的快速調度方法

在審

• 申請號: 201711023219.3
• 申請日: 2017-10-27
• 公開（公告）號: CN107908466A
• 公開（公告）日: 2018-04-13
• 發明（設計）人: 孫晉;張毅;董韻;冒晶晶;孫露露;何愛清;張華旭;龔炎
• 申請（專利權）人: 南京理工大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 南京理工大學專利中心32203
• 代理人: 薛云燕

1.一種云環境下BoT任務的快速調度方法，其特征在于，步驟如下：

步驟1，信息讀取：讀取BoT任務的所有參數；

步驟2，作業調度：基于讀取的參數，確定所有作業的開始時間；

步驟3，作業執行：按照步驟2的結果執行各個作業。

2.根據權利要求1所述的云環境下BoT任務的快速調度方法，其特征在于，所述BoT任務的所有參數包括：所有BoT任務中各作業的處理時間，各任務所需的VM類型。

3.根據權利要求1所述的云環境下BoT任務的快速調度方法，其特征在于，所述基于讀取的參數，確定所有作業的開始時間，所采用的作業調度方法如下：

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

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

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

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

設任務a_i的完工時間為c_i，時間軸的最大時間戳S＝max_{i＝1，2，…，n} c_i；設c_ii為作業t_ij的完工時間，故有：

ci=maxj=1,2,···,Ticij---(1)]]>

若作業t_ij的開始時間為st_ij，那么c_ii如下：

c_ii＝st_ij+r_ij(2)

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

C_max＝max_i＝_{1，2，…，n} c_i(3)

s.t.

Σi=1nΣq=1kΣj=1TizijsxiqCPUq≤CPU*,s=0,1,...,S---(4)]]>

Σi=1nΣq=1kΣj=1TizijsxiqMemq≤Mem*,s=0,1,...,S---(5)]]>

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

4.根據權利要求3所述的云環境下BoT任務的快速調度方法，其特征在于，作業調度方法具體如下：

按照各個作業對VM的配置要求和處理時間，將任務按照處理時間的升序排列組成一個作業執行隊列，依次提供滿足任務要求的VM，確定每個任務的開始時間，以保證整個任務最小化makespan，作業調度的具體步驟如下：

(1)接收一個作業執行隊列；

(2)如果隊列為空，則轉到(7)；否則，轉到(3)；

(3)從隊列取出一個作業t_i，其要求的VM類型VM_i由云C_j提供，處理時間為time_i，轉到(4)；

(4)記s＝0，轉到(5)；

(5)在C_j中，從s時刻開始尋找C_j中是否有連續個time_i個時間段能夠滿足VM_i的配置要求，如果能夠找到，則記錄s為t_i的最早開始時間，并將此時間段的資源按照VM_i的配置分配，轉到(2)；否則，轉到(6)；

(6)記最后一個無法滿足VM_i配置的時刻為e，令s＝e+1，轉到(5)；

(7)結束。