潘善亮，黃 希，茅琴嬌

（1.寧波大學信息科學與工程學院 寧波315211；2.西安交通大學電子與信息工程學院 西安710049）

1 引言

網(wǎng)格計算[1]環(huán)境下，有效的資源管理方案及資源調(diào)度算法對優(yōu)化資源的使用和資源調(diào)度效率的提高有著十分重要的作用。近年來提出的基于超級節(jié)點模式（super-peer model）的網(wǎng)格資源管理模式[2]在集中式搜索與擴展性強的、具有負載平衡以及容錯性的分布式搜索之間實現(xiàn)了平衡，并為位于不同區(qū)域的網(wǎng)格物理組織之間進行互聯(lián)提供了一個很好的框架。因此，基于超級節(jié)點模式的網(wǎng)格計算在提出后便成為研究的熱點。超級節(jié)點網(wǎng)絡與傳統(tǒng)的P2P網(wǎng)絡相似，在傳統(tǒng)P2P網(wǎng)絡的基礎上，把每一個P2P節(jié)點變?yōu)橐粋€超級節(jié)點，每一個超級節(jié)點作為服務器與一系列的客戶機相連。這些超級節(jié)點之間則采用P2P方式在更高層次上相互連接。面向服務的開放網(wǎng)格服務體系結(jié)構（OGSA）[3]和Web服務資源框架（WSRF）[4]為網(wǎng)格與P2P的集成提供了一個框架，使不同區(qū)域的服務器可以使用Web服務實現(xiàn)P2P互連。

目前，國內(nèi)外學者對超級節(jié)點模式網(wǎng)格計算的研究主要集中在如下3個方面：

·資源的發(fā)現(xiàn)與定位；

·超級節(jié)點之間的拓撲連接協(xié)議與體系結(jié)構；

·超級節(jié)點的選擇方法，如Carlo M等[5]對超級節(jié)點模式的網(wǎng)格以及層次式網(wǎng)格、分布式純P2P模式網(wǎng)格進行了性能仿真、分析和對比，得出超級節(jié)點模式網(wǎng)格的優(yōu)點，還講述了超級節(jié)點模式如何實現(xiàn)多機構網(wǎng)格資源管理中進行的服務發(fā)現(xiàn)[2]；Kwan S K等[6]采用一種gossip協(xié)議交換超級節(jié)點之間的資源信息，大大提高了資源的發(fā)現(xiàn)效率；Peter M等人[7]針對個人計算機P2P網(wǎng)絡提出了一個能自行組織和管理的超級節(jié)點網(wǎng)絡；Yin L等人[8]利用經(jīng)常在線的節(jié)點作為超級節(jié)點來管理那些經(jīng)常離開的不穩(wěn)定節(jié)點，這些穩(wěn)定的節(jié)點之間構成DHT（distribute hash table）環(huán)；Pasquale C等人[9]提出了一個超級節(jié)點模式系統(tǒng)結(jié)構的網(wǎng)格，可以對龐大的數(shù)據(jù)量進行分析；Wu C C等人[10]提出了一種網(wǎng)格架構G2G以實現(xiàn)自治網(wǎng)格之間的互聯(lián)；Sheng H Z等人[11]對超級節(jié)點的選擇進行了研究，通過評估超級節(jié)點的計算能力，提出了一個超級節(jié)點的選擇策略。

Petri網(wǎng)[12]具有并發(fā)、異步、動態(tài)等特點，已成為模擬和分析信息系統(tǒng)的有力工具，在資源調(diào)度中得到了廣泛研究和應用，但還有一些問題值得探討，如參考文獻[13]中利用Petri網(wǎng)對超級節(jié)點模式的網(wǎng)格調(diào)度進行形式化建模與理論分析，將超級節(jié)點模式的網(wǎng)格任務、資源節(jié)點和時間限制映射到層次、顏色、時延Petri網(wǎng)，但所建立的模型只考慮了時間維度的服務屬性，其調(diào)度對象是簡單的不可分割的獨立任務，沒有考慮網(wǎng)格資源的動態(tài)性等機制。

目前Petri網(wǎng)調(diào)度建模機制在超級節(jié)點模式網(wǎng)格計算方面的應用研究還存在如下幾個方面的不足。

·資源分配和任務調(diào)度策略大部分以系統(tǒng)為中心，只考慮了服務時間維度的服務屬性參數(shù)，較少考慮面向用戶QoS的要求（如截止時間、費用上限以及二者之間的權衡參數(shù)）和用戶需求的多目標性，導致資源分配無效和不公平的情況發(fā)生。

·超級節(jié)點模式的網(wǎng)格調(diào)度是針對相互獨立的不可分割的任務進行的，而網(wǎng)格任務通常是可以分解的復合任務，因此有必要建立復合任務的調(diào)度機制，以優(yōu)化調(diào)度策略。

·沒有考慮網(wǎng)格資源的動態(tài)性，當資源出現(xiàn)故障時對

重調(diào)度機制考慮不足。

本文重點研究面向用戶QoS參數(shù)（時間、價格以及二者之間的權重）要求的超級節(jié)點模式網(wǎng)格復合任務調(diào)度算法，分析復合任務的調(diào)度過程，給出系統(tǒng)的最佳調(diào)度方案和重調(diào)度機制，對任務的調(diào)度過程進行價格時延Petri網(wǎng)形式化建模與理論分析，以驗證算法的有效性，為系統(tǒng)性能評價提供依據(jù)。

2 超級節(jié)點模式的網(wǎng)格資源管理模型

本文討論的超級節(jié)點模型是如圖1所示的分層體系結(jié)構。

依據(jù)節(jié)點的非功能參數(shù)，把性能評估參數(shù)較高的節(jié)點（以下稱為超級節(jié)點）作為上層管理，構成系統(tǒng)中的骨干層。每個超級節(jié)點作為服務器與一系列由不同組織管理的客戶機一起構成一個傳統(tǒng)的網(wǎng)格模式，而這些上層超級節(jié)點采用P2P通信方式構成一個大規(guī)模網(wǎng)格。每個超級節(jié)點控制著一組本地計算機資源的訪問權限，代表著一個超級管理域，稱為網(wǎng)格社區(qū)。一般地，當網(wǎng)格社區(qū)內(nèi)的用戶節(jié)點需要訪問網(wǎng)格時，超級節(jié)點在它的管理域內(nèi)以傳統(tǒng)網(wǎng)格集中式搜索方式查找匹配的資源，如果沒有找到，則通過P2P方式在其他超級節(jié)點之間進行查詢[14，15]。由此，引入如下定義。

定義1 peer-to-peer grid={super-peer1,super-peer2,…,super-peern}，其中，super-peer1,super-peer2,…,super-peern是grid community1,grid community2,…,grid communityn所 對應的網(wǎng)格虛擬社區(qū)。

定義2 super-peeri={node1,node2,…,nodem}，其中node1,node2,…,nodem表示具有自主能力的主機或其他資源。

定義3 nodei=(IDi,IDsuper-peeri)表示節(jié)點的屬性，IDi、IDsuper-peeri分別表示節(jié)點標識符和節(jié)點所在的超級節(jié)點網(wǎng)格社區(qū)標識符。

3 基于市場經(jīng)濟體制的超級節(jié)點模式網(wǎng)格復合任務調(diào)度算法

3.1 復合任務調(diào)度模型

在網(wǎng)格環(huán)境中進行資源管理和調(diào)度是個非常復雜的問題。在網(wǎng)格系統(tǒng)中，大量地理上分布的各種資源為不同的組織所擁有，這些組織具有不同的使用規(guī)則、計費模型、負荷能力和使用模型，資源擁有者和資源使用者各自具有不同的目標、目的、策略和需求，一些傳統(tǒng)的資源管理和調(diào)度方式在網(wǎng)格系統(tǒng)中并不適用，而基于計算經(jīng)濟模型的網(wǎng)格任務調(diào)度方案是一個很好的解決方案。

圖1 網(wǎng)格計算超級節(jié)點模式的兩層資源管理體系結(jié)構

基于市場經(jīng)濟的超級節(jié)點模式的網(wǎng)格復合任務調(diào)度模型如圖2所示。在模型中，超級節(jié)點具有代理[16]功能，用戶直接在本地計算機（源節(jié)點）提交任務，并規(guī)定任務的截止完成時間和費用上限以及時間和費用的偏好參數(shù)，任務被傳輸?shù)奖镜爻壒?jié)點，稱這個超級節(jié)點為源超級節(jié)點。超級節(jié)點判斷該任務是否能分解成子任務，如果能，則將任務分解成具有時間依賴關系的子任務集合，同時將時間、費用總要求分解，形成每個子任務的具體要求，并建立調(diào)度列表，然后按照調(diào)度列表選取并判斷任務（子任務）能否在超級節(jié)點社區(qū)內(nèi)提交它的資源節(jié)點并在截止時間內(nèi)完成，如果能，則直接調(diào)度到它上面執(zhí)行。

這里做出如下規(guī)定：

·每個資源節(jié)點在對應的超級節(jié)點處有一個用戶賬戶，記錄費用的使用狀況，由超級節(jié)點負責管理；

·超級節(jié)點根據(jù)它所管理的資源利用狀況給出對于具體任務的估計執(zhí)行時間和費用；

·任務（子任務）在資源節(jié)點上執(zhí)行時，不產(chǎn)生網(wǎng)格費用消耗。

相反地，當資源節(jié)點執(zhí)行由其他節(jié)點（包括本網(wǎng)格社區(qū)內(nèi)的其他資源節(jié)點和遠程超級節(jié)點管理域內(nèi)的資源節(jié)點）提交的任務（子任務）時，將收取一定的網(wǎng)格費用。因此，超級節(jié)點優(yōu)先將任務（子任務）調(diào)度到提交它的資源節(jié)點上執(zhí)行。若不行，則考慮將任務（子任務）調(diào)度到本地網(wǎng)格社區(qū)內(nèi)滿足用戶要求的其他某一最優(yōu)節(jié)點上執(zhí)行。這一階段，超級節(jié)點對其管理域內(nèi)的本地資源節(jié)點采用集中式調(diào)度并進行內(nèi)部資源節(jié)點之間的轉(zhuǎn)賬交易，這種優(yōu)先本地任務策略能夠減少網(wǎng)絡阻塞。

圖2 超級節(jié)點模式的網(wǎng)格任務調(diào)度模型

若任務（子任務）不能在超級節(jié)點社區(qū)內(nèi)完成，超級節(jié)點將會與遠程超級節(jié)點進行通信，以尋找符合要求的某一最優(yōu)資源節(jié)點執(zhí)行任務（子任務），并為之代付一定的費用。每個超級節(jié)點都有一張遠程超級節(jié)點列表，并且可與它們交互，或存在一個中心目錄來維護與每個遠程超級節(jié)點相關的信息。這一階段，超級節(jié)點之間采用分布式調(diào)度。

對于復合任務，以上過程不斷地重復，直至調(diào)度列表中所有子任務都執(zhí)行完畢。只有當子任務的所有前驅(qū)子任務都執(zhí)行完畢后，該子任務才擁有被調(diào)度權。對于每一個任務（子任務），當執(zhí)行它的資源節(jié)點發(fā)生故障時，攜帶錯誤報告的執(zhí)行結(jié)果被傳送到源超級節(jié)點，源超級節(jié)點進行必要的重調(diào)度，并撤銷原來的相關交易。

基于以上調(diào)度模型，網(wǎng)格計算超級節(jié)點模式的超級節(jié)點代理框架如圖3所示，其中GKD是global knowledge database的縮寫，LKD是local knowledge database的縮寫。

圖3 超級節(jié)點代理的架構

超級節(jié)點代理架構包括4個分代理：任務分發(fā)代理（task-dividing agent）、本地代理 （local agent）、全球代理（global agent）、市場代理（market agent），各分代理的功能職責介紹如下。

·任務分發(fā)代理負責將本地資源節(jié)點上提交的網(wǎng)格應用分解成具有相互依賴關系的子任務集合（如果網(wǎng)格應用為元任務（meta task），則不用分解），建立調(diào)度列表，并將準備調(diào)度的任務交給本地代理。

·本地代理收到調(diào)度請求后，優(yōu)先將任務（子任務）調(diào)度到源節(jié)點。如果不行，則在本地網(wǎng)格資源社區(qū)內(nèi)查找相關的資源信息，若找到符合要求的資源，則聯(lián)系市場代理為任務（子任務）選擇最優(yōu)的資源進行調(diào)度，并由市場代理進行交易管理。否則，把調(diào)度請求發(fā)送給全球代理。

·全球代理負責兩方面的職責：一方面是將本地的XML Schema轉(zhuǎn)換為全球的Rdf本體，存儲在GKD中；另一方面是接收本地代理發(fā)送過來的調(diào)度請求，與其他超級節(jié)點代理中的全球代理進行交互，尋找合適的資源并聯(lián)系市場代理，為任務（子任務）選擇最優(yōu)的資源進行調(diào)度，并由市場代理完成超級節(jié)點間的交易管理。全球代理準確地知道其他超級節(jié)點域的所有本體，并且含有相關本體的概要信息。

3.2 復合任務調(diào)度算法

3.2.1 基于時間和價格的多目標線性規(guī)劃評價模型

定義如下參數(shù)：ti,j為任務（子任務）i在資源節(jié)點j上的估計執(zhí)行時間，T為任務（子任務）的截止期限與到達時間之差，ci,j為任務 （子任務）i在資源節(jié)點j上的估計執(zhí)行費用，C為任務（子任務）的費用上限，α+β=1,α≥0，β≥0。α、β為用戶定義的時間和費用權重。

定義4在截止期限和費用上限均能滿足的情況下，資源j對于任務（子任務）i的評價函數(shù)為：

即超級節(jié)點將從符合要求的多個資源中選擇使目標函數(shù)I最小的資源j作為任務（子任務）i的調(diào)度目標。

為了簡化模型，假設超級節(jié)點模式的網(wǎng)絡帶寬足夠?qū)?，資源節(jié)點與超級節(jié)點以及超級節(jié)點與超級節(jié)點之間的通信、任務（子任務）以及結(jié)果的傳輸時延很小，相對于任務的執(zhí)行時間可以忽略不計，所有任務或子任務均能在系統(tǒng)內(nèi)找到合適的資源。

3.2.2 超級節(jié)點模式網(wǎng)格復合任務調(diào)度算法

算法具體如下。

Input：grid task GT

Output：mapping and assignment of grid tasks on nodes Begin

While GT comes from local grid community do

If GT can decompose

Else GT is called indivisible task；

For every grid task GTi(GTiis an sub-task or indivisible task)

If ExecutedTime(GTi,super-peers,nodej)≤DeadlineTime(GTi)//nodej是提交GTi的源資源節(jié)點

Then Allocate(GTi,super-peers,nodej)；

If an error occurs to nodej

Then SendResult0(GTi,super-peers)；

在PLC的理論教學中，我們通常會說PLC的功能很強大，在工業(yè)現(xiàn)場和許多場合都得到了廣泛的應用。無論老師在課堂上講得有多么精彩，學生對PLC的具體應用還是不清楚。如果在PLC的教學中運用虛擬仿真技術，通過計算機模擬實際的控制系統(tǒng)，那么效果將會大大提升。

//返回一個含有錯誤報告的執(zhí)行結(jié)果，超級節(jié)點將會對GTi進行重調(diào)度

Else SendResult1(GTi,super-peers)；//返 回 正 常 的執(zhí)行結(jié)果

Else if in super-peersexist nodek(k≠j)which meets the following two requirements:

ArrivalTime(GTi)+

ExecutedTime(GTi,super-peers,nodek)≤Deadline Time(GTi);//時間屬性要求

ExecutedCost(GTi,super-peers,nodek)≤CostLimt(GTi)；//費用屬性要求

Then for all nodekcalculate the function I;

Seek for the smallest I and the corresponding nodek′；

Allocate(GTi,super-peers,nodek′)；

If an error occurs to nodek′

Then SendResult0(GTi,super-peers)；

Else SendResult1(GTi,super-peers)；

Else Queuing(GTi,Peer-to-Peer Grid)；//先 將GTi插入隊列中

Interact with other super-peers;

For every nodelin every(super-peers)which meets the following two requirements：

ArrivalTime(GTi)+

ExecutedTime(GTi,super-peers,nodel)≤Deadline Time(GTi)；

ExecutedCost(GTi,super-peers,nodel)≤CostLimt(GTi)；

Calculate the function I；

Seek for the smallest I and the corresponding super-peers、nodel′；

Send(GTi,super-peers);//將GTi發(fā)送到目標資源節(jié)點所屬的超級節(jié)點End While

While GT comes from remote super-peers

Allocate(GT,super-peers,nodem)；//nodem指上面提到的nodel′

If an error occurs to

Then SendResult0(GT,super-peers,super-peerr)；

Else SendResult1(GT,super-peers,super-peerr)；

End While

End

4 網(wǎng)格調(diào)度的層次顏色、價格時延Petri網(wǎng)模型

Petri網(wǎng)是一個描述異步并發(fā)的圖形工具，具有可達樹、可達圖、關聯(lián)矩陣等多種分析方法，并且可以通過數(shù)學方法證明其正確性，本文把它同網(wǎng)格調(diào)度結(jié)合起來作為研究的工具。

4.1 價格時延Petri網(wǎng)以及用戶應用定義

有關Petri網(wǎng)的基本概念、詳細內(nèi)容見參考文獻[20]。本文給出價格時延Petri網(wǎng)的定義，具體如下。

定義5價格時延Petri網(wǎng)[21]CTPN=(PN,Γ,D,C)，其中：

·PN是Petri網(wǎng)，PN=（S,T,F）；

·Γ是一個集合，其元素（tj,τk）表示變遷tj實施的時刻為τk；

·D={dj/j=1,…，m},dj∈R+∪{0},表示完成 每個變遷tj所需要的時間，m為變遷的個數(shù)；

·C={cj/j=1,…，m},cj∈R+∪{0},表示完成每個變遷tj所需要的費用，m為變遷的個數(shù)。

用戶可通過給定的d、c、τ定義對任務的QoS需求。用戶復合任務進行分解后形成相互之間具有依賴關系的子任務集合，子任務之間存在諸如順序、分支、循環(huán)、并行等關系。

定義6用戶應用UA可以用類BNF表示為UA::=ε/X/T/T◇T/T茚T/T茌T/μT，其中：

·ε代表空任務；X代表一個任務常量，需要固定的時間和成本完成，這兩個任務是為保證系統(tǒng)的完整性而引入的；

·T◇T代表兩個任務順序執(zhí)行，總的執(zhí)行時間為兩

者執(zhí)行時間之和，費用為兩者執(zhí)行費用之和；

·T茚T代表兩個任務分支執(zhí)行，一旦執(zhí)行了其中的一個，則不執(zhí)行另一個，相應的執(zhí)行時間、費用等于被選中任務的執(zhí)行時間、費用；

·T茌T代表兩個任務并行執(zhí)行，T1和T2應并行調(diào)度執(zhí)行，總的執(zhí)行時間取兩者中執(zhí)行時間最大的，而費用是兩者之和；

·μT表示循環(huán)執(zhí)行T共μ次，總的執(zhí)行時間和費用為一次執(zhí)行任務T對應值的μ倍。

4.2 網(wǎng)格任務調(diào)度的層次顏色、價格時延Petri網(wǎng)模型

定義7超級節(jié)點模式網(wǎng)格任務調(diào)度所對應的Petri網(wǎng)模型是一個層次顏色Petri網(wǎng)，HCPN=（Σ，P，S，T，F(xiàn)，C，G，E，I），其中：

·Σ={（rt,dt,dc,α,β）}∪{(et,ct)}∪{(ms,gt,gs)}是顏色的集合，rt、dt、dc分別是任務（子任務）的到達時間、截止期限、費用上限；α、β分別是用戶規(guī)定的時間費用權重；et、ct是任務（子任務）在各資源節(jié)點上執(zhí)行時所花費的時間和費用估計值；ms、gt、gs分別是資源的狀態(tài)信息、任務（子任務）及其執(zhí)行結(jié)果；

·P是子網(wǎng)的集合，P={super-peeri/i=1,2,…,n}，n是全局超級節(jié)點的個數(shù)，super-peeri是第i個超級節(jié)點所對應的子網(wǎng)；

·S是庫所的集合，S={si1,si2/i=1,2,…,n}，n是全局超級節(jié)點的個數(shù)，si1是超級節(jié)點負責接收從遠程超級節(jié)點發(fā)送過來的任務（子任務）與資源信息的單元，si2是超級節(jié)點向遠程超級節(jié)點發(fā)送任務 （子任務）與資源信息的發(fā)送單元；

·T是變遷的集合，T={tijk/i,j=1,2,…,n,i≠j，k=1，2，3}，n是全局超級節(jié)點的個數(shù)，tijk表示第i個超級節(jié)點的發(fā)送單元向第j個超級節(jié)點的接收單元發(fā)送消息，此處每個變遷的時延、價格屬性均為0，k=1，2，3分別表示發(fā)送本地資源節(jié)點的狀態(tài)信息、任務（子任務）及其執(zhí)行結(jié)果；

·F是弧的集合，F(xiàn)哿(P×S，S×P，S×T，T×S)；

·C是顏色函數(shù)，C∶S→∑；

·G是哨崗函數(shù)，G∶T→BoolExpression并且滿足坌t∈T：Type(G(t))=Boolean∧Type(var(G(t))哿∑，其中，var(G(t))表示函數(shù)G(t)所含變量的集合；

·E為弧函數(shù)，E∶F→BoolExpression，并且滿足坌f∈F，Type(E(f))=C(s)MS∧type(var(E(f))哿∑其 中，s為f連接的庫所；

·I為初始化函數(shù)，I∶S→∑為每一個庫所賦顏色值生成初始標識MS，即坌s∈S∶Type(I(s))=C(s)MS；

針對圖1，為了簡化模型，假定超級節(jié)點模式的網(wǎng)格由3個互連的超級節(jié)點組成，則對應的層次顏色Petri網(wǎng)（HCPN）模型如圖4所示。

定義8第i個超級節(jié)點super-peeri所對應的子網(wǎng)為一個價格時延、顏色、增廣Petri網(wǎng)。super-peeri=（Σ，S，T，F(xiàn)，W，M0，D，C），各變量的定義介紹如下：

·Σ={（rt,dt,dc,α,β）}∪{(et,ct)}∪{(ms,gt,gs)}是顏色的集合，rt、dt、dc分別是任務（子任務）的到達時間、截止期限、費用上限；α、β分別是用戶規(guī)定的時間費用權重；et、ct是任務（子任務）在各資源節(jié)點上執(zhí)行時所花費的時間和費用估計值；ms、gt、gs分別是資源的狀態(tài)信息、任務（子任務）及其執(zhí)行結(jié)果；

圖4 超級節(jié)點模式網(wǎng)格調(diào)度全局層次顏色Petri網(wǎng)模型

·S是庫所的集合，S={si/i=1,2,…,13}∪{(in,out)}，in對應超級節(jié)點的接收單元，out對應超級節(jié)點的發(fā)送單元；

·T是變遷的集合，T={tj/j=1,2,…,17}；

·F是弧的集合，W是弧的加權函數(shù)的集合，M0是初始標識；

·D∶T→R0是定義在變遷集T上的時延函數(shù)，D(t)=a表示變遷的發(fā)生需要a個單位時間來完成；

·C∶T→R0是定義在變遷集T上的價格函數(shù)，C(t)=b表示變遷的發(fā)生需要b個單位費用來完成。

super-peeri所對應的Petri網(wǎng)子網(wǎng)如圖5所示，它是一個價格時延、顏色、增廣Petri網(wǎng)。

對圖5中對應的庫所、變遷和抑制弧的說明見表1～表3。

5 系統(tǒng)性能

為了得到超級節(jié)點模式的網(wǎng)格任務最優(yōu)調(diào)度方案，觀察各任務（子任務）在執(zhí)行過程中產(chǎn)生的時延和費用情況，對系統(tǒng)進行性能評價，構造和分析對應的Petri網(wǎng)可達任務圖。

定義9層次顏色Petri網(wǎng)是超級節(jié)點模式網(wǎng)格調(diào)度對應的全局Petri網(wǎng)模型，HCPN的可達任務圖(RTG)是一個有向圖，表示為RTG(HCPN)=(V,E)，其中，V是由帶標記的標識所組成的頂點集合，E是由帶標記的連接標識的有向邊所組成的邊集合。借鑒參考文獻[20]，RTG(HCPN)=(V,E)的構造算法如下。

圖5 super-peeri所對應的價格時延、顏色、增廣Petri網(wǎng)

表1 圖5中的庫所含義說明

表2 圖5中的變遷含義說明

表3 圖5中的抑制弧含義說明

算法2計算可達任務圖

輸入：Petri網(wǎng)系統(tǒng)HCPN=。

輸出：對于有界網(wǎng)系統(tǒng)，可達任務圖RTG(HCPN)=(V,E)。

步驟1 RTG垂直分成m1+m2+…+mk+n個區(qū)域，其中n是超級節(jié)點的個數(shù)，mk是第k個超級節(jié)點中的客戶機的個數(shù)。

步驟2初始化任務可達圖RTG(HCPN)=（{M0，Φ}），M0標記為“新”。

步驟3 While在集合V中還存在標記為“新”的節(jié)點do

（1）從集合V中任意選擇一個標記為“新”的節(jié)點M∈V

（2）For每一個在標識M下可以發(fā)生的變遷tj do

計算M′,使得M→tjM′；

If M′埸V

Then i V=V∪{M′};

ii If tj∈{t1,t2,t3,t4,t5,t6,t7,t11,t14,t16,tijk},則 將M′放在超級節(jié)點域內(nèi)；

iii If tj∈{t8,t9,t10,t12,t13,t15,t17}則將M′放在超級節(jié)點內(nèi)某一指定的資源節(jié)點域內(nèi)。

E=E+{M,M′},并 將{M,M′}標 記 為tj/GTi,若tj∈{t9,t13}，則將tj附加標記[et,ec]，et、ec分別為GTi任務（子任務）在指定的資源節(jié)點上執(zhí)行產(chǎn)生的時延和費用。

將M′標記為[a,b]，a表示當前的時刻，b表示目前任務執(zhí)行到此累計消耗的費用。

（3）如果在標識M′下，原不可分解的任務執(zhí)行完畢或者復合任務的所有子任務均已執(zhí)行完畢，則將M′標記為“端點”；否則將M′標記為“新”。

（4）刪除M的“新”，然后轉(zhuǎn)到步驟3繼續(xù)執(zhí)行。

步驟4輸出可達任務圖RTG（HCPN）。

命題1設ne是RTG（HCPN）中“端點”的個數(shù)，則系統(tǒng)的吞吐量為ne。

證明 由算法2知，在RTG（HCPN）中，若為M′標記的“端點”，則表明有一個任務執(zhí)行完畢，因此整個系統(tǒng)當前已完成的任務數(shù)，即系統(tǒng)的吞吐量為RTG（HCPN）中“端點”的個數(shù)。

命題2設etj為RTG（HCPN）的第k個資源節(jié)點區(qū)域中標注在執(zhí)行變遷tj邊上的時延分量，sek=∑etj，μ與s分別是序列{sek/=1,2,…，m1+m2+…+mk}的平均值與標準差，則離散系數(shù)v=s/μ可用來判斷系統(tǒng)的負載平衡狀態(tài)。

證明 由算法2知，RTG（HCPN）的第k個資源節(jié)點區(qū)域中標注在執(zhí)行變遷tj邊上的etj為某一任務(子任務)在第k個機器上的執(zhí)行時間，而sek=∑etj即第k個機器執(zhí)行時間之和。又因為離散系數(shù)v=s/μ用來度量序列{sek}中數(shù)據(jù)的離散程度，如果離散系數(shù)較小，說明各機器執(zhí)行時間之和比較接近，因而系統(tǒng)就處于負載平衡狀態(tài)，反之，系統(tǒng)就處于負載不平衡狀態(tài)。因此，離散系數(shù)v=s/μ可用來判斷系統(tǒng)的負載平衡狀態(tài)。

命題3設Mk是RTG（HCPN）中的“端點”，ak、bk分別為Mk的時間、費用標識，則整個系統(tǒng)目前完成所有任務后所處的時刻為max{ak}，所消耗的總費用為∑bk。

證明 由算法2知，若Mk為RTG（HCPN）的“端點”，則表明某一個任務執(zhí)行完畢，標注在Mk上的實數(shù)ak為當前時刻，即任務執(zhí)行完畢的時刻，而系統(tǒng)完成所有任務后所處的時刻就是最后一個任務執(zhí)行完畢的時刻，因此整個系統(tǒng)完成所有任務后所處的時刻為max{ak}；標注在Mk上的實數(shù)bk為當前任務執(zhí)行完畢所耗費的累積費用，各復合任務之間相互獨立，所以，系統(tǒng)目前完成所有任務后所消耗的總費用為∑bk。

6 實例分析

假設在如圖6所示的一個超級節(jié)點模式的網(wǎng)格計算環(huán)境中，有兩個相互獨立的復合任務分別在節(jié)點1、節(jié)點3提交，它們的子任務結(jié)構如圖7所示，其中節(jié)點1和節(jié)點2屬于超級節(jié)點1所在的網(wǎng)格社區(qū)；節(jié)點3屬于超級節(jié)點2所在的網(wǎng)格社區(qū)；節(jié)點4屬于超級節(jié)點3所在的網(wǎng)格社區(qū)。

用戶在提交任務時，可以定義其QoS參數(shù)要求，如完成截止時間、能承受的費用上限、時間與費用的權重。超級節(jié)點在接收到復合任務后，為了使調(diào)度方案的形成相對簡單[21]，將復合任務的時間和價格QoS要求分解到每一個子任務，方便了調(diào)度方案的形成，大大減小了調(diào)度的復雜性。

圖6 一個超級節(jié)點模式網(wǎng)格任務調(diào)度實例

圖7 復合任務的子任務執(zhí)行依賴關系結(jié)構

表4給出了這些任務（子任務）的到達時間、截止期限、費用上限、時間費用權重、任務（子任務）在各資源節(jié)點上的估計執(zhí)行時間和估計執(zhí)行費用。

根據(jù)這些參數(shù)和算法1、Petri網(wǎng)模型以及算法2，可以構造出該系統(tǒng)網(wǎng)格調(diào)度對應的Petri網(wǎng)的RTG（HCPN），如圖8所示。

由表4及圖8可得到如下分析結(jié)果。

網(wǎng)格任務GT1、GT2的子任務均不能完全在各自的提交節(jié)點上完成。對于任務GT1，其子任務GT1-1可以在截止時間內(nèi)在提交它的節(jié)點1上執(zhí)行完成，并不產(chǎn)生費用消耗。GT1-2、GT1-3雖然不能在提交它的資源節(jié)點1上按時完成，但是在截止時間和預算允許的情況下，它們都能在本地超級節(jié)點管理的資源節(jié)點2上執(zhí)行。其中，GT1-2循環(huán)執(zhí)行5次。對于任務GT2，其子任務GT2-1、GT2-2可以在截止時間內(nèi)在提交它的節(jié)點3上執(zhí)行完成，并不產(chǎn)生費用消耗。對于GT2-3，本地網(wǎng)格社區(qū)不能滿足其QoS要求，超級節(jié)點2與超級節(jié)點1、3進行交互，發(fā)現(xiàn)滿足其截止時間和費用上限要求的節(jié)點有節(jié)點1、節(jié)點2、節(jié)點4，此時超級節(jié)點2中的市場代理將計算每個符合要求的資源節(jié)點的評價函數(shù)：

通過對比可以看出，節(jié)點1的評價函數(shù)值最小，將GT2-3調(diào)度到超級節(jié)點1管理的節(jié)點1節(jié)點上執(zhí)行。對于GT2-4，本地網(wǎng)格社區(qū)也不能滿足其QoS要求，同時符合其截止時間和費用上限要求的資源節(jié)點只有超級節(jié)點3管理的節(jié)點4，故節(jié)點4就是其調(diào)度目標。同理，對于GT2-5，其調(diào)度目標也是節(jié)點4。

節(jié)點1執(zhí)行所有任務所用時間之和se1=30+105=135，節(jié)點2執(zhí)行所有任務所用時間之和se2=110+35=145，節(jié)點3執(zhí)行所有任務所用時間之和se3=15+25=40，節(jié)點4執(zhí)行所有任務所用時間之和se4=120+60=180。se1、se2、se3、se4的平均值為μ=125，標準差為s=51.84，離散系數(shù)v==0.41，由命題2知，系統(tǒng)目前的負載平衡狀態(tài)一般，從執(zhí)行時間分布上看，節(jié)點3的負載比較輕。

可達任務圖有2個端點：M112、M215,系統(tǒng)的吞吐量為2。目前整個系統(tǒng)執(zhí)行完所有任務后所處的時刻為max{175,245}=245，所消耗的總費用為120+160=280。

表4 網(wǎng)格任務（子任務）的時間、價格等QoS要求

圖8 網(wǎng)格調(diào)度Petri網(wǎng)模型的RTG（HCPN）

7 結(jié)束語

本文首先給出了一種超級節(jié)點模式的網(wǎng)格資源管理模型。針對此模型，引入市場經(jīng)濟機制，允許網(wǎng)格用戶提出任務的完成截止期限、費用上限以及時間費用權重，將它們作為QoS參數(shù)。然后，給出對應的網(wǎng)格任務（復合任務）調(diào)度算法，并利用一種新的Petri網(wǎng)——價格時延Petri網(wǎng)對超級節(jié)點模式的網(wǎng)格任務調(diào)度進行建模?？紤]到網(wǎng)格環(huán)境中資源是動態(tài)變化的，在調(diào)度算法及Petri網(wǎng)模型中增加相應的容錯機制，當資源出現(xiàn)故障時，對任務進行重調(diào)度。最后，構建Petri網(wǎng)模型的可達任務圖，通過一個例子，分析了具有順序、并行或循環(huán)結(jié)構的復合任務的最佳調(diào)度方案、調(diào)度過程以及系統(tǒng)的吞吐量、負載平衡、調(diào)度時間、調(diào)度費用等重要特性。下一步的工作是進一步優(yōu)化此模型，完善網(wǎng)格任務的調(diào)度算法，使各資源節(jié)點的時間負載特性能盡量保持平衡。

1 Foster I,Kesselman C.The Grid:Blueprint for New Computing Infrastructure.Morgan Kaufmann Publishers,San Francisco,CA,1999

2 Mastroianni C,Talia D,Verta O.A super-peer model for resource discovery services in large-scale grids.Future Generation Computer Systems,2005,21(10):1235～1248

3 Foster I,Kesselman C,Jeffrey M,et al.Grid services for distributed system integration.IEEE Computer,2002,35(6):37～46

4 The web services resource framework.http://www.globus.org/wsrf/

5 Mastroianni C,Talia D,Verta O.Designing an information system for grids:comparing hierarchical,decentralized P2P and super-peer models.Parallel Computing,2008(34):593～611

6 Kwan S K,Muppala J K.Resource discovery and scheduling in unstructured peer-to-peer desktop grids.Proceedings of the International Conference on Parallel Processing Workshops,San Diego,CA,2010:303～312

7 Merz P,Wolf S,Schwerdel D,et al.A self-organizing super-peer overlay with a Chord core for desktop grids.Proceedings of IWSOS 2008,Vienna,Austria,2008:23～34

8 Li Y,Huang X L,Ma F Y,et al.Building efficient super-peer overlay network for DHT systems.Proceedings of GCC 2005,Beijing,China,2005:787～798

9 Cozza P,Talia D.A Super-Peer Model for Multiple Job Submission on a Grid.Core GRID Technical Report Number TR-0067,2007

10 Wu C C,Chin J H,Lin Y S,et al.G2G:a meta-grid framework for the convergence of P2P and grids.Proceedings of GPC 2009,Geneva,Switzerland,2009

11 Zhao S H,Chen G L，Wu G X,et al.A strategy for selecting super-peer in P2P and grid based hybrid system.Proceedings of Edutainment 2008,Nanjing,China,2008:192～199

12 Colored J K.Petri Nets-Basic Concepts,Analysis Methods and Practical Use:Basic Concepts(2nd Edition).Springer-Verlag,Heidelberg,Berlin,1996

13 熊曾剛,楊揚,曾明.基于Petri網(wǎng)的兩階段網(wǎng)格任務調(diào)度模型與分析.通信學報,2009,30(8):69～77

14 Andrade,Brasileiro N,Cirne F,et al.Discouraging free riding in a peer-to-peer CPU-sharing grid.High Performance Distributed Computing,2004,12(3):129～137

15 熊曾剛,楊揚,劉麗等.網(wǎng)絡資源管理的Grid和P2P集成方案及其關鍵技術分析.控制與決策,2008,23(1):1～7

16 Foster I,Jennings N R,Kesselman C.Brain meets brawn:why grid and agents need each other.Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems,New York,USA,July 2004

17 Xiong Z G,Yang Y,Zhang X M.Integrated agent and semantic P2P grid resource discovery model.Proceedings of Eighth ACIS International Conference on Software Engineering,Artificial Intelligence,Networking,and Parallel/Distributed Computing,IEEE Computer Society Press,Qingdao,China,2007

18 袁崇義.Petri網(wǎng)原理與應用.北京:電子工業(yè)出版社,2005

19 吳哲輝.Petri網(wǎng)導論.北京：機械工業(yè)出版社,2006

20 吉羅,瓦爾克.系統(tǒng)工程Petri網(wǎng)建模、驗證與應用指南.北京:電子工業(yè)出版社,2005

21 劉衛(wèi)東,宋佳興,林闖.基于價格時間Petri網(wǎng)的網(wǎng)格計算應用模型及分析.電子學報,2005,33(8):1416～1420