柔性制造系统Petri网模型中的一类共享资源

岳 昊，李文杰

(1.漳州师范学院 计算机科学与工程系,福建 漳州 363000；2.山东科技大学 机电学院,山东 青岛 266510;3.西北核技术研究所,陕西 西安 710065)

由于存在共享资源，加之对共享资源的管理不当，柔性制造系统(flexible manufacturing systems，简称FMS)会出现可能的死锁[1].在FMS中，死锁状态就是由于有限资源的共享而导致的一种操作间的循环等待状态，即每种操作都在等待某些资源，而这些资源又被其它操作所占用.死锁问题最早是由计算机科学家在研究操作系统的进程管理时正式提出的[2].生死锁的4个必要条件如下所述[3]：①互斥条件：一个资源每次只能被一个进程使用.②请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放.③不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺.④循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系.这4个条件是死锁的必要条件.只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁.

不同于阻塞，死锁会引起系统部分或全部的停顿，系统的死锁是制约系统控制和调度实现的关键问题[4].而共享资源则是死锁发生的根本原因.因此，很多学者对柔性制造系统中的共享资源进行了深入的研究[4-9].文献[5]将制造系统中的共享资源分为顺序互相抑制(sequential mutual exclusion,SME)，和并行互相抑制(parallel mutual exclusion,PME)两种结构.在文献[5]的基础上，文献[4,6～9]深入研究了独立制造过程的共享资源.其中，文献[4,6]针对具有多个并行共享资源的系统，提出了该类系统具有可能死锁的一个充分必要条件.而文献[7]则提出了具有顺序共享资源制造系统Petri网控制器的形式化设计理论和方法.文献[8]从另外一个角度出发，根据FMS中多种操作对有限资源的竞争会导致死锁状态，介绍了一种死锁避免方法.文献[9]则利用Petri网为多资源共享系统建立模型，并讨论了系统的安全性与无死锁性.

在柔性制造系统中，引发死锁的资源不仅限于独立制造过程所共享的资源，也包括同一加工过程的不同加工操作所共享的资源.本文定义加工过程内共享资源，并通过一实际制造系统的Petri网模型，说明此类资源可能导致系统死锁.

1 基本概念和定义

考查制造系统中的共享资源，对制造系统的建模采用Petri网这种形式化数学工具.因此，本文研究对象为一类S3PR网FMS的Petri网模型.有关S3PR网的相关定义及性质详见文献[1]，下面只给出同本文密切相关的基本概念和相关说明.

定义1[1]一个简单加工过程(simple sequential process，简称S2P)一个网N=(P∪{p0},T,F)，其中：

1)P≠φ(称p∈P为一个操作库所)，p0∉P(称p0为一个过程空闲库所)；

2)N是一个强连通的S-图；

3)N中的每一个圈都包含p0.

定义2[1]称网N=(P∪{p0}∪PR,T,F)是一个带有资源的简单加工过程(simple sequential process with resources，简称S2PR)，其中：

1)N的由P∪{p0}∪T生成的子网是一个简单加工过程；

2)PR≠φ(称r∈PR为一个资源或一个资源库所)，(P∪{p0})∩PR=φ；

3)∀p∈P，∀t∈·p，∀t/∈p·，∃rp∈PR，·t∩PR=t/·∩PR={rp}；

4)下面两点成立：①∀r∈PR,··r∩P=r··∩P≠φ；②∀r∈PR,·r∩r·=φ;

5)··(p0)∩PR=(p0)··∩PR=φ.

∀r∈PR，记H(r)=··r∩P=r··∩P，即使用资源r的操作库所集合.记H(r1)∪H(r2)∪…∪H(rm)为∪r∈RH(r)，其中R={r1,r2,…,rm}为一个资源子集.在下文的S2PR中记P0={p0}.

关于定义2的说明：由条件1)和2)知S2PR是在S2P的基础上加上了若干个资源及相关弧形成的；条件3)说明S2PR中的每一个操作库所使用且仅使用一个资源；条件4)中的①说明对于每一个资源而言，在S2PR中都存在使用它的操作库所，②说明相邻的两个操作库所使用的资源不同；条件5)说明过程空闲库所不使用任何资源.

定义3[1]递归定义S2PR系统(systemofsimplesequentialprocesswithresources，简称S3PR网)如下：

1)一个S2PR是一个S3PR网；

例如,图3所示的S3PR网N由图1和图2中的两个S2PR组合得到：

图4 一个实际的柔性制造系统Petri网模型

图1 一个S2PRN1 图2 一个S2PRN2 图3 一个S3PR网N

2 加工过程内共享资源

就制造系统而言，机器(包括各种加工机床)、托盘、机械臂、缓冲库等常常作为若干分支(如加工单元)等共享的资源[9].所谓共享资源，其可能是因为被多个独立加工过程的不同加工操作所共用，而成为“共享”资源.也可能是因为被同一加工过程内的不同加工操作所共用.目前的研究大多是独立加工过程的共享资源，而本节将定义同一加工过程内的共享资源.

实例设某加工中心有两台机器M1，M2，加工两种工件J1，J2，每台机器同时只能加工一个工件.两种工件的输入工件库分别为I1，I2，存放若干个(分别为C1个和C2个)待加工工件，输出工件库分别为O1，O2，缓冲库为B1，B2，每个缓冲库同时只能放置一个待加工或已加工完毕的工件.

为了方便讨论，可将上面的加工过程看成是一个闭合加工过程，对此将待建模型中的Ii与Oi合并(i=1,2)，得到如下闭合式的加工系统Petri网模型.

读者不难理解模型中网元素(即变迁、库所和有向弧)的意义.在图4中，容易发现M1，M2，B1，B2均为共享资源.其中由定义4，可知B1，B2是都是同一加工过程内的共享资源.考查系统模型如下两种死锁状态.

在图5和图6所示的死锁状态中，加工系统均被迫处于停顿状态，没有工件的加工过程可以推进.在图5中，造成死锁状态的是共享资源M1和M2，而在图6中，造成死锁状态的却是加工过程内共享资源B1.

图5 死锁状态1 图6 死锁状态2

3 结束语

柔性制造系统中的共享资源可能导致系统死锁.现有研究结果都是针对独立加工过程之间的共享资源.本文则以同一加工过程内的不同加工操作所共享的资源作为研究对象，并将其定义为加工过程内共享资源.文中指出，加工过程内共享资源亦有可能产生系统死锁.为了避免系统因死锁而陷入瘫痪状态，对此类资源同样需要合理分配与管理.

参考文献:

[1]Ezpeleta J, Colom J M,Martinez J.A petri net based deadlock prevention policy for flexible manufacturing systems[J].IEEE Trans Robot Automat,1995,11(4):173-184.

[2]黄忠华.自动制造系统中的无死锁调度与控制[D].上海:上海交通大学,2007.

[3]Coffman E G,Elphick M J,Shoshani A.System deadlocks[J].ACM Computing Surveys,1971(3):67-78.

[4]李志武,贾建援,王安荣.复制并行共享资源与系统死锁[J].中国机械工程,2003,14(4):280-284.

[5]Zhou M C, DiCesare F. Parallel and sequential mutual exclusion for Petri net modeling of manufacturing systems with shared resources[J].IEEE Trans Robotics and Automation,1991,7(4):515-527.

[6]李志武,陶晓峰.复杂并行共享资源柔性制造系统中的死锁结构[J].机械科学与技术,2002,21(4):543-545.

[7]李志武,郝林.顺序共享资源制造系统Petri网控制器的形式化设计方法[J].机械科学与技术,2002,21(3):488-490.

[8]韩赞东,李基范.FMS中资源共享导致的死锁状态及其避免方法[J].中国机械工程，2004,15(10):212-216.

[9]许广银.多资源共享系统的死锁分析与控制[J].应用科学学报1998,16(3):331-337.

[10]张会福.数字制造系统资源共享理论框架及关键技术研究[D].武汉：武汉理工大学,2007.

[11]薛雷,郝跃.面向柔性制造系统的基于“自治子网”的Petri网结构化建模方法及其活性保障策略[J].中国科学，2003,33(10):876-886.