INTRODUCTION TO THE NETS OF PETRI.

We should define to the nets of Petri previously what are the concurrent processes and their problems to be able to understand and to specify a net of Petri later on, the requirements that it should complete and their operation.

CONCURRENT PROCESSES.

They are the processes rushed in processors with multiple functional or multiple units CPU's. They can execute several instructions at the same time, also the hardware pennite the existence of several processes and the processor can commute among them and to execute instructions of several processes jumping among them.
Instructions exist in the concurrent programming of high level, so that a process denominated father it believes one or several processes denominated processes son. The inconvenience of the concurrent processes is that they make operations on common variables. This generates several problems that we can observe in the examples.

Example: Launching of five concurrent processes that they consist of a single instruction.

cobegin

P1: a:=4;
P2: b:=3;
P3: d:=a-b;
P4: d:=d+1;
P5: d:=d+1;

coend

These five processes share the variables to, b and d. If we suppose that the order of the execution is the one described, the value of d is d=3. Evidently we cannot presuppose any order in the execution. Let us suppose the following succession of events:

Initially   {a=?, b=?, d=?}
     
P3: d:=a-b;   {a=?, b=?, d=?}
Pl: a:=4;   {a=4, b=?, d=?}
P2: b:=3;   {a=4, b=3, d=?}
P4: d:=d+l;   {a=4, b=3, d=?}
P5: d:=d+l;   {a=4, b=3, d=?}

When concluding the processes we ignore the value of d. This happens because the precedence has not been respected in the execution of the processes. We will suppose that the sentence "d:=d+1" is executed by means of three instructions independent machine:

registroCPU:=d;
registroCPU:=registroCPU+ 1;
d:=registroCPU;

Let us suppose the following succession now of events:

Inicialmente   {a=?, b=?, d=?}
     
P2: b:=3;   {a=?, b=3, d=?}
Pl: a:=4;   {a=4, b=3, d=?}
P3: d:=a-b;   {a=4, b=3, d=l}
P4: registroCPU:=d;   {a=4, b=3, d=l}
P4: registroCPU:=registroCPU+ 1;   {a=4, b=3, d=l}
P5: registroCPU:=d;   {a=4, b=3, d=l}
P5: registroCPU: =registroCPU+ 1;   {a=4, b=3, d=l}
P5: d:=registroCPU;   {a=4, b=3, d=2}
P4: d:=registroCPU;   {a=4, b=3, d=2}

It is observed that the process P4 has been interrupted while it operated on d. The increments in d that should have had as a result d=3 has given d=2.

To the resource to the one that several concurrent processes can consent at the same time it is denominated critical section.

We have observed two errors in the example:

The solution to the synchronization problems and exclusion mutual they can be solved by means of the tool traffic light. A traffic light S is a whole variable that later on to its initialization, it can only be consented by two operations standard and indivisible denominated P and V.

The classic definition of P and V are:

P(S): if S>0 then S:=S-l
  else Skip; /* espera activa */
V(S): if (hay procesos en cola) then liberar el primero
  else S:=S+l;

If we suppose binary traffic lights, traffic lights that alone they can to take the value 0 or 1, and the processes attendee are in the way:

Pl:

P(S1);
a:=4;
V(S3);

P2:

P(S2);
b:=3;
V(S4);

P3:

P(S3);
P(S4);
d:=a-b;
V(S5);

P4:

P(S5);
d:=d+ 1;
V(S6);

P5:

P(S6);
d:=d+l;

Initialization of the traffic lights and launching of those concurrent processes:

begin

S1:=1;
S2:=1;
S3:=0;
S4:=0;
S5:=0;

cobegin

Pl;
P2;
P3;
P4;
P5;

coend;

end

The mathematical modelización that bear the processes concurrent, the precedence problems and the problems of mutual exclusion on sections criticizes they are solved by means of the use of Nets of Petri that next we describe.

DEFINITION OF THE NETS OF PETRI.

Generalities:

The nets of Petri are used for modelizar the one dynamic behavior of discreet systems.

They are composed of two types of objects:

The squares that allow to represent the states of the one system by means of the use of marks.
The transitions that represent the group of actions to carry out when some certain ones are completed precondiciones in the system.
By means of a net of Petri it can modelate a system of evolution in parallel made up of several processes that they cooperate for the realization of a common objective.

In general, the presence of marks in a square is interpreted as the presence of resources. The postage of a transition (the action to execute) it is carried out when some are completed determined precondiciones, indicated by the marks in those squares (there is an enough quantity of resources), and the transition (execution of the action) it generates some postcondiciones that modify the marks of other squares (you they liberate the resources) and the postage is allowed this way of later transitions.

Definition: A net of Petri it is a group formed by R={P, T, Pre, Post}

P: Group of squares of cardinal n.
T: Group of transitions of cardinal m.

Pre: Application of previous incidence. It comes defined as:
Pre:PxT--> Natural
Post: Application of later incidence. It comes defined as:
Post:PxT--> Natural

Definition: A marked net is the one group formed for {R, M} where:

R is a Net of Petri like the defined one.
M is a marked denominated application.
M: P--> Natural
It associates to each square a number natural, denominated mark. Those marks for a square meet in columns.

For the applications Pre and Post a notación it exists matricial.

Example: Be a net of Petri with five squares (1 ..5) and five transitions (to ..e) that will denominate R1.

Pre a b c d e   Post a b c d e
1 1 0 0 0 0   1 0 0 0 1 0
2 0 1 0 0 0   2 1 0 0 0 0
3 0 0 1 0 0   3 1 0 0 0 1
4 0 0 0 1 0   4 0 1 0 0 0
5 0 0 0 1 1   5 0 0 1 0 0

The columns are denoted by Pre (., t), and the lines are denoted for Post (., p).

Number of marks associated to the squares. M0 the one marked defined for. The marks for all the squares meet for columns:

M0
1
0
0
0
0

Definition: The condition so that one net is degenerate it is that some line or column of those applications Pre or Post it is zero.

Definition: A net is pure if it completes the following Pre(p,t) * Post(p,t) = 0 (for all p and t).

Definition: Grafo associated to a net: A net of Petri has a bipartite guided grafo that you it defines as:
P union T that is the group of vertexes.
F: P union T--> you Leave of (P union T) that is the group of arches.

The grafo {P, T, F, V} associated to the net R = {P, T, Pre, Post) it is:

F(p)={t belongs to T if Pre(p,t)>0, for all p}
F(t)={p petenece to T if Post(p,t)>0, for all t}
V(p,t)=Pre(p,t)
V(t,p)=Post(p,t)

V is the valuation of the arches.

The definition of the grafo indicates that the alone arches can go:

From the squares until the transitions.
From the transitions to the squares.

REPRESENTATION OF THE NET.

In the representation of a net of Petri, the arches are omitted valued with 0, and the 1 in the arches valued with 1.
The squares are represented by means of circles, the transitions by means of horizontal rectangles or you line horizontal, and those marks by means of points inside the squares.

Example: Representation like grafo of the net of Petri, R1.

F(1)={a}
F(2) = {B}
F(3) = {C}
F(4)={d}
F(5) = {D,E}

F(a)={2,3}
F(b)={4}
F(c)={5}
F(d)={1}
F(e)={3}

OPERATION OF THE NET.

Definition: A transition t it is franqueable if for a marked M it is completed:

M(p) >= Pre(p,t); (for all p)

This is indicated with the notación M(t >... and it is the postage precondición.
It means that the marked one allows the postage of the transition t.
If a transition t is franqueable for M, the postage defines a new marked M'.
This new marked is defined as:

M'(t) = M(p) - Pre(p,t) + Post(p,t) (for all p)

M' is deduced from M and M(t >M is denoted ' (M gives M' for t).
For a net, t is franqueable for M if the squares entrance p of t they have a number of marks superior to that of the arch (p,t). You V(p,t eliminates) you mark of each entrance square t and they are added V(t,p) you mark to each exit square t.

It is observed that,

M >= Pre (., t) and M(t >M ' = > M' >= Post (. ,t)

The marked minimum that allows the postage of t is Pre(p,t).
The marked minimum that one obtains of the postage of t is Post(p,t).

Example: Operation of the net of Petri, R1:

And the successive ones marked that are obtained they are:

M0   M1   M2   M3   M4
1   0   0   0   0
0   1   0   1   0
0   1   1   0   0
0   0   1   0   1
0   0   0   1   1

Given the previous example is observed that:

M0(to > it means that the transition to it is franqueable for the marked M0.
M0(a>M1 it means that the transition to it is franqueable for the marked M0 and it gives the marked M1.
The transition b is not franqueable for the marked M0.

At this time one can observe the similarity with those concurrent processes:

The squares are the traffic lights.
The marks the integer that initializes to the traffic light and their later one evolution..
The transitions are the code of a section it criticizes that it uses the concurrent processes.
The entrance to the sections criticizes it is governed by those traffic lights.

Example: Implementation of the net of Petri, R1, using traffic lights. It can break down in five processes concurrent:

P1:

P(semáforo1);
/* transición a */
V(semáforo2);
V(semáforo3);

P2:

P(semáforo3);
/* transición c */
V(semáforo5);

P3:

P(semáforo4);
P(semáforo5);
/* transición e */
V(semáforo1);

P4:

P(semáforo2);
/* transición b */
V(semáforo4);

P5:

P(semáforo4);
/* transición d */
V(semáforo2);

Initialization of the traffic lights and launching of those concurrent processes:

begin

semáforo1:=1;
semáforo2:=0;
semáforo3:=0;
semáforo4:=0;
semáforo5:=0;

cobegin

P1;
P2;
P3;
P4;
P5;

 

coend;

end

Definition: Two transitions t1 and t2 they are in structural conflict if, a p exists, such that, Post(p, t1) * Post(p, t2) be different from 0.

If they have a square at least of having entered in common.

Definition: Two transitions are in effective conflict for a marked M if besides being completed, M(t1>, M(t2> and it exists a such p that M(p) < Pre(p, t1) + Pre(p,t2)

An effective conflict consists on an election among postages.

APPLICATION PRACTICES.

Problem of those philosophers: (Dijkstra 1965, problem 5.13 of Operating systems, H. M. Deitel)

Five philosophers are seated around a table to circulate. The five take a very simple life, they alternate between to think and to eat. In front of each philosopher there is a plate of eat that a servant maintains full the whole time. There is exactly five forks in the table, one among each couple of adjacent philosophers. To eat each philosopher it should use simultaneously the two adjacent forks to their plate.

The modelización of the applications Pre and Post they are:

Pre a b c d e   Post a b c d e
1 1 0 0 0 0   1 1 0 0 0 0
2 1 1 0 0 0   2 1 1 0 0 0
3 0 1 1 0 0   3 0 1 1 0 0
4 0 0 1 1 0   4 0 0 1 1 0
5 0 0 0 1 1   5 0 0 0 1 1

The marked initial is:

M0
1
1
1
1
1

The grafo associated to the net is:

Comments to the net of the problem of the philosophers:

The net is not degenerate, according to the definition there is not none line or column of the applications Pre or Post similar to 0.

The net is not pure, it exists squares and transitions such a that Pre(p,t) * Post(p,t) different from 0. Example, Pre(1,a) * Post(1,a)<>0.

The net contains a structural conflict, squares exist such a that Post(p,t1) *Post(p,t2) <>0. Example, Post(2,a) * Post(2,b)<>0.

The net contains an effective, given conflict the marked M0, all the transitions are franqueables.

In fact, M0 (any transicion>M0. This means that given the marked M0 there is that to decide that transition is executed.

Modelización of the net of Petri obtained with processes concurrent:

Observation: it should be kept in mind that in the pattern theoretical, the one erased of the marks it is simultaneous and instantaneous but when modeling it like concurrent process exists the possibility of a mortal hug for what has been opted for the code for an asymmetric model in the process that models the one a philosopher's behavior.

The concurrent processes are:

Pa:

P(S2);
P(S1);
/* el filósofo a come */
V(S1);
V(S2);

Pb:

P(S2);
P(S3);
/* el filósofo b come */
V(S3);
V(S2);

Pc:

P(S4);
P(S3);
/* el filósofo c come */
V(S3);
V(S4);

Pd:

P(S4);
P(S5);
/* el filósofo d come */
V(S5);
V(S4);

Pe:

P(S1);
P(S5);
/* el filósofo e come */
V(S5);
V(S1);

Initialization of the traffic lights and launching of those concurrent processes:

begin

S1:=1;
S2:=1;
S3:=1;
S4:=1;
S5:=1;

cobegin

Pa;
Pb;
Pc;
Pd;
Pe;

coend;

end

Problem of the smokers of cigarettes: (Patil 1971, problem 5.19 of Operating Systems, H. M. Deitel)

Three smokers are represented by the processes F1, F3 and F3. Three salespersons are represented by the processes V1, V2 AND V3. For fumarc each smoker needs tobacco, paper for tobacco and a match; when it has these resources, the smoker smokes a cigarette until finishing it and then it is eligible for to smoke again. F1 has tobacco, F2 has paper and F3 has matches. V1 sells tobacco and paper, V2 sells paper for tobacco and matches, and V3 sells matches and tobacco. V1, V3 and V3 work in mutual exclusion; one of the processes can only work to the time and the following salesperson cannot work until those resources given by the previous salesperson have been consumed by a smoker.

The modelización of the applications Pre and Post they are:

Pre V1 V2 V3 F1 F2 F3   Post V1 V2 V3 F1 F2 F3
1 1 1 1 0 0 0   1 0 0 0 1 1 1
2 0 0 0 0 0 1   2 1 0 0 0 0 0
3 0 0 0 1 0 0   3 0 1 0 0 0 0
4 0 0 0 0 1 0   4 0 0 1 0 0 0

The marked initial is:

M0
1
0
0
0

The grafo associated to the net is:

Comments to the net of the problem of the smokers:

The net is not degenerate, according to the definition there is not none line or column of the applications Pre or Post similar to 0.

The net is pure, Pre(p,t) * Post(p,t)<>0 for all p and t.

The net contains a structural conflict in the square 1, Post(1,V1) * Post(1,V2)<>0.

The net contains an effective, given conflict the marked M0, M0(V1> AND M0(V2> also for the square 2, M(2)<Pre(2,V1) + Pre(2,V2). This means that given the marked M0 it is necessary to decide that transition is executed.

Model of the net of Petri obtained with concurrent processes:

Observation: it should be kept in mind the structural conflict spirit in the net, in the real processes, the decision you it solves in time of execution, the first process will be executed that it carries out the operation V on the traffic light.

The concurrent processes are like it is described to continuation:

P_V1:

P(S1);
/* V1 vende tabaco y papel */
V(S2);

P_V2:

P(S1);
/* V2 vende papel y fósforos */
V(S3);

P_V3:

P(S1);
/* V3 vende fósforos y tabaco */
V(S4);

P_F1:

P(S3);
/* F1 tiene tabaco ha comprado papel y fósforos a V2, puede fumar en exclusión mutua */
V(S1);

P_F2:

P(S4);
/* F2 tiene papel ha comprado fósforos y tabaco a V3, puede fumar en exclusión mutua */
V(S1);

P_F3:

P(S2);
/* F3 tiene fósforos ha comprado papel y tabaco a V1, puede fumar en exclusión mutua */
V(S1);

Initialization of the traffic lights and launching of those concurrent processes:

begin

S1:=1;
S2:=0;
S3:=0;
S4:=0;

cobegin

P_V1;
P_V2;
P_V3;
P_F1;
P_F2;
P_F3;

coend;

end

BIBLIOGRAPHY.

| Web PEMH | Top of page | pedrmar@mixmail.com |

This page has been visited, Contador de visitas. times.

The same author's pages web:

 

Producido por PEMH.It dates of the last one bring up to date: 11 enero, 2001.