工作流執行中的資源衝突消解方法

2023-05-12 17:51:31

專利名稱：工作流執行中的資源衝突消解方法
技術領域：
本發明涉及一種工作流執行中的資源衝突消解方法，以「衝突檢測模型」(Conflict Detecting，簡稱⑶模型)作為消解工作流執行中資源衝突的主要策略，尤其適用於辦公自動化領域。
背景技術：
工作流(Workf low)是辦公自動化中不可或缺的內容,它涉及業務過程的部分或整體在計算機應用環境下的自動化，它主要解決的是在多個參與者之間按照某種預定義的規貝U，將傳遞文檔、信息或任務的過程自動推進，從而使某種預期的業務目標得以實現。
為此於1993年成立了國際工作流管理聯盟(Workflow ManagementCoalition,WfMC, http://www. wfmc. org/),聯盟的成立標誌著工作流技術業已進入相對成熟的階段。為了實現不同工作流產品之間的互操作，WfMC在工作流管理系統的相關術語、體系結構、參考模型及應用編程接口等方面制定了一系列標準。雖然，一個具體的工作流管理系統可以只實現了這個模型的一部分，但這個模型提出的結構和模塊間的職能分工仍是業內層級最高的樣板(參見圖I)。在該模型中設置了工作流引擎功能模塊以及流程定義、客戶端應用、應用程式調用、(與其他工作流管理系統的)互操作和管理監控等接口。簡述如下工作流引擎功能模塊工作流引擎是工作流參考模型的核心，它為工作流提供一個切實有效的運行環境。工作流引擎對工作流程進行初始化、調度和執行，包括執行中的退回、轉交(任務轉派)、催辦，以及任務的合併和跳過等具體內容。特別地，流程引擎應能支持同一業務活動的多人指派原則(簡稱「雙人原則」或「四眼原則」 一一Four EyesPrinciple)，即流程引擎能將某些關鍵業務指派給兩個或兩個以上的工作人員共同完成或決策，以期獲得預期的效果。這種多人指派機制應該體現在業務流程的設計和建模過程中，並通過並行分支結構和同步結構來完成。流程定義接口 工作流中需要通過流程定義工具制定一個完整的流程。本接口實現流程定義工具與工作流引擎間數據模型和API的交換，生成可被計算機執行的形式化描述。客戶端應用接口 定義所有客戶應用和工作流服務間的功能操作方式，其主要表現形式是工作表處理器(Worklist Handler)。工作流參與者通過表處理器實現在工作表中選取、分配工作項，通報工作項完成情況。應用程式調用接口 是工作流引擎和直接調用的應用程式間的接口，工作流引擎通過本接口調用外部提供的應用服務。比如，在流程執行過程中調用業務系統提供的業務數據等。互操作接口 本接口實現與不同工作流管理系統間的信息交互。系統管理與監控接口 本接口提供對運行實例的管理與監控，包括用戶管理、角色管理、資源控制、運行狀態監控等。
工作流(Workf low)是辦公自動化中不可或缺的內容，它涉及部分或整體業務過程在計算機應用環境下的自動化，而「雙人原則」或「四眼原則」是工作流實施中必須貫徹的普遍性原則。為保證此種原則的實施，就必須發現並消解工作流實施中的資源衝突，即必須在保持資源完整性和一致性的前提下，最大限度地「同時」滿足工作人員甲、乙、丙、…對資源的共同需求。在異地跨區域網的情況下，由於網間傳輸所附加的時延更大、消息到達的時間和工作人員發出消息的順序可能改變、甚至消息會丟失等原因，所以在此種背景下發現並消解工作流實施中的資源衝突就更為必要。傳統做法是當資源訪問衝突嚴重時放棄資源的共享，或採用分時間片的鎖機制，鎖的鎖定及釋放完全由時間標誌確定，幾名工作人員同時訪問同一資源時由時間標誌確定僅接受哪一位工作人員的訪問以避免衝突。
這種方式的不便之處在於雖然理論上可以將「作用域」設置得「無限小」，從而可以使資源衝突局限在相對非常小的空域中；但在實踐中，太小的空域又會影響執行效率。這種平衡只有在工程實施中針對不同的延時響應要求折衷地解決，也即，只能根據延時響應的允許值確定相應的空域設置，因而其應用受到諸多限制。因此，有必要設計一種新的工作流執行中的資源衝突消解方法。

發明內容
本發明所要解決的技術問題是提供一種工作流執行中的資源衝突消解方法，該工作流執行中的資源衝突消解方法適用範圍廣，能有效減輕工作量中的資源衝突。發明的技術解決方案如下一種工作流執行中的資源衝突消解方法，用一個六元組表示對象P，即有P=(i，j，D，A，t，L)；其中，i，j為不相關的正整數，記i為用戶號，j為屬於用戶i的有序對象號，D為對象描述，A為P的有界作用域，t為P的到達時間，即對象P投入應用的時間點，L表示對象P的修改屬性，L = I為允許被其他對象修改，L = O則不允許被其他對象修改；多個用戶共同參與對於對象P的工作流；用戶數為N，對象序列為1，2，3，···，則標記某一特定的對象為與之相對應的
有 Di』 j，Ai, j，ti, j，Li, j ；記無衝突搶佔為C1，有衝突搶佔為C2 ;稱C1或C2為I時為成功搶佔，C2 = O為失敗搶佔；資源衝突消解進程如下步驟I :工作流對象進入堆棧；步驟2 :工作流對象從堆棧彈出，並進行如下衝突檢測當下述兩公式之一得到滿足時，判斷對象的實施為無衝突實施(a) (Ag;i fV-.n Atl) = Φ ;(b) ((Ag, i n Ah,」η …η Atl) Φ Φ) Λ (Lgji = O) Λ ((Liik Λ…Λ LtlM)而當下述公式滿足時，判斷對象的實施為有衝突實施((Agji n Ah；j η …n Atl)關 Φ) Λ ((Lga V…V LhJ=O) Λ ((Li,, Λ…Λ Ltl)=!)
公式中g，k,I均為序號(相當於身份證號)，其取值由工作流實施程序指定，例如張三指定為g，Ag,i表示張三的第i個對象；李四指定為k，Aiu就是李四的第I個對象；A的第一個下標為用戶號，A的第二個下標為對象號；步驟3:消解衝突步驟當兩對象的實施為有衝突實施時，優先級高優先級由工作流實施程序指定的對象獲得即時實施，並鎖定相應空域；而優先級低的對象被壓入堆棧，返回步驟2 ；隨著時間片推進，當堆棧為空時，結束工作流執行中的資源衝突消解進程。所述的對象為數據對象、文字對象、圖像對象、語音對象、過程對象、通信對象和輸入輸出對象中的至少一種。所述的空域為有界數據空間、資料庫欄位、有界文字空間、有界圖像空間、有界語·音空間、命名程序段、通信設備或輸入輸出設備通信設備或輸入輸出設備，這些都是資源，都可能出現資源競爭衝突，如多人共用一臺通訊設備有益效果為檢測資源衝突並將這種衝突的影響鎖定在儘可能狹小的範圍內，即盡最大可能地推進工作流的進程，本專利提出一種「衝突檢測模型」(Conflict Detecting),簡稱⑶模型。在本模型中，將所有資源都視作不同類型、不同大小的對象，而且引入作用域、重疊方式等概念。因此具有如下特點(I)適用性強不僅適合有界數據空間，而且適合圖像對象、語音對象、文字對象、過程對象、輸入輸出對象等；不僅適合雙人協同工作時發生的資源衝突消解，而且適合多人協同工作時發生的資源衝突消解。(2)引入作用域的概念。由於理論上可以將「作用域」設置得「無限小」，故工程實踐中在保證效率的考量下，可以使資源衝突局限在相對非常小的空域中。(3)引入重疊方式的概念體現在「L = I為允許被其他對象修改，L = O則不允許被其他對象修改；」，進一步減輕衝突。(4)控制對象的佔時度，以限制空域衝突的持續期。本專利提出的⑶模型不僅適合有界數據空間，而且適合圖像對象、語音對象、文字對象、過程對象、輸入輸出對象等；不僅適合雙人協同工作時發生的資源衝突消解，而且適合多人協同工作時發生的資源衝突消解。本模型引入作用域的概念，使競爭局限在相對小得多的空域中；引入重疊方式的概念，進一步減輕衝突。本模型通過控制對象的粒度以控制衝突的持續期。基於上述模型，使本專利能通過計算機編程實現最大限度的資源衝突消解。


圖I. WfMC的工作流管理系統模型；圖2. CD模型的二維示意圖[三角形、圓形圖案只是區分不同內涵的對象，著色與未著色在圖例中已說明是可覆蓋和不可覆蓋。];圖3.衝突檢測及其消解的軟體機制；圖4為工作流執行中的資源衝突消解方法的流程圖；圖I中的接口說明如下
接口 I :流程定義接口，實現流程定義工具與工作流引擎間數據模型和API的交換；接口 2 :客戶端應用接口，定義所有客戶應用和工作流服務間的功能操作方式；接口 3 :應用程式調用接口，工作流引擎和直接調用的應用程式間的接口 ；接口 4 :系統管理與監控接口，實現對工作流的管理與監控；接口 5 :互操作接口，實現不同工作流管理系統間的信息交互。
具體實施例方式以下將結合附圖和具體實施例對本發明做進一步詳細說明 實施例I :CD模型由模型定義與衝突檢測、消解兩部分組成，分別在如下段落敘述。一、模型定義定義I.對象、空域與搶佔對象=數據對象U文字對象U圖像對象U語音對象U過程對象U通信對象U輸入輸出對象；空域=有界數據空間U資料庫欄位U有界文字空間U有界圖像空間U有界語音空間U命名程序段U通信設備U輸入輸出設備；搶佔某空域已被某一對象鎖定，在解鎖前其他對象無法使用該空域。定義2.對象對象P為一六元組P= (i, j, D, A, t, L) (I)其中，i, j為不相關的正整數，記i為用戶號，j為屬於用戶i的有序對象號，D為對象描述(含對象實施指南)，A為P的有界作用域，t為P的到達時間，(即對象P投入應用的時間點),L=I為允許被其他對象修改，L = O則不允許被其他對象修改。設用戶數為N，對象序列為1，2，3，···，則可標記某一特定的對象P為Pu，與之相對應的有Di,」，Li,」這裡的i，j是就是P=(i，j，D，A，t，L)中的i，j。i為用戶號，j為屬於用戶i的有序對象號，對於這個處理文檔的實例，j具體一個操作的次序定義3.時間段時間段為一具有起止點的時間閉區間。用時間段控制對象的粒度，可以將連續的操作分割為離散的對象，僅對處於同一時間段內的對象才判斷它們是否存在衝突，並考慮予以消解，記為T1, T2,…。定義4.無衝突搶佔與有衝突搶佔，以及成功搶佔與失敗搶佔記無衝突搶佔為C1，有衝突搶佔為C2;稱C1或C2為I時為成功搶佔，C2 = O為失敗搶佔。其中無衝突搶佔總是成功搶佔。設有效空間為S』Ah,」, Ai^, . [S，稱Ph,」，Pi^,…與Ptl在同一時間段中，
即Vu，tijk,…，均在時間段Ti中。從而有C1 = 1，iff ((Agji η…n Ak；1) = Φ) (2)C2=l，ifT(((Ag,i η Ah;J rv..n Atl)關 Φ) Λ (Lgii = O) Λ ((LLkA-ALiu)=I)
(3)C2=O, iff (((Agji n Ahjj n…n Aka)關 Φ) Λ(UHVLhJ=O)A(U-ALiu)=I)) (4)Iff表示「若且唯若」；顯見在C2=I的情況下Pg，i有衝突搶佔獲得成功；僅C2=O的情況下才需對Pg,i;…，Ph, j引起的衝突予以消解。由於本模型中引入對象作用域和重疊方式這兩概念，從而得以區分無衝突搶佔和有衝突搶佔，並將有衝突搶佔失敗的可能性減至最小。二、衝突檢測及其消解 (I)衝突檢測對象實施衝突檢測的依據是定義4給出的公式(2) (4)，即當下述兩公式之一得到滿足時，判斷對象的實施為無衝突實施(a) iff ((Ag；i η …n Aka) = Φ)(b)iff(((Ag, i η Ah,j η…η Atl)古 Φ) Λ (Lga = O) Λ ((LikAwALtl)=I)而當下述公式滿足時，判斷對象的實施為有衝突實施(C) ifT(((Ag,i n Ah，j η …n Aiu)關 Φ) Λ ((LgiiV-VLhij)=O) Λ ((Li,,八…Λ LiuM))公式(a)的含義~,1，，，，\1這幾個有界作用域並無交集(=Φ)所以是無衝突實施；公式(b)的含義雖然Ag,i，，，，Aiu這幾個有界作用域有交集(關Φ )，但是僅一個空域Lg, i不允許被其他對象修改(Lg, i = O)，其它的Li, k，，，Ltl是可以被其他對象修改的D-N 1^0=1，所以資源可以被Lg,i獨佔而不存在衝突，與公式(b)相反，公式(C)中存在實實在在的衝突，因為邏輯運算中(I V 0)= 1，(O V O) = 0，因此在(C)中((Lg,i V…V Lh；J)=0)是說LgV^Lh,」均不為1，即均不能被改寫，因此有衝突。(2)衝突消解當兩對象的實施為有衝突實施時，優先級高的對象獲得即時實施，並鎖定相應空域；而優先級低的對象被壓入堆棧，等待在下一時間段中再次檢測衝突。為完成衝突消解，在工作流引擎中設計了專屬於每一工作人員的緩存棧，以及一個稱為「虛擬空域」(Agii U Ah,j U…U Au)的衝突偵測區域，如圖3所示。為簡化表述，作出如下三項約定I.假設工作人員g以較高的優先級和工作人員i共同參與此項任務；2.將時間劃分成TcTT1, ΤΓΤ2, Tf T3，T3'這樣4個時間段；3.工作人員g和i僅需要某些圖像對象，據此，工作人員g和i所需要的對象以及能否搶佔的情況將如圖2所表示。從前面關於⑶模型的定義可以判定，上述三項約定僅為用圖定義2中i, j僅是一個序號，可以是1，2，3，4，……·，中任一數字，並不特指某一值，P12和P22是分屬用戶I和用戶2的對象，它們之間沒有內在聯繫配合文字的表述而已，它絲毫不影響衝突檢測和消解的實質。
工作流實施過程一、實施準備對象流壓入堆棧。工作流引擎在工作流程初始化時，將工作人員g和i所需要的對象流壓入各自的緩存棧中；各自的棧計數器記錄所壓入的對象數。前文的i並非唯一的i，而僅表示用戶中的一人，一個序號而已，所以這裡i與前文的i不存在衝突二、工作流實施步驟I.如果棧計數器均不為0，則從工作人員g和i各自的緩存棧中彈出最下部的對象進入衝突檢測模塊，轉步驟2 ;如僅一棧計數器不為0，從相應緩存棧中彈出最下部的對象轉步驟4 ;反之即當兩個棧計數器均為O就結束轉步驟5。步驟2.衝突檢測 衝突檢測的依據是在模型定義中由定義4給出的公式(2) (4)，即當下述兩公式之一得到滿足時為無衝突(a) iff ((Agji η …η Aka) = Φ)(b) iff (((Agji η Ah, j... η Atl)關 Φ) Λ (Lgii = O) Λ ((Liik Λ…Λ 1^)=1)而當下述公式滿足時判斷為有衝突iff (((Agji n Ahj j. . . n Ak；1)關 Φ) Λ ((Lgii V …V LhJ=O) Λ ((Li, k Λ ...Λ LiuM))根據工作人員g和i所需要的對象以及能否被覆蓋的情況，得到如下檢測結果和後繼步驟步驟2a.如C2 = I (圖2的Tq'時間段即Casel時)，轉步驟4。因為這時P。與Pu無衝突，工作人員g和i各自推進工作。步驟2b.如C2 = 0(圖2的T廣!^時間段即Case2時)，轉步驟4。因為這時Pg，i重疊在Pu上，而此時Pu是允許重疊的(因為L = I )，所以無衝突，工作人員g和i也可各自推進工作。步驟2c.如C2 = O (圖2的TfT3時間段即Case3出現C2 = O的情況)，轉步驟3。步驟3.衝突消解在TfT3時間段(Case3時)，出現C2 = O的情況。這時Pg，i與Pi,k均不允許重疊，比較Dgii和Dy中設定的工作人員優先級後繼步驟步驟3a.優先級高的Pgii在虛擬空域中搶佔成功，從而鎖定相關實際空域，轉步驟
4。工作人員g的工作推進一步。步驟3b.優先級低的Piik在虛擬空域中搶佔失敗，將它壓入緩衝棧i底部，緩存棧i的棧計數器+ 1，轉步驟I。這是因為Piik在與P&i搶佔資源中搶佔失敗，所以Piik要壓入緩衝棧i底部，以使工作人員i的工作今後有機會推進。步驟4.根據Dy和/或Dy中的實施指南尋址在(圖3的)「資源指派」中獲得已鎖定的實際空域，從而可以實施工作流規定的操作(包括數據改寫)；時間段推進I ;棧計數器一 I;轉步驟I。步驟5.工作流實施完成。
權利要求
1.一種工作流執行中的資源衝突消解方法，其特徵在於，用一個六元組表示對象P，即有 P=(i，j，D，A，t，L)；其中，i，j為不相關的正整數，記i為用戶號，j為屬於用戶i的有序對象號，D為對象描述，A為P的有界作用域，t為P的到達時間，即對象P投入應用的時間點，L表示對象P的修改屬性，L = I為允許被其他對象修改，L = O則不允許被其他對象修改；多個用戶共同參與對於對象P的工作流；用戶數為N，對象序列為1，2，3，···，則標記某一特定的對象為Pu，與之相對應的有記無衝突搶佔為C1，有衝突搶佔為C2 ;稱C1或C2為I時為成功搶佔，C2 = O為失敗搶佔;資源衝突消解進程如下步驟I:工作流對象進入堆棧；步驟2 :工作流對象從堆棧彈出，並進行如下衝突檢測當下述兩公式之一得到滿足時，判斷對象的實施為無衝突實施(a)(Ag i η …n Atl) = Φ ;(b)((Agji η Ah；j η…η Ak l)關 Φ) Λ (Lgii = O) Λ ((Liik Λ…Λ 1^)=1)而當下述公式滿足時，判斷對象的實施為有衝突實施((Ag,i n Ah,j η…n Aiu) ^ Φ) Λ ((Lg,, ν…V L1J=O) Λ ((Liik 八…八 LtlM)步驟3 :消解衝突步驟當兩對象的實施為有衝突實施時，優先級高的對象獲得即時實施，並鎖定相應空域；而優先級低的對象被壓入堆棧，返回步驟2 ;隨著時間片推進，當堆棧為空時，結束工作流執行中的資源衝突消解進程。
2.根據權利要求I所述的工作流執行中的資源衝突消解方法，其特徵在於，所述的對象為數據對象、文字對象、圖像對象、語音對象、過程對象、通信對象和輸入輸出對象中的至少一種。
3.根據權利要求I所述的工作流執行中的資源衝突消解方法，其特徵在於，所述的空域為有界數據空間、資料庫欄位、有界文字空間、有界圖像空間、有界語音空間、命名程序段、通信設備或輸入輸出設備。
全文摘要
本發明公開了一種工作流執行中的資源衝突消解方法，用一個六元組表示對象P，即有P=(i,j,D,A,t,L)；資源衝突消解進程如下步驟1工作流對象進入堆棧；步驟2工作流對象從堆棧彈出，並進行衝突檢測當下述公式滿足時，判斷對象的實施為有衝突實施((Ag，i∩Ah,j∩…∩Ak,l)≠φ)∧((Lg，i∨…∨Lh，j)=0)∧((Li，k∧…∧Lk，l)=1)；步驟3消解衝突步驟當兩對象的實施為有衝突實施時，優先級高的對象獲得即時實施，並鎖定相應空域；而優先級低的對象被壓入堆棧，返回步驟2；隨著時間片推進，當堆棧為空時，結束工作流執行中的資源衝突消解進程。該工作流執行中的資源衝突消解方法適用範圍廣，能有效減輕工作量中的資源衝突。
文檔編號G06F9/44GK102945154SQ201210398080
公開日2013年2月27日 申請日期2012年10月18日 優先權日2012年10月18日
發明者李新宇, 宋鷹, 沈清, 周澤峰, 鄭年斌, 龍熾, 王平, 王忠強 申請人:拓維信息系統股份有限公司