Petri Nets

PetriNets*JAMESL.PETERSONDepartmentofComputerSciences,TheUnwers~tyofTexas,Austin,Texas78712Overthelastdecade,thePetrinethasgamedincreasedusageandacceptanceasabasicmodelofsystemsofasynchronousconcurrentcomputation.ThispapersurveysthebasicconceptsandusesofPetmnets.ThestructureofPetrinets,theirmarkingsandexecution,severalexamplesofPetmnetmodelsofcomputerhardwareandsoftware,andresearchintotheanalysisofPetmnetsarepresented,asaretheuseofthereachabilitytreeandthedecidabilityandcomplexityofsomePetrinetproblems.Petrinetlanguages,modelsofcomputationrelatedtoPetmnets,andsomeextensionsandsubclassesofthePetrinetmodelarealsobmeflydiscussedKeywordsandPhrases:Petnnets,systemmodels,asynchronousconcurrentevents.CRCategories.1.3,5.29,8.1INTRODUCTIONAPetrinetisanabstract,formalmodelofinformationflow.Theproperties,con-cepts,andtechniquesofPetrinetsarebeingdevelopedinasearchfornatural,simple,andpowerfulmethodsfordescrib-ingandanalyzingtheflowofinformationandcontrolinsystems,particularlysys-temsthatmayexhibitasynchronousandconcurrentactivities.ThemajoruseofPe-trinetshasbeenthemodelingofsystemsofeventsinwhichitispossibleforsomeeventstooccurconcurrentlybutthereareconstraintsontheconcurrence,prece-dence,orfrequencyoftheseoccurrences.SincemanyreadersmaybeunfamiliarwithPetrinets,wefirstpresentaverybriefandinformalintroductiontotheirfundamentalsandhistory.Thenwecon-siderseveralaspectsofPetrinetsinmoredetail.Webegin,inSection2,byconsider-ingtheuseofPetrinetsformodelingsys-*Thisworkwassupported,mpart,bytheNationalScienceFoundation,underGrantNumberMCS75-16425.temsofparallelorconcurrentactivities.Section3presentsamoreformaldefinitionanddiscussionofthefundamentalcon-ceptsandnotationsofPetrinets.Section4considerstheextensivebodyofresearchdealingwiththeanalysisofPetrinets,theiradvantages,andtheirlimitations.PetrinetlanguagesarepresentedinSec-tion5.Finally,inSection6,weconsidersomeofthemanyvariationsofPetrinetsthathavebeendefined,bothasgenerali-zationsofPetrinetsandassubclassesofthegeneralmodel;themoregeneralmodelshavecertainadvantagesformodel-ing,whilethemorerestrictedmodelshavecertainadvantagesforanalysis.1.OVERVIEWFigure1showsasimplePetrinet.ThepictorialrepresentationofaPetrinetasagraphusedinthisillustrationiscommonpracticeinPetrinetresearch.ThePetrinetgraphmodelsthestaticpropertiesofasystem,muchasaflowchartrepresentsthestaticpropertiesofacomputerpro-gram.Copyright©1977,AssociationforComputingMachinery,Inc.Generalpermismontorepublish,butnotforprofit,allorpartofthismaterialisgrantedprovidedthatACM'scopyrightnoticeisgivenandthatreferenceismadetothepublication,toitsdateofmsue,andtothefactthatreprintingprivilegesweregrantedbypermissionoftheAssociat]onforComputingMachinery.ComputingSurveys,Vol9,No.3,September1977224*J.L.PetersonCONTENTSINTRODUCTION1OVERVIEWHmtory2.MODELINGWITHPETRINETSPropertiesofPetnNetsUsefulmModelingModelingofHardwareModehngofSoftware3STRUCTUREOFPETRINETSThePetnNetGraphMarkingsExecutmnRulesforMarkedPetrlNetsTheStateSpaceofaPetnNetTheReachabflltySetofaPetrlNet4ANALYSISOFPETRINETSAnalysisQuestmnsSolutmnTechmquesAnalysisUsingtheReachabflltyTreeTheReachablhtyProblemUnsolvableProblemsComplexity5PETRINETLANGUAGES6EXTENSIONSANDSUBCLASSESExtendedPetrtNetsSubclassesofPetrlNetsRelatedModelsCONCLUSIONSACKNOWLEDGMENTSBIBLIOGRAPHYvThegraphcontainstwotypesofnodes:circles(calledplaces)andbars(calledtransitions).Thesenodes,placesandtran-sitions,areconnectedbydirectedarcsfromplacestotransitionsandfromtransi-tionstoplaces.Ifanarcisdirectedfromnodeitonodej(eitherfromaplacetoatransitionoratransitiontoaplace),theniisaninputtoj,andjisanoutputofi.InFig.1,forexample,placeplisaninputtotransitiont2,whileplacesP2andp3areoutputsoftransitiont2.Inadditiontothestaticpropertiesrepre-sentedbythegraph,aPetrinethasdy-namicpropertiesthatresultfromitsexe-cution.Assumethattheexecutionofacomputerprogramrepresentedbyaflow-chartisexhibitedbyplacingamarkerontheflowcharttomarktheinstructionbeingexecuted,andthatastheexecutionprogresses,themarkermovesaroundtheflowchart.Similarly,theexecutionofaPetrinetiscontrolledbythepositionandmovementofmarkers(calledtokens)inthePetrinet.Tokens,indicatedbyblackdots,resideinthecirclesrepresentingtheplacesofthenet.APetrinetwithtokensisamarkedPetrinet.Theuseofthetokensratherresemblesaboardgame.Thesearetherules:Tokensaremovedbythefiringofthetransitionsofthenet.Atransitionmustbeenabledinordertofire.(Atransitionisenabledwhenallofitsinputplaceshaveatokeninthem.)Thetransitionfiresbyremovingtheenablingtokensfromtheirinputplacesandgeneratingnewtokenswhicharedepositedintheoutputplacesofthetransition.InthemarkedPetrinetofFig.2,forexample,thetransitiont2isenabledsinceithasatokeninitsinputplace(Pl)Transitionts,ontheotherhand,isnotenabledsinceoneofitsinputs(P3)doesnothaveatoken.Ift2fires,themarkedPetrinetofFig.3results.Thefiringoftransi-tiont2removestheenablingtokenfromplacePlandputstokensinp2andP3,thetwooutputsoft2.ThedistributionoftokensinamarkedPetrinetdefinesthestateofthenetandiscalleditsmarking.Themarkingmaychangeasaresultofthefiringoftransi-ti