Critical paths in the Partial Order Unfolding of a Stochastic Petri Net

Anne Bouillard

Description

Critical paths in the Partial Order Unfolding of a Stochastic Petri Net Anne Bouillard Irisa/ENS Cachan, Campus de Beaulieu, Rennes, France Stefan Haar INRIA Saclay/ENS Cachan 61, avenue du President Wilson 94235 CACHAN Cedex - France France Sidney Rosario Irisa/Inria Rennes, Campus de Beaulieu, Rennes, France June 24, 2009 Abstract In concurrent real-time processes, the speed of individual components has a double im- pact: on the one hand, the overall latency of a compound process is affected by the latency of its components. But, if the composition has race conditions, the very outcome of the pro- cess will also depend on the latency of component processes. Using stochastic Petri nets, we investigate the probability of a transition occurrence being critical for the entire process, i.e. such that a small increase or decrease of the duration of the occurrence entails an increase or decrease of the total duration of the process. The first stage of the analysis focuses on occurrence nets, as obtained by partial order unfoldings, to determine criticality of events; we then lift to workflow nets to investigate criticality of transitions inside a workflow. 1 Introduction This paper studies the impact of component performances - measured by transition delays - on the global performance of a composite workflow. This impact analysis is complicated by the presence of concurrency and of conflict, both of which may either hide individual delays or accentuate their impact.

• transitions t0


• looping transition


• no pe


• pair ?


• pairwise concurrent


• has height


• unfolding semantics


• g? ?


• output transition

Sujets

• Wilson

Informations

• Publié par: pefav
• Nombre de lectures: 31
• Langue: English

Extrait

CriticalpathsinthePartialOrderUnfolding ofaStochasticPetriNet AnneBouillardStefanHaarSidneyRosario Irisa/ENSCachan,INRIASaclay/ENSCachanIrisa/InriaRennes, CampusdeBeaulieu,61,avenueduPre´sidentWilsonCampusdeBeaulieu, Rennes,France94235CACHANCedex-FranceRennes,France France June24,2009 Abstract Inconcurrentreal-timeprocesses,thespeedofindividualcomponentshasadoubleim- pact:ontheonehand,theoveralllatencyofacompoundprocessisaffectedbythelatency ofitscomponents.But,ifthecompositionhasraceconditions,theveryoutcomeofthepro- cesswillalsodependonthelatencyofcomponentprocesses.UsingstochasticPetrinets,we investigatetheprobabilityofatransitionoccurrencebeingcriticalfortheentireprocess,i.e. suchthatasmallincreaseordecreaseofthedurationoftheoccurrenceentailsanincrease ordecreaseofthetotaldurationoftheprocess.Thefirststageoftheanalysisfocuseson occurrencenets,asobtainedbypartialorderunfoldings,todeterminecriticalityofevents; wethenlifttoworkflownetstoinvestigatecriticalityoftransitionsinsideaworkflow. 1Introduction Thispaperstudiestheimpactofcomponentperformances-measuredbytransitiondelays- ontheglobalperformanceofacompositeworkflow.Thisimpactanalysisiscomplicatedby thepresenceofconcurrencyandofconflict,bothofwhichmayeitherhideindividualdelaysor accentuatetheirimpact.Tocapturetheseeffects,weconsidercontinuoustimeprocesseswithin theframeworkofpartialorderunfoldingsemantics[8,9,13]ofPetrinets. Tomotivatetheideas,consideramachineservicingworkflow,representedasaPetrinet inFigure1.Atokenintheinitialplacerepresentsaclientrequestingthathismachinebe serviced.Aclientcanrevokehisrequest(byfiringtransitionN),butthishastobedonebefore theservicingprocesshasbeenstarted(bythefiringofS).Themachinehastwocomponents C X andC Y ,theoperationsservicingthemaredenotedbythetransitionsXandYrespectively. ThecomponentC Y degradeswhenitisidleandhastobeshippedtotheclient(denotedby transitionD)assoonaspossibleafteritsservicing.Ifthemachinecannotbedelivered(either becausecomponentC X ’sservicinghasnotyetfinishedorbecausetheshippingprocesshasnot yetbegun),afteracertaintimethecomponentC Y hastobesentforservicingagain(denoted bythefiringofC). Now,thelatencyofindividualeventshasadoubleimpactontheconfigurations.Firstly,the overalllatencyofaconfigurationisaffectedbythelatencyofitsindividualevents:thelatency ofaconfigurationisamax-pluscombinationofthelatenciesofitsindividualevents.Asecond impactofthelatenciesoftheindividualeventsisthechoiceofconfigurationitself,sinceanevent withashorterlatencycanpre-empttheoccurrenceofaconflictingeventwhosedelayislarger. Theauthorsof[15]haveanalyzedfirst-passagetimeineventstructuresforafixedconfiguration; 1