1. PETRI NETS

Petri-Sim

by Hugh Jack

The University of Western Ontario

August, 11th, 1991.

1.0 INTRODUCTION:

Petri nets are useful tools for modelling systems with control flow. In particular they aid in modelling systems with concurrency, and parallelism. A set of routines have been developed at UWO to serve as the basis for a manufacturing simulation. The routines will support a number of various Petri net functions. The basic operation of the Petri net may be simulated. As well the EOR transitions will also be modelled. An attempt has been made to add ‘colors’ to the tokens, but at the present there is insufficient information (i.e., no references) to verify the implementation.

The routines have been written in a user friendly way to allow simple application interface. Places and Transitions are specified with textual names. A brief theory of petri nets follows.

2.0 A BRIEF OUTLINE OF PETRI NET THEORY:

There are four basic elements in a petri net; places, transitions, arcs, and tokens. If we are to think in terms of a factory, tokens are equivalent to work parts. Arcs are the paths the work will follow through the factory. Places are buffers where parts are stored temporarily, and transitions are equivalent to machines where the parts are used to make new parts.

The basic operation is that tokens are introduced to the network, and then transitions are fired in different orders, and thus tokens are created and destroyed at the transitions. The example below follows the petri net for a few cycles. The first figure shows the Petri Net with the initial markings.

The reader should note that there are a few interesting properties found in Petri nets.

• Transitions are fired when all of their inputs are satisfied, and the user specifies that transition.

• Most analysis of petri nets uses random firings of the transitions to obtain statistical performance.

Other basic references to the petri net theory are available in Peterson [1981] and Reisig [1985].

3.0 USING THE SUBROUTINES:

3.1 Basic Petri Net Simulation:

The subroutines are applied in a methodical manner. Before the user can integrate the subroutines into their program, they must draw out the petri net, and label all places and transitions. The example given above is illustrated below.

After these labels are determined, they are defined using the petri net subroutines. The arcs in the petri net are also defined in the program. There are defined with respect to the transitions. That is to say that an arc is an input to, or output from a transition. After the petri net structure has been defined, tokens may be placed in the places of the net. The tokens are as given in the previous example.

The transitions are then selectively fired in the net, by function calls in the program. This program also has calls to functions which print the petri net structure after each transition. The code is show below for the example above.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include “global.h”

#include “petri.h”

int test1()

/*

* BASIC TEST NET (Peterson book, 1981, pg. 19)

*/

{

static int error;

static struct petri_net net;

static int p1, p2, p3, p4, p5;

static int t1, t2, t3, t4;

error = petri_init(&net);

p1 = petri_place(&net, “p1”);

p2 = petri_place(&net, “p2”);

p3 = petri_place(&net, “p3”);

p4 = petri_place(&net, “p4”);

p5 = petri_place(&net, “p5”);

t1 = petri_transition(&net, “t1”);

t2 = petri_transition(&net, “t2”);

t3 = petri_transition(&net, “t3”);

t4 = petri_transition(&net, “t4”);

petri_input(&net, p1, t1, 1);

petri_input(&net, p2, t2, 1);

petri_input(&net, p3, t2, 1);

petri_input(&net, p4, t2, 1);

petri_input(&net, p4, t3, 1);

petri_input(&net, p4, t3, 1);

petri_input(&net, p5, t4, 1);

petri_output(&net, p2, t1, 1);

petri_output(&net, p3, t1, 1);

petri_output(&net, p4, t1, 1);

petri_output(&net, p4, t1, 1);

petri_output(&net, p2, t2, 1);

petri_output(&net, p5, t3, 1);

petri_output(&net, p3, t4, 1);

petri_output(&net, p4, t4, 1);

petri_add_tokens(&net, p1, 1);

petri_add_tokens(&net, p4, 2);

petri_add_tokens(&net, p5, 1);

petri_print(&net);

petri_event(&net, t4);

petri_print(&net);

petri_event(&net, t1);

petri_print(&net);

petri_event(&net, t3);

petri_print(&net);

return error;

}

As can be seen this method of implementation is very simple. The user is able to define a number of nets, and refer to transitions and places by name.

3.2 Transitions With Inhibiting Inputs:

In some cases we want to prevent a transition from firing. To do this, the idea of inhibiting inputs has been proposed. If a transition has an inhibiting input from a place, that has any tokens in it, then the transition cannot fire. Otherwise the transition may fire normally. A sample net has been devised for this case, it is seen below.

The program below shows that the inhibiting input is simply defined when the arc is defined.

int test2()

/*

* INHIBITED TEST NET (Peterson book, 1981, pg. 196)

*/

{

static int error;

static struct petri_net net;

static int p1, p2, p3, p4, p5, p6;

static int t1, t2, t3, t4;

error = petri_init(&net);

p1 = petri_place(&net, “p1”);

p2 = petri_place(&net, “p2”);

p3 = petri_place(&net, “p3”);

p4 = petri_place(&net, “p4”);

p5 = petri_place(&net, “p5”);

p6 = petri_place(&net, “p6”);

t1 = petri_transition(&net, “t1”);

t2 = petri_transition(&net, “t2”);

t3 = petri_transition(&net, “t3”);

t4 = petri_transition(&net, “t4”);

petri_input(&net, p1, t1, 1);

petri_input(&net, p2, t2, 1);

petri_input(&net, p3, t2, 1);

petri_input(&net, p5, t3, 1);

petri_input(&net, p3, t4, INHIBIT);

petri_input(&net, p4, t4, 1);

petri_input(&net, p6, t4, 1);

petri_output(&net, p1, t1, 1);

petri_output(&net, p3, t1, 1);

petri_output(&net, p2, t2, 1);

petri_output(&net, p4, t3, 1);

petri_output(&net, p5, t3, 1);

petri_output(&net, p6, t4, 1);

petri_add_tokens(&net, p1, 1);

petri_add_tokens(&net, p2, 1);

petri_add_tokens(&net, p5, 1);

petri_add_tokens(&net, p6, 1);

petri_print(&net);

petri_event(&net, t1);

petri_print(&net);

petri_event(&net, t3);

petri_print(&net);

petri_event(&net, t4);

petri_print(&net);

petri_event(&net, t2);

petri_print(&net);

petri_event(&net, t4);

petri_print(&net);

return error;

}

3.3 An Exclusive OR Transition:

The inhibitory inputs are complimentary to the exclusive or function. Thus another research proposed an Exclusive or transition which will fire when one (and only one) input is from a place with tokens. An example of a problem using this, a ring shift register was modelled. This net is modelled as shown below.

In this example the EOR transition is marked with a plus in a circle (at ‘t7’). When run, a token will appear in p1, p3, and p5 in a repeating cycle. The program to set this up is seen below.

int test3()

/*

* EOR TEST NET (Peterson book, 1981, discussed pg. 190)

* This is for a single bit shifter

*/

{

static int error;

static struct petri_net net;

static int p1, p2, p3, p4, p5, p6, p7, p8, p9, p10;

static int t1, t2, t3, t4, t5, t6, t7;

error = petri_init(&net);

p1 = petri_place(&net, “p1”);

p2 = petri_place(&net, “p2”);

p3 = petri_place(&net, “p3”);

p4 = petri_place(&net, “p4”);

p5 = petri_place(&net, “p5”);

p6 = petri_place(&net, “p6”);

p7 = petri_place(&net, “p7”);

p8 = petri_place(&net, “p8”);

p9 = petri_place(&net, “p9”);

p10 = petri_place(&net, “p10”);

t1 = petri_transition(&net, “t1”);

t2 = petri_transition(&net, “t2”);

t3 = petri_transition(&net, “t3”);

t4 = petri_transition(&net, “t4”);

t5 = petri_transition(&net, “t5”);

t6 = petri_transition(&net, “t6”);

t7 = petri_transition(&net, “t7”);

petri_input(&net, p6, t1, 1);

petri_input(&net, p7, t1, 1);

petri_input(&net, p2, t2, 1);

petri_input(&net, p7, t2, 1);

petri_input(&net, p4, t3, 1);

petri_input(&net, p7, t3, 1);

petri_input(&net, p1, t4, 1);

petri_input(&net, p3, t5, 1);

petri_input(&net, p5, t6, 1);

petri_input(&net, p8, t7, 1);

petri_input(&net, p9, t7, 1);

petri_input(&net, p10, t7, 1);

petri_output(&net, p1, t1, 1);

petri_output(&net, p3, t2, 1);

petri_output(&net, p5, t3, 1);

petri_output(&net, p2, t4, 1);

petri_output(&net, p8, t4, 1);

petri_output(&net, p4, t5, 1);

petri_output(&net, p9, t5, 1);

petri_output(&net, p6, t6, 1);

petri_output(&net, p10, t6, 1);

petri_output(&net, p7, t7, 1);

petri_type_transition(&net, t7, EOR);

petri_add_tokens(&net, p1, 1);

petri_print(&net);

petri_event(&net, t4);

petri_print(&net);

petri_event(&net, t7);

petri_print(&net);

petri_event(&net, t2);

petri_print(&net);

petri_event(&net, t5);

petri_print(&net);

petri_event(&net, t7);

petri_print(&net);

petri_event(&net, t3);

petri_print(&net);

petri_event(&net, t6);

petri_print(&net);

petri_event(&net, t7);

petri_print(&net);

return error;

}

3.4 Colored Tokens:

This section should be considered incorrect. The theory has not been found, although the approach should adhere to the concept. The concept is that each token may now have a color, and a second bit of private information. If a transition is specified to be colored, it will only fire if tokens of the specified color are available at the inputs. The subroutines will then require that the user supply a new set of instance information so that new tokens may be issued.

The net used has tokens of mixed colors in it, an is seen below.

The code is shown below. The reader should note that a second subroutine is used. This is done because there is a bit of code which would be repeated for each update of tokens at the transition.

int test4()

/*

* COLOR TEST NET (Assumed for now)

* Two consumers of different colors and one input. The instances of tokens

* are kept track of.

*/

{

static int error, i;

static struct petri_net net;

static int p1, p2, p3;

static int t1, t2;

static int color1 = 1, color2 = 2;

static int instance[20], instance_pnt;

error = petri_init(&net);

p1 = petri_place(&net, “p1”);

p2 = petri_place(&net, “p2”);

p3 = petri_place(&net, “p3”);

t1 = petri_transition(&net, “t1”);

t2 = petri_transition(&net, “t2”);

petri_input(&net, p1, t1, 1);

petri_input(&net, p3, t1, 1);

petri_input(&net, p2, t2, 1);

petri_input(&net, p3, t2, 1);

petri_output(&net, p1, t1, 1);

petri_output(&net, p2, t2, 1);

petri_type_transition(&net, t1, COLORED);

petri_type_transition(&net, t2, COLORED);

for(i = 0; i < 20; i++) instance[i] = i;

instance_pnt = 0;

petri_add_color_token(&net, p1, color1, instance[instance_pnt]);

instance_pnt++;

petri_add_color_token(&net, p2, color2, instance[instance_pnt]);

instance_pnt++;

petri_add_color_token(&net, p3, color1, instance[instance_pnt]);

instance_pnt++;

petri_add_color_token(&net, p3, color2, instance[instance_pnt]);

instance_pnt++;

petri_print(&net);

sub4(&net, t2, color1, instance, &instance_pnt);

petri_print(&net);

sub4(&net, t1, color1, instance, &instance_pnt);

petri_print(&net);

sub4(&net, t1, color1, instance, &instance_pnt);

petri_print(&net);

sub4(&net, t2, color2, instance, &instance_pnt);

petri_print(&net);

return error;

}

int sub4(net, transition, color, instance, instance_pnt)

struct petri_net *net;

int transition, color, *instance, *instance_pnt;

{

static int error, i, list[20], n, outputs;

error = ERROR;

if(petri_in_event(net, transition, color) == NO_ERROR){

if(petri_get_consumed(net, transition, &color, list, &n, &outputs) == NO_ERROR){

for(i = 0; i <= n; i++) instance[list[i]] = -1000;

if(petri_set_produced(net, transition, &(instance[*instance_pnt]),outputs) == NO_ERROR){

*instance_pnt += outputs;

error = petri_out_event(net, transition);

}

}

}

return error;

}

3.5 RELATIONAL NETS

Relational nets will use various firing rules for each transition. This is by far the most useful for varied manufacturing conditions. An example is seen below.

This may be seen in the fifth test subroutine in the program.

4.0 SOFTWARE:

At present there is one data structure used which holds structures for Places and for Transitions. Arc information is stored (redundantly) in both. These are defined when a Place or Transition number is requested for one that does not exist. Each place and transition have reference numbers, which are used by all other net functions.

The software is still undergoing development, and testing, thus a list of functions would be premature.

5.0 REFERENCES:

Peterson, J.L., “Petri Net Theory and the Modelling of Systems”, Prentice-Hall, Inc., N.J., U.S.A., 1981.

Reisig, W., “Petri Nets; An Introduction”, Springer-Verlag, 1985.