[發(fā)明專利]一種無中心節(jié)點(diǎn)計(jì)算機(jī)網(wǎng)絡(luò)的任務(wù)調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310741037.5
• 申請(qǐng)日: 2013-12-26
• 公開（公告）號(hào): CN103746838A
• 公開（公告）日: 2014-04-23
• 發(fā)明（設(shè)計(jì)）人: 丁一鳴;林川;王蘇岳
• 申請(qǐng)（專利權(quán)）人: 華北計(jì)算技術(shù)研究所
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 北京理工大學(xué)專利中心 11120
• 代理人: 高燕燕;仇蕾安

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

本發(fā)明涉及一種無中心節(jié)點(diǎn)計(jì)算機(jī)網(wǎng)絡(luò)的任務(wù)調(diào)度方法，屬于計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域，適用于無中心控制節(jié)點(diǎn)或關(guān)鍵節(jié)點(diǎn)的計(jì)算機(jī)網(wǎng)絡(luò)，尤其適用于并行處理應(yīng)用的無中心節(jié)點(diǎn)計(jì)算機(jī)網(wǎng)絡(luò)。

背景技術(shù)

目前，并行處理應(yīng)用主要采用的網(wǎng)絡(luò)架構(gòu)有兩種：一種為計(jì)算機(jī)集群網(wǎng)絡(luò)，另一種為無中心節(jié)點(diǎn)的計(jì)算機(jī)網(wǎng)絡(luò)。

對(duì)于計(jì)算機(jī)集群網(wǎng)絡(luò)來說，包括集群管理節(jié)點(diǎn)和集群計(jì)算節(jié)點(diǎn)幾類不同用途的網(wǎng)絡(luò)節(jié)點(diǎn)。其中，集群管理節(jié)點(diǎn)用來分配和管理集群系統(tǒng)的用戶帳號(hào)和權(quán)限，管理節(jié)點(diǎn)安裝集群管理軟件，作為主節(jié)點(diǎn)對(duì)整個(gè)集群進(jìn)行監(jiān)控、管理和作業(yè)調(diào)度等工作；集群計(jì)算節(jié)點(diǎn)用于科學(xué)計(jì)算，運(yùn)行并行計(jì)算程序，是計(jì)算機(jī)集群網(wǎng)絡(luò)的主體。在計(jì)算機(jī)集群網(wǎng)絡(luò)中，是由集群管理節(jié)點(diǎn)統(tǒng)一實(shí)現(xiàn)對(duì)集群計(jì)算節(jié)點(diǎn)的狀態(tài)監(jiān)控和作業(yè)調(diào)度等，即集群管理節(jié)點(diǎn)是網(wǎng)絡(luò)中的中心節(jié)點(diǎn)或關(guān)鍵節(jié)點(diǎn)，如果集群管理節(jié)點(diǎn)出現(xiàn)故障，則導(dǎo)致整個(gè)計(jì)算機(jī)集群網(wǎng)絡(luò)處于癱瘓狀態(tài)，因此為了提高計(jì)算機(jī)集群網(wǎng)絡(luò)的可靠性，通常都是用兩臺(tái)互為熱備的服務(wù)器作為集群管理節(jié)點(diǎn)，但是仍然會(huì)存在著網(wǎng)絡(luò)整體癱瘓的可能性。

無中心節(jié)點(diǎn)的計(jì)算機(jī)網(wǎng)絡(luò)可以避免集群網(wǎng)絡(luò)的這種問題，對(duì)于無中心節(jié)點(diǎn)計(jì)算機(jī)網(wǎng)絡(luò)來說，網(wǎng)絡(luò)中的各計(jì)算機(jī)在控制地位上是平等的，沒有主備之分，當(dāng)有新任務(wù)發(fā)起或有計(jì)算機(jī)出現(xiàn)故障時(shí)，由各計(jì)算機(jī)自行發(fā)起任務(wù)調(diào)度控制。任意一臺(tái)或者幾臺(tái)計(jì)算機(jī)節(jié)點(diǎn)出現(xiàn)故障都不會(huì)影響網(wǎng)絡(luò)完成并行處理應(yīng)用的能力。

然而目前無中心節(jié)點(diǎn)的計(jì)算機(jī)網(wǎng)絡(luò)大多研究重點(diǎn)都在無線傳感器網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)在實(shí)際應(yīng)用時(shí)節(jié)點(diǎn)數(shù)量眾多、分布密集，相鄰節(jié)點(diǎn)之間產(chǎn)生的冗余數(shù)據(jù)很多，無線傳感器網(wǎng)絡(luò)的任務(wù)調(diào)度方法并不適用于計(jì)算機(jī)網(wǎng)絡(luò)，而通常計(jì)算機(jī)網(wǎng)絡(luò)的任務(wù)調(diào)度方法僅考慮某一個(gè)方面的影響，因此需要一種針對(duì)無中心節(jié)點(diǎn)的計(jì)算機(jī)網(wǎng)絡(luò)的多維全面的任務(wù)調(diào)度方法。

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

有鑒于此，本發(fā)明提供了一種無中心節(jié)點(diǎn)計(jì)算機(jī)網(wǎng)絡(luò)的任務(wù)調(diào)度方法，該方法考慮多維因素、綜合全面的任務(wù)調(diào)度方法，適用于并行處理應(yīng)用，以解決無線傳感器網(wǎng)絡(luò)的任務(wù)調(diào)度方法不適用于計(jì)算機(jī)網(wǎng)絡(luò)以及現(xiàn)有任務(wù)調(diào)度方法考慮方面單一不夠全面的問題。

為達(dá)到上述目的，本發(fā)明的技術(shù)方案為：

一種無中心節(jié)點(diǎn)計(jì)算機(jī)網(wǎng)絡(luò)的任務(wù)調(diào)度方法，該方法包括如下步驟：

步驟1、建立一個(gè)無中心節(jié)點(diǎn)的計(jì)算機(jī)網(wǎng)絡(luò)，所述網(wǎng)絡(luò)中具有k個(gè)節(jié)點(diǎn)，對(duì)所述k個(gè)節(jié)點(diǎn)進(jìn)行1至k的編號(hào)，記為N₁～N_k；每個(gè)節(jié)點(diǎn)中均存儲(chǔ)有節(jié)點(diǎn)負(fù)載表，所述節(jié)點(diǎn)負(fù)載表中記載所有節(jié)點(diǎn)實(shí)時(shí)負(fù)載狀態(tài)，其中負(fù)載狀態(tài)包括已啟動(dòng)的任務(wù)的數(shù)目、CPU剩余可用量、內(nèi)存剩余可用量以及硬盤剩余可用量；

各節(jié)點(diǎn)均定期通信，以獲取所有節(jié)點(diǎn)的實(shí)時(shí)負(fù)載狀態(tài)更新節(jié)點(diǎn)負(fù)載表；

步驟2、客戶端向上述網(wǎng)絡(luò)中所有節(jié)點(diǎn)廣播任務(wù)t的啟動(dòng)請(qǐng)求；

網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)執(zhí)行如下步驟3～步驟10；

步驟3、網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)在接收到任務(wù)t的啟動(dòng)請(qǐng)求后，解析該請(qǐng)求，獲得任務(wù)t的負(fù)載要求以及客戶端為各負(fù)載要求指定的優(yōu)先級(jí)，所述負(fù)載要求包括已啟動(dòng)的任務(wù)的數(shù)目、CPU剩余可用量、內(nèi)存剩余可用量以及硬盤剩余可用量，所述優(yōu)先級(jí)從1開始，數(shù)值越高，表示優(yōu)先級(jí)越低；

步驟4、令C=1，選擇所有節(jié)點(diǎn)作為候選最優(yōu)節(jié)點(diǎn)，任務(wù)t的負(fù)載要求中最低優(yōu)先級(jí)級(jí)數(shù)為U，進(jìn)入步驟5；

步驟5、由節(jié)點(diǎn)負(fù)載表獲取所有候選最優(yōu)節(jié)點(diǎn)中對(duì)應(yīng)該優(yōu)先級(jí)為C的負(fù)載狀態(tài)，并進(jìn)行對(duì)比，轉(zhuǎn)入步驟6；

步驟6、在候選最優(yōu)節(jié)點(diǎn)中，若僅存在節(jié)點(diǎn)N_j，其對(duì)應(yīng)優(yōu)先級(jí)為C的負(fù)載狀態(tài)最優(yōu)，則轉(zhuǎn)入步驟7；

在候選最優(yōu)節(jié)點(diǎn)中，若存在多個(gè)節(jié)點(diǎn)，其對(duì)應(yīng)優(yōu)先級(jí)為C的負(fù)載狀態(tài)相同且均為最優(yōu)，則更新候選最優(yōu)節(jié)點(diǎn)為該處所述多個(gè)節(jié)點(diǎn)，則轉(zhuǎn)到步驟8；

負(fù)載狀態(tài)最優(yōu)具體為：已啟動(dòng)的任務(wù)的數(shù)目最小為最優(yōu)，CPU剩余可用量、內(nèi)存剩余可用量以及硬盤剩余可用量最大為最優(yōu)；

步驟7、節(jié)點(diǎn)N_j是運(yùn)行任務(wù)t的最優(yōu)節(jié)點(diǎn)，轉(zhuǎn)到步驟10；

步驟8、判斷C是否小于U，如果是，則令C的值自增1，返回步驟5，否則轉(zhuǎn)到步驟9；

步驟9、在候選最優(yōu)節(jié)點(diǎn)中選擇編號(hào)最小或者最大的節(jié)點(diǎn)為最優(yōu)節(jié)點(diǎn)；

步驟10、最優(yōu)節(jié)點(diǎn)啟動(dòng)任務(wù)t。

進(jìn)一步地，步驟10中，最優(yōu)節(jié)點(diǎn)啟動(dòng)任務(wù)t之后，還包括如下步驟：

最優(yōu)節(jié)點(diǎn)實(shí)時(shí)監(jiān)測(cè)著任務(wù)t的運(yùn)行狀態(tài)，若任務(wù)t運(yùn)行不正常，則保存任務(wù)運(yùn)行斷點(diǎn)，同時(shí)最優(yōu)節(jié)點(diǎn)重新啟動(dòng)任務(wù)t，并使任務(wù)t從斷點(diǎn)處開始運(yùn)行。

進(jìn)一步地，步驟10中，最優(yōu)節(jié)點(diǎn)啟動(dòng)任務(wù)t之后，還包括如下步驟：