Client/Server FIFO computer system analysis (sharpe software)

Università degli Studi di Messina Facoltà di Ingegneria

Computer system analysis

Petri nets

Introduction

• Markov chains are useful to study many problems – reliability

– availability

– performance

– performability

• They are difficult to be managed

Markov chain based models

• State space

• It could be difficult to represent a system with a model

• A more intuitive representation could be useful

Petri nets • Petri nets are a graphical tool to

represent activity flows

• It is possible to easily represent system interactions – Synchronization

– Sequences

– Concurrency

– Conflicts

Definition • A Petri net is a tupla

• PN={P, T, I, O, M0}

– P: set of nP places

– T: set of nT transitions

– I, O: sets of input and output functions

– M0 = {m1, m2, ..., mnp}: initial marking (state)

Place and transitions

• A place is drawn as a circle

• A transition is drawn as a bar

Input and output functions • I : T -> Bag(P)

• O : T -> Bag(P)

• Bag(A) is a set with repeated elements – es: {p1, p1, p4} = {p1(2), p4} = {2, 0, 0, 1}

• Input and output arcs are drawn as oriented arcs

Token

• Each place can contain tokens

• A token is drawn as a little black circle

• A token distribution over places identify a Petri net state

• Petri net states are defined through markings

Marking

• M0={m1, m2, ..., mnp}

• mi є Ν ; number of tokens into place pi

Notation

• Let us denote with: – I(t): the bag of input places of transition t – I(t, p): multiplicity of place p in bag I(t) – O(t): the bag of output places of transition t – O(t, p): multiplicity of place p in bag O(t)

Example (1) p1

p2 p3

p4 p5

t1

t2 t3t4

t5

P={p1,p2,p3,p4,p5}

T={t1,t2,t3,t4,t5}

I(t1)={p1}, O(t1)={p2,p3}

I(t2)={p2}, O(t2)={p4}

I(t3)={p3}, O(t3)={p5}

I(t4)={p4}, O(t4)={p2}

I(t5)={p4,p5}, O(t5)={p1}

M0={1, 0, 0, 0, 0}

Example (2)

I(t)={P} I(t, P)=1

I(t)={P(2)} I(t, P)=2

P t 2

Enabling rule

• PI(tk): set of input places of transition tk

• Mi(p): number of tokens in place p in marking M

• Transition tk is said enabled in marking M iff the number of tokens in its input places is at least equal to the multiplicity of its input arcs

∀ p∈PI tk⇒ M i p≥I tk , p

Transition firing • An enabled transition can fire producing

a marking change according to the following rule

• Petri net dynamics

• What happen when more transitions are enabled?

M j=M i−I tkOtk

Definitions

• Two enable transitions are said – in conflict when the firing of one disable the

other

– concurrent when the firing of one does not disable the other

Examples

t2t1

P1

P2

P3

P4

t2t1

P1

P2

P3

P4

conflict concurrency

Example - concurrency

t2t1

P1

P2

P3

P4

Example - syncronization

t2t1

P1

P2

P3

P4

t3

Example – finite resources

t2

P1

P2

P3

t1

P4

Example – producer/consumer

t2

P1

P2

t1

t2

P3

P4

t1

P5

P4

Example – mutual exclusion

t2

P1

P2

t1

P3

P7 t5

P4

P5

t4

P6

t3 t6

Inhibitor arcs

• PN={P, T, I, O, H, M0)

• H : T -> Bag(P)

P1 t1 2

H (t1)={P1, P1}

Enabling rule

1. each input place has at least as many tokens as the multiplicity of the input arcs

2.each inhibitor place has less tokens than the multiplicity of the corresponding arc

∀ p∈PI tk⇒ M i p≥I tk , p

∀ p∈PH tk ⇒ M i pH tk , p

Example

P1

t1

P2 t1 is enabled

t1 is not enabled

Example – priority

t2

P1

P2

t1

P3

P7 t5

P4

P5

t4

P6

t3 t6

Reachability graph

• M0 is the starting state (initial marking)

• A new marking Mj is computed when an

enabled transition tkєT in Mi fires

• Mj is said directly reachable from Mi

M i  t k

M j

Reachability graph (2) • The repeated application of the firing

rule generates the reachability graph

• Petri net dynamics

• A marking Mi is said reachable iff, given

M0, a firing sequence from M0 to Mi exists

Reachability graph (3) • The set of all the reachable markings is

said reachability set

• It is denoted with RS(M0)

• RS(M0) + firing events = reachability graph

• Firing sequence ={M 1,t1;M 2,t2 ,⋯M n ,tn}

Example P1

P2 P3

t1 t2

10010

01010 00110

01001

t1

t3

t2 P4

P5

t3

00101

10001

t3 t3 t2

t1

Timed PN

• TPN={P, T, I, O, H, M0,Θ)

• Θ : T-> R+, function assigning a time delay to transitions

• Firing sequence

={M 1,t1,1 ,M 2,t2,2;⋯;M n ,tn ,n}

Stochastic Petri nets

• Firing delays are exponentially distributed r.v.

• SPN ={P, T, I, O, H, M0,L)

• L: T->R – L(ti)=λi , cdf's parameter

• Transitions are drawn as empty bar

Example

t2

P1

P2

t1

P3 P7

t5

P4

P5

t4

P6

t3 t6

Stochastic Petri nets

• Transition with shorter sampled delay fires

• After the firing, all the enabled transitions start for scratch (memoryless property)

SPN – Reachability graph

Reachability graph labeled with λi is a CTMC

SPN - Analysis

• State probabilities = Marking probabilities

T e (i) ={t∈T :t is enabled into M i}

E jM i={tk∈Tei:M i  t k

M j}

qij={ ∑

k :t k∈E j M i

k i≠ j

− ∑ k : t

k ∈T

e i 

k i= j

Generalized Stochastic Petri Nets • GSPN ={P, T, I, O, H, M0, L, c)

• Immediate and timed transitions

• L(tk) depends on tk

– Timed tk: L(tk)=λk

– Immediate tk: L(tk)=wk • c: T-> N associates a priority to transitions

GSPN – Enabling rule

• Timed t: c(t)=0

• Immediate t: c(t)>0 – Used to model logic events

∀ p∈PI tk⇒ M i p≥I tk , p

∀ p∈PH tk ⇒ M i pH tk , p

∀ t∈T e i ,t≠tk⇒ct ≤ctk

Definitions • A marking where some immediate

transitions is enabled is said vanishing – The visit time is null

• A marking where only timed transitions are enabled is said tangible

Properties

• Timed and immediate transitions cannot be enabled in the same marking

• If a timed transition is enabled in a marking, all the enabled transitions are timed

Transition firing

• Probabilistic choice

sk (i) =P{tk fires∣M (t)=M i}=

wk

∑ t∈T

e (i)

wt

Transition enabling

• Three cases can arise in a marking M

1) Timed transitions are enabled

2) One immediate transition is enabled

3) More immediate transitions are enabled

Case 1)

• M is a tangible marking

P1

t1 t2 t3

P2 P3 P4

1000

0100

0010

0001

Case 2)

• One immediate transition is enabled

P2

t1 t2 t3

P3 P4 P5

P1

10000

01000

00100

λ1

10000

00100

λ1

Case 3) • More immediate transitions are enabled

1000

0100

0010

λ1

0001

u

1-u

1000

0010

(1-u)λ1

0001

u λ1

P1

P2

P3 P4

t1

t2 t3 u

1-u

• Problem: cycles of vanishing markings

Analysis

• All the vanishing markings are erased

• Reduced reachability graph

• Some informations are lost

• The resulting stochastic process is a CTMC

Marking dependent transitions

• Transition rates can depend on the marking

• L(tk) = λk(M)

example k equal redundant components subject to faults. Only one repair resource

k p1 p2

fail

repair

λ(fail)=λ f * (#p1)

Multiple enabling • Different semantics can be assumed

when more than one token is in a place – single server: tokens generate serial

transition enablings

– infinite-server: different timers are associated to each token; parallel evolution

– multiple server: tokens are processed in parallel with parallel degree equal to k

Example P1

P2

T1

Sampled delays: •A1 -> 3 •A2 -> 2 •A3 -> 4

t3 5 9

Single server

t32 4

Infinite server

t32 6

Multiple server (k=2)