[發明專利]一種云環境下的Max-D作業調度方法

有效

• 申請號: 201310038329.2
• 申請日: 2013-01-31
• 公開（公告）號: CN103257896A
• 公開（公告）日: 2013-08-21
• 發明（設計）人: 李千目;陸路;侯君
• 申請（專利權）人: 南京理工大學連云港研究院
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50
• 代理公司: 南京理工大學專利中心 32203
• 代理人: 朱顯國

1.一種云環境下的Max-D作業調度方法，其特征在于步驟如下：

第一步：確定云環境中所有計算資源以及空閑資源的集合；

第二步：對待分配作業按作業提交先后排序成隊列，新提交的作業被加入該隊列尾部；

第三步：對排序后的作業進行調度，采用Max-D方法選擇合適的資源進行執行。

2.根據權利要求1所述的云環境下的Max-D作業調度方法，其特征在于，所述第三步的Max-D方法，其步驟如下：

步驟3.1：對所有待分配作業，計算作業在所有計算資源上的平均估計運行時間；

步驟3.2：計算每個作業的平均估計運行時間以及其在單個空閑的計算資源上最少的運行時間之間的差值Di，并記錄該計算資源；

步驟3.3：在所有作業中找到差值Di最大的作業，并將該Di記為D；

步驟3.4：若???????????????????????????????????????????????，則分派作業給記錄的資源進行處理，同時將該資源從空閑資源集合中去除；若，則重新確定分配的資源和空閑資源集合，將完成其分配作業的資源加入到空閑資源集合中，然后返回步驟3.1；

步驟3.5：重復步驟3.2到步驟3.4直到為所有申請作業的資源分配了作業。

3.根據權利要求1所述的云環境下的Max-D作業調度方法，其特征在于，所述步驟3.1中計算資源平均估計完成時間方法如下：

假設云環境是由n個未分配作業和m個資源組成，每個資源同時只能對一個作業進行處理；資源中空閑的資源個數為k，記為，其中k<m；作業ti在資源rj上的估計運行時間為TCirj，則作業ti在所有資源上的平均運行時間為；

作業ti在資源rj上的完成時間，是正在rj上執行的作業的剩余完成時間以及作業ti在rj上的完成時間之和；

假設在云環境中，對于同一類作業，資源處理的速率與其處理的數據量成正比，作業i在資源r上的預計完成時間為正在資源r上運行作業的剩余完成時間以及作業i在資源r上執行時間之和：

??（1）

其中，表示將資源rj處理作業ti所需的完成時間，表示前一個作業在資源rj上的預測完成時間；是運行該作業所需時間與運行單位作業所需時間的比值；表示前一個作業在rj上實際運行時間，表示前一個作業的完成比例，如果資源rj是空閑資源，即前一個作業已經執行完成，則，上述公式可以簡化為

??????????（2）

通過該資源上前一個作業的估計執行時間和實際執行時間，使用公式（1）進行估算得到未調度的作業在某個資源上的執行時間；

在系統剛啟動時，對于所有資源，令

??????????????????????????????（3）

待執行作業會首先選擇未執行過作業的資源進行執行，在資源執行完第一個作業后，便得到了作業的實際執行時間，令等于，則之后作業的運行時間按照公式（1）進行估算。

4.根據權利要求1所述的云環境下的Max-D作業調度方法，其特征在于，步驟3.2中計算差值D的方法如下：

作業ti在所有未分配工作的節點上的最小運行時間記為，記錄下滿足的未分配作業rj’，并記，然后根據公式，得到作業i的差值Di。