Máquinas de estados finitos
Características




Simple
Formal
Operacional
Número finito de estados
Definición
Una máquina de estados finitos M consiste
de:

Un conjunto finito de estados, Q;
Un conjunto finito de entradas, I;
Una función de transición δ: Q  I  Q.




δ puede ser una función parcial
Representación gráfica

Grafo


nodos representan los estados;
un arco rotulado i va del estado q a q’ si y sólo si
δ(q, i) = q’.
Q = {q0, q1, q2, q3}
δ(q0, a) = q1
δ(q1, a) = q2
δ(q1, b) = q3
δ(q2, b) = q3
δ(q3, c) = q0
I = {a, b, c}
Modelado con una MEF
MEF que modela el switch de una lámpara
Modelado con una MEF

Una planta química.


Los niveles de temperatura y de presión deben ser
monitoreados por razones de seguridad. Se han instalado
sensores para generar señales adecuadas cuando alguno
de dichos niveles excede un valor predefinido.
Política trivial: cuando alguna de las señales es originada
por el correspondiente sensor, el sistema de control apaga
la planta y emite una señal de alarma; el sistema es reiniciado manualmente cuando la causa de la falla ha sido
corregida.
Modelado con una MEF
Modelado con una MEF

Cuando se origina
alguna de las dos
señales, se invoca
automáticamente
una acción de
recuperación (existe
una “acción de
temperatura” y una
“acción de presión”).
Modelado con una MEF

Si, después de un
rato, la acción de
recuperación tiene
éxito, el sistema es
automáticamente reinicializado al estado
“normal” y un mensaje
de “todo OK” es
emitido.
Modelado con una MEF

Si la
recuperación no
tiene éxito, la
señal de alarma
debe ser lanzada
y la planta debe
ser apagada.
Modelado con una MEF

El sistema debe
también ser apagado si
se está tratando de
recuperar de algún tipo
de anormalidad (de
temperatura o presión)
y la otra señal aparece.
Limitaciones de las MEF
Limitación: Número finito de
estados.
 Soluciones:

No describir todos los detalles del
sistema.
 Cambiar de herramienta de
modelado.
 Enriquecer la notación.

Limitaciones de las MEF

Sistema productor-consumidor




Un proceso productor produce mensajes y los
graba en un buffer.
Un proceso consumidor lee mensajes y los saca
de dicho buffer (consume).
Si el buffer está lleno, el productor debe esperar
hasta que el consumidor lo haya vaciado.
Si el buffer está vacío, el consumidor debe
esperar hasta que el productor coloque un
mensaje en el buffer.
DTE - Una primera aproximación
(a) proceso productor; (b) proceso consumidor; (c) buffer.
Suponemos un buffer con capacidad para 1 mensaje.
DTE para Productor-Consumidor
DTE para Productor-Consumidor
DTE para Productor-Consumidor
DTE para Productor-Consumidor
DTE para Productor-Consumidor
DTE para Productor-Consumidor
DTE para Productor-Consumidor
DTE para Productor-Consumidor
DTE para Productor-Consumidor
Problemas en el modelo

Tamaño: n subsistemas cada uno con ki
estados, sistema resultante k1 k2  ...  kn
estados.

Modelo sincrónico.

El sistema está siempre en un único estado y
ejecuta exactamente una única acción en cada
instante de tiempo, sin embargo por ej. no hay
razón para imponer tal serialización entre la
acción “produce” y la acción “consume” (las
transiciones deberían ocurrir
asincrónicamente).
Introducción a las
Redes de Petri
Redes de Petri

Notación formal, operacional, gráfica.

Sistemas asincrónicos y concurrentes.
Redes de Petri - Definición
Una Red de Petri es un multigrafo bipartito dirigido representado
por una cuádrupla PN = <P, T, I, O>
donde

P = {p1, p2, ..., pn}
conjunto finito de lugares (places), n  0

T = {t1, t2, ..., tm}
conjunto finito de transiciones, m  0

I: T  P
P denota los multisets o bolsas de P.
pi  I(tj) si existe un arco de pi a tj

O: T  P
pi  O(tj) si existe un arco de tj a pi
Ejemplo 1
p1
p2
P = {p1, p2, p3, p4, p5, p6, p7}
T = {t1, t2, t3, t4, t5, t6}
t1
t2
p3
p4
p5
t3
p7
t5
t6
O(t1) = {p4}
I(t2) = {p2}
O(t2) = {p5}
I(t3) = {p3, p4}
O(t3) = {p6}
I(t4) = {p3, p5} O(t4) = {p7}
t4
p6
I(t1) = {p1}
I(t5) = {p6}
O(t5) = {p1, p3}
I(t6) = {p7}
O(t6) = {p2, p3}
Ejemplo 2
p2
p1
t1
P = {p1, p2}
T = {t1}
I(t1) = {p1, p1}
O(t1) = {p2, p2, p2}


Si un arco va desde un place a una
transición, al place se lo llama input place
(lugar de entrada) de la transición.
Si un arco va desde una transición a un
place, al place se lo llama output place
(lugar de salida) de la transición.
Redes de Petri
Marcación y ejecución



Una red de Petri recibe su estado marcando
sus places.
Una marcación (marking) consiste en asignar
un número entero no negativo de tokens a
cada place.
En las redes tradicionales de Petri los tokens
son indistinguibles y no representan
información específica.
Ejemplo de red marcada
p1

p2
t1
P = {p1, p2}
T = {t1}
I(t1) = {p1, p1}
O(t1) = {p2, p2, p2}
Marcación
Una marcación de una Red de Petri
PN = <P, T, I, O> es una función:
: P  {0, 1, 2, ...}
que asigna un número entero no negativo de
tokens a cada place de la red.
Marcación

Una marcación puede representarse como
un vector de dimensión n (n es el número de
lugares de la red).
p1

p2
t1
(p1) = 2 (p2) = 0
 = (2,0)
Red de Petri marcada
Una Red de Petri marcada
M = <PN, >
es un una estructura de Red de Petri
PN = <P, T, I, O> y un marking .
p1
p2
•
•
t1
P = {p1, p2, p3, p4, p5, p6, p7}
T = {t1, t2, t3, t4, t5, t6}
t2
p3
p4
p5
•
t3
p7
t5
t6
O(t1) = {p4}
I(t2) = {p2}
O(t2) = {p5}
I(t3) = {p3, p4}
O(t3) = {p6}
I(t4) = {p3, p5} O(t4) = {p7}
t4
p6
I(t1) = {p1}
I(t5) = {p6}
O(t5) = {p1, p3}
I(t6) = {p7}
O(t6) = {p2, p3}
 = (1, 1, 1, 0, 0, 0, 0)
Ejecución de una Red de Petri


Durante la ejecución de la red el número y
posición de los tokens puede variar dando
lugar a una nueva marcación.
Cada marcación corresponde a un estado de
la red.
Reglas de Ejecución
1.
2.
Una transición puede disparar si está
habilitada.
Una transición está habilitada si en cada uno
de sus input places existen al menos tantos
tokens como arcos existan desde el place a la
transición.
t1
t1
p1

t1 no habilitada
p2
p1

t1 habilitada,
puede disparar
p2
Reglas de Ejecución
3.
Cuando una transición dispara, en cada uno de sus
input places se remueven tantos tokens como arcos
existan desde el input place hacia la transición, y en
cada uno de los output places de la transición se
insertan tantos tokens como arcos existan desde la
transición al output place.
t1
p1

t1
p1 
p2
 p2
Disparó t1


p3
p4
p4
p3
Reglas de Ejecución
Formalmente, una transición t  T está
habilitada en una red de Petri PN = <P, T, I, O>
sii
p  I(t) : (p)  #(p, I(t))
donde
#(p, I(t)) es el número de arcos desde p a t.
Reglas de Ejecución
Formalmente, el disparo de una transición t  T
con un marking  resulta en un nuevo marking ’
definido por:
p  P : ’(p) = (p)  #(p, I(t)) + #(p, O(t))
donde
#(p, I(t)) es el número de arcos desde p a t.
#(p, O(t)) es el número de arcos desde t a p.
Ejecución de una Red de Petri
p1
p2
•
•
t1
0 = (1, 1, 1, 0, 0, 0, 0)
t2
p3
p4
p5
•
t1 y t2
t3
están
t4
p6
p7
t5
t6
habilitadas.
Ejecución de una Red de Petri
p1
p2
•
t1
0 = (1, 1, 1, 0, 0, 0, 0)
t2
p3
p4
•
p5
•
t3
•secuencia de
disparos: (t1)
t4
p6
p7
t5
t6
1 = (0, 1, 1, 1, 0, 0, 0)
•t2 y t3 quedaron
habilitadas.
Ejecución de una Red de Petri
p1
p2
0 = (1, 1, 1, 0, 0, 0, 0)
t1
t2
p3
p4
•
•
•
t3
p5
1 = (0, 1, 1, 1, 0, 0, 0)
2 = (0, 0, 1, 1, 1, 0, 0)
t4
p6
p7
t5
t6
•secuencia de
disparos: (t1,t2)
•t3 y t4 quedaron
habilitadas.
Ejecución de una Red de Petri
p1
p2
0 = (1, 1, 1, 0, 0, 0, 0)
t1
t2
p3
p4
•
p5
1 = (0, 1, 1, 1, 0, 0, 0)
2 = (0, 0, 1, 1, 1, 0, 0)
3 = (0, 0, 0, 1, 0, 0, 1)
t3
t4
p6
p7
•
t5
t6
•secuencia de
disparos: (t1,t2,t4)
•t6 quedó
habilitada.
Ejecución de una Red de Petri
p1
p2
•
t1
0 = (1, 1, 1, 0, 0, 0, 0)
t2
p3
p4
•
p5
•
1 = (0, 1, 1, 1, 0, 0, 0)
2 = (0, 0, 1, 1, 1, 0, 0)
3 = (0, 0, 0, 1, 0, 0, 1)
t3
t4
p6
p7
4 = (0, 1, 1, 1, 0, 0, 0)
•secuencia de
disparos: (t1,t2,t4,t6)
t5
t6
•t2 y t3 quedaron
habilitadas. ...
Ejecución de la Red de Petri


La secuencia de disparos dada es una de las
posibles secuencias, no la única.
El modelo es no determinístico, en el sentido
que dado un marking inicial 0 distintas
evoluciones de la red son posibles.
Ejecución de una Red de Petri
t2
t1
t3
t1 siempre habilitada
Modelado con Redes de Petri




Una transición, usualmente, modela un
evento o acción.
El disparo de la transición representa la
ocurrencia de tal evento o la ejecución de la
acción.
Una transición está habilitada, si se
satisfacen las condiciones necesarias para la
ocurrencia de tal evento o acción.
La presencia de tokens en los input places
modelan tales condiciones.
Modelado con Redes de Petri
p1
p2
•
•
t1
Eventos del
proceso 1
t2
p3
p4
p5
•
t3
t1 = proceso 1 solicita
recurso
t4
p6
p7
t5
t6
t3 = proceso 1 toma
recurso
t5 = proceso 1 libera
recurso
Modelado con Redes de Petri
p1
p2
•
•
t1
Eventos del
proceso 2
t2
p3
p4
p5
•
t3
t2 = proceso 2 solicita
recurso
t4
p6
p7
t5
t6
t4 = proceso 2 toma
recurso
t6 = proceso 2 libera
recurso
Modelado con Redes de Petri
p1
p2
•
•
t1
t2
p3
p4
p5
•
t3
p3 representa la
disponibilidad o
no de un recurso.
t4
p6
p7
t5
t6
Modelado con Redes de Petri
Transiciones concurrentes
p1
p2
•
•
t1
t2
p3
p4
p5
•
t3
t4
p6
p7
t5
t6
t1 y t2 habilitadas y
el disparo de una
no deshabilita la
otra =>
concurrentes
Modelado con Redes de Petri
Transiciones
en
conflicto
p1
p2
t1
t2
p3
p4
•
•
•
t3
p5
t4
p6
p7
t5
t6
t3 y t4 habilitadas y
el disparo de una
deshabilita la otra
=> en conflicto
Modelado con Redes de Petri
Starvation
p1
p2
•
secuencia de
disparos:
t1
t2
(t2)
p3
p4
•
•
t3
p5
t4
p6
p7
t5
t6
Modelado con Redes de Petri
Starvation
p1
p2
•
secuencia de
disparos:
t1
t2
(t2,t4)
p3
p4
p5
t3
t4
p6
p7
•
t5
t6
Modelado con Redes de Petri
Starvation
p1
p2
•
•
t1
secuencia de
disparos:
t2
(t2,t4,t6)
p3
p4
p5
•
t3
t4
p6
p7
t5
t6
Modelado con Redes de Petri
Starvation
p1
p2
•
secuencia de
disparos:
t1
t2
(t2,t4,t6,t2)
p3
p4
•
•
t3
p5
t4
p6
p7
t5
t6
Modelado con Redes de Petri
Starvation
p1
p2
•
secuencia de
disparos:
t1
t2
(t2,t4,t6,t2,t4)
p3
p4
p5
t3
t4
p6
p7
•
t5
t6
Modelado con Redes de Petri
Starvation
p1
p2
•
•
t1
secuencia de disparos:
(t2,t4,t6,t2,t4,t6,...)
t2
p3
p4
p5
•
starvation de proceso 1
t3
t4
p6
p7
t5

t6
Modelado con Redes de Petri
Deadlock
p2
p1
•
•
p3
t1
p4
t1: proc1 solicita ambos recursos
t2
••
p5
t3’: proc1 toma un recurso
t3’’: proc1 toma otro recurso
t5: proc1 libera ambos recursos
t4’
t3’
p6
p7
t2: proc2 solicta ambos recursos
t4’: proc2 toma un recurso
t3’’
p8
t4’’: proc2 toma otro recurso
t4’’
p9
t5
t6
t6: proc2 libera ambos recursos
Modelado con Redes de Petri
Una posible ejecución sin deadlock
p2
p1
•
p3
t1
p4
t2
••
•
p5
t4’
t3’
p6
(t1)
p7
t3’’
p8
t4’’
p9
t5
t6
secuencia de
disparos:
Modelado con Redes de Petri
Una posible ejecución sin deadlock
p2
p1
•
p3
t1
p4
t2
•
•
p5
(t1, t3’)
t4’
t3’
p6
p7
t3’’
p8
t4’’
p9
t5
t6
secuencia de
disparos:
Modelado con Redes de Petri
Una posible ejecución sin deadlock
p2
p1
•
p3
t1
t2
p4
p5
(t1, t3’, t3’’)
t4’
t3’
p6
p7
t3’’
p8
t4’’
p9
•
t5
t6
secuencia de
disparos:
Modelado con Redes de Petri
Una posible ejecución sin deadlock
p2
p1
•
•
p3
t1
p4
t2
••
p5
(t1, t3’, t3’’, t5)
t4’
t3’
p6
p7
t3’’
p8
t4’’
p9
t5
t6
secuencia de
disparos:
Modelado con Redes de Petri
Una posible ejecución con deadlock
p2
p1
•
p3
t1
p4
t2
••
•
p5
t4’
t3’
p6
(t1)
p7
t3’’
p8
t4’’
p9
t5
t6
secuencia de
disparos:
Modelado con Redes de Petri
Una posible ejecución con deadlock
p2
p1
p3
t1
p4
t2
••
•
p5
•
t4’
t3’
p6
(t1, t2)
p7
t3’’
p8
t4’’
p9
t5
t6
secuencia de
disparos:
Modelado con Redes de Petri
Una posible ejecución con deadlock
p2
p1
p3
t1
p4
t2
•
•
p5
•
(t1, t2, t3’)
t4’
t3’
p6
p7
t3’’
p8
t4’’
p9
t5
t6
secuencia de
disparos:
Modelado con Redes de Petri
Una posible ejecución con deadlock
p2
p1
p3
t1
t2
p4
p5
•
(t1, t2, t3’, t4’)
t4’
t3’
p6
•
t3’’
p8
p7
t4’’
p9
t5
t6
secuencia de
disparos:
deadlock (ninguno
de los procesos
puede continuar)
DTE para Productor-Consumidor
Primera aproximación
(a) proceso productor; (b) proceso consumidor; (c) buffer.
Suponemos un buffer con capacidad para 1 mensaje.
PN para Productor-Consumidor
Primera aproximación
write
p1
consume
•
p2
c1
produce
•
c2
read
read
0
•
write
1
DTE para Productor-Consumidor
PN para Productor-Consumidor
consume
c1
•
c2
read
0
•
1
write
p1
•
p2
produce
Limitaciones de las Redes de Petri
tradicionales y algunas extensiones

Limitación: los tokens son anónimos.


p.e. la presencia de un token en un place
puede denotar la presencia de un mensaje en
un buffer pero no lo que el mensaje dice.
Extensión: asignación de valores a tokens
más asociación de predicados y acciones
a las transiciones.
p2
p1
p1 < p2
7
3
1
4
4
p3
p2 = p3
t1
t2
p4:=p2+p1
p4:=p3-p2
p5 p5:= p2+p3
p4
•t1 habilitada: tuplas ready: (3,7) (3,4)
elecciones no determinísticas
•t2 habilitada: tuplas ready: (4, 4)
p2
p1
p1 < p2
1
4
4
p3
p2 = p3
t1
t2
p4:=p2+p1
p4
p4:=p3-p2
p5 p5:= p2+p3
10
sec. de disparos: (t1)
t1 deshabilitada.
t2 habilitada: tuplas ready: (4, 4)
p2
p1
p1 < p2
1
p3
p2 = p3
t1
t2
p4:=p2+p1
p4
p4:=p3-p2
p5 p5:= p2+p3
10
0
sec. de disparos: (t1, t2)
8
Limitaciones de las Redes de Petri
tradicionales y algunas extensiones


Limitación: no se pueden fijar políticas de
selección cuando varias transiciones están
habilitadas.
Extensión: asignación estática o dinámica
de prioridades a las transiciones.
p2
p1
prioridad = 1


t1
p4

p3
t2 prioridad = 2
p5
t1 y t2 habilitadas, dispara t2 porque tiene mayor
prioridad.
Limitaciones de las Redes de Petri
tradicionales y algunas extensiones

Limitación: Problemas con el manejo del tiempo.


p.e. un proceso envía mensajes a una cierta velocidad. Estos
son colocados en un buffer y procesados. Si un mensaje no
es tomado del buffer antes del arribo del próximo, es
sobrescrito por el nuevo.
Extensiones: Redes de Petri con tiempo donde a cada
transición se le asocia un par <tmin, tmax> que indica el
intervalo de tiempo dentro del cual debe disparar.
p2
p1
prioridad = 1
tmin = 1
tmax = 4


t1
p4

t2
p3
prioridad = 2
p5 tmin = 2
tmax = 3
Descargar

Redes de Petri