Programming Realization And Testing Of Using Resource Digraphs To Compute The Number Of Elementary Siphons Of An S~3PR Net

With the rapid development of computing technology, communication technology and sensor technology, dynamic systems, such as air traffic control systems, automated manufacturing systems, computer communication networks, embedded network systems, software systems, etc, has become more and more complex. In order to ensure their normal operation, most of the dynamic systems usually involve the allocation of resources and resource competition issues. Since the operation rules of these dynamic systems are entirely formulated by people and their status are usually driven by asynchronous discrete events, this type of systems is called discrete event systems. Various mathematical models and tools have been used to analyze discrete event systems and Petri nets are one of the main mathematical tools. In discrete event systems, deadlock is an undesirable state. The occurrence of deadlock means the whole or part of the system is blocked, which may cause disastrous consequences. Therefore, the control of deadlock attracts a lot of attention of researchers. Deadlock prevention and deadlock avoidance have been two primary methodologies for handing deadlocks in Petri nets for the last two decades. A deadlock prevention policy provides an offline resource allocation mechanism,while a deadlock avoidance one needs an online decision-making algorithm. A monitor and related arcs are added for every strict minimal siphon in a plant Petri net model by traditional deadlock prevention methods in literature.Since siphons are a structural object of Petri nets and in theory, their number has an exponential relationship with the net size,the supervisor’s structure of a large sized Petri net is usually too complicated to manage. The theory of elementary siphons has proved that a supervisor can be computed whose size is linear with the size of the net model. However, the enumeration of siphons is required for the purpose of determining the set of elementary siphons.By studying the structure of an S3 PR net, a subclass of Petri nets, it is proved that the rank of the complementary matrix of an S3 PR net is equal to the number of its elementary siphons. Considering that there exists a bijective mapping from a strongly connected contributing block of its resource digraph to a strict minimal siphon of S3 PR net, the resource digraph can be used to determine the number of elementary siphons. This method can significantly decrease the complexity of computing the number of elementary siphons. In this thesis, based on Matlab programming, the realization of using resource digraph to determine the number of the elementary siphons in an S3 PR net is discussed in detail. Furthermore, all of strictly minimal siphons of an S3 PR net can be obtained by this program.The work of this thesis provides a useful and efficient tool for determining the number of elementary siphons in an S3 PR net. With the help of this program, two special examples are obtained which further verify the correctness of the available method.