S~4PR Net Based Siphon Controllability Conditions And Applications

In typical resource allocation systems, resource sharing may cause deadlocks. Deadlock is a state of a set of processes being blocked for waiting infinitely upon each other to release resources that are needed for their further advancement. Due to the existence of deadlocks, the system performances may be deteriorated dramatically. Petri net is an important formal model and S4PR net is a class of generalized Petri nets which can well model a large class of resource allocation systems. The deadlock control theory for S4PR nets has been a hot research topic in recent years. Deadlock prevention policies based on siphon control are the main approach for liveness of S4PR nets. Current siphon controllers are designed based on overly restrictive siphon controllability conditions and this will leads to low permissively controlled systems. Hence the siphon controllability theory for S4PR needs to be further improved. Based on this, this paper studies the siphon controllability conditions and applications. The completed work mainly divides into the following two parts:(1) The siphon controllability problem for S4PR nets is studied first. Based on the existing ones, this paper presents two classes of improved and more general siphon controllability conditions called maxⅢand maxⅣ-controlled condition, respectively. It is proved that an S4PR net is live if all its siphons are maxⅢor maxⅣ-controlled. Compared with the preceding ones, these two conditions are more relaxed.(2) Based on the maxⅢand maxⅣ-controlled condition, this paper further extends the research. Two improved siphon computation algorithms are introduced. By selecting particular markings in the statement space of an S4PR and solving the MIP problems, a non-maxⅢ-marked or a non-maxⅣ-marked siphon can be obtained. The result of application examples illustrates that these two algorithms are more efficient than the preceding ones.Furthermore, some redundant siphons can be eliminated so that the permissiveness of the controlled systems can be improved.This paper presents two new siphon controllability conditions for liveness of S4PR nets, which are more general than the existing ones.It is concluded that if all siphons in an S4PR net are maxⅢor maxⅣ-controlled, then the net is live. The applications based on these two conditions are further studied and two new siphon computation algorithms are proposed. Application examples illustrate their feasibility and effectiveness.