Redes de Petri - Introducción
Dr Chris Ling
School of Computer Science & Software
Engineering
Monash University
(Traducido por Cesáreo Raimúndez)
[email protected]
Introducción
 Desarrolladas por Carl Adam Petri en 1962.
 Herramienta gráfica para modelar concurrencia y
sincronización en sistemas distribuidos.
 Muy similar a los Diagramas de Transición de
Estados.
 Utilizado como método de descripción visual del
comportamiento de sistemas dinámicos.
 Bases teóricas matematicamente sólidas.
(C) Copyright 2001, Chris Ling
Especificación de una RdP
 Es formada de tres tipos de componentes:
plazas (círculos), transiciones (rectángulos)
y arcos (flechas):
– Las Plazas representan los estados posibles del
sistema;
– Las Transiciones son eventos o acciones que
causan el cambio de estado;
– Cada Arco conecta una Plaza con una
Transicion o una Transición con una Plaza.
(C) Copyright 2001, Chris Ling
El Cambio de Estado …
 Se indica por el movimiento de marca(s)
(puntos negros) de plaza(s) a plaza(s); es
causado por el disparo de una transicion.
 El disparo representa un evento ocurrido o
una acción tomada.
 El disparo está supeditado a las condiciones
de entrada, denominada como
disponibilidad de marcado.
(C) Copyright 2001, Chris Ling
El Cambio de Estado
 Una transición es disparable o está
habilitada cuando hay marcas suficientes en
las plazas que llegan a la transición.
 Después del disparo, las marcas se
transferirán de las plazas de entrada
(estados viejos) para las plazas de salida,
que denotan los estados nuevos.
(C) Copyright 2001, Chris Ling
Ejemplo: Máquina Expendedora
 La máquina expende dos tipos de productos
que cuestan – 20c y 15c respectivamente.
 Apenas se pueden utilizar dos tipos de
monedas:
– 10c y 5c.
 La máquina no devuelve cambio.
(C) Copyright 2001, Chris Ling
Ejemplo: Máquina Expendedora (MEF)
Retira producto 15c
5 cents
Deposita 10c
15 cents
0 cent
10 cents
Deposita 10c
Retira producto 20c
(C) Copyright 2001, Chris Ling
20 cents
Ejemplo: Máquina Expendedora (Red de Petri)
Retira prod.15c
Dep. 10c
5c
15c
Dep. 5c
Dep. 5c
0c
Dep. 10c
Dep. 5c
Dep. 5c
20c
10c
Dep. 10c
Retira prod. 20c
(C) Copyright 2001, Chris Ling
Ejemplo: Máquina Expendedora (3 Casos)
 Caso 1:
– Deposita 5c, deposita 5c, deposita 5c, deposita 5c,
compra producto de 20c.
 Caso 2:
– Deposita 10c, deposita 5c, compra producto de 15c.
 Caso 3:
– Deposita 5c, deposita 10c, deposita 5c, compra
producto de 20c.
(C) Copyright 2001, Chris Ling
Ejemplo: Máquina Expendedora (Evolución)
Compra 15c
Dep. 10c
5c
15c
Dep. 5c
Dep. 5c
0c
Dep. 10c
Dep. 5c
Dep. 5c
20c
10c
Dep. 10c
Compra 20c
(C) Copyright 2001, Chris Ling
Simultaneidad de Evolución de Estados
 En el mundo real, los eventos ocurren
simultaneamente.
 Un sistema puede poseer muchos estados
locales constituyendo un estado global.
 Hay necesidad de modelar la concurrencia y
la sincronización.
(C) Copyright 2001, Chris Ling
Ejemplo: En un Restaurante (RdP)
Camarero
libre
Cliente 1
Cliente 2
Toma
pedido
Toma
pedido
espera
espera
Pedido
realizado
comiendo
comiendo
Plato servido
(C) Copyright 2001, Chris Ling
Pedido al
cocinero
Plato servido
Ejemplo: En un Restaurante (Dos Casos)
 Caso 1:
– Camarero emite pedido de cliente 1; sirve
cliente 1; emite pedido de cliente 2; sirve al
cliente 2.
 Caso 2:
– Camarero emite pedido de cliente 1; emite
pedido de cliente 2; sirve cliente 2; sirve al
cliente 1.
(C) Copyright 2001, Chris Ling
Ejemplo: En un Restaurante (Caso 1)
Camarero
libre
Cliente 1
Cliente 2
Emite
pedido
Emite
pedido
Esperando
Pedido
emitido
Esperando
Comiendo
Sirve Plato
(C) Copyright 2001, Chris Ling
Comiendo
Pedido al
cocinero
Sirve Plato
Ejemplo: En un Restaurante (Caso 2)
Camarero
libre
Cliente 1
Cliente 2
Emite
Pedido
Emite
Pedido
Esperando
Pedido
Emitido
Esperando
Comiendo
Sirve Plato
(C) Copyright 2001, Chris Ling
Comiendo
Pedido al
Cocinero
Sirve Plato
Red: Estructuras
 Secuencia de eventos/acciones:
e1
e2
e3
e2
e3
e4
e5
 Concurrencia:
e1
(C) Copyright 2001, Chris Ling
Red: Estructuras
 Conflicto, elección, decisión: Elejir uno entre
diversos e1, e2 ...
e1
e2
e3
e4
(C) Copyright 2001, Chris Ling
Red: Estructuras
 Sincronización
e1
(C) Copyright 2001, Chris Ling
Red: Estructuras
 Sincronización y Concurrencia
e1
(C) Copyright 2001, Chris Ling
Otro Ejemplo
• Un sistema productor-consumidor, está formado
por un productor, dos consumidores y un almacén
intermediario, de acuerdo con las reglas:
• El almacen intermediario tiene capacidad 5;
• El productor produce 3 items de cada vez;
• Apenas un consumidor puede acceder al almazen
intermediario de cada vez;
• Cada consumidor consume 2 items de cada vez
(C) Copyright 2001, Chris Ling
Sistema Productor-Consumidor
k=2
k=1
aceptado
listo
p1
produce
3
t2
t1
p4
Almacén p3
2
acepta
t3
t4
consume
envia
p2
k=5
p5
libre
k=1
Productores
(C) Copyright 2001, Chris Ling
listo
k=2
Consumidores
Ejemplo Productor-Consumidor
• En esta RdP, cada plaza tiene una capacidad
y cada arco un peso.
• Esto hace posible que múltiplas marcas
residan en una misma plaza podiendo
modelarse comportamientos más complejos.
(C) Copyright 2001, Chris Ling
Propiedades Comportamentales
• Alcanzabilidad
• “¿Se puede alcanzar un estado particular a partir de
qualquier otro estado?”
• Acotación
• “¿Puede alguna plaza acumular un número ilimitado de
marcas?”
• Vivacidad
• “¿Puede la evolución detenerse en un estado
determinado?”
(C) Copyright 2001, Chris Ling
Recordando la Máquina Expendedora
Compra 15c
Deposita 10c
5c
15c
Deposita 5c
Deposit
0c
5c
Deposita 10c
Deposita
5c
20c
10c
Deposita 10c
Compra 20c
(C) Copyright 2001, Chris Ling
Deposita
5c
Un marcado es un estado ...
t8
p4
t4
p2
t1
p1
t3
t5
t7
M0 = (1,0,0,0,0)
M1 = (0,1,0,0,0)
M2 = (0,0,1,0,0)
M3 = (0,0,0,1,0)
M4 = (0,0,0,0,1)
Marcado Inicial:M0
t6
t2
p3
(C) Copyright 2001, Chris Ling
t9
p5
Alcanzabilidad
t8
p4
t4
M0 = (1,0,0,0,0)
p2
M1 = (0,1,0,0,0)
t1
M2 = (0,0,1,0,0)
p1
t3
t7
t5
p3
M4 = (0,0,0,0,1)
t6
t2
M3 = (0,0,0,1,0)
p5
Marcado inicial:M0
t9
M0
t1
M1
t3
(C) Copyright 2001, Chris Ling
M2
t5
M3
t8
M0
t2
M2
t6
M4
Alcanzabilidad
Dada la secuencia de disparo:
M0
t1
M1
t3
M2
t5
M3
t8
M0
t2
M2
t6
• “M2 es alcanzable desde M1 y M4 es
M4
alcanzable desde M0.”
• De hecho, en el ejemplo de la máquina
expendedora, todos marcados son
alcanzables desde cualquier otro marcado.
(C) Copyright 2001, Chris Ling
Acotación
• Una RdP se dice k-acotada o simplemente
acotada si el número de marcas en cada
plaza no excede un número finito k para
cualquier marcado alcanzable a partir del
marcado inicial.
• La RdP de la Máquina Expendedora es 1acotada.
• Toda RdP 1-acotada es también segura.
(C) Copyright 2001, Chris Ling
Vivacidad
• Una RdP con marcado inicial M0 es viva si,
independientemente del marcado alcanzado
a partir de M0, es posible disparar cualquier
transicion escogiendo una secuencia de
disparo adecuada.
• En una RdP viva no puede ocurrir abrazomortal, sea cual fuere la secuencia de
disparo escogida.
(C) Copyright 2001, Chris Ling
Vivacidad
• La máquina expendedora es viva y el
sistema productor-consumidor es también
viva.
• Una transición es muerta si no puede ser
disparada desde qualquier secuencia de
disparo.
(C) Copyright 2001, Chris Ling
Un Ejemplo
t1
p3
p2
p1
t2
t3
t4
p4
M0 = (1,0,0,1)
M1 = (0,1,0,1)
M2 = (0,0,1,0)
M3 = (0,0,0,1)
RdP Limitada y no-Viva
(C) Copyright 2001, Chris Ling
Otro Ejemplo
M0 = (1, 0, 0, 0, 0)
p1
M1 = (0, 1, 1, 0, 0)
M2 = (0, 0, 0, 1, 1)
t1
M3 = (1, 1, 0, 0, 0)
p2
p3
t2
t3
p4
p5
t4
(C) Copyright 2001, Chris Ling
M4 = (0, 2, 1, 0, 0)
RdP No Acotada y Viva
Métodos de Análisis
• Reachability Analysis:
• Reachability or coverability tree.
• State explosion problem.
• Incidence Matrix and State Equations.
• Structural Analysis
• Based on net structures.
(C) Copyright 2001, Chris Ling
Otros Tipos de RdP’s
• RdP coloreadas
• Las marcas tienen “colores”, modelando
sistemas complejos de información.
• RdP temporizadas
• Retardos temporales asociados a transiciones
y/o plazas.
• Retardos fijos o intervalados.
• RdP estocásticas: retardos modelados por
variables aleatorias con distribución
exponencial.
(C) Copyright 2001, Chris Ling
Otros Tipos de RdP’s
• RdP Orientadas a Objetos
• Marcas son instancias de clases, moviéndose de
plaza a plaza, llamando métodos y cambiando
Atributos.
• La estructura de la red modela el
comportamiento interno de los Objetos.
• El propósito es elaborar paradigmas Orientados
a Objetos para estructurar y construir el
sistema.
(C) Copyright 2001, Chris Ling
Una RdP O-O
Producer
Consumer
accepted
ready
produce
send
Storage
accept
consume
ready
Producer
data: ITEM
ITEM produce( )
void send(ITEM)
(C) Copyright 2001, Chris Ling
Consumer
data: ITEM
ITEM accept( )
void consume(ITEM)
Referencias de RdP’s
 Murata, T. (1989, April). Petri nets: properties, analysis
and applications. Proceedings of the IEEE, 77(4), 541-80.
 Peterson, J.L. (1981). Petri Net Theory and the Modeling
of Systems. Prentice-Hall.
 Reisig, W and G. Rozenberg (eds) (1998). Lectures on
Petri Nets 1: Basic Models. Springer-Verlag.
 The World of Petri nets:
http://www.daimi.au.dk/PetriNets/
(C) Copyright 2001, Chris Ling
Descargar

An Introduction to Petri Nets