基于語義網(wǎng)格環(huán)境的資源共享模型與分布式資源調(diào)度算法研究

王帥+馬景奕

摘要：為解決多資源文件共享和語義網(wǎng)格環(huán)境下異構(gòu)資源共享管理問題，提出了一種新的分布式調(diào)度算法。該算法采用語義網(wǎng)格的分布式技術(shù)，充分利用資源共享模型實現(xiàn)高效的資源調(diào)度。仿真實驗表明，該算法具有較好的執(zhí)行效率。與其它算法相比，在相同任務(wù)數(shù)量時響應(yīng)更快。

關(guān)鍵詞：語義網(wǎng)格；輕量級目錄訪問協(xié)議；資源共享模型；分布式調(diào)度算法；資源發(fā)現(xiàn)

DOIDOI：10.11907/rjdk.172030

中圖分類號：TP312

文獻標(biāo)識碼：A 文章編號：1672-7800（2017）012-0064-03

Abstract：rid is a hot technology for sharing， managing information resources and providing information services. In the current situation of increasingly serious environmental pollution， green cloud computing has become an important issue in the field of green communications.

In order to solve the problems in the management of heterogeneous resources in multi resource file sharing and semantic sharing in grid， this paper proposes a new distributed scheduling algorithm， the algorithm adopts the distributed semantic grid technology， and make full use of the resource sharing model， to achieve efficient resource scheduling， the simulation results show that the proposed algorithm has good execution efficiency， at the same time the number of tasks in response， faster response， and prove the effectiveness of the algorithm.

Key Words：semantic grid； lightweight directory access protocol； resources sharing model； distributed scheduling algorithm； resource discovery

0 引言

網(wǎng)格技術(shù)是新興的互聯(lián)網(wǎng)技術(shù)，是下一代互聯(lián)網(wǎng)技術(shù)研究和應(yīng)用的重要領(lǐng)域 [1]。近年來，物聯(lián)網(wǎng)、車聯(lián)網(wǎng)、云計算、大數(shù)據(jù)、綠色通信、量子通信、智慧城市、智能家居、深度學(xué)習(xí)等新概念和新技術(shù)層出不窮，語義網(wǎng)格逐漸引起人們的關(guān)注。網(wǎng)格是協(xié)調(diào)管理各種地理分布資源的手段，為用戶提供透明、一致的訪問接口，實現(xiàn)資源共享 [2]。

互聯(lián)網(wǎng)頁面大多數(shù)基于Web頁面技術(shù)，它的缺點是用HTML編寫，這種語言主要用于文本格式化，而不是識別和標(biāo)記內(nèi)容。同時，受限于用戶端，加載效率、兼容性不高。新的HTML標(biāo)準(zhǔn)已經(jīng)擴展（元標(biāo)簽），可向頁面添加更多信息，用于標(biāo)記整個頁面，而不是在給定頁面上的內(nèi)容描述[3]。HTML頁面的另一個目標(biāo)是提供到其它頁面和信息源鏈接。語義Web應(yīng)用于網(wǎng)格環(huán)境，形成語義網(wǎng)格，用于描述網(wǎng)格中信息的語義網(wǎng)格元數(shù)據(jù)。語義網(wǎng)格是網(wǎng)格相關(guān)技術(shù)的延伸，包括信息和服務(wù)，可使計算機系統(tǒng)與人更好地協(xié)同工作。語義網(wǎng)格通常是網(wǎng)格和語義Web技術(shù)的多重組合，通過不同組合提高計算能力和數(shù)據(jù)集成能力。

為解決多資源文件共享和語義網(wǎng)格環(huán)境下的管理問題，本文提出了一種基于語義網(wǎng)格環(huán)境的文件資源共享模型和分布式調(diào)度算法。該模型將注冊通知機制、確定性算法與非確定性算法消息傳遞機制互相組合，從而對網(wǎng)格中的各節(jié)點進行有效管理調(diào)度。本文提出一種新的分布式調(diào)度算法（NDSA），用于解決語義網(wǎng)格中的異構(gòu)資源共享問題。圖1 描述的是語義網(wǎng)格的文檔結(jié)構(gòu)。

通過應(yīng)用語義網(wǎng)格的分布式技術(shù)，將兩者有機結(jié)合，可極大提高資源調(diào)度的利用率。

1 語義網(wǎng)格資源共享模型

資源信息表現(xiàn)在兩個方面：①存儲在數(shù)據(jù)庫或其它介質(zhì)中的信息通過可視化呈現(xiàn)給用戶；②針對存儲介質(zhì)中的信息 [4]創(chuàng)建多個中間層信息，中間層在應(yīng)用邏輯層中用相應(yīng)的數(shù)據(jù)表示。

元數(shù)據(jù)是描述數(shù)據(jù)的數(shù)據(jù)，是對數(shù)據(jù)對象的抽象描述，使各種信息體現(xiàn)在屬性和值之間的關(guān)系上[5]。資源目錄服務(wù)功能模塊為分布式資源共享模型提供Grid信息服務(wù)[6]。資源目錄由元數(shù)據(jù)描述的所有資源構(gòu)成。資源目錄服務(wù)的主要任務(wù)是管理網(wǎng)格中的各種資源，包括資源發(fā)現(xiàn)、注冊、修改和取消。系統(tǒng)使用LDAP（輕量級目錄訪問協(xié)議）目錄服務(wù)器存儲資源目錄信息[7]。LDAP目錄樹結(jié)構(gòu)以樹級結(jié)構(gòu)存儲數(shù)據(jù)，以條目的形式存儲一組屬性，每條記錄包括屬性類型和屬性值，一個屬性可以存儲多個值。LDAP數(shù)據(jù)庫的靈活性和可擴展性，非常適用于廣域分布式資源共享系統(tǒng)。每個網(wǎng)格節(jié)點都要注冊本地資源來查找和收集監(jiān)控，并且每個節(jié)點維護本地LDAP服務(wù)器和本地存儲的資源信息。圖2描述的是語義網(wǎng)格之間的數(shù)據(jù)共享過程。

2 網(wǎng)格任務(wù)調(diào)度算法

通過互聯(lián)網(wǎng)將不同地理位置的分布式計算資源、存儲資源、通信資源、軟件資源、信息資源和知識資源集成為一個巨大的超級計算機，各種資源實現(xiàn)共享，這是網(wǎng)格作業(yè)調(diào)度的主要任務(wù)[8]。用戶向網(wǎng)格系統(tǒng)提交計算任務(wù)，為了共享網(wǎng)格資源和網(wǎng)格調(diào)度器，這些任務(wù)被分配到適當(dāng)?shù)恼{(diào)度資源上。高效的調(diào)度策略或算法可以利用網(wǎng)格系統(tǒng)的處理能力，提高面向?qū)ο蟮膽?yīng)用性能。在網(wǎng)格調(diào)度算法中，策略的主要目的是提高圖2 語義網(wǎng)格之間的數(shù)據(jù)共享過程

系統(tǒng)吞吐量和利用率，通過經(jīng)濟系統(tǒng)和用戶約束，使整個系統(tǒng)任務(wù)中的網(wǎng)格最小化。遺傳算法創(chuàng)建一個調(diào)度集合，從中找到最佳調(diào)度，這種繼承特性可以遺傳到下一代，遺傳算法通過適應(yīng)度函數(shù)交叉和重組實現(xiàn)最優(yōu)調(diào)度[9]。這是一種迭代算法，它具有吸收系統(tǒng)在演變過程中的變化差異優(yōu)勢，并能夠適應(yīng)網(wǎng)格系統(tǒng)的動態(tài)變化。

在網(wǎng)格技術(shù)的許多問題中，網(wǎng)格計算、任務(wù)調(diào)度是一般形式的NP問題，沒有最優(yōu)解。有效的調(diào)度算法，如并行資源分配決策和分布式調(diào)度算法，并不能很好地適應(yīng)資源異構(gòu)性網(wǎng)格的各種特性。因此，如何合理地分配和管理網(wǎng)格資源以滿足廣泛的服務(wù)需求，實現(xiàn)資源的最佳利用，成為該領(lǐng)域研究的關(guān)鍵。

網(wǎng)格任務(wù)調(diào)度可分為通信間任務(wù)、任務(wù)組調(diào)度和獨立任務(wù)組調(diào)度。集中式調(diào)度是系統(tǒng)中的中央調(diào)度員，負(fù)責(zé)收集狀態(tài)信息并作出所有調(diào)度決策。機器周期性地將分組更新到其發(fā)送狀態(tài)，報告其負(fù)載信息；中央調(diào)度服務(wù)建立一個主機候選者序列表，以響應(yīng)客戶請求的遠(yuǎn)程執(zhí)行。解決容錯集中調(diào)度問題的典型方法是提供多個備用服務(wù)員[10]。

3 實驗與結(jié)果分析

在Matlab環(huán)境下設(shè)計網(wǎng)格任務(wù)調(diào)度系統(tǒng)仿真程序。該程序根據(jù)主機處理能力、主機數(shù)量、任務(wù)數(shù)量、每個任務(wù)的預(yù)測執(zhí)行時間、通信開銷和時間的仿真等需求，生成任務(wù)開銷和其它參數(shù)。

圖3顯示的是在語義網(wǎng)格環(huán)境中3種算法的負(fù)載均衡度比較。負(fù)載均衡度越高，表明該算法執(zhí)行的效果越理想，資源利用的公平性越好。隨著系統(tǒng)任務(wù)數(shù)量的不斷增加，NDSA算法性能始終優(yōu)于其它兩種算法。

圖4顯示的是3種調(diào)度算法的響應(yīng)時間比較。圖5和圖6分別顯示在不同進化代數(shù)和不同任務(wù)規(guī)模時，3種調(diào)度算法的執(zhí)行時間情況。

4 結(jié)語

網(wǎng)格技術(shù)作為一種高性能的廣域分布式計算模型，是許多機構(gòu)的研究熱點。Matlab仿真實驗結(jié)果表明，本文提出的分布式調(diào)度算法（NDSA）具有較好的執(zhí)行效率，在相同任務(wù)數(shù)量時響應(yīng)速度更快，可在網(wǎng)格資源中實現(xiàn)公平有效的任務(wù)調(diào)度；在負(fù)載均衡度、系統(tǒng)響應(yīng)時間、系統(tǒng)執(zhí)行時間等方面，NDSA算法都比傳統(tǒng)的Max-min算法和GA算法表現(xiàn)出更佳的性能，該算法能有效應(yīng)用到語義網(wǎng)格各領(lǐng)域。

參考文獻：

[1] I FOSTER， C KESSELMAN，S TUECKE.The anatomy of the grid： enabling scalable virtual organizations[J]. International Journal Supercomputing Application， 2001，15（3）：200-222.

[2] M KAYA.Multi-objective genetic algorithm based approaches for mining optimized fuzzy association rules[J]. Soft Comput，2006，10（7）：578-586.

[3] L C JIAO， L WANG. A novel genetic algorithm based on immunity [J].IEEE Transaction on Systems， Man， and Cybernetics-Part A，Systems and Humans， 2000，30（5）：552-561.

[4] ZHONG WEI CAI， LIU JING， XUE MING ZHI， et al. A multi-agent genetic algorithm for global numerical optimization[J]. IEEE Trans.System，Man and Cybernetics—Part B，2004，34（2）：1128-1141.

[5] T HONG， C CHEN， Y WU， et al.A GA-based fuzzy mining approach to achieve a trade-off between number of rules and suitability of membership functions[J].Soft Comput，2006，10（11）：1091-1101.

[6] WANNENG SHU， SHIJUE ZHENG.A Real-course-based load balanced algorithm of VOD cluster[C].2005 International Symposium on Computer Science and Technology （ISCST 2005），Ningbo，2005.

[7] ZHANG JIANG SHE， XU ZONG BEN， LIANG YI. Global Annealing genetic algorithm and its convergence well necessary condition [J].science in China（Series E），1997，27（2）：154-164.

[8] WANG XIA， ZHOU GUO BIAO. Strong convergence of global annealing genetic algorithm[J]. mathematica applicata，2003，16（3）：1-7.

[9] RAJKUMAR BUYYA， DAVID ABRAMSON， JONATHAN GIDDY. Grid resource management， scheduling， and computational economy [C].WGCC，Japan， 2000.

[10] 孫清超，孫偉，郭鋼.多項目環(huán)境下復(fù)雜產(chǎn)品開發(fā)資源動態(tài)分配技術(shù)[J].中國機械工程，2011，22（23）：2844-2848.

[11] 熊張悅，姜俊穎，舒萬能.綠色云計算的任務(wù)調(diào)度與能耗優(yōu)化機制研究[J].軟件導(dǎo)刊，2016，15（4）：38-40.

（責(zé)任編輯：杜能鋼）