PN modelling - University of Liverpool

PN modelling - University of Liverpool

Software Engineering COMP 201 Lecturer: Sebastian Coope Ashton Building, Room G.18 E-mail: [email protected] COMP 201 web-page: http://www.csc.liv.ac.uk/~coopes/comp201 Lecture 9, 10 Modelling Based on Petri Nets High-Level Petri Nets The classical Petri net was invented by Carl Adam Petri in 1962. A lot of research has been conducted (>10,000 publications). Until 1985 it was mainly used by theoreticians. Since the 80s their practical use has increased because of the introduction of high-level Petri nets and the availability of many tools. High-level Petri nets are Petri nets extended with colour (for the modelling of attributes)

time (for performance analysis) hierarchy (for the structuring of models, DFD's) COMP201 - Software Engineering 2 Why do we need Petri Nets? Petri Nets can be used to rigorously define a system (reducing ambiguity, making the operations of a system clear, allowing us to prove properties of a system etc.) They are often used for distributed systems (with several subsystems acting independently) and for systems with resource sharing. Since there may be more than one transition in the Petri Net active at the same time (and we do not know which will fire first), they are non-deterministic. COMP201 - Software Engineering 3

The Classical Petri Net Model A Petri net is a network composed of places ( ) and transitions ( ). t2 t1 p2 p1 t3 p4 p3 Connections are directed and between a place and a transition, or a transition and a place (e.g. Between p1 and t1 or t1 and p2 above).

Tokens ( ) are the dynamic objects. COMP201 - Software Engineering 4 The Classical Petri Net Model Another (equivalent) notation is to use a solid bar for the transitions: p2 p1 t2 p4 t1 p3 t3

We may use either notation since they are equivalent, sometimes one makes the diagram easier to read than the other.. The state of a Petri net is determined by the distribution of tokens over the places (we could represent the above state as (1,2,1,1) for (p1,p2,p3,p4)) COMP201 - Software Engineering 5 Transitions with Multiple Inputs and Outputs p1 p4 t1 p2 p3 Transition t1 has three input places (p1, p2 and p3) and two output places (p3 and p4).

Place p3 is both an input and an output place of t1. COMP201 - Software Engineering 6 Enabling Condition Transitions are the active components and places and tokens are passive components. A transition is enabled if each of the input places contains tokens. t1 t2 Transition t1 is not enabled, transition t2 is enabled. COMP201 - Software Engineering 7

Firing An enabled transition may fire. Firing corresponds to consuming tokens from the input places and producing tokens for the output places. t2 t2 Firing is atomic (only one transition fires at a time, even if more than one is enabled) COMP201 - Software Engineering 8 An Example Petri Net COMP201 - Software Engineering

9 Example: Life-Cycle of a Person child puberty marriage bachelor married divorce death dead COMP201 - Software Engineering

10 Creating/Consuming Tokens A transition without any input can fire at any time and produces tokens in the connected places: T1 T1 P1 T1 T1 P1 After After firing firing 33 times.. times..

P1 COMP201 - Software Engineering P1 11 Creating/Consuming Tokens A transition without any output must be enabled to fire and deletes (or consumes) the incoming token(s): T1 P1 T1 P1 T1 P1 After

After firing firing 33 times.. times.. T1 P1 COMP201 - Software Engineering 12 Non-Determinism in Petri Nets t1 t2 Two transitions fight for the same token: conflict. Even if there are two tokens, there is still a conflict. The next transition to fire (t1 or t2) is arbitrary (non-deterministic).

COMP201 - Software Engineering 13 Modelling States of a process can be modelled by tokens in places and state transitions leading from one state to another are modelled by transitions. Tokens can represent resources (humans, goods, machines), information, conditions or states of objects. Places represent buffers, channels, geographical locations, conditions or states. Transitions represent events, transformations or transportations. COMP201 - Software Engineering 14

Modelling a Traffic Light COMP201 - Software Engineering 15 Modelling Two Traffic Lights Imagine that we are designing a traffic light system for a crossroads junction (i.e. with two sets of (simplified) lights). An informal specification of a traffic light junction: o A single traffic light turns from Red to Green to Amber and then back to Red (well ignore red and amber for now). o There are two sets of lights. When one of the traffic lights is Amber or Green, the other must be Red. As a first step, we may decide to model the system as a Petri net. This allows us to make sure the specification is rigorously defined and reduces potential ambiguities later. We can also prove properties about the model if we wish. COMP201 - Software Engineering

16 Example: Traffic Light red yr amber rg gy green COMP201 - Software Engineering 17 Two Traffic Lights

red1 red2 yr1 rg1 yr2 amber1 gy1 amber 2 rg2 gy2

green1 COMP201 - Software Engineering green2 18 Two Safe Traffic Lights red2 red1 safe yr1 rg1 yr2 amber1 gy1

amber 2 rg2 gy2 green1 COMP201 - Software Engineering green2 19 Two Safe and Fair Traffic Lights red1 red2 safe2 yr2

yr1 rg1 yellow1 rg2 yellow2 gy1 gy2 safe1 green1 COMP201 - Software Engineering green2 20

Exercise 1) Can you prove that the Petri net from the previous slide will never allow two red lights to be shown simultaneously? COMP201 - Software Engineering 21 Exercise COMP201 - Software Engineering 22 Arcs in Petri Nets br red

black rr bb The number of arcs between two objects specifies the number of tokens to be produced/consumed (we can alternatively represent this by writing a number next to a single arc). This can be used to model (dis)assembly processes. COMP201 - Software Engineering 23 Some Definitions Current state (also called current marking) - The configuration of tokens over the places. Reachable state - A state reachable form the current state by

firing a sequence of enabled transitions. Deadlock state - A state where no transition is enabled. br red black rr COMP201 - Software Engineering bb 24 Some Definitions If we write the places in some fixed order (red, black say), then we can use a tuple: (n,m) to denote the number of tokens in each corresponding place (n tokens in red and m tokens in black). The example below is thus in state (3,2). After firing transition rr, it will move to state (1,3) etc..

br red black rr COMP201 - Software Engineering bb 25 (3,2) br rr red

black bb\br (1,3) (3,1) rr br bb\br rr bb (1,2) (3,0)

rr bb\br (1,1) br (1,0) 7 reachable states, 1 deadlock state. COMP201 - Software Engineering 26 Exercise: Readers and Writers begin receive_mail mail_box rest

rest type_mail send_mail read_mail ready How many states are reachable? Are there any deadlock states? How to model the situation with 2 writers and 3 readers? How to model a "bounded mailbox" (buffer size =4)? COMP201 - Software Engineering 27 Exercise COMP201 - Software Engineering

28 The Four Seasons Let us try to model the four seasons of the year together with their properties by a Petri net. We would like to denote the current season {spring, summer, autumn, winter}, the temperature {hot, cold} and the light level {bright, dark}. As a first step, let us model the seasons (with a token to represent that it is currently autumn). COMP201 - Software Engineering 29 The Four Seasons Summer Autumn

0 Spring Winter COMP201 - Software Engineering 30 The Four Seasons Summer Bright Hot Autumn Cold 0

Spring Dark Winter COMP201 - Software Engineering 31 High-Level Petri Nets In practice, classical Petri nets have some modelling problems: The Petri net becomes too large and too complex. It takes too much time to model a given situation. It is not possible to handle time and data. Therefore, we use high-level Petri nets, i.e. Petri nets extended with: colour time hierarchy COMP201 - Software Engineering

32 Example - High-Level Petri Nets To explain the three extensions we use the following example of a hairdresser's salon: hairdresser ready to begin free client waiting start waiting finish busy finished Note how easy it is to model the situation with multiple hairdressers..

COMP201 - Software Engineering 33 The Extension with Colour A token often represents an object having all kinds of attributes. Therefore, each token has a value (colour) with refers to specific features of the object modelled by the token. name: Sally age: 28 hairtype: BL free start waiting name: Harry age: 28 experience: 2

finish busy COMP201 - Software Engineering finished 34 The Extension with Colour Each transition has an (in)formal specification which specifies: the number of tokens to be produced, the values of these tokens, and (optionally) a precondition. The complexity is divided over the network and the values

of tokens. This results in a compact, manageable and natural process description. COMP201 - Software Engineering 35 Examples c := a+b a b := -a + b neg a

b c a >=0 | b := a a b a select if a> 0 then b:= a else c:=a fi sqrt

b c Exercise: calculate |a+b| using these buiding blocks COMP201 - Software Engineering 36 The Extension with Time To analyse performance, we must model durations, delays, etc. A timed Petri net associates a pair tmin and tmax with each transition (there are other possible definitions for timed Petri net, but we shall only consider this one). free start

waiting Tmin = 0 Tmax = 3 finish busy COMP201 - Software Engineering Tmin = 5 Tmax = 10 finished 37 The Extension with Time The values tmin and tmax, tell us the minimum and maximum time that a transition will take to fire once enabled.

This allows us to model performance properties of the system, although the analysis of such systems may be more difficult. free start waiting Tmin = 0 Tmax = 3 finish busy COMP201 - Software Engineering Tmin = 5 Tmax = 10 finished

38 The Extension with Time Question: What is the minimum/maximum time for all three people to have their hair cut in this system? (Harder) Question: What about with n clients and m hairdressers? Is there a general formula for the required time? free start waiting Tmin = 0 Tmax = 3 finish busy COMP201 - Software Engineering

Tmin = 5 Tmax = 10 finished 39 Exercise COMP201 - Software Engineering 40 The Extension with Hierarchy A hierarchy is a mechanism to structure complex Petri nets comparable to Data Flow Diagrams. A subnet is a net composed out of places, transitions and other subnets. This allows us to model a system at different levels of

abstraction and can reduce the complexity of the model. We shall see an example of this on the next slide.. COMP201 - Software Engineering 41 The Extension with Hierarchy h1 h2 waiting ready h3 Here Here we we expand

expand subnet subnet h3.. h3.. free start busy COMP201 - Software Engineering finish 42 Exercise: Remove Hierarchy h1 h2

waiting ready h3 free begin start busy pending end finish begin COMP201 - Software Engineering

pending end 43 Another Example Recall the following example of an informal specification from a critical system [1] : The message must be triplicated. The three copies must be forwarded through three different physical channels. The receiver accepts the message on the basis of a two-out-of-three voting policy. Questions: Can you identify any ambiguities in this specification? How could we model this system with a Petri net? [1] - C. Ghezzi, M. Jazayeri, D. Mandrioli, Fundamentals of Software Engineering, Prentice Hall, Second Edition, page 196 - 198

44 Message Triplication Original Message Tmin = c1 Tmax = k1 Message Copies Tmin = c2 Tmax = k2 P1 Tmin = c3 Tmax = k3 Tvoting1 P2 Tvoting2 COMP201 - Software Engineering

P3 Tvoting3 Tvoting1: P1 = P2 Tvoting2: P1 = P3 Tvoting3: P2 = P3 45 Message Triplication (2) Original Message Tmin = c1 Tmax = k1 Message Copies Tmin = c2 Tmax = k2 P1

Tmin = c3 Tmax = k3 P2 P3 Tvoting Tvoting: (P1 = P2) or (P2 = P3) or (P1 = P3) else ERROR COMP201 - Software Engineering 46 A Final Note on Petri Nets We can see from the previous example that the ambiguity (or impreciseness) in the informal specification for the message triplication protocol is clearly highlighted by the more formal

Petri net model. We can also perform some analysis on the model itself, for example to see if certain bad states ever occur or if deadlock/livelock is possible in the model. Finally we can represent timing constraints (to encode even more constraints on the system) and use hierarchical models to show different levels of abstration. 47 A Final Note on Petri Nets Imagine modelling the elevator system of a skyscraper which contains three elevators and twenty floors. What would be some of the advantages of using a Petri net model for this? We can ensure if someone at a floor pushes the lift button (up or down), the elevator will eventually come. We can attempt to model the timing constraints of the system (Timed Petri net).

We can also use hierarchies to simplify the system. Finally we could try to optimize the model in some way if its performance is not optimal. Etc.. 48 Lecture Key Points Petri nets have Arcs, Places and Transitions. Petri nets are non-deterministic and thus may be used to model discrete distributed systems. They have a well defined semantics and many variations and extensions of Petri nets exist. The state or marking of a net is an assignment of tokens to places. For those interested, the book Fundamentals of Software Engineering (Prentice Hall) by C. Ghezzi, M. Jazayeri and D. Mandrioli has an extensive example of using Petri nets for an elevator system.

COMP201 - Software Engineering 49

Recently Viewed Presentations

  • Mink Dissection - Roderick Anatomy and Physiology

    Mink Dissection - Roderick Anatomy and Physiology

    Scapula. Depresses and rotates scapula *Masseter. Skull. Mandible. Elevates mandible *Temporalis. Skull. Mandible. Elevates and Retracts Mandible ... There will be a quiz over them on Friday. * Will be on the muscle identification portion of the test. Brachioradials .
  • Title: Palatino, TCNJ Blue

    Title: Palatino, TCNJ Blue

    We use their monthly search and full text (FT) download data, from Jan. 2006 to Nov. 2018 (155 months). So we have a total of 155 pairs of search and FT data for each database, except PsycInfo and PsycArticle. The...
  • Sacramento Cal-SOAP Consortium A California Student ...

    Sacramento Cal-SOAP Consortium A California Student ...

    A way to pay for a college education. Government (federal & state) support for college attendance. Institutional (college) support for college attendance
  • Medication-Assisted Treatment for Opiate Use Disorders-Youth and Young

    Medication-Assisted Treatment for Opiate Use Disorders-Youth and Young

    American Psychiatric Association: manual of Clinical Psychopharmacology. American Psychiatric Publishing, Inc. 2010. Practice Guideline for the treatment of patients with substance use disorders, 2nd edition. American Journal of Psychiatry . 2006; 164-suppl A5-A124. Sigmon SC, Dunn KE, et al.
  • Parent & Athlete Meeting

    Parent & Athlete Meeting

    The Spartans have a highly successful booster organization which promote school spirit and pride. The PTSO can help raise money to support transportation costs, replace or upgrade equipment, provide awards/recognition, provide desserts for banquet and other needs that may arise...
  • PowerPoint Template - University of Texas at Austin

    PowerPoint Template - University of Texas at Austin

    A = R x K x LS x C x P . A: average annual potential soil loss ... C factor is a ratio comparing the soil loss from a specific type of vegetation cover. Landcover data of shapefile came...
  • Who are our hypothetical patients?

    Who are our hypothetical patients?

    Is There a Better Way to Reduce Growth in Medicare Spending? National Academy of Social Insurance 17th Annual Conference Washington, D.C. January 28, 2005
  • Experimental Psychology - University of Richmond

    Experimental Psychology - University of Richmond

    Order of APA Paper Sections The order of the sections of the manuscript are as follows: A.Title Page B.Abstract C.Introduction D.Method E.Results F.Discussion G.References H.Other Sections Appendix Tables Figure captions Figures Title Page The title page formally announces the title...