[發(fā)明專利]任務(wù)調(diào)度方法、裝置及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201611267226.3
• 申請(qǐng)日: 2016-12-31
• 公開（公告）號(hào): CN108268319A
• 公開（公告）日: 2018-07-10
• 發(fā)明（設(shè)計(jì)）人: 李湛;田江濤;劉毅;閆振英
• 申請(qǐng)（專利權(quán)）人: 中國(guó)移動(dòng)通信集團(tuán)河北有限公司;中國(guó)移動(dòng)通信集團(tuán)公司
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50;G06F17/30
• 代理公司: 北京東方億思知識(shí)產(chǎn)權(quán)代理有限責(zé)任公司 11258
• 代理人: 彭瓊

1.一種任務(wù)調(diào)度方法，其特征在于，包括：

依據(jù)控制流中多個(gè)任務(wù)之間的依賴關(guān)系，確定各個(gè)任務(wù)的初始優(yōu)先級(jí)，所述優(yōu)先級(jí)反映同一控制流中的各個(gè)任務(wù)的執(zhí)行順序；

以任務(wù)的執(zhí)行順序、任務(wù)的構(gòu)成以及任務(wù)在多個(gè)處理器中的分配情況為約束規(guī)則，建立任務(wù)調(diào)度模型；

對(duì)所述任務(wù)調(diào)度模型進(jìn)行求解以確定任務(wù)調(diào)度方案，使得按照所述任務(wù)調(diào)度方案執(zhí)行所述多個(gè)任務(wù)所需的時(shí)間最短，其中，所述任務(wù)調(diào)度方案包括所述多個(gè)任務(wù)的執(zhí)行順序。

2.按照權(quán)利要求1所述的方法，其特征在于，確定任務(wù)調(diào)度方案的步驟包括：

步驟A，基于所述初始優(yōu)先級(jí)確定當(dāng)前方案，以所述當(dāng)前方案作為所述任務(wù)調(diào)度模型的輸入值，計(jì)算執(zhí)行所述多個(gè)任務(wù)所需的時(shí)間Z(C)；

步驟B，以對(duì)所述當(dāng)前方案進(jìn)行調(diào)整而得到的新方案作為所述任務(wù)調(diào)度模型的輸入值，計(jì)算執(zhí)行所述多個(gè)任務(wù)所需的新時(shí)間Z’(C)；

步驟C，計(jì)算時(shí)間差ΔZ(C)＝Z'(C)-Z(C)；

步驟D，當(dāng)所述時(shí)間差ΔZ(C)的數(shù)值小于零時(shí)，將所述當(dāng)前方案更新為所述新方案，并執(zhí)行步驟F；

步驟E，當(dāng)所述時(shí)間差ΔZ(C)的數(shù)值大于或等于零時(shí)，執(zhí)行步驟F；

步驟F，若所述ΔZ(C)的數(shù)值連續(xù)大于或等于零的次數(shù)未達(dá)到閾值次數(shù)，則返回執(zhí)行所述步驟B；若所述ΔZ(C)的數(shù)值連續(xù)大于或等于零的次數(shù)達(dá)到所述閾值次數(shù)，則將所述當(dāng)前方案確定為所述任務(wù)調(diào)度方案。

3.按照權(quán)利要求1所述的方法，其特征在于，確定各個(gè)任務(wù)的初始優(yōu)先級(jí)的步驟包括：

依據(jù)所述各個(gè)任務(wù)中每一任務(wù)的后續(xù)任務(wù)的數(shù)量，確定該任務(wù)的初始優(yōu)先級(jí)，使得后續(xù)任務(wù)的數(shù)量越多，該任務(wù)的初始優(yōu)先級(jí)越高。

4.按照權(quán)利要求1所述的方法，其特征在于，所述任務(wù)調(diào)度模型由以下表達(dá)式確定：

j∈[1,m_i],o∈[1,l]；并且，

r(t_i,j,t_i,k)＝1→z_s(t_i,k)-z_e(t_i,j)≥0,j≠k,j,k∈[1,m_i]；

其中，

l表示處理器的總數(shù)，n表示控制流的總數(shù)，m_i表示第i個(gè)控制流中的任務(wù)的總數(shù)；t_i,k表示第i個(gè)控制流中的第k個(gè)任務(wù)；表示第i個(gè)控制流中的第j個(gè)任務(wù)t_i,j被分配到第o個(gè)處理器c_o上執(zhí)行的概率；π(c_o)表示處理器c_o中等待任務(wù)隊(duì)列的數(shù)量閾值；表示任務(wù)與任務(wù)t_i,k的執(zhí)行順序關(guān)系，若任務(wù)t_i,k是任務(wù)的后續(xù)任務(wù)，則的值取為1，否則為0；表示任務(wù)t_i,j在處理器c_o上執(zhí)行的優(yōu)先級(jí)，表示任務(wù)執(zhí)行的開始時(shí)間，z_e(t_i,j)表示任務(wù)t_i,j執(zhí)行的結(jié)束時(shí)間。

5.一種任務(wù)調(diào)度裝置，其特征在于，包括：

初始優(yōu)先級(jí)確定模塊，用于依據(jù)控制流中多個(gè)任務(wù)之間的依賴關(guān)系，確定各個(gè)任務(wù)的初始優(yōu)先級(jí)，所述優(yōu)先級(jí)反映同一控制流中的各個(gè)任務(wù)的執(zhí)行順序；

任務(wù)調(diào)度模型建立模塊，用于以任務(wù)的執(zhí)行順序、任務(wù)的構(gòu)成以及任務(wù)在多個(gè)處理器中的分配情況為約束規(guī)則，建立任務(wù)調(diào)度模型；

任務(wù)調(diào)度方案確定模塊，用于對(duì)所述任務(wù)調(diào)度模型進(jìn)行求解以確定任務(wù)調(diào)度方案，使得按照所述任務(wù)調(diào)度方案執(zhí)行所述多個(gè)任務(wù)所需的時(shí)間最短，其中，所述任務(wù)調(diào)度方案包括所述多個(gè)任務(wù)的執(zhí)行順序。