Reachability graph is a very important tool to analyze the dynamic properties of Petri nets, but the concurrent relation of transitions in Petri nets cannot be represented by reachability graph. Petri net is a concurr...Reachability graph is a very important tool to analyze the dynamic properties of Petri nets, but the concurrent relation of transitions in Petri nets cannot be represented by reachability graph. Petri net is a concurrent system, while reachability graph is a serial one. However, concurrency is a kind of property which is not only very significant but also difficult to be analyzed and controlled. This paper presents the concepts of concurrent reachable marking and concurrent reachable graph in order to represent and analyze the concurrent system. The algorithm constructing concurrent reachable marking set and concurrent reachability graph is also shown so that we can study the response problems among services in a network computing environment and analyze the throughput of the system. The Dining Philosophers Problem, which is a classic problem of describing the management of concurrent resources, is given as an example to illustrate the significance of concurrent reachability graph.展开更多
Logic Petri nets （LPNs） are suitable to describe and analyze batch processing functions and passing value indeterminacy in cooperative systems. To investigate the dynamic properties of LPNs directly, a new method fo...Logic Petri nets （LPNs） are suitable to describe and analyze batch processing functions and passing value indeterminacy in cooperative systems. To investigate the dynamic properties of LPNs directly, a new method for analyzing LPNs is proposed based on marking reachability graphs in this paper. Enabled conditions of transitions are obtained and a marking reachability graph is constructed. All reach- able markings can be obtained based on the graph; the fairness and reversibility of LPNs are analyzed. Moreover, the computing complexity of the enabled conditions and reachable markings can be reduced by this method. The advantages of the proposed method are illustrated by examples and analysis.展开更多
Concurrency and sharing resource of system are the main properties of concurrent operating system. Dead-lock is a important problem to solve in concurrent operating system. As a useful tool of modeling and analyzing c...Concurrency and sharing resource of system are the main properties of concurrent operating system. Dead-lock is a important problem to solve in concurrent operating system. As a useful tool of modeling and analyzing con-current, asynchronous and distributed system ,Petri net has been used to solve many problems of operating system.However, most of the models are common Petri net. The common Petri net model is too complex when the scale ofsystem is bigger. This paper models the concurrent system with colored Petri net. It makes the model much simpler.Moreover, the paper gives an algorithm for constructing reachable marking graph of colored Petri net. As a result,the paper gives a sufficient and necessary condition for judging the system deadlock and a method for avoiding the sys-tem deadlock.展开更多
文摘Reachability graph is a very important tool to analyze the dynamic properties of Petri nets, but the concurrent relation of transitions in Petri nets cannot be represented by reachability graph. Petri net is a concurrent system, while reachability graph is a serial one. However, concurrency is a kind of property which is not only very significant but also difficult to be analyzed and controlled. This paper presents the concepts of concurrent reachable marking and concurrent reachable graph in order to represent and analyze the concurrent system. The algorithm constructing concurrent reachable marking set and concurrent reachability graph is also shown so that we can study the response problems among services in a network computing environment and analyze the throughput of the system. The Dining Philosophers Problem, which is a classic problem of describing the management of concurrent resources, is given as an example to illustrate the significance of concurrent reachability graph.
基金This work is supported by the National Basic Research Program of China （2010CB328101） the National Natural Science Foundation of China （Grant Nos. 61170078 and 61173042）+2 种基金 the Doctoral Program of Higher Education of the Specialized Research Fund of China （20113718110004） Basic Research Program of Qingdao City of China （13- 1-4-116-jch） and the SDUST Research Fund of China （2011KYTD 102）.
文摘Logic Petri nets （LPNs） are suitable to describe and analyze batch processing functions and passing value indeterminacy in cooperative systems. To investigate the dynamic properties of LPNs directly, a new method for analyzing LPNs is proposed based on marking reachability graphs in this paper. Enabled conditions of transitions are obtained and a marking reachability graph is constructed. All reach- able markings can be obtained based on the graph; the fairness and reversibility of LPNs are analyzed. Moreover, the computing complexity of the enabled conditions and reachable markings can be reduced by this method. The advantages of the proposed method are illustrated by examples and analysis.
文摘Concurrency and sharing resource of system are the main properties of concurrent operating system. Dead-lock is a important problem to solve in concurrent operating system. As a useful tool of modeling and analyzing con-current, asynchronous and distributed system ,Petri net has been used to solve many problems of operating system.However, most of the models are common Petri net. The common Petri net model is too complex when the scale ofsystem is bigger. This paper models the concurrent system with colored Petri net. It makes the model much simpler.Moreover, the paper gives an algorithm for constructing reachable marking graph of colored Petri net. As a result,the paper gives a sufficient and necessary condition for judging the system deadlock and a method for avoiding the sys-tem deadlock.
