基于QoS的超級節點模式網格調度研究*

潘善亮，黃 希，茅琴嬌

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

1 引言

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

目前，國內外學者對超級節點模式網格計算的研究主要集中在如下3個方面：

·資源的發現與定位；

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

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

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

目前Petri網調度建模機制在超級節點模式網格計算方面的應用研究還存在如下幾個方面的不足。

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

·超級節點模式的網格調度是針對相互獨立的不可分割的任務進行的，而網格任務通常是可以分解的復合任務，因此有必要建立復合任務的調度機制，以優化調度策略。

·沒有考慮網格資源的動態性，當資源出現故障時對

重調度機制考慮不足。

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

2 超級節點模式的網格資源管理模型

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

依據節點的非功能參數，把性能評估參數較高的節點（以下稱為超級節點）作為上層管理，構成系統中的骨干層。每個超級節點作為服務器與一系列由不同組織管理的客戶機一起構成一個傳統的網格模式，而這些上層超級節點采用P2P通信方式構成一個大規模網格。每個超級節點控制著一組本地計算機資源的訪問權限，代表著一個超級管理域，稱為網格社區。一般地，當網格社區內的用戶節點需要訪問網格時，超級節點在它的管理域內以傳統網格集中式搜索方式查找匹配的資源，如果沒有找到，則通過P2P方式在其他超級節點之間進行查詢[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所 對應的網格虛擬社區。

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

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

3 基于市場經濟體制的超級節點模式網格復合任務調度算法

3.1 復合任務調度模型

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

圖1 網格計算超級節點模式的兩層資源管理體系結構

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

這里做出如下規定：

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

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

·任務（子任務）在資源節點上執行時，不產生網格費用消耗。

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

圖2 超級節點模式的網格任務調度模型

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

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

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

圖3 超級節點代理的架構

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

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

·本地代理收到調度請求后，優先將任務（子任務）調度到源節點。如果不行，則在本地網格資源社區內查找相關的資源信息，若找到符合要求的資源，則聯系市場代理為任務（子任務）選擇最優的資源進行調度，并由市場代理進行交易管理。否則，把調度請求發送給全球代理。

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

3.2 復合任務調度算法

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

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

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

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

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

3.2.2 超級節點模式網格復合任務調度算法

算法具體如下。

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的源資源節點

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

If an error occurs to nodej

Then SendResult0(GTi,super-peers)；

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

//返回一個含有錯誤報告的執行結果，超級節點將會對GTi進行重調度

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

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發送到目標資源節點所屬的超級節點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 網格調度的層次顏色、價格時延Petri網模型

Petri網是一個描述異步并發的圖形工具，具有可達樹、可達圖、關聯矩陣等多種分析方法，并且可以通過數學方法證明其正確性，本文把它同網格調度結合起來作為研究的工具。

4.1 價格時延Petri網以及用戶應用定義

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

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

·PN是Petri網，PN=（S,T,F）；

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

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

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

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

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

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

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

者執行時間之和，費用為兩者執行費用之和；

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

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

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

4.2 網格任務調度的層次顏色、價格時延Petri網模型

定義7超級節點模式網格任務調度所對應的Petri網模型是一個層次顏色Petri網，HCPN=（Σ，P，S，T，F，C，G，E，I），其中：

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

·P是子網的集合，P={super-peeri/i=1,2,…,n}，n是全局超級節點的個數，super-peeri是第i個超級節點所對應的子網；

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

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

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

·C是顏色函數，C∶S→∑；

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

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

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

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

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

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

圖4 超級節點模式網格調度全局層次顏色Petri網模型

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

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

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

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

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

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

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

5 系統性能

為了得到超級節點模式的網格任務最優調度方案，觀察各任務（子任務）在執行過程中產生的時延和費用情況，對系統進行性能評價，構造和分析對應的Petri網可達任務圖。

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

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

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

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

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

算法2計算可達任務圖

輸入：Petri網系統HCPN=。

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

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

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

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

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

（2）For每一個在標識M下可以發生的變遷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′放在超級節點域內；

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

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

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

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

（4）刪除M的“新”，然后轉到步驟3繼續執行。

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

命題1設ne是RTG（HCPN）中“端點”的個數，則系統的吞吐量為ne。

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

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

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

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

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

6 實例分析

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

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

圖6 一個超級節點模式網格任務調度實例

圖7 復合任務的子任務執行依賴關系結構

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

根據這些參數和算法1、Petri網模型以及算法2，可以構造出該系統網格調度對應的Petri網的RTG（HCPN），如圖8所示。

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

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

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

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

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

表4 網格任務（子任務）的時間、價格等QoS要求

圖8 網格調度Petri網模型的RTG（HCPN）

7 結束語

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

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網的兩階段網格任務調度模型與分析.通信學報,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 熊曾剛,楊揚,劉麗等.網絡資源管理的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網原理與應用.北京:電子工業出版社,2005

19 吳哲輝.Petri網導論.北京：機械工業出版社,2006

20 吉羅,瓦爾克.系統工程Petri網建模、驗證與應用指南.北京:電子工業出版社,2005

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