PDF de programación - REDES DE PETRI: PROPIEDADES Y MÉTODOS DE ANÁLISIS

REDES DE PETRI: PROPIEDADES Y
REDES DE PETRI: PROPIEDADES Y
MÉTODOS DE ANÁLISIS

PROGRAMACIÓN CONCURRENTE

MASTER EN COMPUTACIÓN

DEPARTAMENTO DE ELECTRÓNICA Y COMPUTADORES

UNIVERSIDAD DE CANTABRIA
CURSO 2012/13

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

REDES DE PETRI:
PROPIEDADES
Las propiedades de las redes de Petri nos permiten
detectar fenómenos de interés o errores de
detectar fenómenos de interés o errores de
funcionamiento en el sistema que modelan.

• Vivacidad
• Ciclicidad
• Limitación
• Conservación
• Conflictividad
• Exclusión mutua

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

1

2

22/10/2012

1

PROPIEDADES DE LAS REDES
DE PETRI: VIVACIDAD
• Una transición t de una RdP marcada es viva si para cada marcado Mi

existe un marcado alcanzable desde Mi en el cual t está habilitada.
• Una RdP marcada es viva si cada una de sus transiciones es viva.
• Una RdP es no viva para un marcado Mi si, para algún marcado Mj

sucesor de Mi, todas las transiciones son no vivas.

RdP viva

RdP no viva
(se bloquea
totalmente)

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

PROPIEDADES DE LAS REDES
DE PETRI: VIVACIDAD
• Una RdP es parcialmente viva si
contiene si contiene transiciones
que siempre son vivas y otras que
no lo son.

• En una RdP viva se garantiza una
operación libre de puntos muertos
independientemente de la
secuencia de disparo elegida. La
propiedad de vivacidad es muy
p p
y
importante porque sirve para
caracterizar el bloqueo total o
parcial de un sistema.

RdP parcialmente viva

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

3

4

22/10/2012

2

22/10/2012

PROPIEDADES DE LAS REDES
DE PETRI: CICLICIDAD
• Una RdP para un marcado inicial M0 se

p

q

p

dice que posee un comportamiento
globalmente cíclico, si existe una
secuencia de disparos que permite
alcanzar el marcado inicial M0 a partir de
cualquier marcado Mi sucesor de M0.

• La ciclicidad de una RdP para un

j

marcado M0 garantiza la no existencia
de subconjuntos de estados finales; esto
es, de conjuntos de estados a partir de
los cuales no son alcanzables algunos
otros estados sucesores de M0.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

5

RdP cíclica

PROPIEDADES DE LAS REDES
DE PETRI: LIMITACIÓN
• Una plaza p de una RdP marcada es k-limitada para un marcado M0 si, para
cualquier marcado Mi sucesor de M0, el número de marcas en p es menor o igual
que k. Esto es, si y sólo si existe un k fijo tal que Mi(p)  k para todo marcado
q
alcanzable desde M0.

i(p)

q

p

y

j

• Se denomina limite de la plaza p al menor entero k que verifica la desigualdad

anterior.

• Una RdP marcada es k-limitada para un marcado M0 si, para algún k fijo, cada

plaza es k-limitada.

• Una plaza es segura si es 1-limitada.
• Una RdP marcada es segura o binaria si cada una de sus plazas es segura.
• El interés de la k-limitación de una red es que garantiza la finitud de sus marcados

g

p

g

alcanzables. Desde un punto de vista práctico, una red k-limitada puede
implementarse con un conjunto de recursos finitos.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

6

3

PROPIEDADES DE LAS REDES
DE PETRI: LIMITACIÓN

RdP 3-limitada

RdP binaria

RdP no limitada

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

LAS PROPIEDADES DE VIVACIDAD, CICLICIDAD Y
LIMITACIÓN SON INDEPENDIENTES

LVC

LVC

LVC

LVC

LVC

LVC

LVC

LVC

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

7

8

22/10/2012

4

PROPIEDADES DE LAS REDES
DE PETRI: CONSERVACIÓN
• Una RdP con un marcado inicial M0 se dice que es conservativa si,
para cualquier marcado Mi alcanzable desde M0, el número total de
marcas en la RdP es el mismo; esto es si para todo marcado se verifica
marcas en la RdP es el mismo; esto es, si para todo marcado se verifica

pM
(
i

)





Pp

i

pM
(
i

0

)



Pp

i

• El concepto de conservación está relacionado con el número de
recursos disponibles, que no puede variar durante la ejecución de la red
de Petri La manera más simple de conseguirlo es requerir que el
de Petri. La manera más simple de conseguirlo es requerir que el
número total de testigos en la red permanezca constante. Sin embargo,
la conservación estricta es una relación muy fuerte y normalmente
conviene hablar de conservación con respecto a un vector peso.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

9

PROPIEDADES DE LAS REDES
DE PETRI: CONSERVACIÓN
Una RdP con un marcado inicial M0 se dice que es conservativa respecto a
un vector peso w, w=(w1,w2,...,wn), wi0, si para cualquier marcado M
alcanzable desde M0 la suma del producto del número de marcas de cada
alcanzable desde M0, la suma del producto del número de marcas de cada
lugar por el factor de peso correspondiente es constante; esto es, si para todo
marcado MR(M0) se verifica:


pMw
(
i
i

pMw
(
i
i





)

)

0

n



i

1


n



i

1


RdP conservativa estricta

RdP conservativa con peso

w=(1,1,1,2,2)

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

10

22/10/2012

5

PROPIEDADES DE LAS REDES
DE PETRI: CONFLICTIVIDAD
• Se dice que en una RdP existe un conflicto estructural cuando un lugar posee

t

t

• Se dice que dos transiciones ti y tj están en conflicto efectivo para M0 si:
M i

más de una transición de salida.
S di
• Existe un marcado alcanzable desde M0 que sensibiliza simultáneamente a ti y tj.
• Si al dispararse ti (tj) el marcado que se obtiene no habilita a tj (ti).

fli t

tá

ti

d

f

t

i

i

RdP con conflicto estructural

RdP con conflicto efectivo

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

11

PROPIEDADES DE LAS REDES
DE PETRI: CONFLICTIVIDAD
• En general, un conjunto de transiciones TcT se dice que

están en conflicto si el disparo de cualquier subconjunto de
lt d
t
transiciones {ti}Tc da como resultado un marcado en el cual
l
alguna transición tjTc se deshabilita.

{t } T d

d

l

i

i

• Se dice que una red de Petri es persistente si no existe un
conjunto de transiciones que estén en conflicto para ningún
marcado M del conjunto de alcanzabilidad.

• La situación de conflicto efectivo es normalmente inaceptable
para cualquier descripción de un sistema dado que
para cualquier descripción de un sistema, dado que
corresponde a una situación ambigua. El conflicto efectivo se
resuelve mediante una interpretación asociada a la red.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

12

22/10/2012

6

PROPIEDADES DE LAS REDES
DE PETRI: EXCLUSIÓN MUTUA
• Un conjunto de transiciones TeT se dice que son mutuamente exclusivas si el

disparo de cualquier transición tiTe genera un marcado en el cual todas las
demás transiciones tjTe, ij, se deshabilitan.

e

j

j

• Se dice que dos plazas de una red de Petri están en exclusión mutua para un

marcado M0 si no pueden estar marcadas simultáneamente en los marcados
alcanzables a partir de M0.

• Una aplicación típica de plazas con exclusión mutua es el modelado de recursos

compartidos por múltiples usuarios.

Las plazas 4 y 5 y las transiciones 1 y 2
son mutuamente exclusivas.

t

t

l

i

- R recurso disponible
- R1 recurso tomado por 1
- R2 recurso tomado por 2

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

13

REDES DE PETRI: SUBCLASES

•

•

•

Las redes de Petri, a pesar de basarse en unas reglas bastante simples, pueden exhibir
comportamientos muy complicados. Como consecuencia, se han introducido clases
restringidas de redes de Petri, que son más fáciles de analizar, y se han estudiado sus
propiedades
propiedades.
El objetivo que se persigue al definir una subclase de red de Petri es que pueda modelar una
gran variedad de sistemas y que, al menos para los problemas de interés, se puedan utilizar
procedimientos de análisis simples.
Las principales subclases de redes de Petri ordinarias son:
• Grafos de estados (GE) o máquinas de estados (ME) son RdP en las que cada transición ha de tener
exactamente una entrada y una salida. Una máquina de estados es estrictamente conservativa, muy sencilla de
analizar, puede representar conflictos o alternativas, pero no paralelismo, concurrencia ni sincronización.

• Grafo marcado (GM) o grafo de sincronización es una RdP en la que cada plaza tiene exactamente una
entrada y una salida. Los grafos marcados pueden representar paralelismo, concurrencia y sincronización, pero no
conflicto o decisiones dependientes de datos
conflicto o decisiones dependientes de datos.

• Red de libre elección (RLE) es aquella en la que cada plaza p es o bien la única plaza de entrada de una
transición o hay como mucho una transición que tiene p como una plaza de entrada. Esta subclase permite el
modelado de concurrencia y conflicto, pero de una manera más restringida que en el modelo general. En una RLE,
siempre que un lugar esté marcado y posea más de una transición de salida, es posible elegir libremente
(independientemente del resto del marcado) la transición que se disparará.

• Red de Petri simple (RS) es aquella en la que cada transición tiene como máximo una plaza de entrada

compartida con otra transición.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

14

22/10/2012

7

SUBCLASES DE REDES DE PETRI
ORDINARIAS

Programación Concurrente:
Redes de Petri

Mercedes Granda

D