分布式系统的并发理论模型

1、分布式系统的并发理论模型分布式系统的并发理论模型Jidong GAutomata? ConcurrencyPetri Nets for Automata Communication并发理论模型分类并发理论模型分类n真并发语义的并发模型真并发语义的并发模型(true concurrency)(true concurrency)nPetriPetri网网n交叠语义并发模型交叠语义并发模型(Interleaving semantic)(Interleaving semantic)n进程代数进程代数, , 如如CSP, CCS, Pi-CSP, CCS, Pi-演算演算 等等等等陆汝钤陆汝钤, , 计

2、算机语言的形式语义计算机语言的形式语义, , 科学出版社科学出版社, 1992. , 1992. 并发理论E. W. DijkstraTony HoareCommunicating Sequential Processes, Hoare Logic, etc.PV操作操作, 程序设计理论程序设计理论, 并发理论并发理论, 算法算法, etc. Robin MilnerCarl Adam PetriCCS Calculus of Communication SystemsPi calculus, ML- Meta LanguageLCF: Logic of Computable Function

3、s, etc.Petri网网, 并发理论并发理论Outlinesn1. Introduction to Petri netsn2. High-level Petri netsn3. Object Petri nets n4. Workflow modeling with Petri nets n5. Analysis Methods of Workflow net1. Introduction to Petri netsqBrief History of Petri netsqBasic ConceptsqMarking, Enabled, Firing, qReachable, State

4、SpaceqBasic PropertiesqLiveness, BoundednessqAn important result about liveness and boundednessHistory of Petri nets nC. A. Petri: Kommunikation mit Automaten, Bonn Univ. 1962nUse A formal modeling tool for concurrent and distributed systemnEarlier research GMD Funding at MITnCommoner Theorem for Fr

5、ee Choice Petri Nets, 1971nHack - Decidability questions for Petri nets, 1976nAcademic annals nInternational Conference on Application and Theory of Petri Nets, since 1980，published by Springer-LNCS Example Producer/Consumer Systemn(1) A Petri net is a 3-tuple wherenP is a finite set of places, nT i

6、s a finite set of transitions, n is a set of arcs (flow relation)n(2)Preset n Postset ),(FTPPN PTTPF),( ,|FxyTPyyx),( ,|FyxTPyyxTP变迁 Transition库所 Place托肯 Token弧 ArcToken GameMarking, Enable, Firing (1)nMarking the state of Petri Net, Multiset, n means the token number of the place at the marking n m

7、eans in every input place of transition , the token number is bigger than onenA transition is Enabled iff denoted PMttMttM)(pMpMtMM是库所集上的一个向量是库所集上的一个向量Token GameMarking, Enable, Firing (2)nA transition is Enabled iff denoted nBasic State equation nAfter firing, the following statettMMttMtM=p2+ p3+p4

8、, t1 is not enabled, t2 is enabledAfter t2 firing, M = p6+p7p6t1t2t1t2After t 2 firingp7p6p5p4p3p2p1p1p7p5p4p3p2t1t2t1t2After t 2 firingp7p6p5p4p3p2p1p1p7p5p4p3p2tMMMtToken GameMarking, Enable, Firing (1)Token GameReachable nFor a marking , after a firing sequence, 1.21nittt t1MntttMMMn121.21nMM*1Al

9、so can be denoted Here, empty sequence is allowed)(MRSdenotes the state set of reachable from MRunning (1)p4t1t2p2p1p5p6t3t4p3p4t1t2p2p1p5p6t3t4p3t1M1=p1+p3+p5M2=p2+p3+p51 0 1 0 1 00 1 1 0 1 0Running (2)p4t1t2p2p1p5p6t3t4p3t2M2=p2+p3+p5M3=p1+p4+p5p4t2p2p1p5p6t3t4p3t10 1 1 0 1 01 0 0 1 1 0Running (3)

10、t3M3=p1+p4+p5M4=p1+p3+p6p4t2p2p1p5p6t3t4p3t1p4t2p2p1p5p6t3t4p3t1p4t2p2p1p5p6t3t4p3t1t1M5=p2+p4+p51 0 0 1 1 01 0 1 0 0 10 1 0 1 1 0Running (4)t4M4=p1+p3+p6M1=p1+p3+p5 (back to initial)p4t2p2p1p5p6t3t4p3t1p4t2p2p1p5p6t3t4p3t1t1M6=p2+p3+p6p4t2p2p1p5p6t3t4p3t11 0 1 0 0 11 0 1 0 1 00 1 1 0 0 1Running (5)

11、t3p4t2p2p1p5p6t3t4p3t1M5=p2+p4+p5M6=p2+p3+p6p4t2p2p1p5p6t3t4p3t10 1 1 0 0 11 0 1 0 1 0Running (6)p4t1t2p2p1p5p6t3t4p3t4M6=p2+p3+p6M2=p2+p3+p50 1 1 0 0 10 1 1 0 1 0State space - reachability graphnConnect the arc relations between the markingsn- get the state space1 0 1 0 1 01 0 1 0 1 01 0 1 0 1 01 0

12、 1 0 0 10 1 1 0 0 11 0 0 1 1 0State space - reachability graphnConnect the arc relations between the markingsn- get the state spaceM1=p1+p3+p5, M2=p2+p3+p5, M3=p1+p4+p5, M4=p1+p3+p6,M5=p2+p4+p5, M6=p2+p3+p6322211,MMMMtt513433,MMMMtt614144,MMMMtt246635,MMMMttState space - reachability graphnConnect t

13、he arc relations between the markingsn- get the state space交叠语义的并发：交叠语义的并发：状态可达图中的平状态可达图中的平行四边形结构行四边形结构61|33MMtt State space - reachability graphnConnect the arc relations between the markingsn- get the state space交叠语义的并发：交叠语义的并发：状态可达图中的平状态可达图中的平行四边形结构行四边形结构24|14MMtt State space methods Petri net an

14、alysisnBased on the generation algorithm to search the state space of one Petri net systemnHowever, there are state space explosion problemsnPartial order reductionnSymmetrical reduction nEtc. other state space reduction techniques to mitigate the explosion Petri Nets的描述能力 Petri Nets的描述能力 n图灵机等价，Tur

15、ing Powerfuln抑制弧(inhibitor arc) n带抑制弧的增广Petri网与图灵机在计算能力上等价Hack75Hack75 Hack, M.H.T.: Decidability questions for Petri Nets. PhD Thesis, MIT, Dept. Electrical Engineering, (1975) Well-handledNot Well-handledNot Well-handledState MachineMarked GraphUMLt2t1t4t3t1t2t3t4t5t6t2t1t4t3t1t2t3t4t5t6Invariant

16、method T-component/P-component DecompositionInvariant method T-component DecompositionInvariant method P-component DecompositionLiveness, Boundedness of Petri net systemnA Petri net with a marked initial state is called a Petri net system0MThe producer/consumer example is live and boundedAn Example

17、about liveness or boundedness (1)p1p3p2t3t1t2An Example about liveness or boundedness (2)1. p2 is unbounded, 2. if t2 is fired, then t1 will be never fired again, so it is not live001100An important result about liveness and boundednessnFree-choice structurenA net is free-choice iff for every two tr

18、ansitions t and u, either implies nAn important result: nThe problem can be solved in polynomial time: Given a free-choice net, to decide it is liveness and boundedness21tt21ttt1t2s 1s 2t 1t 2s 1s 2Free-choice constraintNot Free-choice 2, 121sstt2,2, 11stsst哲学家吃通心粉问题n有五个哲学家围坐在一圆桌旁，桌子中央有一有五个哲学家围坐在一圆桌

19、旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后，间放一把叉子。每个哲学家思考、饥饿、然后，欲吃通心面。为了吃面，每个哲学家必须获得欲吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边两把叉子，且每人只能直接从自己左边或右边去取叉子。去取叉子。死锁死锁47例:哲学家问题的P/T系统描述 h-hungerk-thinkingf fork/chopsticke-eating?无死锁的解法(1) 增加一个服务生(2) 设定规则:奇数先拿左手,偶数先拿右手释放筷子释放筷子获取筷子获取筷子

20、Petri网的组合与分布式系统建模n合并库所合并库所: : 哲学家问题哲学家问题n合并变迁合并变迁: :生产者生产者/ /消费者问题消费者问题n层次式，一个层次式，一个PetriPetri网替换一个变迁网替换一个变迁n进程交互进程交互Petri网的组合与分布式系统建模n合并变迁合并变迁 : 生产者生产者/消费者问题消费者问题p4t1t2p2p1p5p6t3t4p3合并变迁合并变迁Petri网的组合与分布式系统建模n层次式，一个层次式，一个PetriPetri网替换一个变迁网替换一个变迁Petri网的组合与分布式系统建模registersend_questionnaireprocess_ques

21、tionnairetime_outarchiveevaluateprocessing_OKprocessing_requiredprocess_complaintcheck_processingprocessing_NOKn层次式，一个层次式，一个PetriPetri网替换一个变迁网替换一个变迁no_processingprocessingPetri网的组合与分布式系统建模registersend_questionnaireprocess_questionnairetime_outarchiveevaluateno_processingprocessing_OKprocessing_requi

22、redprocess_complaintcheck_processingprocessing_NOKn层次式，一个层次式，一个PetriPetri网替换一个变迁网替换一个变迁Petri网的组合与分布式系统建模一个订票业务的工作流模型过程模型一个订票业务的工作流模型过程模型 Laymann01 IBM WSFL特点特点: 将多个组织的业务过程协同起来将多个组织的业务过程协同起来n进程交互进程交互一种基于一种基于Petri网的表示网的表示特点特点: 用用Petri网的交互集表示不同过程模型之间的协同交互关系网的交互集表示不同过程模型之间的协同交互关系n进程交互进程交互2. High-level P

23、etri netsPetri网模型的分类 Yuan98类别类别S_元素元素例例又称又称特征特征EN_系统系统条件条件代表同一信息代表同一信息信息流函数信息流函数C/E_系统系统K=1, W=1P/T_系统系统库所库所/变迁变迁代表无个性同类资源代表无个性同类资源P/T_网网K=，W为任意为任意函数函数高级网系统高级网系统谓词谓词/着色着色代表作用及状态类似代表作用及状态类似的不同类资源的不同类资源着色网系统着色网系统Pr/T_系统系统个性个性Token 增加: Object Petri Nets, Petri Nets as Token Objects Val96,98Petri Nets的基

24、本模型的发展简史 类比程序语言的发展历程汇编，高级程序语言，OO1962Petri NetsC.A.Petri博士论文，Petri Nets的开始1970sP/T, 包含Inhibitor netsK库容, W弧权为任意函数1981Predicate/TransitionHartmann J. GenrichIndividual Token1981CP-netsKurt JensenIndividual Token1996,1998nets within netsRudiger Valktoken as object nets，赋予Token自治的计算能力High-level Petri Ne

25、ts, 缩减状态空间对于Petri Nets基本模型的扩展形态 n扩展方法：nInhibitor arcs/read arcs n时间timed nets，n随机stochastic nets，nHierarchical Nets(模块化程序设计), n扩展模型总是在以一个基本模型为基础高级网高级网-High-level Petri Netsn高级Petri网提出的目的：缩减Petri Nets的状态空间,个性TokennPr/T Nets Gen81， Predicate/Transition 谓词网nCP81-nets Jen81, Coloured Petri nets, 着色网n丹麦A

26、arhus Univ.Pr/T Nets (谓词网) (着色网)合并库所和变迁，增加谓词判断合并库所和变迁，增加谓词判断P4谓词网 哲学家问题抽取对称单元，抽取对称单元，建立谓词网或者着色网建立谓词网或者着色网例:哲学家问题的CP-nets系统描述 CP-nets的工业应用 Jen92nCP-nets工具在工业界已经得到广泛的应用，n在40个国家的300多个组织得到应用，其中包括75个商业公司n著名通信设备公司Nokia与CP-nets也有合作研究的项目，由此可见一项成熟的Petri网模型技术的应用前景是非常可观的 nCP-nets成功的原因与启示n对于每一种Petri网的基本模型要真正投入实

27、际应用都必须建立完备的和成熟度分析方法与技术,以及设计支持这些模型分析的工具n丹麦Kurt Jensen的工作很重要, 1981-进程与出现网 nProcess，nOccurrence Nets/Process Nets/Casual Nets，一个运动的历程，一个运动的历程n出现网的元素出现网的元素(变迁元素和库所元素变迁元素和库所元素)构成一个偏序集构成一个偏序集(partial order sets, 缩写缩写poset)。偏序集中没有顺序关系的两个元素称为并发的。偏序集中没有顺序关系的两个元素称为并发的(concurrent)，时间上无法比较它们的先后，网论中称为，时间上无法比较它们的

28、先后，网论中称为“同时同时”。原图3. Object Petri NetsnNets within Nets (德国汉堡) ICATPN1998nLOOPN+ (澳洲Adelaide, Lakos, 1995)nCO-OPN2 (瑞士苏黎世)nOB(PN)2 (柏林工业)nOCoN (德国Muenster-Object coordination nets) PNtalk(捷克布尔诺)nHOONets (韩国)nNested Petri Nets (俄罗斯)Nets within nets的思想Petri Nets as Token Objects初始状态可能状态3，Object Autonom

29、ous可能状态1, Transport 可能状态2，Synchronous InteractionPlat nets Two-level netsUEOS-Example,e1, t1, , t4,e3, t5,e2, t6, , t7,e4, ,e5 交互集 =, , , , ,e1, t1, , t4,e3, t5,e2, t6, , t7,e4, ,e5 交互集 =, , , , ,e1, t1, , t4,e3, t5,e2, t6, , t7,e4, ,e5 交互集 =, , , , ,e1, t1, , t4,e3, t5,e2, t6, , t7,e4, ,e5 交互集 =, ,

30、 , , ,e1, t1, , t4,e3, t5,e2, t6, , t7,e4, ,e5 交互集 =, , , , ,e1, t1, , t4,e3, t5,e2, t6, , t7,e4, ,e5 交互集 =, , , , ,e1, t1, , t4,e3, t5,e2, t6, , t7,e4, ,e5 交互集 =, , , , ,e1, t1, , t4,e3, t5,e2, t6, , t7,e4, ,e5 back end交互集 =, , , , nMobile Agent自治的计算实体nObject Nets自治的计算实体nMobile Agent的迁移nObject nets

31、在System nets中的迁移nMobile Agent的交互nSystem nets与Object Nets的三种点火行为Nets within nets and Mobile AgentNets within nets and Mobile AgentNew YorkLondonMadrid (cannot back)BerlinRomMadridNew YorkLondonParisBerlinRomMardrid模型应用模型应用:Agent System Architecture MULAN: Agent systems as nets within nets Koe01 例例:工作

32、流工作流 System-netObject-netValk意图:Workflow, FMSNets within nets的形式描述的形式描述-Unary EOS System NetObject NetInteraction set between two level netstT eE bi-marking- (M, m)Unary EOS的点火方式的点火方式-三种三种Unary EOS的点火方式的点火方式-三种三种Process-Marking nProcess-Marking使用Occurrence-nets的概念n三种方式nTransport nInteraction nObject

33、-autonomous event: nLUB (Lub运算-Least Upper Bound)n意义: 多个Token Objects协作完成一个过程Process-Marking 三种方式 a)Process-Marking使用Occurrence-nets的概念Lub运算-Least Upper BoundProcess-Marking 三种方式 b)Process-Marking 三种方式 c)没有System net level的变迁Reference Semantics and Value SemanticsReference SemanticsReference Semanti

34、cs and Value Semantics 两种语义可以类比程序设计语言中的概念LUBValue SemanticsEOS形式定义 例例:哲学家问题的哲学家问题的nets within nets系统描述系统描述 Five Philosophers Object NetsFive Philosophers System NetFive Philosophers System NetResourcesnBooksnW. Reisig, Petri net : an introduction, Springer, 1985, nJL, Peterson, Petri Net Theory and

35、the Modeling of Systems, Prentice Hall, 1981 nJ. Desel and J. Esparza, Free Choice Petri nets, Cambridge Press, 1995, nC Girault, R Valk, Petri Nets for System Engineering, Springer, 2003 n袁崇义, Petri网原理, 电子工业出版社, 1998, 2005(第二版)nJournalsnTheoretical Computer Sciences, Information and Computation, nA

36、cta Informaticae, Fundamenta Informaticae, nWebsite - Petri Nets Worldn nGlobal bibliography for Petri nets nMailing listApplications nCommunication Protocols, nWorkflow Modeling, nFlexible Manufacturing Systems, nDiscrete Events Dynamic SystemsnEtc.5. Workflow modeling with Petri nets nWfMCnWfMS Bu

37、siness computing, nThree dimensions of workflow nWorkflow netnSoundnessnAn important result for checking soundness of workflow netsWorkflow concepts - WFMCnA system that completely defines, manages, and executes workflows through the execution of software whose order of execution is driven by a comp

38、uter representation of the workflow logic. (WFMC, Workflow Management Coalition)WFMCWFMCWFMCWFMCWFMCWFMCWFMCWFMCWorkflow process modeling resourcescasesprocessThe three dimensions of workflow(Kernel and focused)A process consists of a sequence of activities.The transitions represent the activities o

39、f workflow processes. The tokens and the places represent the enabled conditions of the process activities. Why we choose Petri nets for workflow modeling nformal semanticsnA workflow process specified in terms of a Petri net has a clear and precise definition. ngraphical naturenPetri nets are a gra

40、phical language. As a result, Petri nets are intuitive and easy to learn.nanalysisnPetri nets are marked by the availability of many analysis techniques.WF-net (abbr. of Workflow net) Aalst98nA Petri net PN = (P, T, F) is a WF-net iff: n(1) PN has two special places: i and o. Place i is a source pla

41、ce: . Place o is a sink place: .n(2) If we add a transition to PN such that and , then the resulting Petri net is strongly connected. io*t*ot*it )*,*,*,(ittoFtTPPNThe Basic Structures of WF-netsequentialChoiceParallelIterationp1p2p3t1t2t3t4p1p2p4t1t2t3p3t4t5t6p1p2p5t1t2t4t3p3p4p1p2p3t2t3t5t4p4Soundn

42、ess Property of WF-netnCorrectness Issues on WorkflowsnNo deadlocksnNo dangling tasksnTermination guaranteednDefinition (soundness Aalst98) nA WF-net PN = (P, T, F) is sound if and only if:n(1) M (i M) (M o)n(2) M (i M M o) (M = o)n(3) t T M, M i M M*t * Soundness Property of WF-netExamples of non-s

43、ound (1)没有TokenExamples of non-sound (2)An example of sound workflowResults about WF-net SoundnessnTheorem 1 A WF-net PN is sound if and only if is live and bounded.nCorollary 1 A free-choice WF-net can be checked for soundness in polynomial time.);(iPN)*,*,*,(ittoFtTPPNExample - A WF-net for the pr

44、ocessing of complaintsregistersend_questionnaireprocess_questionnairetime_outarchiveevaluateno_processingprocessing_OKprocessing_requiredprocess_complaintcheck_processingprocessing_NOK5. Analysis Methods of Workflow netnStructural reduction Murata1989, nStructural subclass DE1995, nState space metho

45、d GV2003, nInvariant method Desel1996.structural reductionstructural subclassstructural subclassstructural subclassstructural subclassState space method and Model CheckingState space methodState space methodPetri网的不变量网的不变量(一般概念一般概念)nT-invariants:n含义: 对应工作流网中的一个执行分支, n若向量 Jk 0且Jk 0, 称为半正(semi-positive) T-不变量nP-invariants:n含义: 表示一组库所中的token的个数的总和保持不变, n若向量 Ik 0且Ik 0, 称为半正(semi-positive) P-不变量110000000011000000010110000001001000000100100000010010000001001000000111100000001*987654321987654321ppppppppptttttttttPNFptFtporFptFptifFtpifFtpiftpPN),(),(),(),(1),(0),(1),(0YPNTJk:0PNXPIk:方程的解方程的解方程的解方