[發(fā)明專利]一種基于預(yù)調(diào)度的任務(wù)分配方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310403754.7
• 申請(qǐng)日: 2013-09-06
• 公開(kāi)（公告）號(hào): CN103500119A
• 公開(kāi)（公告）日: 2014-01-08
• 發(fā)明（設(shè)計(jì)）人: 董小社;劉強(qiáng);朱正東;陳衡
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F9/46
• 分類號(hào): G06F9/46;G06F9/50
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 陸萬(wàn)壽

1.一種基于預(yù)調(diào)度的任務(wù)分配方法，其特征包括以下步驟：

1）啟動(dòng)主節(jié)點(diǎn)Job?Tracker，開(kāi)始主循環(huán)并啟動(dòng)IPC?Handler監(jiān)聽(tīng)和處理子節(jié)點(diǎn)的心跳信息；

2）IPC?Handler循環(huán)判斷是否有子節(jié)點(diǎn)發(fā)來(lái)心跳信息，若沒(méi)有則返回步驟1)；

若有心跳信息到來(lái)則判斷該子節(jié)點(diǎn)之前是否執(zhí)行了預(yù)調(diào)度任務(wù)，若沒(méi)有執(zhí)行預(yù)調(diào)度任務(wù)則轉(zhuǎn)步驟3），若執(zhí)行了預(yù)調(diào)度任務(wù)則查看前次預(yù)調(diào)度任務(wù)是否成功，若失敗則記錄該失敗任務(wù)的子節(jié)點(diǎn)編號(hào)，成功則從預(yù)調(diào)度任務(wù)隊(duì)列和待調(diào)度任務(wù)隊(duì)列刪除已完成的任務(wù)；

3）判斷該子節(jié)點(diǎn)的負(fù)載是否較輕，若該子節(jié)點(diǎn)負(fù)載較輕，則為其在待調(diào)度任務(wù)隊(duì)列中尋找符合下列條件的預(yù)調(diào)度任務(wù)，即當(dāng)一個(gè)任務(wù)滿足：

①該任務(wù)處于可運(yùn)行的狀態(tài)；

②該任務(wù)未在此子節(jié)點(diǎn)上失敗過(guò)；

③該任務(wù)滿足數(shù)據(jù)本地性；

這三個(gè)條件時(shí)，選中該任務(wù)并將其加入預(yù)調(diào)度任務(wù)列表，Job?Tracker將預(yù)調(diào)度任務(wù)和其他待執(zhí)行任務(wù)一起加入心跳信息中，否則，按普通任務(wù)指令進(jìn)行；

否則，返回步驟1）；

4）Job?Tracker將心跳信息返回子節(jié)點(diǎn)。

2.根據(jù)權(quán)利要求1所述的基于預(yù)調(diào)度的任務(wù)分配方法，其特征在于：所述的判斷該子節(jié)點(diǎn)的負(fù)載是否較輕，是根據(jù)預(yù)先分配任務(wù)即其數(shù)量占總體任務(wù)的比例由用戶自行配置，默認(rèn)是5%，同時(shí)在當(dāng)前尚未運(yùn)行的任務(wù)集合中去掉該任務(wù)的信息，將其加入預(yù)分配任務(wù)列表。

3.根據(jù)權(quán)利要求1所述的基于預(yù)調(diào)度的任務(wù)分配方法，其特征在于：所述的子節(jié)點(diǎn)(Task?Tracker)端與主節(jié)點(diǎn)(Job?Tracker)端相關(guān)的部件包括以下幾個(gè)部分：

1）主節(jié)點(diǎn)(Job?Tracker)端相關(guān)的部件為IPC?Handler，用于處理子節(jié)點(diǎn)的心跳請(qǐng)求和任務(wù)預(yù)分配流程；

2）子節(jié)點(diǎn)(Task?Tracker)端的部件為：

①Task?Launcher：即任務(wù)執(zhí)行部件，其從待執(zhí)行任務(wù)隊(duì)列(Task?Queue)中取出待執(zhí)行任務(wù)，放入相應(yīng)的資源槽(slot)中執(zhí)行該任務(wù)；

②Task?Pre?Scheduler：即預(yù)調(diào)度線程，負(fù)責(zé)在滿足預(yù)調(diào)度的條件下，將預(yù)先存儲(chǔ)在預(yù)調(diào)度任務(wù)隊(duì)列(Task?Pre?Schedule?Queue)中的任務(wù)取出，放入待執(zhí)行隊(duì)列，執(zhí)行預(yù)調(diào)度。

4.根據(jù)權(quán)利要求3所述的基于預(yù)調(diào)度的任務(wù)分配方法，其特征在于：所述的子節(jié)點(diǎn)(Task?Tracker)從主節(jié)點(diǎn)(Job?Tracker)接收到心跳信號(hào)后，將其中的任務(wù)指令存入待執(zhí)行任務(wù)隊(duì)列(Task?Queue)并通知消費(fèi)者(Task?Launcher)，Task?Launcher則按照時(shí)間順序依次執(zhí)行Task?Queue隊(duì)列中的任務(wù)；

如果出現(xiàn)了Task?Queue隊(duì)列為空且此時(shí)離下一次心跳周期還有較長(zhǎng)時(shí)間，系統(tǒng)中又有空閑資源的情況下，會(huì)啟動(dòng)預(yù)調(diào)度線程Task?Pre?Scheduler，將先前預(yù)分配的任務(wù)放入Task?Queue隊(duì)列并通知Task?Launcher線程開(kāi)始工作。

5.根據(jù)權(quán)利要求1所述的基于預(yù)調(diào)度的任務(wù)分配方法，其特征在于：所述的子節(jié)點(diǎn)Task?Tracker接收預(yù)分配的任務(wù)后按下列步驟進(jìn)行：

1）Task?Tracker啟動(dòng)后開(kāi)始主循環(huán)，同時(shí)啟動(dòng)任務(wù)的執(zhí)行線程Task?Launcher；

2）Task?Tracker的主循環(huán)接收到主節(jié)點(diǎn)返回的心跳信息，該返回的心跳信息中包含著分配的任務(wù)指令，如果心跳信息中包含預(yù)調(diào)度指令則保存該預(yù)調(diào)度任務(wù)，啟動(dòng)預(yù)調(diào)度線程Task?Pre?Scheduler，并對(duì)Task?Pre?Scheduler進(jìn)行計(jì)時(shí)，如果超時(shí)，將預(yù)調(diào)度失敗結(jié)果存入心跳信息后執(zhí)行步驟5），否則繼續(xù)執(zhí)行步驟3）；

3）Task?Pre?Scheduler會(huì)持續(xù)的判斷當(dāng)前是否滿足如下條件:

①Task?Launcher的待執(zhí)行任務(wù)池是否為空；

②此時(shí)距離下一次心跳開(kāi)始的時(shí)間是否足夠長(zhǎng)；

③當(dāng)前是否有空閑資源；

如果條件均滿足則Task?Pre?Scheduler就會(huì)將先前保存的預(yù)調(diào)度任務(wù)加入Task?Launcher的待執(zhí)行任務(wù)池中并通知Task?Launcher開(kāi)始執(zhí)行；

否則返回Task?Tracker主循環(huán)；

4）當(dāng)該任務(wù)完成后，Task?Tracker銷毀Task?Pre?Scheduler線程，保存任務(wù)的執(zhí)行結(jié)果；

5）Task?Tracker通過(guò)心跳信息通知Job?Tracker，預(yù)調(diào)度流程結(jié)束。