Download - RedesPetriBW_2009_d1_d2

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


Ejemplos:

Desactivada Activada ActivadaActivada

10


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


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


Ejemplos.


Propiedades.





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


Ejemplos.


Propiedades.




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


(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


48

(0 1 1 0)

t2

(1 0 0 0)

t1

p1

p2

p3

p4

t1

t2

t3

t3


(1 0 w 0)

49

(0 1 1 0)

t2

(1 0 0 0)

t1

p1

p2

p3

p4

t1

t2

t3

t3


(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


(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:


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


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


Ejemplos.


Propiedades.





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


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


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


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


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


Ejemplos.


Propiedades.


Invariantes




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


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


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


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


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


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


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]


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


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=


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.

Download - RedesPetriBW_2009_d1_d2

Top Related