PDF de programación - REDES DE PETRI: DEFINICIÓN REDES DE PETRI: DEFINICIÓN, FORMALIZACIÓN Y EJECUCIÓN

REDES DE PETRI: DEFINICIÓN
REDES DE PETRI: DEFINICIÓN,
FORMALIZACIÓN Y EJECUCIÓN

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

1

REDES DE PETRI
• Las redes de Petri (RdP) (C.A. Petri, 1962) son una
herramienta de modelado muy efectiva para la
representación y el análisis de procesos concurrentes.

i d

áli

t

t

ió

l

• Modelar un sistema usando redes de Petri tienen tres

ventajas potenciales:
1) El sistema completo es a menudo más fácil de entender debido a la

naturaleza gráfica y precisa del esquema de representación.

2) El comportamiento del sistema puede ser analizado utilizando la teoría

de las redes de Petri, que incluye herramientas para el análisis tales
como los árboles de marcados y establece relaciones entre ciertas
como los árboles de marcados y establece relaciones entre ciertas
estructuras de redes y el comportamiento dinámico. Pueden aplicarse
también técnicas para la verificación de programas paralelos.

3) Puesto que las redes de Petri pueden sintetizarse usando técnicas

"bottom-up" y "top-down", es posible diseñar automáticamente sistemas
cuyo comportamiento es conocido o fácilmente verificable.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

2

1

REDES DE PETRI
• Su éxito se debe básicamente a la simplicidad de su

mecanismo básico, si bien, la representación de grandes
sistemas es costosa.
i t

t

• Para facilitar su uso en diferentes campos de aplicación,

el modelo original se ha extendido en dos aspectos:
1) Introducción de modificaciones estructurales para
incrementar la potencia o la comodidad de modelado
o para facilitar la solución de los problemas de
análisis
análisis.

2) Definición de redes de Petri temporizadas que se
pueden utilizar para analizar cuantitativamente las
prestaciones del sistema modelado.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

REDES DE PETRI:
DEFINICIONES BÁSICAS
Las redes de Petri son un grafo orientado formado por:
• Plazas o lugares representadas mediante circunferencias
Plazas o lugares, representadas mediante circunferencias.
• Transiciones, representadas por segmentos rectilíneos.
• Arcos dirigidos que unen transiciones y plazas.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

3

4

2

REDES DE PETRI:
DEFINICIONES BÁSICAS
• Una plaza p es entrada de una transición t si existe un
arco desde p a t
arco desde p a t.
• Una plaza p es salida de una transición t si existe un arco
desde t a p.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

5

REDES DE PETRI:
MARCADO
• Una plaza puede contener un número positivo o nulo de testigos o
marcas, que se representan por un punto en el interior del círculo
que representa una plaza.

p

q

p

p

• El marcado de una red de Petri es el conjunto de testigos asociados
con cada una de las plazas en un instante dado. Define el estado de
la red de Petri.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

6

3

REDES DE PETRI Y
PROGRAMACIÓN CONCURRENTE

• Transiciones: representan los procesos del

programa
programa.

• Plazas: representan las condiciones

necesarias para que un proceso se ejecute.
• Arcos dirigidos: relacionan condiciones y

• Testigos: si están presentes en una plaza,

procesos.
T ti
l
indican que se verifica la condición que
representa esa plaza.

tá

t

i

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

7

REDES DE PETRI: DISPARO

• Una transición está sensibilizada o

habilitada si todos las plazas de entrada
habilitada si todos las plazas de entrada
están marcadas.

• Una transición habilitada se puede

disparar.

i t

• El disparo de una transición habilitada
l

consiste en quitar un testigo de cada plaza
de entrada y añadir un testigo a cada uno
de las plazas de salida.

d

d

ti

it

t

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

8

4

REDES DE PETRI:
EJEMPLOS DE DISPARO

ANTES

DEL DISPARO

t 1

t 2

DESPUÉS
DESPUÉS

DEL DISPARO

t1

t 2

t 3

t 3

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

9

EVOLUCIÓN DEL MARCADO:
DISPARO DE LA TRANSICIÓN t1

t1

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

10

5

EVOLUCIÓN DEL MARCADO:
DISPARO DE LAS TRANSICIONES t2 ó t3.

t2

t3

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

11

EVOLUCIÓN DEL MARCADO:
DISPARO DE LA TRANSICIÓN t2.

t2

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

12

6

EVOLUCIÓN DEL MARCADO:
DISPARO DE LAS TRANSICIONES t3 ó t4.

t3

t4

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

13

EVOLUCIÓN DEL MARCADO:
DISPARO DE LAS TRANSICIONES t4 ó t5.

t4

t5

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

14

7

EVOLUCIÓN DEL MARCADO

t3

p4

t2

p3

t1

p2

p1

t1

t3

4
p4

t2

p3

t1

p2

p1

t5

p5

t4

t5

p5

t4

t2

t3

t3

t2

p3

t1

p2

p3

t1

p2

p1

p1

t3

p4

t2

t3

p4
p4

t2

t5

p5

t4

t5

p5

t4

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

t5

t3

p4

t2

p3

t1

p2

p1

t4

t5

p5

t4

15

REDES DE PETRI:
FORMALIZACIÓN
• En una red de Petri, se permite que más de un arco

conecte una plaza con una transición o una transición
con una plaza.

l

• Si P es el conjunto de plazas de la red de Petri y T es el

conjunto de transiciones, se define:
• Función incidencia previa, I:P×T  N

I(pi,tj)=número de arcos que unen la plaza pi con la
transición tj.

• Función incidencia posterior, O:T×P  N

O(tj,pi)=número de arcos que unen la transición tj
con la plaza pi.
• Peso o valoración de un arco: etiqueta de valor
I(p,t) u O(t,p). Un arco no etiquetado tiene peso uno.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

16

8

REDES DE PETRI:
FORMALIZACIÓN
Una red de Petri es una cuadrupla RdP=(P,T,I,O)
tal que
tal que

• P es un conjunto finito y no vacío de plazas.
• T es un conjunto finito y no vacío de

transiciones.

• P∩T=Φ
I:P T N es la función de incidencia
• I:P × T N es la función de incidencia
previa.

• O:T × P N es la función de incidencia

posterior.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

17

REDES DE PETRI:
FORMALIZACIÓN
• Una red de Petri es ordinaria si sus funciones
de incidencia sólo pueden tomar valores 0 y 1
de incidencia sólo pueden tomar valores 0 y 1
(todos sus arcos son de peso unitario).

• Una red de Petri es generalizada si sus

funciones de incidencia pueden tomar cualquier
valor entero mayor o igual que cero.

• Una red de Petri es pura o no reflexiva si

ninguna plaza es a la vez entrada y salida de
una misma transición.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

18

9

REDES DE PETRI: MARCADO

• Un marcado M de

de Petri
RdP=(P,T,I,O) es una función desde el conjunto
, ,
de las plazas P al conjunto de los enteros no
negativos N:

una

red

j

(

,

)

M: P  N

• Si n es el número de plazas de la red de Petri,
un marcado puede interpretarse como un
vector de dimensión n, M=(m1,m2,...,mn), en el
que mi es el número de testigos que M asigna a
pi y se verifica M(pi)=mi.

p

p

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

19

REDES DE PETRI MARCADAS

Una red de Petri con un marcado inical M0 es una red de Petri
marcada,C=(RdP,M0):

C=(RdP,M0)
RdP=(P,T,I,O)
P={p1, p2,...,pn}
T={t1, t2,...,tm}
I:P×T  N
O:T×P  N
M0=(m01, m02,..., m0n)

El estado de una red de Petri marcada se define por el número mi de
testigos contenidos en cada plaza pi y se representa por su marcado.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

20

10

REDES DE PETRI MARCADAS:
EJECUCIÓN

Una red de Petri se ejecuta de acuerdo con las siguientes reglas.

1) Una transición t se dice que está habilitada en una red de Petri con un marcado
M si todas sus plazas de entrada contienen al menos tantos testigos como arcos
M si todas sus plazas de entrada contienen al menos tantos testigos como arcos
haya desde cada plaza a la transición, esto es, si M(p)I(p,t) para toda plaza de
entrada de la transición t.
Una transición sin plazas de entrada, lo que se denomina transición fuente, está siempre
habilitada puesto que no tiene restricciones de entrada.

2) Una transición habilitada puede dispararse retirando de cada plaza de entrada
tantos testigos como arcos haya desde la plaza hacia la transición (I(p,t)) y
depositando tantos testigos en cada plaza de salida como arcos haya desde la
transición a la plaza (O(t,p)). La selección de cuál entre todas las transiciones
habilitadas es la próxima en dispararse es arbitraria y se supone que se decide
en un nivel de abstracción inferior.

3) El disparo de una transición modifica la distribución de testigos en las plazas. Si,

desde un marcado Mi, se produce el disparo de una transición t, el nuevo
marcado que se obtiene, Mj, se calcula mediante la expresión:

Mj(p) = Mi(p) + O(t,p) - I(p,t) pP

Los testigos se utilizan para definir la ejecución de la red de Petri. Una transición sin lugares
de salida, lo que se denomina transición sumidero, elimina testigo