PDF de programación - EXTENSIONES DE LAS REDES DE PETRI: TEMPORIZACIÓN

EXTENSIONES DE LAS REDES
EXTENSIONES DE LAS REDES
DE PETRI: TEMPORIZACIÓ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

REDES DE PETRI:
EXTENSIONES
Se han introducido extensiones en las redes de Petri para
incrementar la potencia de modelado o para conseguir
d
descripciones más condensadas de la herramienta. Las
extensiones más importantes son:

d l h

d

i

i

d

á

i

t

L

• Redes de Petri generalizadas (RPG)
• Red de Petri con capacidad limitada (RPC)
• Redes de Petri con transiciones no estándar
• Redes de Petri coloreadas
• Red de Petri con arcos inhibidores (RPAI)
• Redes de Petri temporizadas

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

22/10/2012

1

1

2

22/10/2012

REDES DE PETRI:
EXTENSIONES

• Redes de Petri generalizadas (RPG) son aquellas en las que se introduce un

peso en los arcos. Un arco no etiquetado es de valoración unidad.
Redes de Petri con capacidad limitada (RPC)
• Redes de Petri con capacidad limitada (RPC) son aquellas en la que la
capacidad para contener testigos de cada plaza está limitada a un valor máximo.
Una transición estará habilitada sólo si en todos los lugares de entrada hay marcas
y si el marcado que resulte de su disparo no viola las restricciones de capacidad
establecidas.

ll

l

l

• Redes de Petri con transiciones no estándar son aquellas en las que se

modifica la regla de disparo de las transiciones.

y

g

• Redes de Petri coloreadas son aquellas en las que cada arco de entrada a las
transiciones y cada testigo pueden llevar asociado un color que los diferencie de
otros. A cada lugar y a cada transición se les asigna unos conjuntos de colores. Los
colores de las marcas pueden ser modificados por el disparo de una transición.
La regla de disparo depende del color de los testigos y se puede incluir en el
modelado del evento el conocimiento del origen del testigo. Las redes de Petri
coloreadas se utilizan para condensar la descripción y el análisis de sistemas en los
que se identifican diferentes subsistemas independientes pero que operan en
paralelo o de forma síncrona.

g

j

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

3

REDES DE PETRI:
EXTENSIONES

• Red de Petri con arcos inhibidores (RPAI) es aquella a la que se añaden arcos

inhibidores. Un arco inhibidor conecta una plaza a una transición (partiendo
siempre de la plaza) y se representa por una línea que termina con un círculo (en
siempre de la plaza) y se representa por una línea que termina con un círculo (en
vez de con una flecha) en la transición.

La condición de disparo de una transición se generaliza diciendo que una transición
está habilitada cuando todas sus plazas de entrada unidas a la transición con arcos
normales contienen al menos tantos testigos como arcos hay desde cada plaza a la
transición (I(p,t)) y no hay ningún testigo en las plazas de entrada unidas a las
transiciones por arcos inhibidores. El disparo de la transición t retira I(p,t) testigos de
cada una de sus plazas de entrada normales y añade O(t,p) testigos a sus plazas de
salida.

A
Arco inhibidor

i hibid

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

4

2

REDES DE PETRI:
EXTENSIONES
• Redes de Petri temporizadas son redes de Petri en las

que se introduce el tiempo de duración de los eventos.
li
N
Normalmente, esta extensión se realiza asociando con
cada transición un tiempo de disparo.

i d

ió

t

l

t

t

• La introducción del tiempo en los modelos de redes de

Petri estándar permite la descripción del
comportamiento dinámico del sistema, teniendo en
cuenta tanto los cambios de estado como la duración de
cada acción realizada por el mismo.

• Estas redes son las de mayor interés para los procesos

de descripción y evaluación de los sistemas
concurrentes.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

REDES DE PETRI
TEMPORIZADAS
• Se han propuesto diferentes maneras de introducir el
t

tiempo en una red de Petri, lo que da lugar a diferentes
clases de redes de Petri temporizadas. Básicamente,
l
Bá i
se pueden clasificar en dos grandes grupos:
deterministas y probabilísticas.

d P t i t

i d

d

d

• En las RdP deterministas, se supone que los tiempos

de llegada y de ejecución de las tareas y la
sincronización consiguiente se conocen antes del
análisis.

• En las RdP probabilísticas, la velocidad de llegada y
los tiempos de servicio de las tareas se especifican
mediante funciones de distribución de probabilidad. Se
analizan utilizando la teoría de los procesos de Markov.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

5

6

22/10/2012

3

REDES DE PETRI
TEMPORIZADAS
Algunas de las clases más importantes de redes
de Petri temporizadas son:
de Petri temporizadas son:

1) Redes de Petri con tiempos deterministas (TPN).
2) Redes de Petri estocásticas (SPN).
3) Redes de Petri estocásticas generalizadas (GSPN).
4) Redes de Petri con tiempos deterministas

generalizadas (GTPN).
(GTPN)

li d

5) Redes de Petri estocásticas extendidas (ESPN).

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

REDES DE PETRI CON TIEMPOS
DETERMINISTAS (TPN)

• Una posibilidad para introducir el tiempo en las redes de Petri
consiste en asociar con cada transición un número que indica el
retraso temporal que se produce desde que una transición se
retraso temporal que se produce desde que una transición se
habilita hasta que se dispara.

• Cuando este retraso es una cantidad fija, las redes de Petri se
denominan redes de Petri con tiempos deterministas (Timed
Petri Nets, TPN).

• Las restricciones temporales de una TPN pueden hacer que tenga

menos estados que la RdP asociada.
PROBLEMAS:
• PROBLEMAS:
• Resolución de los conflictos no definida.
• Permiten sólo la validación de los sistemas modelados; no hay

métodos de evaluación.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

7

8

22/10/2012

4

REDES DE PETRI CON TIEMPOS
DETERMINISTAS (TPN)

• En la figura (b), se muestra la máquina de testigos

de la RdP de la figura (a) si se considera no
temporizada.

• En la figura (c), se muestra la máquina de testigos
de la RdP de la figura (a) si se considera
temporizada y el tiempo de disparo de la transición
t2 es menor que el tiempo de disparo de las
transiciones t3 y t4.

• Las restricciones temporales de la RdP impiden

que se alcancen algunos de los estados de la figura
(b).

(a)

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

(b)

(c)
(c)

9

REDES DE PETRI CON TIEMPOS
DETERMINISTAS (TPN)

• En la figura, se muestra una TPN. Junto a cada transición, se

muestra su tiempo de disparo, i. Esta red modela el
comportamiento de una unidad de procesado que necesita la
comportamiento de una unidad de procesado que necesita la
posesión de un recurso compartido con otras unidades. Un testigo
en p3 significa que el recurso está disponible y un testigo en p1
representa el estado inicial de la unidad de procesado, cuando no lo
necesita.

(0,1,1,0)

(1,0,1,0)

t1
1

t2
2

(0,0,0,1)
t3
3
(1,0,1,0)

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

10

22/10/2012

5

22/10/2012

REDES DE PETRI
ESTOCÁSTICAS (SPN)

• En las redes de Petri estocásticas (SPN) se utilizan variables aleatorias

para especificar el comportamiento temporal del modelo.

• En las SPN, se asocia con cada transición de la red de Petri una variable
aleatoria geométrica o exponencialmente distribuida que expresa el retraso
desde la habilitación hasta el disparo de la transición. Se pueden analizar
matemáticamente utilizando la teoría de las cadenas de Markov
homogéneas en tiempo discreto o continuo, respectivamente.
La combinación de las redes de Petri, con su capacidad de descripción de
las sincronizaciones y paralelismos de tareas, y de un modelo estocástico,
con su capacidad de abstraer el comportamiento estacionario del sistema,
constituye una de las herramientas más potentes de que se dispone para
evaluar las prestaciones de sistemas de cálculo complejos
evaluar las prestaciones de sistemas de cálculo complejos.

•

• VENTAJAS: Resolución de conflictos y herramientas de análisis.
• DESVENTAJAS: El número de estados de la SPN es el mismo que el del

la red de Petri asociada.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

11

REDES DE PETRI ESTOCÁSTICAS
GENERALIZADAS (GSPN)

•

•

•

p

Las redes de Petri estocásticas generalizadas (Generalized SPN,
GSPN) tienen transiciones de dos clases diferentes: inmediatas y
temporizadas.
Las transiciones inmediatas se disparan instantáneamente (en tiempo
cero) una vez que están habilitadas.
Las transiciones temporizadas se disparan después de un tiempo de
habilitación aleatorio exponencialmente distribuido.

•

• Se adopta el convenio de dibujar las transiciones temporizadas con trazo

grueso y las transiciones inmediatas con trazo fino. Los tiempos de disparo
están asociados sólo con las transiciones temporizadas y pueden depender
del marcado de la GSPN.
del marcado de la GSPN.
Las GSPN asocian el tiempo sólo con los eventos que tengan un mayor
impacto sobre el comportamiento del sistema. En el caso de un sistema
que realice tareas cuya duración difiera en varios órdenes de magnitud, las
actividades cortas se pueden modelar sólo desde el punto de vista lógico y
el tiempo se puede asociar con las má