Deadlock Prevention Policy Based On Max-controlled Property Of Siphons For Resource Allocation Systems

This thesis investigates deadlock problems for a special class of sequential resource allocation systems, which is called S~4PR within the scope of flexible manufacturing systems (FMS). Two different deadlock prevention policies based on max-controlled property of siphons are developed.The first deadlock prevention policy purposes a way making every strict minimal siphon max-controlled by adding a control place to every elementary siphon. The initial markings of control places are predetermined with a variable expression satisfied with the elementary max-controlled. Subsequently, we check the max-controlled property of the dependent siphons and get the constraint including some controlled deep variables. From a practical standpoint, all the optimal values of controlled deep variable are obtained and determined every initial marking of the control place. The policy ensures the max-controlled property of the system, which implies to liveness property of the systems with respect to the structure of S~4PR.The second deadlock policy is based on insufficient marked siphons. Comparing with the first deadlock prevention policy, more constraint is imposed on the net system because all the control places for elementary siphons are added to a system and the flowing arcs of control places are brought forward, synchronously. An iterative method is adopted and the flowing arcs of control places are brought forward to a rational transition that the augment net has no insufficient marked siphon. A control place is added to an optimal insufficient marked siphon satisfied with its max-controlled in every interactive process until the augment net has no insufficient siphon.The first policy is adequate to larger net systems and the second is sutiable for small-sized net systems.