基于Ｐｅｔｒｉ Ｎｅｔｓ的協調機制研究

摘要：利用形式化和圖形化的建模工具Petri Nets對協調問題中的依賴關系及協調機制進行研究；提出任務之間基于資源的三種基本依賴關系；并用Petri Nets對這三種依賴關系相應的協調機制進行了表述，為協調問題的可計算描述提供了一種新的思考角度。

關鍵詞：協調； 依賴關系； 協調機制； Petri網

中圖分類號：TP3014文獻標志碼：A

文章編號：10013695(2007)04002603

0引言

協調作為一個重要的概念廣泛地出現在多個學科和社會經濟領域中，成為廣大學者共同關注的一個研究課題。近年來，關于協調已有大量的研究成果，例如組織理論中基于角色的任務分派^[1]、運籌學中關于資源分配的優化模型^[2]、分布式開放系統中支持軟件集成的軟件平臺Middleware等^[3]。然而這些關于協調的研究成果與具體應用領域密切相關，可移植性差，不利于協調理論及其應用的進一步發展。因此人們致力于探索通用的協調理論。

Malone和Crowston綜合多個學科關于協調的研究成果后，給出的定義是：協調是用來管理活動間依賴關系的額外動作^[4]。這種基于依賴觀點的研究從協調問題的描述層上研究協調，側重于協調問題的表達。其研究思路是通過對協調問題的分析，將其中的依賴進行分類，然后針對各種依賴設計相應的協調策略，靜態地反映協調的兩個過程，即發現依賴和決定行動。這種研究方法，使得協調脫離了具體的應用領域而存在，成為一種專門的知識（對應于領域知識而言）。作為研究成果的依賴關系以及相應的協調策略可以在解決各個領域中不同的協調問題時發揮作用。

然而目前對于依賴關系及協調策略的研究，多是作定性表述，給出的一般都是非形式化描述。這樣不利于協調問題在計算機上的表述，難以實現協調問題的計算機求解，阻礙了協調理論的進一步發展。針對這一問題，本文利用形式化和圖形化的建模工具Petri Nets對協調問題中的依賴關系及協調機制進行了研究。

1任務之間依賴關系的描述

1.1任務之間依賴關系的文獻綜述

關于任務之間依賴關系的研究已經有相當長的歷史，主要的研究成果集中在組織科學領域和人工智能領域。在組織科學領域，有的學者從任務執行體的角度討論依賴關系，如Thompson在其組織理論中提出匯聚（Pooled）、序列（Sequential）和交互（Reciprocal）三種相互依賴^[5]。有的學者從任務執行時間角度來討論依賴關系，如Allen提出活動基于時間的Before、Meet、Overlap、Start、End、During、Equal七種基本相互依賴^[6]。還有的學者從任務執行時所消耗的資源出發來研究相互依賴，如Malone和Crowston提出的三種基本相互依賴，即流（Flow）依賴、共享（Sharing）依賴和共同（Fit）依賴^[7]。在人工智能領域，Von Martial將任務之間的依賴關系分為有利的（Positive）和不利的（Negative）兩種。其中有利的關系包括協同關系、平等關系等，不利的關系包括使用資源的沖突、邏輯上的不相容等^[8]。Chen和Decker按任務之間關系的緊密程度將依賴關系分為硬（Hard）關系和軟（Soft）關系。其中硬關系包括使能（Enable）關系等，軟關系包括促進（Facilitate）關系等^[9]。Omicini A.和Ossowski S.按任務關系的存在方式將依賴關系分為主觀（Objective）依賴和客觀（Subjective）依賴^[10]。另外Raposo將任務之間的依賴分為時序依賴和資源依賴兩種類型，分別從任務的執行級和對象級兩個層次上加以討論，定義任務之間的相互依賴框架^[11]。

1.2任務之間基于資源的依賴關系

Malone從與多個活動相關的資源出發，提出了三種基本相互依賴，即流依賴、共享依賴和共同依賴，如圖1所示。其中流依賴是指一個活動發生所需要的資源由另一個活動產生，如流水線作業中相鄰兩個活動間的關系；共享依賴是指多個活動的發生需要相同的資源，如兩個活動都需要使用同一臺機器或由同一個人完成；共同依賴是指多個活動共同產生某種資源，如對于汽車這種資源，是由生產零部件和組裝等活動共同產生的^[12]。

目標和行動在微觀層次上可以得到統一，任何一個目標都可以分解為不能再繼續細分的子目標；而每一個小的子目標都可以用一個行動（或是一系列小的行動組成復雜的行動）來完成。這里將目標和行動統一抽象為任務，認為一個需要協調的環境，只由兩部分組成，即資源和任務。其中資源是一個廣義概念，既包括行動所需要的資源，也包括行動的執行者。而且時間也是一種特殊的資源，任務之間的時序關系可以通過資源約束方式表述出來。更一般地說，所有與任務（活動）有關的東西都可以歸入資源這一類。而任務則包括需要完成的目標或是需要執行的動作。到此就能將11節所討論的依賴關系歸結為任務之間基于資源的依賴關系。任務之間基于資源的依賴關系最簡單的情形就是兩個任務關于一種資源的相互依賴，其他所有復雜的依賴關系都可以通過這種最基本的依賴關系組合表示出來。兩個任務關于一種資源的相互依賴的基本形式，就是圖1所示的三種基本依賴關系。

1.3基于Petri Nets的任務表示方式

Petri Nets是一種適用于多種系統的圖形化、數學化建模工具。自20世紀60年代由德國學者Petri C.A.提出以來，經過三十多年的發展，已被廣泛用于各個領域的系統建模、分析和控制，例如通信協議的驗證、網絡性能的分析、柔性制造系統的控制、工作流分析、知識推理以及人工神經網絡等。

Petri Nets在描述具有并行、異步、分布式和隨機性等特征的復雜系統時，有其獨特的優勢。這里選用Petri Nets作為描述任務之間的依賴關系及其相應協調機制的工具主要有以下原因^[13]：

（1）Petri Nets兼顧了嚴格語義與圖形兩個方面。無論是經典的Petri Nets（如庫所/變遷），還是高級的Petri Nets（如有色Petri Nets、時間Petri Nets、層次Petri Nets、謂詞/變遷網等）的所有元素都是經過嚴格定義的，具有規范的模型語義。這樣不僅使得依賴關系及協調機制有清晰與嚴格的定義，從而容易表述和理解；更使得依賴關系及協調機制計算機化，進而使計算機自動協調成為可能。

（2）Petri Nets是一種基于狀態的建模方法。它明確定義了模型元素的狀態，這樣不僅能嚴格區分活動的使能與活動的執行，而且使得基于狀態的過程定義具有更豐富的表達能力，對表達任務之間的依賴關系，有著天然的優勢。

（3）Petri Nets具有強有力的分析技術與手段。經過三十多年的發展，Petri Nets擁有許多可以利用的分析技術，可以用來分析模型的各種特性，如有界性（安全性）、活性（無死鎖）、不變量等；也可以用來計算模型的各種性能指標，如響應時間、等待時間、占有率等。這些分析技術都能夠用來分析依賴關系的各種屬性，以及用來評價協調策略的優劣。

下面給出Petri Nets的一個簡單的形式化定義^[14]：

Petri Nets被定義為一個五元組(P，T，F，w，M0)。其中P={P1，…，Pm}代表庫所；T={t1，…，tn}代表變遷；F（P×T）∪（T×P）代表連接庫所和變遷的弧線；w∶F→{1，2，…}代表弧線上的權函數；M0∶P→{0，1，2，…}代表網的初始狀態；同時有約束（P∩T）=AND （P∪T）≠。

根據前面對任務之間依賴關系的討論，利用Petri Nets將單個任務表示成圖2的形式^[15]。

任務本身包含四個變遷ta、tb、tc、t以及三個庫所P1、P2、P3。任務通過虛線框外部的五個庫所與外部發生聯系。除了輸入/輸出庫所外，還有請求資源、分配資源、釋放資源三個庫所。任務基于資源的依賴關系也是由這些庫所與外部的連接來表示。

可以利用Petri Nets將12節中提到的任務之間的時序關系用任務之間基于資源的依賴關系表示出來。圖3表示的是任務1完成之后，任務2才可能發生的情況。

圖3中的變遷t就是用來保證任務1完成后，任務2才能夠發生的機制。當任務1完成后，庫所“釋放資源_1”得到Token；同時當任務2中的“請求資源_2”中有Token時，變遷t才能夠發生，庫所“分配資源_2”得到Token，任務2得以發生。這里需要說明的是，圖3中包含了一個超時保護的措施，當任務1一直沒有發生，而任務2必須發生時起作用。即“請求資源_2”中存在的Token在等待一段預先設定的時間后，變遷“超時設定”被觸發，進而變遷t的替代者t′得以發生（如圖中標有字母R的變遷）。庫所“分配資源_2”得到Token，任務2發生。

任務之間的時序關系還有很多種，如Allen J.F.列出了七種最基本的時序關系，并且證明了這七種時序關系的完備性^[6]。通過以上介紹的Petri Nets的知識，這些時序關系都有可能通過資源依賴的方式表示出來，這里就不一一詳述了。

2基于Petri Nets的協調機制表達

根據上述對任務之間依賴關系的討論以及Petri Nets對任務的表示，可以利用Petri Nets對上面所說的三種基本任務之間基于資源的依賴關系給出相應的協調機制。

第一種依賴關系——流依賴，它是最簡單的，即第一個任務的輸出是第二個任務的輸入。這里需要注意的一點是，流依賴關系中包含了一種時序關系，即任務1發生完成后，任務2才能夠發生。所以流依賴關系相應協調機制的Petri Nets表示與圖3非常相似。它只需利用一個變遷將任務1的輸出庫所與任務2的輸入庫所連接起來即可，這里就不重新繪制了。

第二種依賴關系——共享依賴，這里考慮最簡單的情形。兩個任務共享一個資源，同時忽略資源本身的屬性，即假設這一個資源是能夠被兩個任務同時使用的，而且資源不具有揮發性，即資源是可重用的。任務基于資源的共享依賴關系如圖4所示。

圖4中的庫所Pn(n=1，2，3，4，…)以及變遷T1、T2就是用來控制任務1和任務2資源共享依賴的機制。Pn中的Token表示可用的資源。圖4的Token剛好有兩個，使得兩個任務發生有足夠的資源。當Pn中有足夠的資源，同時庫所“請求資源_1”或“請求資源_2”中有Token時，變遷T1或T2才能夠發生，任務1或任務2得以執行。在任務執行完畢后，通過庫所“釋放資源_1”和“釋放資源_2”，代表資源的Token又重新回到Pn中，供下次使用。

第三種依賴關系——共同依賴。共同依賴關系本意是指多個活動共同產生某種資源，如對于汽車這種資源，需要由生產零部件以及組裝等活動共同產生。從任務基于資源依賴關系的角度來考慮共同依賴關系，可以將其理解為多個活動必須同時使用某種資源，這時這種資源才是有效的，即并發使用資源。這兩種理解方式在本質上是一致的，只是觀察的角度不同，一個是正向的，另一個是反向的。但是后一種表述方式使得依賴關系及協調機制的表述變得更為方便和清晰。這里也考慮最簡單的情形，即兩個任務并發地使用同一種資源，并且不考慮資源的屬性，如圖5所示。

圖5中的庫所Pn(n=1，2，3，4，…)、P1以及變遷t1就是用來控制任務1和任務2并發資源依賴關系的機制。其中庫所Pn包含n個Token（圖中n=2，即表示有兩個Token）。通過一段賦權的弧和變遷t1相連接，弧的權值是n，也就是說只有當庫所Pn中的Token數量達到了n，變遷t1才有可能被觸發。與此相類似，只有當庫所P1中有n個Token時，變遷t1才有可能發生，這也就保證了同時有n個任務請求使用這個資源。只有以上兩個條件同時滿足后，t1才被確保發生。在t1被觸發后，n個Token被轉移到庫所P2中，然后由P2將這n個代表資源Token分配到相應的“分配資源_x”庫所中去。與庫所P3和P4相連的弧線中各有一條抑制弧（Inhibitor Arc），其作用在于防止同一個任務多次申請資源。另外任務1中，還有一個“超時設定”變遷與庫所“請求資源_1”相連，這樣當等待規定的時間后仍然不能執行時，任務1能夠回到最初狀態。任務2也可以加上同樣的超時保護機制，圖5中沒有標出。

以上討論的這三種任務基于資源的依賴關系，都是考慮的最簡單的情形，即兩個任務關于一種資源的依賴關系。現實中的依賴關系是復雜的，如多個任務關于一種資源的依賴關系、多個任務關于多個資源的依賴關系以及多種依賴關系的復合等。但是所有這些依賴關系都能夠用這幾種最基本的依賴關系組合加以表述。在文獻[12]中已有詳細介紹，這樣就有可能用Petri Nets來表示所有任務基于資源的依賴關系了。

3結束語

本文對協調問題中的依賴關系作了詳細探討，認為所有依賴關系都可以歸結為任務之間基于資源的依賴關系，并且討論了三種最基本的任務基于資源的依賴關系。利用Petri Nets對協調問題中的任務進行建模，指出時間是一類特殊的資源，并給出了任務之間時序關系的資源約束表示。最后給出了三種基本依賴關系相應協調機制的Petri Nets表示。上述工作對于協調問題在計算機中的表述，以及將來利用計算機求解協調問題作了有益探索。

對于協調理論的完善及其真正廣泛的應用，還有很長一段路要走。例如對于同一種依賴關系，常常有許多種不同的協調策略來管理。本文給出的協調機制僅僅是各種具體協調策略的抽象表示。本文沒有考慮資源的屬性問題，資源的可重用性、并發使用能力以及資源的質量都將影響協調的結果。這些都是通用協調理論所必須考慮的問題。如何對于各種不同的協調問題，找出明確的依賴關系，以及針對各種具體的依賴關系建立相應的協調策略；如何真正在計算機中表達這些依賴關系及其協調策略；如何能夠讓計算機根據不同的具體應用，對于同一種依賴關系，選擇最適合的協調策略等，都是值得進一步研究的。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。