propiedades y métodos de análisis de las redes de petri


En la clase de hoy de la asignatura de Programación Concurrente del Máster en Computación hemos tenido la segunda sesión dedicada a las Redes de Petri. Hemos tratado las propiedades básicas que se pueden extraer de un análisis de dichas redes y que luego nos van a ser útiles cuando modelemos sistemas concurrentes con ellas. Hemos visto también clases restringidas y más fácilmente analizables de estas redes. Después hemos repasado los análisis que se pueden hacer en una red de Petri a partir de su árbol de alcanzabilidad (que tiene limitaciones para señalar la vivacidad y no es escalable en su análisis cuando el número de nodos aumenta) o de sus ecuaciones matriciales o de estado. Todo el contenido de esta sesión se encuentra en el documento pdf de los apuntes.

Las propiedades que se pueden extraer de una Red de Petri son: vivacidad (liveness), ciclicidad, limitación (boundedness), conservación, conflictividad y exclusión mutua. Las tres primeras propiedades son independientes.

La vivacidad se define en primer lugar para una transición asegurando que se puede disparar desde cualquier marcado (estado ) M de la Red de Petri. Si todas las transiciones (nodos transición) de una Red de Petri la cumplen se dice que dicha red es “viva”. Esta propiedad es importante por cuanto una red “no viva” en la que alguna de las transiciones es no viva para algún marcado es seguro que tiene un bloqueo total o parcial. Una red viva garantiza una operación libre de puntos muertos.

La ciclicidad está determinada por la existencia de una secuencia de disparos que permite llegar al estado inicial a partir de un estado sucesor de éste. Esto garantiza que no existen subconjuntos de estados finales (a partir de los cuales no son alcanzables algunos de los estados del estado inicial)

La limitación determina si hay un límite de tokens para una plaza dada en la evolución de la red. El límite puede ser 1 o un valor entero k. En el primer caso se habla de una plaza segura (o red segura o binaria si todas las plazas de la red lo cumplen) El interés de esta propiedad estriba en que una red limitada puede implementarse con recursos finitos.

La conservación implica que todos los tokens que se generan y consumen en la red se mantiene constante, lo cual se puede interpretar como que los recursos disponibles no pueden variar durante la ejecución de la red. Esta condición se suele relajar permitiendo una inconstancia limitada a un número sacado de un vector de pesos.

El conflicto es una de las propiedades más interesantes ya que suele representar estados del modelo inaceptables. Hay dos tipos: estructural y efectivo. El primero se produce cuando una plaza posee más de una transición de salida. El segundo se produce entre dos transiciones para un marcado dado cuando existe una marcado alcanzable desde dicho marcado en el cual se habilitan las dos transiciones de forma simultánea y al dispararse una de ellas, el marcado (estado) resultante no habilita a la otra. El conflicto se puede generalizar de dos a N transiciones. Si una red de Petri no tiene ningún conjunto de transiciones que estén en conflicto para ningún marcado se llama persistente.

Existe un último concepto llamado exclusión mutua que para el caso de dos transiciones coincide con el conflicto efectivo. El matiz es que en el caso de un conjunto de N transiciones, la exclusión mutua se produce cuando todas las demás del subconjunto elegido se inhabilitan, no solamente alguna. La exclusión mutua también se puede producir entre dos plazas cuando no pueden estar marcadas de forma simultánea.

Finalmente hemos tratado las subclases de redes de Petri que existen que simplifican su análisis restringiendo su expresividad. Las subclases son: máquinas de estados (cada transición tiene una entrada y una salida), grafos marcados (cada plaza tiene una entrada y un salida), red de libre elección y red de petri simple (cada transición tiene como máximo una plaza de entrada compartida con otra transición)

Las máquinas de estados representan procesos secuenciales con conflictos o alternativas pero no paralelismo, concurrencia o sincronización. Los grafos marcados por el contrario representan perfectamente lo segundo pero no lo primero. Las redes de libre elección son una mezcla entre las dos anteriores, en la que se permite una forma restringida de conflicto en la que se pueden encontrar las condiciones necesarias y suficientes para que la Red de Petri de libre elección marcada sea viva y segura.

El uso de las técnicas matriciales debe de hacerse con cuidado, sobretodo al interpretar los resultados. Así por ejemplo la obtención de una secuencia de disparo de estados a partir de M’ = M + y.C simplemente nos da el número de transiciones de cada tipo que se pueden producir que representan un conjunto de secuencias, no una secuencia concreta. Además, puede suceder que muchas o incluso todas las secuencias que se puedan obtener no representen secuencias válidas para el sistema que se modela.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s