PDF de programación - REDES DE PETRI: MODELADO DE SISTEMAS CONCURRENTES

REDES DE PETRI: MODELADO
REDES DE PETRI: MODELADO
DE SISTEMAS CONCURRENTES

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

MODELADO DE SISTEMAS
UTILIZANDO REDES DE PETRI
• Una red de Petri representa un sistema
cuando se asigna un significado o una
cuando se asigna un significado o una
interpretación a las plazas, transiciones y
testigos.

• La descripción de un sistema mediante una

red de Petri se basa en dos conceptos:

t

E
• Evento.
• Condición.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

22/10/2012

1

2

1

22/10/2012

REDES DE PETRI:
EVENTOS Y CONDICIONES
• Un evento es una acción que ejecuta el sistema. Se modela

mediante una transición.

• La realización de un evento depende del estado del sistema,
que se describe mediante un conjunto de condiciones, que
se modelan mediante las plazas.

• Los arcos que conectan las transiciones y las plazas
representan la dependencia entre los eventos y las
condiciones.

• La verificación de una condición se representa situando un

testigo dentro de la plaza que lo modela.

• Una RdP marcada representa la coordinación entre eventos.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

3

EJEMPLO DE MODELADO
CON REDES DE PETRI
Máquina de venta
Esta máquina se encuentra inicialmente en espera.
Cuando recibe un pedido, lo procesa y lo envía. Mientras está
procesando el envío, no acepta ningún otro.

CONDICIONES

EVENTOS

a) La máquina se encuentra parada

en espera.

b) U
b) Un pedido ha llegado y está la

did h ll

tá l

d

espera de su proceso.

c) La máquina está trabajando en un

pedido.

d) El pedido está listo para su envío.

1) Un pedido llega.
2) La máquina comienza a

procesar un pedido.

did

3) La máquina finaliza un pedido.
4) El pedido es enviado.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

4

2

22/10/2012

EJEMPLO DE MODELADO
CON REDES DE PETRI

CONDICIONES

a) La máquina se encuentra

parada en espera.

b) Un pedido ha llegado y está

la espera de su proceso.

c) La máquina está trabajando

en un pedido.

d) El pedido está listo para su

envío.

EVENTOS
1) Un pedido llega.
2) La máquina comienza a
2) La máquina comienza a

procesar un pedido.

PRECONDICIÓN
Ninguna
a b
a, b

POSTCONDICIÓN
b
c
c

3) La máquina finaliza un

pedido.

4) El pedido es enviado.

c

d

d, a

Ninguna

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

5

MODELADO DE SISTEMAS
UTILIZANDO REDES DE PETRI
• La comprensión del funcionamiento de un sistema

p j

complejo es más fácil si su descripción se aborda de
forma estructurada y modular.

p

• En gran número de aplicaciones complejas, los

sistemas concurrentes se describen sincronizando
las descripciones (realizadas independientemente)
de diferentes subsistemas o módulos.
A
• A continuación, se muestran algunos esquemas de
d
interconexión o sincronización entre subsistemas.

ió

ti

t

l

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

6

3

ESQUEMAS DE SINCRONIZACIÓN
ENTRE MÓDULOS

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

ESQUEMAS DE SINCRONIZACIÓN
ENTRE MÓDULOS

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

22/10/2012

7

8

4

22/10/2012

CONCURRENCIA, CONFLICTOS Y
SINCRONIZACIÓN
• Las redes de Petri pueden describir

fácilmente sistemas en los que se
producen relaciones de paralelismo,
exclusión mutua y sincronización
entre procesos que ocurren en ellos.

q

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

9

EXCLUSIÓN MUTUA ENTRE
SECCIONES CRÍTICAS

p

• Cuando varios procesos que se
ejecutan en paralelo comparten
j
información, es necesario garantizar
que los accesos a la información
común no se lleve a cabo
simultáneamente para evitar
problemas de interferencia que
conduzcan a resultados erróneos.
• Una solución a este problema es

p

hacer mutuamente excluyentes las
secciones críticas de los diferentes
procesos encargadas de acceder a la
procesos encargadas de acceder a la
información. En la figura, se muestra
una RdP que resuelve este problema.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

10

5

SINCRONIZACIÓN DE TAREAS
PRODUCTOR/CONSUMIDOR

•

Los procesos productor/consumidor involucran elementos de datos
compartidos por ambos procesos y, en consecuencia, es necesario plantear
tareas de sincronización entre ambas.

• En las figuras, se muestran dos procesos de este tipo. El primero supone la

existencia de un buffer infinito capaz de absorber la diferencia de velocidad entre
el productor y el consumidor. El segundo limita la capacidad de este buffer a n
unidades del producto.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

11

PROBLEMA DE LA CENA DE
LOS FILÓSOFOS

•

•

•

Este es un problema de sincronización
para la utilización compartida de recursos.
Supónganse un conjunto de cinco
filósofos que se reúnen para cenar y
filosofar. La comida es china y se
presenta la dificultad de que a cada
comensal sólo le han colocado un palillo.
Con el fin de cenar, llegan a la solución de
que cada comensal puede utilizar el palillo
del comensal que tiene a su izquierda,
siempre que él tenga el suyo (no se lo
haya cogido el de su izquierda) y el
comensal de la derecha no esté
comiendo
comiendo.
En la figura, se muestra una red de Petri
que representa la dinámica que sigue esta
comida.

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

12

22/10/2012

6

22/10/2012

PROCESOS DE LECTURA Y ESCRITURA SOBRE
UN RECURSO COMÚN

• Se supone que existen procesos de dos tipos: procesos de lectura y de escritura. Todos los procesos
comparten un recurso común sobre el que escriben y leen. Los procesos de lectura no modifican la
información y, en consecuencia, todos ellos son compatibles entre sí. Por el contrario, el proceso de
escritura modifica la información y, por tanto, es excluyente con cualquier otro proceso de lectura y de
escritura modifica la información y, por tanto, es excluyente con cualquier otro proceso de lectura y de
escritura. Se pretende establecer el proceso de control que permita el acceso a todos y que no conduzca al
sistema a ningún bloqueo.

• En la figura (a), se muestra una solución para el caso de que el número de lectores que simultáneamente

pueden acceder al recurso sea finito e igual a n.

• En la figura (b), se muestra una solución para el caso en que se considera que el número de lectores es
indefinido y que todos ellos pueden acceder simultáneamente al recurso. En este caso, el problema de
control no tienen solución desde las redes de Petri ordinarias y es necesario acudir a redes de Petri con
arcos inhibidores.

(a)

(b)

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

13

SEMÁFOROS P,V

• Uno de los métodos de sincronización para el

acceso a recursos compartidos más utilizado es el
de los semáforos, basados en las operaciones
d S l
P(S) V(S)
P(S) y V(S), siendo S el semáforo sobre el que
actúa las operaciones.

áf

b

l

i

• Un semáforo es una variable que sólo puede

tomar valores enteros no negativos. La operación
V(S) incrementa el valor de S en 1 y la operación
P(S) decrementa S en 1. La operación P puede
ocurrir sólo cuando S tenga un valor positivo. Si S
tiene el valor 0, la operación P tiene que esperar
hasta que algún otro proceso realice una
operación V sobre el mismo semáforo.
E t
modeladas mediante una red de Petri, como se
muestra en la figura. Cada semáforo es modelado
como una plaza; las operaciones P utilizan dicho
lugar como entrada y las operaciones V lo utilizan
como salida.

• Estas operaciones pueden ser fácilmente

fá il

d

t

i

Programación Concurrente:
Redes de Petri

Mercedes Granda

Departamento de Electrónica y Computadores

14

7