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

pages

English

Documents

Écrit par
Anne Bouillard

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

English

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

Voir

Publié par

pefav

Nombre de lectures

Langue

English

Wilson

CriticalpathsinthePartialOrderUnfoldingofaStochasticPetriNetAnneBouillardStefanHaarSidneyRosarioIrisa/ENSCachan,INRIASaclay/ENSCachanIrisa/InriaRennes,CampusdeBeaulieu,61,avenueduPre´sidentWilsonCampusdeBeaulieu,Rennes,France94235CACHANCedex-FranceRennes,FranceFranceJune24,2009AbstractInconcurrentreal-timeprocesses,thespeedofindividualcomponentshasadoubleim-pact:ontheonehand,theoveralllatencyofacompoundprocessisaﬀectedbythelatencyofitscomponents.But,ifthecompositionhasraceconditions,theveryoutcomeofthepro-cesswillalsodependonthelatencyofcomponentprocesses.UsingstochasticPetrinets,weinvestigatetheprobabilityofatransitionoccurrencebeingcriticalfortheentireprocess,i.e.suchthatasmallincreaseordecreaseofthedurationoftheoccurrenceentailsanincreaseordecreaseofthetotaldurationoftheprocess.Theﬁrststageoftheanalysisfocusesonoccurrencenets,asobtainedbypartialorderunfoldings,todeterminecriticalityofevents;wethenlifttoworkﬂownetstoinvestigatecriticalityoftransitionsinsideaworkﬂow.1IntroductionThispaperstudiestheimpactofcomponentperformances-measuredbytransitiondelays-ontheglobalperformanceofacompositeworkﬂow.Thisimpactanalysisiscomplicatedbythepresenceofconcurrencyandofconﬂict,bothofwhichmayeitherhideindividualdelaysoraccentuatetheirimpact.Tocapturetheseeﬀects,weconsidercontinuoustimeprocesseswithintheframeworkofpartialorderunfoldingsemantics[8,9,13]ofPetrinets.Tomotivatetheideas,consideramachineservicingworkﬂow,representedasaPetrinetinFigure1.Atokenintheinitialplacerepresentsaclientrequestingthathismachinebeserviced.Aclientcanrevokehisrequest(byﬁringtransitionN),butthishastobedonebeforetheservicingprocesshasbeenstarted(bytheﬁringofS).ThemachinehastwocomponentsCXandCY,theoperationsservicingthemaredenotedbythetransitionsXandYrespectively.ThecomponentCYdegradeswhenitisidleandhastobeshippedtotheclient(denotedbytransitionD)assoonaspossibleafteritsservicing.Ifthemachinecannotbedelivered(eitherbecausecomponentCX’sservicinghasnotyetﬁnishedorbecausetheshippingprocesshasnotyetbegun),afteracertaintimethecomponentCYhastobesentforservicingagain(denotedbytheﬁringofC).Now,thelatencyofindividualeventshasadoubleimpactontheconﬁgurations.Firstly,theoveralllatencyofaconﬁgurationisaﬀectedbythelatencyofitsindividualevents:thelatencyofaconﬁgurationisamax-pluscombinationofthelatenciesofitsindividualevents.Asecondimpactofthelatenciesoftheindividualeventsisthechoiceofconﬁgurationitself,sinceaneventwithashorterlatencycanpre-empttheoccurrenceofaconﬂictingeventwhosedelayislarger.Theauthorsof[15]haveanalyzedﬁrst-passagetimeineventstructuresforaﬁxedconﬁguration;1

Voir