redespetribw_2009_d1_d2
TRANSCRIPT
1
Redes de Petri básicas(P/T, B&W)
Juan de Lara con modificaciones de Gonzalo Martínez Muñoz
2
Indice
Definición y Semántica.
Ejemplos.
Grafo de alcanzabilidad y Cubrimiento.
Propiedades.
Técnicas Lineales/Algebraicas.
Técnicas Estructurales.
Técnicas de Reducción.
Lenguajes definidos por una Red de Petri.
Semántica causal.
3
Definición
Grafo dirigido con nodos de tipo:– “places” (estados) ó– transiciones (eventos)
Los nodos de distinto tipo se conectan mediante arcos.
– No hay conectividad entre nodos de igual tipo
Los arcos pueden tener asociado un peso (1 por defecto).
Los estados pueden contener un número arbitrario de tokens (círculos en negro).
Reg1
ALUBusy
ALUIdle
Load r1
Finish-ALU
Load-ALU
Reg2
Load r2
Reg3
empty r3
4
Definición
Estados de Entrada Transición Estados de Salida
Pre-Condiciones Evento Post-Condiciones
Datos de Entrada Paso deComputación
Datos de Salida
Recursos Necesarios Tarea Recursos Liberados
Buffer Procesador Buffer
Condiciones Clausula enlógica
Conclusiones
Algunas interpretaciones típicas de estados y transiciones.
5
Definición(Redes de Petri ordinaria)
Una red de Petri marcada es una tupla:
PN=(P, T, A, m0)
Donde:
P : Conjunto finito no vacío de “Places”, estados. {p1,p2,
…pm}
T : Conjunto finito no vacío de Transiciones. {t1, t2,…,tn}
A (PxT) (TxP) es un conjunto de arcos.
m0 : P {0, ℕ}, m0 Marcado inicial (número de tokens
en cada estado, el estado de la red).
donde P T = P T
6
Definición
Entidades derivadas:
I(tj) = •tj = {pi | (pi, tj) A}, places entrada a transiciones.
O(tj)= tj • = {pi | (tj,, pi) A}, places salida de transiciones.
•pj = {ti | (ti, pj) A}, transiciones entrada a places.
pj • = {ti | (pj,,ti) A}, transiciones salida de places.
Yy
yY
Yy
yY
7
Definición. Ejemplo
Reg1
ALUBusy
ALUIdle
Load r1
Finish-ALU
PN=(P, T, A, m0)
P = {Reg1, Reg2, ALUBusy, ALUIdle, Reg3},
T = {Load r1, Load r2, Load-ALU, Finish-ALU, empty r3}
A = {(Load r2, Reg2), (Load r1, Reg1), (Reg1, Load-ALU), (Reg1, Load-ALU), (Load-ALU, ALU Idle), (Load-ALU, ALU Busy), (ALU Idle, Finish-ALU), (ALU Busy, Finish-ALU), (Finish-ALU, Reg3), (Reg3, emptty r3)}
m0(Reg1)=1, m0(Reg2) = 9, m0(Reg3) = 0, m0(ALU Busy)= 0, m0(ALU Idle) = 0
Vector de estado m0 = [0, 1, 0, 1, 0]
Load-ALU
Reg2
Load r2
Reg3
empty r3
8
Semántica: regla de transición o disparo
1. Una transición t está activada si todos los estados p que están conectados a ella mediante arcos de I tienen al menos un token.
Es decir, una transición tj está activada si:
piI(tj), m(pi) 1
9
Semántica: regla de transición o disparo
Ejemplos:
Desactivada Activada ActivadaActivada
10
Semántica: regla de transición o disparo
2. Una transición puede o no dispararse.
3. El disparo de una transición activada produce:
A los estados pi que pertenecen a I de t se les resta un token.
A los estados pi que pertenecen a O de t se les suma un token.
11
Disparo
Semántica: regla de transición o disparo
Reg1
ALUBusy
ALUIdle
Load r1
Finish-ALU
Load-ALU
Reg2
Load r2
Reg3
empty r3
Estado = [1,1,0,1,0]
Activada Activada
Estado = [0,1,0,1,0]
Reg1
ALUBusy
ALUIdle
Load r1
Finish-ALU
Load-ALU
Reg2
Load r2
Reg3
empty r3
Función de Transición de estados. f: P x T
f está definida para la Transición tj sii:
piI(tj), m(pi) 1
si tj está activada, calcular el nuevo marcado de pi I(tj) O(tj)
m’ = f(m, tj)
m(pi) si pi I(tj) pi O(tj) f(m, tj) = m(pi) - 1 si pi I(tj) pi O(tj)
m(pi) + 1 si pi I(tj) pi O(tj)12
Semántica
Disparo
Transición fuente:– Activada incondicionalmente– Su disparo crea tokens y no
consume ninguno
Transición sumidero:– Su disparo consume tokens pero no
los crea
Transiciones especiales
Disparo
14
Algunos Tipos de Redes
Una red es :
pura sii: x PT [x x = ] No hay auto-bucles
simple sii: x, y PT [x = y && x = y x = y]
No es puraNo es simple
15
Enlaces Inhibidores.
t
p
s
qSi (s, t) es un enlace inhibidor, entonces t sólo está habilitada si m(s) = 0.
16
Queue
Busy
Idle
Arrival
Process
Finish
Exit
En Reparación
Avería-B
Borrado
Arreglado
Avería-I
Averia
Ejemplo.
17
Ejercicio
• Modificar la red anterior, de tal manera que sólo sea posible cargar un registro si esta vacío.
Reg1
ALUBusy
ALUIdle
Load r1
Finish-ALU
Load-ALU
Reg2
Load r2
Reg3
empty r3
18
Solución
o Modificar la red anterior, de tal manera que sólo sea posible cargar un registro si esta vacío. ALU
BusyALUIdle
Finish-ALU
Load-ALU
Reg2
Load r2
empty r3
Reg2’ Reg1
Load r1
Reg1’
Reg3Reg3’
19
Ejercicio
o Modificar la red anterior, de tal manera que se puedan realizar 2 tipos de operaciones binarias: suma y multiplicación. Se seleccionarán una vez cargada la ALU.
ALUBusy
ALUIdle
Finish-ALU
Load-ALU
Reg2
Load r2
empty r3
Reg2’ Reg1
Load r1
Reg1’
Reg3Reg3’
20
Solución
ALUBusy
ALUIdle
ADD
Load-ALU
Reg2
Load r2
empty r3
Reg2’
Reg1
Load r1
Reg1’
Reg3Reg3’
SumaMult
None
PROD
Set_MULT Set_ADD
21
Ejercicio
Modificar la red anterior, de tal manera que se tenga que seleccionar la operación a realizar antes de cargar la ALU.
ALUBusy
ALUIdle
ADD
Load-ALU
Reg2
Load r2
empty r3
Reg2’
Reg1
Load r1
Reg1’
Reg3Reg3’
SumaMultNone
PROD
Set_MULT
Set_ADD
22
ALUBusy
ALUIdle
ADD
Load-ALU
Reg2
Load r2
empty r3
Reg2’ Reg1
Load r1
Reg1’
Reg3Reg3’
SumaMultNone
PROD
Set_MULT
Set_ADD
OP Sel
Solución
23
Redes de Petri con Pesos. Definición.
Una extensión muy popular es poner pesos en los arcos:
PN = (P, T, A, W, x0)
Donde:
P : Conjunto finito no vacío de “Places”, estados. {p1,p2,
…pm}
T : Conjunto finito no vacío de Transiciones. {t1, t2,…,tn}
A (PxT) (TxP) es un conjunto de arcos.
W: A ℕ es una función de peso
m0 : P {0, ℕ}, m0 Marcado inicial (número de tokens
en cada estado, el estado de la red).
donde P T = P T
24
Una transición tj está activada si:
piI(tj), m(pi) w(pi, tj) , donde w(pi, tj) es el peso del arco de pi a tj
Una transición está activada si todos los estados que están conectados a ella mediante arcos de I tienen al menos el mismo número de tokens que el peso del arco.
Activada Desactivada Activada
32 3 2
Pesos. Semántica.
25
Función de Transición de estados.
f: P x T
f está definida para la Transición tj sii:
piI(tj), m(pi) w(pi, tj)
si tj está activada, calcular el nuevo marcado de pi I(tj) O(tj)
m’ = f(m, tj) donde
m(pi) - w(pi, tj) + w(tj, pi) si pi I(tj) pi O(tj)
f(m, tj) = m(pi) - w(pi, tj) si pi I(tj) pi O(tj)
m(pi) + w(tj, pi) si pi I(tj) pi O(tj)
Pesos. Semántica.
26
Pesos. Semántica. Ejemplo
Disparo
Estado = [0,1,0,0]
Queue
Busy Idle
Arrival
Process
Finish
Exit
2
Activada
Activada
Estado = [2,0,1,0]
Queue
Busy Idle
Arrival
Process
Finish
Exit
2
27
Indice
Definición y Semántica.
Ejemplos.
Grafo de alcanzabilidad y Cubrimiento.
Propiedades.
Técnicas Lineales/Algebraicas.
Técnicas Estructurales.
Técnicas de Reducción.
Lenguajes definidos por una Red de Petri.
Semántica causal.
28
Ejemplos. Manufactura.
M1 idle
JobArrival
M1 busy,Operator 1
M1 busy,Operator 2
conveyor
Operator 1 idle
Operator 2 idle
M2 busy,Operator 1
M2 idle
M3 busy,Operator 2
M3 idleOutput
conveyor
29
Ejemplos. Máquinas de Estados.
S0 S1
1/1
1/10/0 0/0
0 1 1
0S0
S1
30
Ejemplos. Pipeline.
Registro de Entradak
Registro de Salidak
Unidad k
Registro de Entradak+1
Registro de Salidak+1
Unidad k+1
Unidad kocupada
RegistroSalida k
lleno
RegistroEntrada k
lleno
Copiar k a k+1
RegistroSalida k
vacío
Registroentrada k+1
lleno
Unidad k+1ocupada
Registroentrada k+1
vacío
Copiar k+1 a k+2
RegistroSalida k+1
vacío
RegistroSalida k+1
lleno
31
Ejemplos. Sistemas Paralelos.La cena de los filósofos.
E1
M1
C1 C2
E2
M2E2
M2
E5
M5
E3
M3
C3
C4
C5
32
Ejemplos. Reacciones Químicas.
H2C2O4
H+
e-
CO2
H2O2
H2O
22
2
22
H2C2O4 2e-+2H++2CO2
2e-+2H++H2O2 2H2O
2
33
Ejercicio (entregar)
Realizar una red de petri de un sistema de componentes ejecutándose en paralelo.
Hay dos tipos de componentes, el primero tiene como interfaz los métodos A, B y D. El segundo tiene como interfaz el método C. Supón una instancia de cada tipo.
Un componente está bien desocupado o ejecutando alguno de sus métodos.
Los métodos de tipo B y C acceden a un disco duro (para escribir), de acceso exclusivo y compartido por todas las instancias de componentes.
El método A llama al método B (de manera asíncrona) de la misma instancia.
El método B llama al método C (de manera asíncrona), antes de escribir en el disco duro.
El método C llama al método D de manera síncrona antes de terminar de usar el disco duro.
El método D simplemente realiza un cómputo local y termina.
Asume un estado inicial en la que la instancia del componente 1 tiene una llamada al método A.
Componente 2
HDEnd
Id1
34
Solución
Componente 1
A
AEx
B
BEx
D
DEx
Id2C
CEx
BWait
Writing
HDId
HDQueue
CWait
DOut
Disco
35
Indice
Definición y Semántica.
Ejemplos.
Grafo de alcanzabilidad y Cubrimiento.
Propiedades.
Técnicas Lineales/Algebraicas.
Técnicas Estructurales.
Técnicas de Reducción.
Semántica causal.
36
Alcanzabilidad.
m m’La transición t se dispara cambiando el
marcadom [t> m’ de m a m’
=t1 t2 .. tn es una secuencia finita de ocurrencias que va de m0 a mn si m0[t1> m1 [t2>..[tn> mn
Un marcado m es alcanzable (desde m0) si hay una secuencia finita de ocurrencias que va de m0 a m.
Notación: [m0> es el conjunto de marcados alcanzables.
t
Disparo
Disparo
Disparo
Disparo
37
Grafo de Alcanzabilidad
Grafo en el que los nodos representan marcados.
Los arcos son las transiciones que al dispararse cambian el estado de la red.
S. Crítica1Proceso1
S. Crítica2
Proceso2
Semáforo
t1
t2
t3
t4
[1 0 1 0 1]
[0 1 0 0 1]
t1
[1 0 0 1 0]
t3
t2t4
Podemos analizar si la red alcanzará un cierto estado, y mediante qué secuencia de eventos.
Problema: El número de estados no siempre es finito (si la red no está acotada)
38
Grafo de Alcanzabilidad. Algoritmo.
1. Inicializar m = m0 (estado inicial)
2. Para cada nuevo nodo m, evaluar f(m, tj) para todo tj:
2.1 Si f(m, tj) está definida para algún tj, entonces crear un nuevo nodo m’=f(m, tj)
2.1.1 Si hay algún nodo n | m’ = n, entonces m’ := n
si no, añadir m’ al grafo.2.1.2 Añadir el enlace (m, tj, m’) al grafo.
Nota: El algoritmo no termina si la red no está acotada.
39
prod
pwait
deliverReadyProduce
cons
cwait
Readyconsumeread
full
empty
Grafo de Alcanzabilidad. Ejercicio.
40
Grafo de Alcanzabilidad. Solución.
[prod, empty, cons]
[pwait, full, cons]
deliver
[prod, empty, cwait]
Readyconsume
[prod, full, cons]
readyproduce
[pwait, full, cwait]
deliverReadyconsume
[prod, full, cwait]
Readyconsume
read
Readyproduce
[pwait, empty, cons]
read
[pwait, empty, cwait]
Readyconsume
Readyproduce
Readyproduce
41
PW Process
r2p
printerp
r2w
sprint
eprint
swrite
ewrite
HDisks
P Processr2p
w
p
W Processr2w
w
Ejercicio: (entregar)Calcula el Grafo de Alcanzabilidad de esta red, o bien de la redobtenida en el ejercicio anterior.
swrite
ewrite
sprint
eprint
42
Ejercicio
•Se permite como mucho un coche en el centro de la intersección en cada momento.•No se permiten giros de 180 grados en la intersección.•El número de coches que entran en la intersección de cada dirección es arbitrario.•Cuando un coche entra en el centro de la intersección, la dirección de salida se determina aleatoriamente
43
westFromWest
eastFromEast
Solución(Sólo entradas de este y oeste)
44
Grafo de Cubrimiento.
Dominancia de nodos:Sean m = [m(p1), ..., m(pn)] && o = [o(p1), ..., o(pn)]
m >d o sii:
m(pi) >= o(pi) para todo i=1...n m(pi) > o(pi) para al menos un i=1...n
“w” : representa el marcado de un place que no está acotado.
w+k = w; w-k = w
45
1. Inicializar m = m0 (estado inicial)
2. Para cada nuevo nodo m, evaluar f(m, tj) para todo tj:
2.1 Si f(m, tj) está definida para algún tj, entonces obtener m’=f(m, tj)2.1.1 Si m(pi)=w para algún i, entonces hacer
m’(pi)=w2.1.2 Si hay algún nodo o en el camino desde m0 a
m’ tal que m’ >d o, entonces hacer m’(pi) = w para todo pi | m’(pi) > o(pi).
2.1.3 Si hay algún nodo o | m’ = o, entonces m’ := o
si no, añadir m’ al grafo.2.1.4 Añadir el enlace (m, tj, m’) al grafo de
cubrimiento.
Nota: Si m>d o entonces para todo j si la función f(o, tj) está definida entonces f(m, tj) está definida y f(m, tj) >d f(o, tj)
Grafo de Cubrimiento.Algoritmo.
46
Grafo de Cubrimiento.
(1 0 0 0)
t1
p1
p2
p3
p4
t1
t2
t3
47
(0 1 1 0)
t2
(1 0 0 0)
t1
p1
p2
p3
p4
t1
t2
t3
t3
Grafo de Cubrimiento.
48
(0 1 1 0)
t2
(1 0 0 0)
t1
p1
p2
p3
p4
t1
t2
t3
t3
Grafo de Cubrimiento.
(1 0 w 0)
49
(0 1 1 0)
t2
(1 0 0 0)
t1
p1
p2
p3
p4
t1
t2
t3
t3
Grafo de Cubrimiento.
(1 0 w 0) (0 0 1 1)
50
(0 1 1 0)
t2
(1 0 0 0)
t1
p1
p2
p3
p4
t1
t2
t3
t3
Grafo de Cubrimiento.
(1 0 w 0) (0 0 1 1)
(0 1 w 0)
t1t2
(0 0 w 1)
t3
51
p1
p2
p3
t1
t2
Ejercicio: Calcular el grafo de cubrimiento de esta red:
Grafo de Cubrimiento.
52
(1 0 w)
(0 1 0)
t2
(1 0 0)
t1
w representa el conjunto {1, 2, 3, ...} de marcados alcanzables para el estado p3.
Grafo de Cubrimiento. Solución.
(0 1 w)
t1t2
53
Grafo de Cubrimiento.
p1
p3
t1
t2
w representa el conjunto {2, 4, 6, ...} de marcados alcanzables para el estado p3.
No siempre es posible saber si un cierto estado es alcanzable.
p2
(1 0 w)
(0 1 0)
t2
(1 0 0)
t1
(0 1 w)
t1t2
2
54
p1
t1
t2
p2
p3
p4t3
t4
EjercicioCalcula el grafo de cubrimiento
55
Solución 1000
0110
0001 0200
100
t1
t2 t4
p1
t1
t2
p2
p3
p4
t3
t4
t3
010 10
t1 t4
001
t2
t3 00
t4
t4
0t4, t2
t4t1
t3
t1, t2, t3, t4
t2
56
Grafo de Alcanzabilidad/Cubrimiento y Concurrencia.
1
2 4
a
c
5
b
3
d
1
2, 4
a
3, 4 2, 5
b c
d
3, 5
c b
b-c y c-b son dos entrelazados.
Concurrencia vs. no-determinismo
57
Grafo de Alcanzabilidad/Cubrimiento y Concurrencia.
1
2 4
a
c
5
b
3
d
1, 6
2, 4, 6
a
3, 4, 6 2, 5, 6
b c
d
3, 5, 6
c b
6
Añadir p6 no cambia el grafo de alcanzabilidad, pero b y c no pueden dispararse a la vez.No tenemos información sobre concurrencia de disparos.
58
Definición y Semántica.
Ejemplos.
Grafo de alcanzabilidad y Cubrimiento.
Propiedades.
Técnicas Lineales/Algebraicas.
Técnicas Estructurales.
Técnicas de Reducción.
Lenguajes definidos por una Red de Petri.
Semántica causal.
Indice
59
Propiedades
Capacidad.
Acotación.
Reversibilidad.
Conservación.
Deadlock / Liveness.
Cubrimiento.
Persistencia.
60
Propiedades. Capacidad.
Queue
Busy Idle
Arrival
Process
Finish
Exit
Capacidad infinita
Capacidad finita: 1
61
Propiedades. Capacidad.
Queue
Arrival
Process
Queremos Capacidad K (ej.5)(número limitado en la cola de clientes)
Queue
Process
Arrival Limitar capacidad K a un estado pi
Añadir un estado pi’ | m0(pi’) = K(pi)-m0(pi) ti| (pi, ti) A, Añadir arco a = (ti, pi’) con w(a) = w((pi, ti)) ti| (ti, pi) A, Añadir arco a = (pi’, ti) con w(a) = w((ti, pi))
62
Ejercicios. Capacidad.
iq
M1
M2
Process-1
Process-2
oq
Restringe la capacidad de la red de la siguiente forma:
iq a 3 M1 y M2 a 1 oq a 3 rework
2
63
Ejercicios. Capacidad.
iq
M1
M2
Process-1
Process-2
oq
Restringe la capacidad de la red de la siguiente forma:
iq a 3 M1 y M2 a 1 oq a 3
iq’
M1’M2’
oq’
rework
22
64
Propiedades. Capacidad.
Capacidad “débil”: Añadir una función k: PN (cota).
Una transición t está habilitada en un marcado m si:
s t, m(s) w(s, t) && s t \ t, m(s) + w(t, s) k(s) && s t t, m(s) + w(t, s) – w(s, t) k(s)
K=3
Complemento débil
65
Propiedades. Capacidad.
Capacidad “fuerte”: Añadir una función k: PN (cota).
Una transición t está habilitada en un marcado m si:
s t, m(s) w(s, t) && s t, m(s) + w(t, s) k(s)
K=3
Complemento fuerte
66
Propiedades. Capacidad.
Reemplazar el arco inhibidor desde un place acotado por un complemento débil.
t
p
s
q
k=3
t
p
s
q3 3
s’
67
Un estado pi de una Red de Petri con marcado inicial m0 está k-acotado (o es k-seguro) sii:
m(pi) k estado alcanzable por la red.
Un estado 1-acotado se llama seguro.
Si k | pi está k-acotado, entonces pi está acotado.
Si todos los estados están acotados, la red está acotada.
Propiedades. Acotación.
68
Propiedades. Acotación.
Una red está acotada sii su grafo de alcanzabilidad es finito.
Prueba:() El número máximo de tokens en cada place es su cota.() Si b(s) es la cota de s, entonces el place puede estar como
máximo en b(s)+1 estados.Por tanto el número de marcados alcanzables no puede superar:(b(s1)+1) (b(s2)+1) ... (b(sn)+1), donde {s1,...,sn} es el
conjunto finito de places.
Corolario: Una red 1-segura con n places tiene 2n marcados alcanzables a lo sumo.
69
Propiedades. Reversibilidad.
Una red es reversible si m0 es alcanzable desde
cualquier otro marcado alcanzable.
Una red es reversible sii su grafo de cubrimiento es fuertemente conexo.
t1
t2
t3
t4
t5
[0100]
[0010]
t3
[1000]t1
t2
[0001]t4
t5
70
E1
M1
C1
E2
M2
C2
Ejercicios. Reversibilidad.¿Es reversible esta red?
eat1
eat2
med2
med1
[0,1,0,1,1,1]
[1,0,0,1,0,0]
eat1
[0,1,1,0,0,0]
med1eat2
med2
Orden: E1 M1 E2 M2 C1 C2
Sí, podemos volver a m0 desde cualquier
marcado
71
Propiedades. Conservación.
En un modelo, un token puede representar un recurso, un proceso...
10 Queue
Busy Idle
Process
Finish
Para nuestro modelo, queremos que la suma de los tokens en la red sea constante durante la simulación.
m(Busy)+m(Idle) = 1
m(Queue)+m(Completed)+ m(Busy) = 10
Personas
PersonasCompleted
Posiblesestadosdel servidor
72
Una Red de Petri con estado inicial m0 es conservativa respecto a
= [1, 2, ..., n ] sii:
n
i ii ctepm1
.)(
para todos los estados m que pueda alcanzar la red. Donde es un vector binario de longitud igual al número de lugares
= [ 0, 1, 1, 0] , m(Busy)+m(Idle) = 1
’= [ 1, 1, 0, 1], m(Queue)+ m(Completed)+ m(Busy) = 10
Propiedades. Conservación.
73
E1
M1
C1
E2
M2
C2
Ejercicios. Conservación.¿Es conservativa esta red?
eat1
eat2
med2
med1
74
E1
M1
C1
E2
M2
C2
Ejercicios. Conservación.¿Es conservativa esta red?
eat1
eat2
med2
med1
Respecto a [1, 1, 1, 1, 0, 0], [1, 1, 0, 0, 0, 0], [0, 0, 1, 1, 0, 0]
[0,1,0,1,1,1]
[1,0,0,1,0,0]
eat1
[0,1,1,0,0,0]
med1eat2
med2
Orden: E1 M1 E2 M2 C1 C2
75
Dependencia cíclica que hace esperar indefinidamente: ninguna transición está activada.
Muchas veces queremos hacer un análisis de nuestro modelo del sistema para ver si:
Puede caer en un estado de deadlock.
Qué secuencia de eventos hacen que el sistema caiga en deadlock.
Si el deadlock es posible, cómo podemos evitarlo.
Una red está libre de deadlock si su grafo de alcanzabilidad no tiene nodos sin sucesores.
Propiedades. Deadlock.
76
Propiedades. Deadlock.
t1
t2
t3
t4
t5
[0100]
[0010]
t3
[1000]t1
t2
[0001]t4
t5
t1
t2t3
t4
t5
[01000]
[00110]
t3
[10000]t1
t2
[00101]t4
t5
[00010][00001]t4Si t3 se dispara => la red entra en deadlock
77
Propiedades. Liveness.
Dado un estado inicial m0, una transición de una Red de Petri está:
Viva a nivel L0 (muerta): Si nunca va a poder dispararse.
Viva a nivel L1: Si hay una secuencia desde m0 tal que la transición puede dispararse al menos una vez.
Viva a nivel L2: Si la transición puede dispararse al menos k veces dado un entero positivo k.
Viva a nivel L3: Si existe alguna secuencia infinita en la que la transición aparece infinitas veces.
Viva a nivel L4: Si la transición está viva a nivel L1 para cada estado alcanzable desde m0.
78
Propiedades. Liveness.
t3
t2t1
p1
p2
t2 está muerta.
t1 está viva a nivel L1.
t3 está viva a nivel L3.
[1, 0]t3
[0, 1]
t1
79
Propiedades. Cubrimiento.
Dada una red de Petri en estado m0, un estado y puede ser cubierto si hay una secuencia de transiciones desde m0 tal que en algún momento la red llega a un estado m, tal que:
m(pi) y(pi) pi P
80
En una situación en la que hay más de una transición habilitada...
Una red de Petri es persistente si, para cualquier conjunto de transiciones habilitadas, el disparo de una no deshabilita el resto.
Si ti, tj T I(ti) I(tj) = , la red es persistente.
Relacionada con el estudio de no-interrumpimiento en modelos en los que se simulan varios procesos.
Propiedades. Persistencia.
81
Ejercicio(Entregar)
Estudia las siguientes propiedades de la red de Petri del ejercicio 1 utilizando el grafo de alcanzabilidad: (solución en transparencia 34)
– Acotación.– Reversibilidad.– Persistencia.– Conservación/Invariantes.– Deadlock.
82
Definición y Semántica.
Ejemplos.
Grafo de alcanzabilidad y Cubrimiento.
Propiedades.
Técnicas Lineales/Algebraicas.
Invariantes
Técnicas Estructurales.
Técnicas de Reducción.
Lenguajes definidos por una Red de Petri.
Semántica causal.
Indice
83
Técnicas Lineales/Algebraicas
m0=[4, 0, 0, 0, 1]t2 = [-1, 1, 1, 0, -1]m0 [t2> m1 => m0+t2=m1 = [3, 1, 1, 0, 0]
s1
s2
s3
s4
s5
t1 t2
t3
t5
t4
84
Representación Matricial de una Red de Petri
s1
s2
s3
s4
s5
t1 t2
t3
t5
t4
s1 s2 s3 s4 s5t1 1 -1 0 0 0t2 -1 1 1 0 -1t3 0 0 -1 1 0t4 0 0 0 -1 1t5 0 0 1 -1 0
A=
85
Representación Matricial de una Red de Petri
A es una matriz |T| x |P|
Aji = w(tj, pi) – w(pi, tj)
x’ = x + uA
Donde u es el vector de disparo (1 en la transición que
dispara).
86
Representación Matricial de una Red de Petri
s1
s2
s3
s4
s5
t1 t2
t3
t5
t4
s1 s2 s3 s4 s5t1 1 -1 0 0 0t2 -1 1 1 0 -1t3 0 0 -1 1 0t4 0 0 0 -1 1t5 0 0 1 -1 0
A=[4,0,0,0,1]+[0,1,0,0,0]A =[3,1,1,0,0]
87
p1
t1
t2
p2
p3
p4
t3
t4
Representación Matricial de una Red de Petri. Ejercicio.
Calcula la Matriz de la siguiente red
88
p1
t1
t2
p2
p3
p4
t3
t4
Representación Matricial de una Red de Petri. Ejercicio.
Calcula la Matriz de la siguiente red
p1 p2 p3 p4 t1 -1 1 1 0 t2 0 -1 -1 1 t3 1 0 1 -1 t4 0 1 -1 0
A=
89
Representación Matricial de una Red de Petri
m0 [t2 t3 t5 t1 t3> m5 =>
m1 = m0+[01000]A; m2 = m1+[00100]A
m2 = m0+[01000]A+[00100]A = m0+[01100]A
m3 = m0+[01100]A+[00001]A = m0+[01101]A
m4 = m0+[11101]A
m5 = m0+[11201]A
[11201] = vector de Parikh de t2 t3 t5 t1 t3
90
Representación Matricial de una Red de Petri
Si m [> m’ y p() es el vector de Parikh de entonces:
m’ = m+ p()A
Por tanto, un marcado m’ es alcanzable desde m si
m’ = m+ xA
tiene solución para x en N*
(Condición necesaria pero no suficiente).
91
Representación Matricial de una Red de Petri
p1
p2
p3
p4
p5
t1
t2
t3
t4
t5
[10000]
[01001] [00110]
t1 t2
[00011]
t3 t4
t5Marcadoalcanzable? Soluciones (vector de Parikh)[10000] Sí [00000], [10101], [01011], ...[01001] Sí [10000], ...[00110] Sí [01000],...[00011] Sí [10100], [01010] ,...[01100] No [11001]
p1 p2 p3 p4 p5t1 –1 1 0 0 1t2 -1 0 1 1 0t3 0 -1 0 1 0t4 0 0 -1 0 1t5 1 0 0 -1 -1
92
Representación Matricial de una Red de Petri
Problema: no tenemos información sobre la secuencia de disparos en el vector de Parikh.
No hay restricción para impedir el disparo de una transición que no está habilitada.
La matriz A no refleja la estructura de la red en los places p | t p•t && pt•
93
Conservación
Una red es conservativa respecto a = [1, 2, ..., n ] sii
AT=[0,...,0]
Dem:
) m0T = m’T m’ | m [>m’
Por tanto, m’T= m0T+AT p()T
m’T = (m0T+AT p() T) = m0
T+ A T p() T
AT p() T = 0, p() A T = [0,...,0]
) AT = 0
Sea m’ | m0 [ > m’ , entonces m’T= m0T+AT p()T
m’T= (m0T+AT p()T) = m0
T+AT p()T
m’T = m0T
94
Conservación. Ejercicio (1)
E1
M1
C1
E2
M2
C2eat1
eat2
med2
med1
Demuestra que esta red es conservativa respecto a =[1, 1, 1, 1, 0, 0], usando técnicas algebraicas.
95
E1
M1
C1
E2
M2
C2eat1
eat2
med2
med1
Respecto a =[1, 1, 1, 1, 0, 0]
Conservación. Ejercicio (1)
E1 M1 E2 M2 C1 C2Eat2 0 0 1 -1 –1 -1Med2 0 0 -1 1 1 1Eat1 1 -1 0 0 –1 -1 Med1 -1 1 0 0 1 1
AT= [0, 0, 0, 0]
96
Conservación. Ejercicio (1)
p1
t1
t2
p2
p3
p4
t3
t4
Calcula las invariantes en places de esta red p1 p2 p3 p4 t1 -1 1 1 0 t2 0 -1 -1 1 t3 1 0 0 -1 t4 0 1 -1 0
A=
97
t1 t2 t3 t4 p1 -1 0 1 0 p2 1 -1 0 1 p3 1 -1 0 -1 p4 0 1 -1 0
AT=
Conservación. Ejercicio (1)
AT=0
-1 + 2 + 3 = 0 - 2 – 3 + 4 = 0 1 = 4 = 22; 2 = 3 1 - 4 = 0 = [2 1 1 2] , ... + 2 – 3 = 0
98
Ejercicio (Entregar).
• Calcular las invariantes en places y transiciones de la red correspondiente al ejercicio 2 entregado el último día.