|
|
INTRODUCCIÓN A LAS REDES DE PETRI.
Debemos definir previamente a las redes de Petri lo que son
los procesos concurrentes y sus problemas para poder comprender y
especificar posteriormente una red de Petri, los requisitos que
debe cumplir y su funcionamiento.
PROCESOS CONCURRENTES.
Son los procesos lanzados en procesadores con múltiples
unidades funcionales o múltiples CPU's. Pueden ejecutar varias
instrucciones a la vez, además el hardware permite la existencia
de varios procesos y el procesador puede conmutar entre ellos y
ejecutar instrucciones de varios procesos saltando entre ellos.
Existen instrucciones en la programación concurrente de alto
nivel, para que un proceso denominado padre cree uno o
varios procesos denominados procesos hijo. El
inconveniente de los procesos concurrentes es que hagan
operaciones sobre variables comunes. Esto genera varios problemas
que podemos observar en los ejemplos.
Ejemplo: Lanzamiento de cinco procesos concurrentes que constan de una sola instrucción.
cobegin
P1: a:=4;
P2: b:=3;
P3: d:=a-b;
P4: d:=d+1;
P5: d:=d+1;
coend
Estos cinco procesos comparten las variables a, b y d. Si suponemos que el orden de la ejecución es el descrito, el valor de d es d=3. Evidentemente no podemos presuponer ningún orden en la ejecución. Supongamos la siguiente sucesión de eventos:
| Inicialmente | {a=?, b=?, d=?} | |
P3: d:=a-b; |
{a=?, b=?, d=?} | |
Pl: a:=4; |
{a=4, b=?, d=?} | |
P2: b:=3; |
{a=4, b=3, d=?} | |
P4: d:=d+l; |
{a=4, b=3, d=?} | |
P5: d:=d+l; |
{a=4, b=3, d=?} |
Al finalizar los procesos desconocemos el valor de d. Esto ocurre porque no se ha respetado la precedencia en la ejecución de los procesos. Supondremos que la sentencia "d:=d+1" se ejecuta mediante tres instrucciones máquina independientes:
registroCPU:=d;
registroCPU:=registroCPU+ 1;
d:=registroCPU;
Supongamos ahora la siguiente sucesión de eventos:
| Inicialmente | {a=?, b=?, d=?} | |
P2: b:=3; |
{a=?, b=3, d=?} | |
Pl: a:=4; |
{a=4, b=3, d=?} | |
P3: d:=a-b; |
{a=4, b=3, d=l} | |
P4:
registroCPU:=d; |
{a=4, b=3, d=l} | |
P4:
registroCPU:=registroCPU+ 1; |
{a=4, b=3, d=l} | |
P5:
registroCPU:=d; |
{a=4, b=3, d=l} | |
P5: registroCPU:
=registroCPU+ 1; |
{a=4, b=3, d=l} | |
P5:
d:=registroCPU; |
{a=4, b=3, d=2} | |
P4:
d:=registroCPU; |
{a=4, b=3, d=2} |
Se observa que el proceso P4 ha sido interrumpido mientras operaba sobre d. Los incrementos en d que deberían haber tenido como resultado d=3 han dado d=2.
Al recurso al que pueden acceder varios procesos concurrentes
a la vez se le denomina sección crítica.
Hemos observado dos errores en el ejemplo:
La solución a los problemas de sincronización y exclusión mutua se pueden resolver mediante la herramienta semáforo. Un semáforo S es una variable entera que posteriormente a su inicialización, sólo puede ser accedida por dos operaciones estándar e indivisibles denominadas P y V.
La definición clásica de P y V es:
P(S): if S>0 then S:=S-lelse Skip; /* espera activa */V(S): if (hay procesos en cola) then liberar el primeroelse S:=S+l;
Si suponemos semáforos binarios, semáforos que solo pueden tomar el valor 0 o 1, y los procesos concurrente son de la forma:
Pl:
P(S1);
a:=4;
V(S3);
P2:
P(S2);
b:=3;
V(S4);
P3:
P(S3);
P(S4);
d:=a-b;
V(S5);
P4:
P(S5);
d:=d+ 1;
V(S6);
P5:
P(S6);
d:=d+l;
Inicialización de los semáforos y lanzamiento de los procesos concurrentes:
begin
S1:=1;
S2:=1;
S3:=0;
S4:=0;
S5:=0;
cobegin
Pl;
P2;
P3;
P4;
P5;
coend;
end
La modelización matemática que conllevan los procesos concurrentes, los problemas de precedencia y los problemas de exclusión mutua sobre secciones criticas se resuelven mediante la utilización de Redes de Petri que a continuación describimos.
DEFINICION DE LAS REDES DE PETRI.
Generalidades:
Las redes de Petri se utilizan para modelizar el comportamiento dinámico de sistemas discretos.
Se componen de dos tipos de objetos:
Mediante una red de Petri puede modelizarse un sistema de evolución en paralelo compuesto de varios procesos que cooperan para la realización de un objetivo común.
En general, la presencia de marcas en una plaza se interpreta como la presencia de recursos. El franqueo de una transición (la acción a ejecutar) se realiza cuando se cumplen unas determinadas precondiciones, indicadas por las marcas en las plazas (hay una cantidad suficiente de recursos), y la transición (ejecución de la acción) genera unas postcondiciones que modifican las marcas de otras plazas (se liberan los recursos) y así se permite el franqueo de transiciones posteriores.
Definición: Una red de Petri es un conjunto formado por R={P, T, Pre, Post}
P: Conjunto de plazas de cardinal n.
T: Conjunto de transiciones de cardinal m.
Pre: Aplicación de incidencia previa. Viene definida como:
Pre:PxT --> Naturales
Post: Aplicación de incidencia posterior. Viene definida como:
Post:PxT --> Naturales
Definición: Una red marcada es el conjunto formado por {R, M} donde:
R es una Red de Petri como la definida.
M es una aplicación denominada marcado.
M: P -->Naturales
Se asocia a cada plaza un número natural, denominado marca. Las
marcas para una plaza se reunen en columnas.
Para las aplicaciones Pre y Post existe una notación matricial.
Ejemplo: Sea una red de Petri con cinco plazas (1..5) y cinco transiciones (a..e), que denominaremos R1.
| Pre | a | b | c | d | e | Post | a | b | c | d | e | |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | |
| 2 | 0 | 1 | 0 | 0 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | |
| 3 | 0 | 0 | 1 | 0 | 0 | 3 | 1 | 0 | 0 | 0 | 1 | |
| 4 | 0 | 0 | 0 | 1 | 0 | 4 | 0 | 1 | 0 | 0 | 0 | |
| 5 | 0 | 0 | 0 | 1 | 1 | 5 | 0 | 0 | 1 | 0 | 0 |
Las columnas se denotan por Pre(. , t), y las filas se denotan por Post(. , p).
Número de marcas asociados a la plazas. M0 el marcado definido por. Las marcas para todas las plazas se reunen por columnas:
| M0 |
| 1 |
| 0 |
| 0 |
| 0 |
| 0 |
Definición: La condición para que una red sea degenerada es que alguna fila o columna de las aplicaciones Pre o Post sea cero.
Definición: Una red es pura si cumple lo siguiente Pre(p,t) * Post(p,t)= 0 (para todo p y t).
Definición: Grafo asociado a una red:
Una red de Petri tiene un grafo orientado bipartido, que se
define como:
P unión T, que es el conjunto de vértices.
F: P unión T --> Partes de (P unión T), que es el conjunto
de arcos.
El grafo {P, T, F, V} asociado a la red R={ P, T, Pre, Post) es:
F(p)={t pertenece a T si Pre(p,t)>0, para todo p}
F(t)={p petenece a T si Post(p,t)>0, para todo t}
V(p,t)=Pre(p,t)
V(t,p)=Post(p,t)
V es la valoración de los arcos.
La definición del grafo indica que los arcos solo pueden ir:
Desde las plazas hasta las transiciones.
Desde las transiciones hasta las plazas.
En la representación de una red de Petri, se omiten los arcos
valorados con 0, y el 1 en los arcos valorados con 1.
Las plazas se representan mediante círculos, las transiciones
mediante rectángulos horizontales o líneas horizontales, y las
marcas mediante puntos en el interior de las plazas.
Ejemplo: Representación como grafo de la red de Petri, R1.
F(1)={a}
F(2) ={b}
F(3) ={c}
F(4)={d}
F(5) = {d,e}
F(a)={2,3}
F(b)={4}
F(c)={5}
F(d)={1}
F(e)={3}
Definición: Una transición t es franqueable si para un marcado M se cumple:
M(p) >= Pre(p,t) ; (para todo p)
Esto se indica con la notación M(t> ... y es la
precondición de franqueo.
Significa que el marcado permite el franqueo de la transición t.
Si una transición t es franqueable para M, el franqueo define un
nuevo marcado M'.
Este nuevo marcado se define como:
M'(t) = M(p) - Pre(p,t) + Post(p,t) (para todo p)
M' se deduce de M y se denota M(t >M' (M da M' por t).
Para una red, t es franqueable para M si las plazas p de entrada
de t tienen un número de marcas superior a la del arco (p,t). Se
eliminan V(p,t) marcas de cada plaza de entrada t y se añaden
V(t,p) marcas a cada plaza de salida t.
Se observa que,
M >= Pre(. , t) and M(t >M' => M' >= Post(. ,t)
El marcado mínimo que permite el franqueo de t es Pre(p,t).
El marcado mínimo que se obtiene del franqueo de t es Post(p,t).
Ejemplo: Funcionamiento de la red de Petri, R1:
Y los sucesivos marcados que se obtienen son:
| M0 | M1 | M2 | M3 | M4 | ||||
| 1 | 0 | 0 | 0 | 0 | ||||
| 0 | 1 | 0 | 1 | 0 | ||||
| 0 | 1 | 1 | 0 | 0 | ||||
| 0 | 0 | 1 | 0 | 1 | ||||
| 0 | 0 | 0 | 1 | 1 |
Dado el ejemplo anterior se observa que:
M0(a> significa que la transición a es
franqueable para el marcado M0.
M0(a>M1 significa que la transición a
es franqueable para el marcado M0 y da el marcado M1.
La transición b no es franqueable para el marcado M0.
En este momento se puede observar la similitud con los procesos concurrentes:
Las plazas son los semáforos.
Las marcas el entero que inicializa al semáforo y su posterior
evolución..
Las transiciones son el código de una seccion critica que
utiliza los procesos concurrentes.
La entrada a las secciones criticas está gobernada por los
semáforos.
Ejemplo: Implementación de la red de Petri, R1, utilizando semáforos. Se puede descomponer en cinco procesos concurrentes:
P1:
P(semáforo1);
/* transición a */
V(semáforo2);
V(semáforo3);
P2:
P(semáforo3);
/* transición c */
V(semáforo5);
P3:
P(semáforo4);
P(semáforo5);
/* transición e */
V(semáforo1);
P4:
P(semáforo2);
/* transición b */
V(semáforo4);
P5:
P(semáforo4);
/* transición d */
V(semáforo2);
Inicialización de los semáforos y lanzamiento de los procesos concurrentes:
begin
semáforo1:=1;
semáforo2:=0;
semáforo3:=0;
semáforo4:=0;
semáforo5:=0;
cobegin
P1;
P2;
P3;
P4;
P5;
coend;
end
Definición: Dos transiciones t1 y t2 están en conflicto estructural si, existe un p, tal que, Post(p, t1) * Post(p, t2) sea distinto de 0.
Si tienen al menos una plaza de entrada en común.
Definición: Dos transiciones están en conflicto efectivo para un marcado M si además de cumplirse, M(t1> , M(t2> y existe un p tal que M(p) <Pre(p, t1) + Pre(p,t2)
Un conflicto efectivo consiste en una elección entre franqueos.
Problema de los filósofos: (Dijkstra 1965, problema 5.13 de Sistemas Operativos, H. M. Deitel)
Cinco filósofos están sentados alrededor de una mesa circular. Los cinco llevan una vida muy sencilla que alternan entre pensar y comer. Frente a cada filósofo hay un plato de comida que un criado mantiene lleno todo el tiempo. Hay exactamente cinco tenedores en la mesa , uno entre cada par de filósofos adyacentes. Para comer cada filósofo debe utilizar simultáneamente los dos tenedores adyacentes a su plato.
La modelización de las aplicaciones Pre y Post son:
| Pre | a | b | c | d | e | Post | a | b | c | d | e | |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 2 | 1 | 1 | 0 | 0 | 0 | 2 | 1 | 1 | 0 | 0 | 0 | |
| 3 | 0 | 1 | 1 | 0 | 0 | 3 | 0 | 1 | 1 | 0 | 0 | |
| 4 | 0 | 0 | 1 | 1 | 0 | 4 | 0 | 0 | 1 | 1 | 0 | |
| 5 | 0 | 0 | 0 | 1 | 1 | 5 | 0 | 0 | 0 | 1 | 1 |
El marcado inicial es:
| M0 |
| 1 |
| 1 |
| 1 |
| 1 |
| 1 |
El grafo asociado a la red es:
Comentarios a la red del problema de los filósofos:
La red no es degenerada, según la definición no hay ninguna fila o columna de las aplicaciones Pre o Post igual a 0.
La red no es pura, existe plazas y transiciones tal que Pre(p,t)*Post(p,t) distintas de 0. Ejemplo, Pre(1,a)*Post(1,a)<>0.
La red contiene un conflicto estructural, existen plazas tal que Post(p,t1)*Post(p,t2)<>0. Ejemplo, Post(2,a)*Post(2,b)<>0.
La red contiene un conflicto efectivo, dado el marcado M0, todas las transiciones son franqueables.
De hecho, M0(cualquier transicion>M0. Esto significa que dado el marcado M0 hay que "decidir" que transición se ejecuta.
Modelización de la red de Petri obtenida con procesos concurrentes:
Observación: Debe tenerse en cuenta que en el modelo teórico, el borrado de las marcas es simultáneo e instantáneo pero al modelarlo como proceso concurrente existe la posibilidad de un abrazo mortal por lo que para la codificación se ha optado por un modelo asimétrico en el proceso que modela el comportamiento de un filósofo.
Los procesos concurrentes son:
Pa:
P(S2);
P(S1);
/* el filósofo a come */
V(S1);
V(S2);
Pb:
P(S2);
P(S3);
/* el filósofo b come */
V(S3);
V(S2);
Pc:
P(S4);
P(S3);
/* el filósofo c come */
V(S3);
V(S4);
Pd:
P(S4);
P(S5);
/* el filósofo d come */
V(S5);
V(S4);
Pe:
P(S1);
P(S5);
/* el filósofo e come */
V(S5);
V(S1);
Inicialización de los semáforos y lanzamiento de los procesos concurrentes:
begin
S1:=1;
S2:=1;
S3:=1;
S4:=1;
S5:=1;
cobegin
Pa;
Pb;
Pc;
Pd;
Pe;
coend;
end
Problema de los fumadores de cigarrillos: (Patil 1971, problema 5.19 de Sistemas Operativos, H. M. Deitel)
Tres fumadores están representados por los procesos F1, F3 y F3. Tres vendedores están representados por los procesos V1, V2 y V3. Para fumarc cada fumador necesita tabaco, papel para tabaco y un fósforo; cuando dispone de estos recursos, el fumador fuma un cigarrillo hasta terminarlo y entonces queda elegible para fumar de nuevo. F1 tiene tabaco, F2 tiene papel y F3 tiene fósforos. V1 vende tabaco y papel, V2 vende papel para tabaco y fósforos, y V3 vende fósforos y tabaco. V1, V3 y V3 trabajan en exclusión mutua; sólo uno de los procesos puede trabajar a la vez y el siguiente vendedor no puede trabajar hasta que los recursos suministrados por el vendedor anterior hayan sido consumidos por un fumador.
La modelización de las aplicaciones Pre y Post son:
| Pre | V1 | V2 | V3 | F1 | F2 | F3 | Post | V1 | V2 | V3 | F1 | F2 | F3 | |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | |
| 2 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 3 | 0 | 0 | 0 | 1 | 0 | 0 | 3 | 0 | 1 | 0 | 0 | 0 | 0 | |
| 4 | 0 | 0 | 0 | 0 | 1 | 0 | 4 | 0 | 0 | 1 | 0 | 0 | 0 |
El marcado inicial es:
| M0 |
| 1 |
| 0 |
| 0 |
| 0 |
El grafo asociado a la red es:
Comentarios a la red del problema de los fumadores:
La red no es degenerada, según la definición no hay ninguna fila o columna de las aplicaciones Pre o Post igual a 0.
La red es pura, Pre(p,t)*Post(p,t)<>0 para todo p y t.
La red contiene un conflicto estructural en la plaza 1, Post(1,V1)*Post(1,V2)<>0.
La red contiene un conflicto efectivo, dado el marcado M0,
M0(V1> y M0(V2> además para la plaza
2,
M(2)<Pre(2,V1)+Pre(2,V2). Esto significa que dado el marcado M0
hay que "decidir" que transición se ejecuta.
Modelización de la red de Petri obtenida con procesos concurrentes:
Observación: Debe tenerse en cuenta el conflicto estructural aparecido en la red, en los procesos reales, la decisión se resuelve en tiempo de ejecución, se ejecutará el primer proceso que realice la operación V sobre el semáforo.
Los procesos concurrentes son como se describe a continuación:
P_V1:
P(S1);
/* V1 vende tabaco y papel */
V(S2);
P_V2:
P(S1);
/* V2 vende papel y fósforos */
V(S3);
P_V3:
P(S1);
/* V3 vende fósforos y tabaco */
V(S4);
P_F1:
P(S3);
/* F1 tiene tabaco ha comprado papel y fósforos a V2, puede fumar en exclusión mutua */
V(S1);
P_F2:
P(S4);
/* F2 tiene papel ha comprado fósforos y tabaco a V3, puede fumar en exclusión mutua */
V(S1);
P_F3:
P(S2);
/* F3 tiene fósforos ha comprado papel y tabaco a V1, puede fumar en exclusión mutua */
V(S1);
Inicialización de los semáforos y lanzamiento de los procesos concurrentes:
begin
S1:=1;
S2:=0;
S3:=0;
S4:=0;
cobegin
P_V1;
P_V2;
P_V3;
P_F1;
P_F2;
P_F3;
coend;
end
| Web PEMH | Top of page | pedrmar@mixmail.com |
| Esta página ha sido visitada,
|
The same author's pages web:
Fecha de la última actualización: 11 enero, 2001.
