短文基于Petri网的并发系统控制器设计①蒋昌俊IT张兆庆1乔如良2(1•同济大学计算机科学与工程系，上海200092;2中科院计算技术研究所国家智能机中心，北京100080;3山东科技大学计算模型与算法研究所，泰安271019)摘要：针对并发系统的死锁现彖，通过原系统Petri网模盘的状态可达图和行为规范,产生目标系统的可达图,进一步牛•成控制器的Petri网模世山此为这类问题的控制器Petri网模型的生成提供一条冇效途径关键词:Petri网；死锁；控制器中图分类号：O233文献标识码:ADes运nofcontroilerofconcurrentsystemsbasedonPetrinetsJI4NGChangjun123,ZHANGZhao-qmg3,QIAORu-lfang2(1.DepartmentofComputerScience&Engineering,TongjiUniversity,Shanghai200092,China；2InstofComputModel&Algorithm,Univ.ofShandongSci&TechnoI,Taian271019,China;3InstofComputTechnoI,ChineseAcademyofScience,Beijing100080,China)AbstractInthispaper,thedesignmethodofdeadlockcontrollerforconcurrentsystemisgivenTheoperationstepsofthismethodincludes,thefirst,thereachablegraphofPetrinetmodeloforiginalsystemisgeneratedThesecond,thereachablegraphofgoalsystemisspannedbythereachablegraphofPelrinetmodeloforiginalsystemandbehaviorspecificationsThelast,thePelrinetmodelofcontrollerisobtainedTheywillbeusedlorthedesigndeadlockcontrollerofconcurrentsystems文章编号:1000-5781(2001)02-0116-05Keywords:Petrinet;deadlock;controller0引言随着科学技术的进步，信息需求与信息处理的海量已不能rh简单的顺序操作来处理,人们迫切需要一些性能好，效率高、稳定可靠的并行操作环境为此，人量涌现出网络并行环境、分布式系统和大规模并行处理机等这些实际系统的抽象就是并发系统模型，人们C大最地研究了并发系统的建模、分析及性能评佔文［1］建立了并发系统的Petri网模型，文［2］提出描述并发的通信顺序进程(CSP),文［3］引入了通信演算系统(CCS).文［4,5］基于CSP和CCS研究了并发系统的建模与分析手段文［6・8］研究了基于Pelri网的并发系统设计、分析与评价这些工作无疑对①收稿日期：1999-08-18;修订日期:1999-11-15基金项目：国家门然科学基金(69973029;69933020),全国优秀博士学位论文作者专项基金(199934).山东省优秀中青年科学家基金和上海市曙光基金项目资助©1995-2004TsinghuaTon^fangOpticalDiscCo.,Ltd.Allrightsreserved.并发理论及应用起到很好的作出然而，关于并发系统的异常现象的控制问题虽有研究，但还不充分为此,针对死锁现象，讨论控制器的综合方法,给出具体的可操作算法，设计出控制器的Peiri网模型，从而为并发系统的死锁处理提供一条有效途径1控制器综合算法系统死锁现象需要控制，如何综合控制器将是十分必要和实际的工作现讨论:在已知原始系统的Petri网模型及控制规范的前提下，综合出控制器的Petri网模型的方法具体步骤是：第1步从原始系统的Petri网模型(E),产生其可达状态图RMG(L);第2步从原始系统可达状态图RMG(L)和控制规范(Spec),产生I」标系统的可达状态图RMG(ZGC)①；笫3步从目标系统可达状态图RMG(S0C),产生控制器的可达状态图RMG(C);第4步从控制器的可达状态图RMG(C),产生控制器的Petri网模型(C).其中每一步的详细过程为算法1输A:L=(P,T,F,Mo)输!B：RMG(D=(V,E;/)Stepl置初值V—{Mo},E—0,并对Mo标以“新”;Step2若V中无“新”的结点,构造过程结束，否则转Step3;Step3选择一个“新”的MeV结点，做如FT作：Step31对X/TWT,若M口>，则做如下工作：Step311求出M'，使得M[f>M'Step312若M'GV，则置E_EU{叙，M')},f(劎，M'))-/,转Step32,否则做StepSL1;StepJ13若3M"ev,使得VpGP,都有M”(p)WMS,则对满足M'(/?)<M‘(〃)的所有p,置M'(〃)—8；Step!14置V—VU{M'},E—EU{,M')},/(M,M'))-r,并对M'标以“新”，转Step31Step32把M的“新”划去，转Step2根据文[12],知道Petri网可达树的生成算法的有限终止性和正确性而可达图算法实际上是将可达树中的相同标识结点合成同一个标识结点，其它照旧由此可以保证可达图生成算法的有限终止性和正确性算法2输入RMG(E),Sp...