Deadlock Control In Resource Allocation Systems And Its Application

Due to the limited resourees that are shared and eomPeted,eireular wait may beeasily eaused when a resouree alloeation system evolves.This may leads to deadloeks.Deadloeks often result in deereased Produetivity or lead to eatastroPhie results in somehighly automated systems.Henee,deadloeks must be taken into aeeount and avoidedfor resouree alloeation systems.In order to avoid deadloeks,eireular wait must be for-bidden when sharing resourees are alloeated.Petri nets,as a major mathematieal tool,due to their inherent eharaeteristies,are inereasingly beeoming a fully fledged formal-ism and have reeeived Partieular attention from aeademie and industrial eommunitiesover the last two deeades.There are three strategies to handle deadloek Problems ofresouree alloeation systems modeled by Petri nets:deadloek deteetion and reeover又deadloek avoidanee,and deadloek Prevention.Deadloek deteetion and reeovery allowsa deadloek to oeeur.When a deadloek 15 deteeted,the system 15 reeovered to the initialstate by realloeating resourees.Deadloek avoidanee uses an online resouree alloeationmeehanism to eontrol resouree requests.In a prevention poliey,deadloeks are eliminatedby establishing an off--line resouree alloeation meehanism to eontrol the requests for re-sourees.Onee it 15 established,the system ean never be in deadloek states.This researeheonsiders deadloek eontrol Problems in resouree alloeation systems.Furthermore,theresults obtained in this study are also extended to the analysis and eontrol of eanaltraffie systems in real world.The major eontributions of this researeh are summarizedas follows:1 .A suboPtimal deadloek Prevention Poliey based on the theory of elementarysiPhons 15 ProPosed.Control Plaees are added for striet minimal siPhons based oneontrollability relationshiP of elementary siPhons and dePendent siPhons.When thedeadloeks eannot be eompletely eliminated,they are prevented by reeonfiguring theinitial markings of the eontrol plaees.Aeeording to the ideas of implieit plaees inaPetri net,an algorithm 15 ProPosed aiming to remove the redundant monitors sueh thata strueturally simPle liveness一enforeing Petri net suPervisor ean be found.ExPerimentalstudies show that the deadloek Prevention Poliey usually brings about a more PermissivesuPervisor eomPared with the ones using siPhon enumeration in the literature.2 .A deadloek eontrol strategy by using the divide一and一eonquer teehnique 15 Pre-sented for S3PR,based on the eoneept of resouree eireuits.A Petri net model deeompo-sition teehnique 15 develoPed sueh that an original Petri net model ean be divided intoaProeess idle subnet,an autonomous subnet,and a number of indePendent subnets.The global suPervisor as well as live eontrolled一system ean be obtained by synehronouslysynthesizing sub一suPervisors develoPed for the subnets.The eomPutational overhead 15greatly redueed if the divide一and一eonquer strategy 15 aPPlied to any deadloek PreventionPoliey existing in the literature.3 .A deadloek eontrol strategy by using deeomPosition teehnique 15 Presented forS4R,based on the eoneept of elementary siphons.There do not alw盯5 exist resoureeeireuits in S4R nets,that 15 tos盯,the divide一and一eonquer deadloek eontrol poliey doesnot work for them any more.A Petri net model deeomPosition teehnique 15 develoPedbased on the eoneept of elementary siphons sueh that an original Petri net model eanbe divided into a Proeess idle subnet,an self--live subnet,and several grouP of siPhonssubnets.The global suPervisor as well as live eontrolled一system ean be obtained bysynehronously synthesizing sub一suPervisors develoPed for the subnets.This Poliey aimsat redueing the eomputational overhead for supervisor design with more permissivebehavior.4 .A deadloek Prevention algorithm 15 develoPed on the basis of Previous studiesfor S4R.The method proposed by park and Reveliotis ean make sure the eontrolledsystem 15 live but overly restrietive.This Poliey ean avoid some eonstraints that are notneeessary by using mixed integer programming(Mlp)teehnique and adding monitorsto eomPlementary sets of siPhons direetly.Usually a liveness一enforeing suPervisor withmore Permissive ean be obtained by the ProPosed Poliey.5 .A set of liveness eonstraints are ProPosed for a Petri net under whieh deadloek-freedom 15 ensured.A liveness eonstraint 15 rePresented by an inequality with resPeetto the markings of idle and resouree Plaees in the Plant net model.The eoneePts ofelementary and dePendent eonstraints are develoPed and an algorithm to identify a setof elementary eonstraints 15 Provided.6 .The results on resouree alloeation systems are aPPlied to the modeling,analysis,and eontrol of eanal traffie systems modeled with Petri nets.Two deadloek eontrolPolieies are used to eontrol the model.Then,we eomPare these two Polieies.Finally,for the first method,its extended aPPlieation 15 demonstrated by an examPle.The results Presented in this Partieular study are signifieant to the deadloek eontrolof resouree alloeation systems and suPervisory eontrol theory of general diserete eventsystems based on Petri nets.