PDF de programación - PROGRAMACION CONCURRENTE Y DISTRIBUIDA - V.1 Redes de Petri: Descripción de sistemas concurrentes

PROGRAMACION CONCURRENTE Y

DISTRIBUIDA

V.1 Redes de Petri: Descripción de sistemas concurrentes.

J.M. Drake

Notas:

1

Redes de Petri

Las redes de Petri (PN) (C.A. Petri, 1962) son una herramienta de
modelado muy efectiva para la representación y el análisis de procesos
concurrentes.
Su éxito se debe básicamente a la simplicidad de su mecanismo básico, si
bien, la representación de grandes sistemas es costosa.
Numerosos autores han extendido el modelo básico:
Redes de Petri Temporizadas o Timed Petri Nets: Introduciendo el concepto

de tiempo, para modelar el comportamiento temporal de los sistemas
dinámicos.

Red de Petri Estocástica (Stochastic Petri Net, SPN): Se especifica el
comportamiento temporal con variables aleatorias exponenciales. Son
isomorficas a las cadenas de Markov. Tienen mayor capacidad que la Teoría
de Colas

Red de Petri Coloreada (CPN): A los testigo se le añade atributos que se

denominan color. Permiten modelar sistemas concurrentes descritos mediante
flujos de datos.

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

2

Notas:

2

Diagramas de estados

Los diagramas de estados es el
método mas usado para analizar
sistemas dinámicos.

Autómatas:
Al pulsar M ambos carros se
desplazan a la derecha. El regreso
lo hacen simultáneamente
cuando ambos carros se
encuentren en el extremo derecho.

l

1

l

2

r
1

r2

T
1

T
2

B

D

M

A

C

C

1

2

5

A

MAC

r 1

r 2,

D

B
l 1

C

4

r 1

,

l 2

7

l1

r 2

3

6

B

D

A

l2

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

3

Notas:

3

Diagramas de estados y sistemas concurrentes

El espacios de estados se hace
muy complejo cuando se tratan
sistemas concurrentes.
- Para N carros: 2N+1-1 estados
- Son pocos flexibles, Cambios de la
especificación implica cambios
drásticos del modelo

Se requieren otros métodos formales,
por ejemplo Redes de Petri

MACE
r1 , r2 , r 3

D

F

1

2

4

r1 , r 3

r1 , r 2

5

B

D

B

F

B

r2 , r 3

3

D F

6

r3

7

r2

8

r1

F

D

B

A C E

9

l1 , l 2 , l 3

A

C

E

10

l2 , l 3

C

E

11

l1 , l 3
E

A

12

l1 , l 2

A

C

13

l3

14

l2

15

l1

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

4

Notas:

4

Redes de Petri

Una red de Petri (RdP) es un grafo
orientado con dos clases de nodos:
lugares (circunferencias) y
transiciones (barras). Los arcos unen
un lugar con una transición o
viceversa.
Un lugar pude contener un número
positivo o nulo de marcas.
Distribución de marcas en los
lugares, marcado → estado de la
RdP.
Se asocian entradas y salidas a
lugares y transiciones p.e.:
salida → lugar marcado
entrada → transición

p1

t 2

p2

p4

t 1

t 4

p3

t 3

p5

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

5

Notas:

5

Evolución de una RdP

Una transición está sensibilizada si todos sus lugares de entrada están
marcados
Transición sensibilizada => puede disparar
Disparo => evolución del estado: Retirada de una marca de cada lugar de
entrada, depósito de una marca en cada lugar de salida

t1

t 2

t1

t 2

t 3

t 3

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

6

Notas:

6

Modelos de los problemas de carros

r1

l1

r2

B

l2

A

D

C

M

2 carros

r
1

l1

r2

B

l2

A

r3

D

l3

C

F

E

M

3 carros

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

7

Notas:

7

Formalización de las RdP

Red de Petri (RdP): es una cuádrupla R = {P, T, α, β} tal que
P es un conjunto finito y no vacío de lugares
T es un conjunto finito y no vacío de transiciones
P ∩T = Ø
α:P x T → N es la función de incidencia previa
β:T x P → N es la función de incidencia posterior

RdP marcada: es un par {R, Mo}, donde R es una RdP y Mo
es un marcado inicial.

Marcado actual: M={m1, m2, m3, ..., mn}
Marcado inicial: Mo={mo1, mo2, mo3, ..., mon}

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

8

Notas:

8

Representación gráfica
Arco de pi a tj ⇔ α(pi,tj) ≠ 0
Arco de tk a pi ⇔ β(tk,pi) ≠ 0
Arcos etiquetados con un peso =

α(pi,tj) ó β(tk,pi)

p1

t 1

t 3

p2

2

2

p3

t 2

p4

Representación matricial
Matriz de incidencia previa: C− =

= [cij

+] donde cij

+ = β(tj,pi)

Matriz de incidencia: C = C+ - C-

[cij

−] donde cij

− = α(pi,tj)

Matriz de incidencia posterior: C+

C

=

p
1
p
2
p
3
p
4

1
−
1
2
0

⎡
⎢
⎢
⎢
⎢
⎣

0
0
1
−
1

1
1
−
0
2
−

⎤
⎥
⎥
⎥
⎥
⎦

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

9

Notas:

9

Representación matricial de una red de Petri

C+

Matriz incidencia posterior

C-

Matriz incidencia previa

10000
01001
00001
00010
00100

00001
00010
00100
11000
10000

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦

C=C+-C-

Matriz incidencia

1
−
1
1
0
0

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣

0
1
−
0
1
0

0
0
1
−
0
1

0
1
0
1
−
0

1
⎤
⎥
0
⎥
0
⎥
⎥
1
−
⎥
⎥
1
−
⎦

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

10

Notas:

10

Cálculo de la evolución con RdP

M

=+1

i

M

i

+

CU

1U

=

1M

=

1
⎡
⎢
0
⎢
0
⎢
⎢
0
⎢
⎢
0
⎣

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦

+

1
−
1
1
0
0

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣

0
1
−
0
1
0

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

Notas:

1
0
0
0
0

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦

0
0
1
−
0
1

Se dispara t1

0
1
0
1
−
0

1
⎤
⎥
0
⎥
0
⎥
⎥
1
−
⎥
⎥
1
−
⎦

1
⎡
⎢
0
⎢
0
⎢
⎢
0
⎢
⎢
0
⎣

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦

0
⎡
⎢
1
⎢
1
⎢
⎢
0
⎢
⎢
0
⎣

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦

=

11

11

Clasificación de RdP

• RdP ordinaria: sus funciones de incidencia sólo pueden tomar los valores 0 y 1:

α(p,t) ∈ {0,1}, β(t,p) ∈ {0,1}

Grafo de Estados (GE): ∀t∈T |•t| = 1 y |t•| = 1
Toda transición tiene una unica plaza de entrada y una única plaza
de salida

Grafo Marcado (GM): ∀p∈P |•p| = 1 y |p•| = 1
Todo lugar tiene como máximo una transición de entrada y
una transición de salida

RdP Libre Elección (RLE): ∀p∈P, |p•| > 1 => ∀tk∈p•, |•tk| = 1
Si ti y tj tienen una plaza de entrada común, esta es la única plaza
de ambas transiciones.

RdP Simple (RS):
Cualquier transición tiene como máximo una única plaza de
entrada compartida con otras transiciones.

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

12

Notas:

12

Clasificación RdP

RdP generalizada (RdPG): las funciones de incidencia pueden tomar valores en todos
los números naturales => arcos con peso

RdP Generalizada

GE

GM

RLE

RS

RdP Ordinaria

RdP binaria: M(p) ≤1 ∀p∈P

t1 habilitada

t1 no habilitada

RdP con arcos inhibidores:

t1

t1

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

13

Notas:

13

Modelo de representación

Entradas:

(eventos discretos, condiciones lógicas externas),

Salidas: (eventos discretos, salidas a nivel),
Código asociado a las transiciones.

Acc. impulsionales asociadas a transiciones

=> disparo instantáneo

Código/actividades en transiciones

=> disparo no instantáneo

----
----
---- w
----
----

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

a b c

set(s)

a b c

a
b
c
evento

señal
s

a
b
c

14

Notas:

14

Modos fundamentales
Ejecución secuencial

Ejecución concurrente

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

15

Notas:

15

Modelo de Productor-Consumidor

P1: Dispuesto a producir
T1: Produce elemento
P2: Dispuesto a entregar
T2: Entrega elemento
P3: Dispuesto a recibir
T3: Recibe elemento
P4: Dispuesto a consumir
T4: Consume elemento
P5: Buffer

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

16

Notas:

16

Modelo Productor-Consumidor con buffer limitado

P1: Dispuesto a producir
T1: Produce elemento
P2: Dispuesto a entregar
T2: Entrega elemento
P3: Dispuesto a recibir
T3: Recibe elemento
P4: Dispuesto a consumir
T4: Consume elemento
P5: Elementos transferidos
P6: Huecos disponibles

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

17

Notas:

17

Modelo Productor-Consumidor: 2 prod.x2 cons.

Productor 1

Productor 2

Consumidor 1

Consumidor 2

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

18

Notas:

18

Exclusión mútua

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

19

Notas:

19

Exclusión mutua con prioridad

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

20

Notas:

20

Filósofos chinos

Piensa

Come

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

21

Notas:

21

Ejemplo modelado: Carros con vía común

MA

L

A

BM

L

B

l
A
A

r
A
W
A
WB

Bl

Br

B

G

M U

U

Dos carros A y B transportan cierto material desde los puntos de carga LA y LB,
respectivamente, hasta el punto de descarga D. Los diferentes movimientos son
controlados mediante las señales lA, lB, rA, rB. Si A está en LA y el pulsador MA
está oprimido, comienza un ciclo LA-U-LA:

- Espera eventual en WA hasta que la zona común a los dos carros esté libre, con el fin
de evitar colisiones;
- Espera obligatoria en U hasta MU (pulsador de fin de descarga).

El carro B tiene un funcionamiento similar pero, en caso de demanda simultánea de la vía
común, B es prioritario. El recorrido WA-U o WB-U se establece por un cambio de agujas
controlado por la acción G.

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

22

Notas:

22

RdP: Carros con vía común

Transiciones => entradas de sensores

Lugares => señales de salida

MA

L
A

BM

L

B

l
A
A

r
A
W
A
WB

Bl

Br

B

G

MU

U

3

1

14

MA
Ar

WA

4

W B
Ar
,G

U

G
MU
, G

A

12

l
W
A

6

8

10

Al
L

A

M B
Br

BW

2

15

5

Br

U

7

9

MU

11

Bl

W

B

13

l

B

L

B

Procodis’08: V.1- Descripción por redes de Petri

José M.Drake

23

Notas:

23

Ejemplo modelo: Lectores y escritores

Dos conjuntos de usuarios (lectores y redactores) tienen que
coordinarse para acceder a unos datos comunes:
los lectores sólo inspeccionan, y por lo tanto pueden acceder

simultáneamente a los datos

los redactores actualizan los datos y su trabajo