Clase Red de Petri para Usos de Recursos Binarios Ordenados

Carlos A. Rovetto, Tomás J. Concepción, Elia E. Cano
Dpto. de Ciencias de la Computacióna
Universidad Tecnológica de Panamá
{carlos.rovetto, tomas.concepcion1, elia.cano}@utp.ac.pa

Resumen-La prevención/evitación de los bloqueos mutuos es un dominio de investigacion activo que exige aplicar diversas políticas de control para hacer frente a este problema. En este artículo presentamos una subclase de Red de Petri especializada llamada Clase red de petri para usos de recursos binarios ordenados (BORPN) y sus principales propiedades estructurales. En esencia se trata de una clase ordinaria construida a partir de diversas máquinas de estados que comparten recursos unitarios en forma compleja, lo que permite bifurcación y procesos de unión. Su estructura reducida da ventajas que permiten el análisis de todo el comportamiento del sistema, siendo una tarea prohibitiva para grandes sistemas debido a la complejidad como los algoritmos de enrutamiento.

Palabras claves: Redes de Petri, clase BORPN, bloqueo mutuo, Sistemas de Asignación de Recursos, sifones.

INTRODUCCIÓN

El concepto de vivacidad está estrechamente relacionado con la ausencia de bloqueos en los sistemas, por lo cual la propiedad de vivacidad es aquella que establece que el sistema debe alcanzar todos los estados para lo que fue diseñado. Esta es una propiedad deseable en sistemas concurrentes que comparten recursos en forma simultánea, porque permite alcanzar todos los estados del sistema. Desde el punto de vista de los sistemas de asignación de recursos, el objetivo es garantizar que se alcanzaran todos los estados deseados utilizando los recursos solicitados por el sistema durante un tiempo determinado. La perspectiva de Sistemas de Asignación de Recursos (RAS) sera utilizada para modelar los sistemas a traves del modelo de Red de Petri, por lo tanto, los recursos se utilizan en forma conservadora, es decir que no se crean ni se destruyen. Un bloqueo mutuo se produce si un estado del sistema se vuelve infinitamente inalcanzable por una solicitud de recursos sin respuesta. Como se sabe, una red de Petri es una técnica formal, gráfica y ejecutable para la especificacion y análisis de sistemas dinámicos de eventos discretos concurrentes. En este trabajo, la vivacidad se garantizara utilizando el modelado y análisis de las Redes de Petri porque los bloqueos mutuos se producen con más frecuencia en los sistemas con concurrencia, que son mejor descritos por las Redes de Petri. Además, las posibilidades de modelado de las redes de Petri no estan limitados por la tecnología debido a que es un modelo matematico con una representacion gráfica utilizando un grafo bipartito.

Normalmente, la manera de sintetizar y analizar sistemas concurrentes utilizando Redes de Petri es a traves de las subclases con fortalezas para abordar problemas específicos. Por lo tanto, vamos a definir una subclase de las redes de Petri llamado Clase Red de Petri para Usos de Recursos Binarios Ordenados (BORPN) que es una subclase de clases previamente existentes que han sido utilizados para abordar los problemas de bloqueo mutuo como el S4PR [1] [2] y las clases de Redes de Petri ES³PR [3].

Es bien conocido que esta estructura reducida nos permite mejorar los algoritmos para analizar el modelo de Red de Petri, por lo tanto conciliar las habilidades que describen el modelo de Red de Petri, mientras se evitan extensos cálculos lo cual es un deseo siempre presente en la literatura. Una estrategia similar se menciona en los enfoques [4] [5] en donde se utilizaban calculos booleanos para evitar operaciones complejas. Intuitivamente, los Diagramas de Decisiones Binarias Ordinarias (OBDD) se han utilizado como estructuras de datos que pueden codificar compactamente muchas funciones en dominios estructurados discretos como [6] [7]. La clase BORPN es una clase especializada con una estructura reducida que enfrentan el problema de bloqueo mutuo de una amplia gama de sistemas distribuidos, en particular en los algoritmos de enrutamiento. Su estructura refuerza los algoritmos durante el proceso de análisis porque evita el gasto de memoria en las operaciones grandes de calculo para detectar objetos estructurales como sifones.

Como muestra la muy conocida propiedad de Commoner, objetos estructurales como los sifones estan estrechamente relacionados con algunas de las propiedades de comportamiento basicas de las Redes de Petri, como la vivacidad y la ausencia de bloqueos activos, en donde una parte del sistema funciona pero otra permanece bloqueada. El análisis estructural nos permite demostrar algunas propiedades como los sifones para asegurar la vivacidad del modelo, sin embargo, es un proceso muy costoso en memoria de computador o incluso, imposible debido al problema de la explosión estados. Varios metodos permiten reducir el numero exponencial de cálculos como ecuaciones lineales o desigualdades, órdenes parciales, simetrías, diseño modular. Un nuevo enfoque se presenta en [8] que trabaja con objetos de nivel mas alto, evitando el desperdicio memoria en los pasos intermedios. El método se apoya en la teorıa de grafos a traves de las manipulaciones de los subgrafos máximos fuertemente conectados de la grafica [9]. Este artículo esta organizado de la siguiente forma. Seccion II incluye la definicion de clase BORPN y sus propiedades basicas. Para asegurar la propiedad de vivacidad de esta clase Petri Net se dedica la sección III, incluyendo un ejemplo del uso de esta clase de Petri Net traves de un ejemplo de enrutamiento básico. Sección IV presenta las conclusiones y finalmente el apéndice A incluyen definiciones básicas y notaciones de las Redes de Petri lugar transicion.

II. DEFINICION DE LA CLASE Y PROPIEDADES

A. Clase Red de Petri para Usos de Recursos Binarios Ordenados

Durante esta seccion vamos a introducir la clase BORPN y sus principales propiedades. Esta clase es una subclase de las clases S⁴PR [1] [2] y los ES³PR [3] de Redes de Petri, por lo tanto, todos los resultados teóricos existentes para estas redes se pueden aplicar para esta subclase, sin embargo el razonamiento contrario no es posible. La clase BORPN tiene una valiosa información estructural dada por su estructura reducida que sera utilizada para el análisis de las propiedades de comportamiento del modelo como la vivacidad. Estas nuevas características provienen de la restricción impuesta a las transiciones de la clase BORP N , porque solo realiza operaciones binarias. Cada transición podrıa tomar o liberar recursos en forma unitaria, de forma muy similar al comportamiento de un algoritmo de enrutamiento como los de tipo wormhole que solicitan y liberan los canales como recursos para transportar los mensajes en forma de cadenas de bits o flits. La clase BORPN se define de la siguiente manera:

Definicion 1 (La clase de Red de Petri de Recursos Binarios Ordenados). Digamos que I_N = {1, 2, ..., m} es un conjunto finito de índices. Una Red de Petri de Recursos Binarios Ordenados es una red de Petri fuertemente conectada, libre de ciclos propios N = (P, T, C) donde:

Todo el modelo de red de Petri BORPN está compuesto por diversas redes fuertemente conectadas denotadas por Ni donde i ∈ IN^*. Una red de Petri libre de auto-bucles existe sii (t ∈ T |•t ∩ t• = ∅. En la figura 2 cada máquina de estado (SM) corresponde a una subred que forman una sola red de Petri BORPN. Debido a que los problemas de bloqueo mutuo están relacionados a estados inalcalzables producido por diversos procesos que de forma simultánea retienen y solicitan recursos generando un auto-bucle que no permite ninguna evolución de los procesos. Como muestra la definición 1 apartado 1 los lugares P son particionados en tres grupos representando el: a) los lugares de proceso PS, b) lugares reposo P0i representando los mensajes en espera c) recursos PR. Los lugares de recursos representan la disponibilidad del recurso y no puede ser creado o destruido por los procesos. La estructura de la clase BORPN impone que cada ciclo contiene los lugares desocupados P0. Si un proceso comienza adquiere un token reposo y debe terminar, por lo que el token del lugar reposo debe retornar. Durante la evolución del proceso diversos recursos pueden ser utilizados, sin embargo deben ser liberados cuando el proceso finalice. La propiedad de vivacidad se busca para garantizar la terminación de los procesos y así tener el sistema libre de bloqueos mutuos. Cada proceso requiere el uso de al menos un recurso, sin embargo deben ser adquiridos o liberados en forma unitaria. Por el motivo anterior el componente Yr es un vector booleano debido al comportamiento peculiar de esta red.

Las transiciones en una BORPN tiene un comportamiento particular siguiendo nuestra enfoque de los procesos. Nosotros consideramos que el comportamiento del proceso se asemeja a una tubería, donde puede ser particionada en unidades de proceso. La primera unidad de proceso en adquirir los recursos es la última unidad en liberarlos. Esta aproximación restringe el comportamiento de las transiciones y nos permite modelar con más fidelidad sistemas particulares a diferencia de aproximaciones tradicionales. Por lo tanto, somos capaces de modelar la transportación de objetos (mensajes, items, etc) a través de redes o centros de distribución de almacén. La definición 1 apartado 2 está relacionada con las transiciones que están particionadas en dos conjuntos disjuntos. Transiciones T_a y T_r que significan adquirir y liberar respectivamente, por consiguiente {t_i, t_j} ∈ T tanto que |•ti ∩ PR|=1 y |t_j^• ∩ PR|=1 donde i≠j. Sin embargo, esta restricción permite ni impide las bifurcaciones, siendo una característica útil para representar sistemas complejos en donde se presentan problemas de bloqueos mutuos. En [10] donde se prueba que una máquina de estado fuertemente conectada ||•t||=||t•||=1 esta viva, por lo que induce una propiedad invariante en la conservación de las marcas en los lugares. Para una BORPN esta propiedad, que se encuentra en la definición 1 apartado 3, donde para todos los i ∈ I_N, la subred Ni generada por Ni=(P0_i ∪ Ps_i, Ta_i ∪ Tr_i,Ci) donde i∈IN^* es una máquina de estado fuertemente conectada, tal que cada ciclo contiene un lugar p_oi. Cada ciclo conteniendo el lugar reposo cierra un circuito que induce un Semiflujo–T en ese camino. Finalmente en la definición 1, los apartados 4 y 5 están relacionados con las propiedades estructurales invariantes de los recursos y lugares reposo respectivamente. De esta forma, para cualquier r ∈ PR existe un mínimo Semiflujo–P donde Y_r ∈ {0, 1}|P|. Los lugares de proceso unidos con el recurso r son conocidos como lugares portadores H. Estos lugares cargan la disponibilidad de los recursos mientras representan un estado de proceso, como lo muestra la definición 2.

Definición 2. Consideremos que N sea una BORPN y PR El conjuto de lugares de recursos. El conjunto de lugares portadores H de r es el soporte del Semiflujo–P mínimo sin el recurso Hr=||Yr||\{r} donde r∈PR.

Una BORPN es una máquina de estado fuertemente conectada con recursos, por lo tanto todas sus transiciones tienen un único lugar de proceso entrada/salida y tendrían un único lugar de recurso entrada/salida. De esta manera, las transiciones podrían ser caracterizadas como habilitadas o deshabilitadas, a través del marcado del lugar de recurso como se muestra en la figura 1 y es formalizado en las definiciones 3 y 4.

Definición 3. Consideremos que N sea una BORPN, siendo P_r el conjunto de lugares de recursos y P_S el conjunto de lugares procesos. Una transición t ∈ T está habilitado en el marcado de proceso o (deshabilitado en el marcado de proceso) resumido mpe o (mpe) si p ∈•t∩PS el marcado M de p como M(p)≥PRE(p, t) o <(M(p)PRE(p, t)).

Figura 1. Marcado de recursos y procesos habilitado y deshabilitado.

Definición 4. Consideremos que N sea una BORPN, siendo PR el conjunto de lugares de recurso y PS el conjunto de lugares de proceso. Una transición t ∈ T está habilitado en el marcado de recursos o (deshabilitado en el marcado de recursos) resumido mre o (mre) si p∈•t∩PR el marcado M de r como M(r)≥PRE(r, t) o (M(r)<PRE(r, t)).

Para transiciones que liberan recursos Tr es suficiente el mpe marcado para que sean disparadas, sin embargo para el conjunto que adquieren recursos Ta deben estar mre y mpe para poder ser disparadas. La transición t1 de la parte izquierda de la figura 1 está habilitada en el marcado de proceso y habilitado en el marcado de recursos, contrario a la transición de la parte derecha que está deshabilitada en el marcado de proceso y deshabilitada en el marcado del recurso. Un camino es un Semiflujo–T de N como X, donde por cada ||X|| = 2 no satisface una de las cuatro condiciones necesarias y suficientes para la existencia de un bloqueo mutuo en [11]. Este tipo de ruta no tiene la condición Retención y Espera porque sólo solicita un recurso para finalizar el proceso completo. Por lo tanto, cada lugar pi que pertenece a este tipo de Semiflujo–T es como sigue: p ∈ PS∩Hr |• p∩r•≠∅∧p•∩• r≠ ∅ donde r ∈ P_R. Debido a la estructura de la clase BORPN, algunos lugares nunca se incluirán en una situación de bloqueo mutuo y se conocen como lugares–sin–bloqueo–mutuo.

Definición 5. Consideremos que N sea una clase BORPN, siendo P_R el conjunto de lugares de recurso y P_S el conjunto de lugares de proceso. Un lugar pi ∈ P_S es llamado lugares–sin–bloqueo–mutuo sii p• i ∩•P_R≠∅

Los lugares que satisfacen la definición 5 serán disparados cuando tengan el marcado mpe, por lo que nunca pertenecen a un estado de bloqueo mutuo, sin embargo pueden formar parte estructural de un sifón.

B. Clase BORPN

La nueva clase es definida para enfrentar problemas de bloqueo mutuo en sistemas concurrentes siguiendo nuestro enfoque RAS de los procesos. La BORPN es una clase ordinaria de red de Petri donde el Semiflujo–P de un recurso es un vector binario, por lo que existe un camino dirigido entre las transiciones que toma el recurso y las transiciones que lo liberan.

Definición 6 (Un camino dirigido). Un camino dirigido es una secuencia de lugares y transiciones p₁t₁p₂t₂...p_kt_k tal que {t₁, t₂, ..., t_k} desde p₁ hasta p_k donde t_i ∈ p• i ∩ PS y t_i ∈•Pi+1 ∩ PS, para 1 ≤ i ≤ k y {i, k} ∈ IN∗

Cuando este camino dirigido es relacionado con una clase BORPN es conocido como la zona de un recurso como muestra la definición 7. Esta característica es muy importante para evitar análisis estructural extensivo del modelo de red de Petri.

Definición 7 (Zona de un recurso). Consideremos que Ni=(Pi, Ti,Ci), i∈IN^*|N| sea una BORPN y PR el conjunto de recursos. La zona de un recurso es el conjunto de lugares portadores de r ∈ P_R que intercepta la red N_i como Z^r_i,j=Hr ∩ Ni, donde i ∈ IN^*|N| y j ∈ IN^*|N|.

El subíndice i representa la clase BORPN y si existe más de una zona el subíndice j se incrementará. Cuando el índice j es omitido, asumimos solo una zona para este recurso. En procesos lineales existe solo un camino dirigido entre la captura y liberación del recurso, sin embargo para procesos no– lineales existiría más de una captura o liberación del recurso. El corolario 1 declara la estructura existente para una zona en procesos lineales.

Corolario 1 (Zona de recurso en procesos lineales). Consideremos que N sea una BORPN con solo procesos lineales, donde PR es el conjunto de lugares de recurso. Consideremos que Z^r_i,j={p₁....p_k}, tal que k ∈ IN^*|P| la zona de un recurso r en la red N_i para j=1. El lugar px ∈ ||Yr||, x=1....k, donde (p•_x)• ∩||Yr|| = P_x+1. Por lo que tal que p₁ ∈ Z^s_i,1,1 y pk ∈ Z^s_1,2.

En una máquina de estado fuertemente conectada podría existir procesos no–lineales, por lo que en esta red la zona de un recurso debe ser generalizada para considerar diferentes tomas y liberaciones de los recursos. Debido al enfoque RAS del proceso los lugares de la primera parte del proceso son del conjunto S_A donde A significa adquiriendo. Los lugares que se mantienen en la última parte del proceso pertenecen al conjunto SR, en donde R signfica liberando. El corolario 2 describe la estructura para una zona en procesos no–lineales.

Corolario 2 (Zona de recurso en procesos no lineales). Dejemos que N sea una BORPN con procesos no lineales, donde P_R es el conjunto de recursos y {r, s} ∈ P_R. Consideremos Z^r_i,j=(S_A ∪ S_R), donde •S_A ⊆ r•, S_R• ⊆• r. De esta manera, pi ∈ S_A, ∃pj ∈ SR tal que (p_i•)• ∩ ||Yr||=pj , i≠j. Por lo que, s tal que ∃px ∈ Z^s_i,1 ∩ S_A y ∃pk ∈ Z^s_i,2 ∩ S_R, x≠k

La zonificación de los recursos producir´ıa una superposición sobre las zonas. Cuando una superposición entre diferentes zonas de recursos es conocido como unos equipos de recursos. El concepto del equipo viene del punto de vista donde un proceso adquiere/libera diversos recursos en orden estricto. Todos ellos estan trabajando juntos durante el progreso del proceso como un equipo. Por otra parte, los equipos son una caracterización de este orden y ser´an usados para describir la nueva clase BORPN. La definición 8 resume este concepto de equipo en una N_i

Definición 8. Consideremos que N sea una BORPN, siendo P_R el conjunto de lugares de recurso. Un equipo es un conjunto de lugares donde {r_i, r_j}∈P_R, satisfaciendo lo siguiente 1) ∃PX⊆||Yri||∩||Yrj||∩Ni≠∅ y ••P_X∩P_R≠P•• X ∩P₂.

2) ∃pi∈||Yri||∩Ni\(PX∪||Yrj||)̸=∅.

3) ∃pj∈||Yrj||∩Ni\(PX∪||Yri||)̸=∅.

Este conjunto P_X ⊆ P_S ∩ Ni estan en la intersección o superposición entre dos recursos en el modelo de red de Petri, no obstante debe ser un conjunto único. La segunda condición previene más de un conjunto PX a traves de los recursos de entrada y salida. Finalmente, para prevenir subconjuntos entre recursos implicados, un conjunto de lugares particulares debe existir. Un lugar que no pertenece al Semiflujo–P del otro recurso implicado debe existir. Si las condiciones previas son cumplidas, una superposicionamiento existe entre todos los recursos implicados y es llamado un equipo de recursos. Una red de Petri donde todos los recursos pertenecen a un equipo es una clase BORPN y adicionalmente es necesario que todos los lugares de proceso pertenezcan a cualquier recurso Semiflujo–P. Además, para cada transición donde el lugar de recurso r introduce (el recurso es asignado), existe un único camino, en la m´aquina de estado fuertemente conectada, para alcanzar cada transición donde r produce (el recurso es liberado).

Definición 9 (Las propiedades de recurso de la clase BORPN). Una red de Petri es una clase BORPN si todo los recursos pertenecen a un Equipo y pi∈P_S tal que pi ∩ ||Yr||=∅, r ∈ P_R.

A continuación se muestran algunas características de una clase BORPN y debe ser mencionadas como restricciones de la siguiente manera:

1) Los estados iniciales y finales están colapsados en un estado, llamado lugar reposo.

2) Las opciones entre el camino son permitidas, pero las iteraciones no.

3) Los recursos no pueden ser creados ni destruidos.

4) Los recursos son compartidos entre los caminos.

5) Los lugares de recursos tienen una marca indicando la disponibilidad.

6) Un estado pudiese usar varios recursos simultáneamente.

7) La asignación de orden de recursos, debe ser el mismo para su liberación.

8) Transiciones adquirirían o liberarían recursos pero nunca ambos eventos.

El comportamiento de muchos sistemas pueden ser descritos en términos de estados de sistemas y sus cambios, por lo que estos estados tiene un significado físico. Por lo tanto una marcación inicial representa ninguna actividad en el sistema y permite el comienzo de los procesos. La clase de red BORPN es conservativa con los recursos debido al Semiflujo–P, todos las marcaciones alcanzables representarían estados posibles del sistema desde un marcación inicial aceptable. Las marcas en lugares P_0i representan la máxima cantidad de procesos esperando en la misma red de Petri o máquina de estados. Las marcas en lugares PR modelan la disponibilidad de recursos, por consiguiente una marca es suficiente para representarlo. El lugar proceso PS carece de marcas de marcación inicial porque la marcación inicial representa ninguna actividad del sistema.

Definición 10. Consideremos que N = (P₀ ∪ P_S ∪ P_R, T,C) sea una red BORPN. Un marcado inicial m₀ es aceptable para N si y solo si:

1) ∈ IN, m0[p_0i] > 0.

2) ∈ PS, m0[p] = 0.

3) ∈ PR, m0[r] = 1.

Para poder aplicar la política de control de prevención de bloqueo mutuo es necesario considerar la marcación inicial para el modelo de red de Petri modificado. A diferencia, nuestra política de control de evitación no modifica el modelo de red de Petri, por lo que la marcación inicial permanece sin cambios. Para aplicar nuestra polítca de control de prevención de bloqueo mutuo es necesario agregar diversos recursos virtuales para hacer un modelo de red de Petri libre-de-bloqueomutuo, sin embargo esos mantienen la misma marcación inicial que en recursos previos.

Al igual, si nuevos lugares de procesos deben ser adicionados, estos permanecen vacios en marcación inicial. Nuestra política de control de bloqueo mutuo no adiciona nuevos procesos al modelo de red de Petri, por lo que ningun lugar reposo será agregado.

III. ANÁLISIS DE VIVACIDAD PARA LA CLASE BORPN

En esta sección, la propiedad de vivacidad es caracterizada por los sifones. Un sifón es un conjunto de lugares que si se vuelven vacios, permanecerán vacios para siempre. Por lo que, todas las transformaciones de salida de los lugares del sifón vacío estarían muertos para siempre porque por lo menos un lugar de entrada (que pertenece al sifón) está vacío para siempre. Sifones vacíos representan una geralización de las esperas circulares, porque en un sifón podemos encontrar una estructura intrincada de ciclos superpuestos de recursos vacíos. En [12] se rompe los sifones al añadir recursos virtuales hasta obtener un modelo de red de Petri libre–de–bloqueo–mutuo. En otra aproximación, se evita quelos sifones pierdan marcas por la vía de funciones lógicas que garantizan la propiedad de vivacidad hacia el modelo de red de Petri. La clase BORPN tiene diversad propiedades relacionadas con la estructura de los sifones y sus recursos implicado, por lo que el concepto de clase Red Estructuralmente Segura será introducido debido a la marcaciíon binaria de los lugares procesos y los lugares recursos. La estructura de la clase BORPN garantiza que todos los estados alcanzables tienen estados booleanos.

Definición 11. Un sistema de red de Petri N es llamado clase Red Estructuralmente Segura si para cada lugar p ∈ P_R∪P_S, existe un Semiflujo–P y ∈ IN∗||PR∪PS|| tal que p ∈||y|| y y.m0 ≤1.

Los siguientes resultados afirman que todos los vectores de marcado R(N,m0) \ {P0i} | i ∈ IN^*|N| excepto de los lugares reposo pertenecen al conjunto {0, 1}. El lugar reposo llena las condiciones necesarias para ser un lugar implicito porque todas sus transiciones de entrada tienen otro lugar de entrada. Resultando el marcado de lugares reposo podría ser generado desde el marcado de otros lugares. Por lo tanto, reduciendo razonamiento acerca de redes de Petri a calculación booleana donde la manipulación de marcación podría ser realizada a travez de caracterización simbólica como los Diagramas de Decisión Binaria Ordinaria (OBBDs). Una estrategia es reducir el número de elementos que tienen que ser tratados simultáneamente produce una red bien-definida. Esta fuerza para reducir la complejidad y manejar sistemas grandes, sin embargo esta discusión está más allá del alcance de este artículo.

Lema 1. Consideremos que (N,m₀), N = (P₀ ∪ P_S ∪ P_R, T,C), sea una red de Petri BORPN. Consideremos que m una marca muerta, tal que m∈ RS(N,m0) y τ ⊆ T el conjunto de transiciones muertas que pertenecen a m. El conjunto τ llena que | τ |>1.

Proof. Provamos este resultado por contradicción. Supongamos que |τ | = 1 y existe una transición t ∈ τ que está muerta en un marcado m ∈ RS(N,mo). Como t es marcación muerta implica que t ∈• S_A|•S_A ∈ r• como establece el corolario 2, para esta t nosotros tenemos el estado mre y mpe.

De mpe podemos disparar transiciones t mantenidas p ∈ S_Pm[p] ̸≠0 y mo podría ser alcanzado. Pero como |τ | = 1 y desde que el sistema es bien definido (por lo establecido en la definición 1() cualquier SemiflujoT mínimo conteniendo t podría ser disparable desde mo que es una contradicción con t estando muerto en m. Esto contradice la hipótesis que |τ | = 1 y podemos concluir que |τ | > 1.

A. Teorema de vivacidad

Una propiedad de vivacidad afirma que la ejecución del programa (proceso) eventualmente alcanza algún estado deseable. La propiedad de vivacidad y su caracterización estructural en la clase BORPN es un caraterización muy importante que apoya los siguientes resultados teóricos. El bloqueo mutuo es un problema mayor para sistemas que asignan recursos en tiempo real. Cuando se hable de sistemas concurrentes esto es relacionado a la propiedad de libertad de bloqueo mutuo, caraterizada como propiedad de vivacidad en la clase BORPN. El teorema 1 resume este resultado.

Teorema 1. La red N está viva si no existe un sifón vacío D, donde | D ∩ PR |≥2 y existe mpe, p ∈ D y mre, r ∈ D

Proof. Probaremos este resultado por contradicción. ⇒) Si | D ∩ P_R |≥2 entonces ∃r1, r2 ∈ D donde r₁• = p y r₂• = p′; p, p′ ∈ Ni como r pertence a la zona de un recurso Z_i,j^r=H_r ∩ Ni, i ∈ IN^*|N| por definición 7 y desde que existe mpe podemos verificar que ∃p′′|•p′′ = r₁• y ∃p′′′|•p′′′ = r₂• donde p′′, p′′′ ∈ Nj (existe tal p′′ y p′′′ porque hay un arco desde r a t a p′′; r₂ a t′ y t′ a p′′′ por construcción) pero como yr[r] = 1 por definición 1, !mre, r ∈ D por lo que D está vacío y la red N no está viva. ⇐) Si mpe, p ∈ D; mre, r ∈ D en | D ∩ PR |≥2 entonces existe r, podemos disparar las transiciones r• para todas los procesos activos que satisfacen la condicion •p = r• pero como p pertenece a los portadores de r, por la definición 2 y hay más de un recurso en el sifón D, esto declara que hay otro recurso r′ que satisface p ∈ H′r en la red N. Como yr[r] = 1 entonces alcanzaremos un mre, y mpe para | D∩PR |≥2 que es un sifón vacío y podemos concluir

Proof. Probaremos este resultado por contradicci´on. ⇒) Si | D ∩ PR |≥2 entonces ∃r1, r2 ∈ D donde r•1 = p y r•2 = p′; p, p′ ∈ Ni como r pertence a la zona de un recurso Zr i,j=Hr ∩ Ni, i ∈ IN^*|N| por definici´on 7 y desde que existe mpe podemos verificar que ∃p′′|•p′′ = r•1 y ∃p′′′|•p′′′ = r•2 donde p′′, p′′′ ∈ Nj (existe tal p′′ y p′′′ porque hay un arco desde r a t a p′′; r₂ a t′ y t′ a p′′′ por contrucción) pero como yr[r] = 1 por definición 1, !mre, r ∈ D por lo que D est´a vac´ıo y la red N no est´a viva. ⇐) Si mpe, p ∈ D; mre, r ∈ D en | D ∩ PR |≥2 entonces existe r, podemos disparar las transiciones r• para todas los procesos activos que satisfacen la condicion •p = r• pero como p pertenece a los portadores de r, por la definición 2 y hay más de un recurso en el sifón D, esto declara que hay otro recurso r′ que satisface p ∈ H′r en la red N. Como yr[r] = 1 entonces alcanzaremos un mre, y mpe para | D∩PR |≥2 que es un sifón vacíon y podemos concluir.

Figura 2. Modelado de un sistema de transporte a traves de una clase

máquina SM2 modela el flujo en la dirección inversa, eso significa, los objetos desde el nodo o estación 3 al nodo o estación 1. Desde nuestra perspectiva RAS, los recursos son los canales del sistema y están representados por los lugares de recurso que denominamos C_A y C_B y tienen una marca que indica cuando ellos esten disponibles o no. Esta red de Petri pertenece a la clase BORPN la cual es adecuada para el modelado de un amplio rango de Sistemas de Asignación de Recursos que adquieren y liberan recursos en el mismo orden. Como mencionamos en el teorema 1, la vivacidad de este tipo de redes está relacionada con la existencia de sifones que son insuficientemente marcadas en m. La red de la figura 2.b tiene un sifón D formado por los siguiente lugares D = {p₂, p₃, p₅, p₆, C_A, C_B}, donde no estan marcados con la marcación m = p1 +p4. Bajo esta marcación, las transiciones de salida de los lugares en el sifón t2 y t6 están muertos y los sifones D sin marcas. Evidentemente, hay un bloqueo mutuo y el sistema no garatiza la propiedad de vivacidad como la red de Petri muestra.

CONCLUSIONES

En este artículo hemos presentado una nueva clase de red de Petri orientada para tratar problemas de bloqueo mutuo en sistemas grandes que asignan recursos en forma unitaria y liberan estos en el mismo orden. La caracterizacion estructural para esta clase fue presentado a la vez que el teorema de vivacidad fue desmostrado. Aplicando analisis estructural sobre el modelo de red de Petri [9] somos capaces de caracterizar la propiedad de vivacidad a traves de una estructura llamada sifon. Diversas aproximaciones pudieron ser usadas para enfrentar problemas de bloqueo mutuo [1], sin embargo una polıtica de prevencion a traves de canales virtuales es la opcion mas adecuada para algoritmos de enrutamiento [12]. Por otra parte, una política de evitación que use funciones lógicas sobre las transiciones podrıa ser usada pero estas polıticas estan fuera del alcance de este artículo.

AGRADECIMIENTO

Este trabajo a sido apoyado por la Universidad Tecnológica de Panamá.

Referencias

[1] F. Tricas, “Analysis, prevention and avoidance of deadlocks in sequential resource allocation systems,” Ph.D. dissertation, Zaragoza. Espa˜na, Departamento de Ingenier´ıa El´ectrica e Inform´atica, Universidad de Zaragoza, May 2003.

[2] F. Tricas and J. Ezpeleta, “Computing minimal siphons in petri net models of resource allocation systems: a parallel solution,” Systems, Man and Cybernetics, Part A, IEEE Transactions on, vol. 36, no. 3, pp. 532– 539, May 2006.

[3] Y.-S. Huang, “Deadlock prevention for sequence resource allocation systems,” J. Inf. Sci. Eng., vol. 23, no. 1, pp. 215–231, 2007.

[4] E. Pastor, J. Cortadella, and O. Roig, “Symbolic analysis of bounded petri nets,” Computers, IEEE Transactions on, vol. 50, no. 5, pp. 432 –448, May 2001.

[5] K. Klai, S. Tata, and J. Desel, “Symbolic abstraction and deadlockfreeness verification of inter-enterprise processes,” in Proceedings of the 7th International Conference on Business Process Management, ser. BPM ’09. Berlin, Heidelberg: Springer-Verlag, 2009, pp. 294–309.

[6] G. Ciardo, “Data representation and efficient solution: a decision diagram approach,” in Proceedings of the 7th international conference on Formal methods for performance evaluation, ser. SFM’07. Berlin, Heidelberg: Springer-Verlag, 2007, pp. 371–394. [Online]. Available: http://portal.acm.org/citation.cfm?id=1768017.1768026

[7] F. Vall´es, F. Tricas, J. Ezpeleta, and J. Colom, “Structurally safe net systems,” R. Boel and G. Stremersch, Eds., Kluwer Academic Press. Kluwer Academic Press, 8 2000, pp. 441–448.

[8] E. Cano, A. Rovetto, and J. Colom, “On the computation of the minimal siphons of S4PR nets from a generating family of siphons,” 15th. IEEE Int. Conf. on Emerging Technologies and Factory Automation, September 2010.

[9] E. E. Cano, C. A. Rovetto, and J. M. Colom, “An algorithm to compute the minimal siphons in s 4 pr nets,” Discrete Event Dynamic Systems, vol. 22, no. 4, pp. 403–428, 2012.

[10] T. Murata, “Petri nets: Properties, analysis and applications,” Proceedings of the IEEE, vol. 77, no. 4, pp. 541–580, April 1989. [11] E. G. Coffman, M. Elphick, and A. Shoshani, “System deadlocks,” ACM Comput. Surv., vol. 3, pp. 67–78, June 1971. [Online]. Available: http://doi.acm.org/10.1145/356586.356588

[12] C. A. Rovetto, E. E. Cano, and J. Colom, “Deadlock analysis in minimal adaptive routing algorithms using petri nets,” Systems, Man, and Cybernetics, 2010 IEEE International Conference on, 10 2010.

APÉNDICE

Una red lugar/transici´on (red L/T), es una tupleta triple N = (P, T,W), donde W es una función total W : (P × T) ∪ (T × P) → IN^*, siendo P, T conjuntos no vacios, finitos y disjuntos. Elementos pertenecientes a los conjuntos P y T son llamados respectivamente lugares y transiciones, o generalmente nodos. Las redes L/T pueden ser representados como un grafo biparito directo, donde los lugares (transiciones) son graficamente denotados por circulos (rectangulos): dejemos que p ∈ P, t ∈ T, u = W(p, t), v = W(t, p), hay un arco directo, etiquetado u (v), comenzando en p (t) y terminando en t (p ) sii u≠ 0 (v≠ 0).

El preset (postset) o conjunto de nodos de entradas (salidas) x ∈ P ∪ T es denotado por •x (x•), donde •x = {y ∈ P ∪ T | W(y, x) ̸= 0} (x• = {y ∈ P ∪ T | W(x, y) ≠ 0}). El preset (postset) es un conjunto de nodos X ∈ _bag(P)∪_bag(T) es denotado por •X (X•), donde •X = {y | y ∈ •x, x ∈ X} (X• = {y | y ∈ x•, x ∈ X}

Una red L/T generalizada es una red con pesos de arcos positivos. Si los pesos del arco son unitarios (i.e., W puede ser definido como una funci´ıon total (P ×T)∪(T ×P) → {0, 1}) la red es llamada ordinaria. Una m´aquina de estado es una red ordinaria tal que para cada transici´on t ∈ T,|•t| = |t•| = 1.

Dejemos que N = (P, T,W) sea una red L/T. Su (red inversa) N^r = (P, T,Wr) es la misma red con sus arco invertidos, i.e. Wr(p, t) = W(t, p) y Wr(t, p) = W(p, t). Un lugar con ciclo propio p ∈ P es un lugar tal que p ∈ p••. Una red L/T pura (tambien una red L/T libre de ciclos propios) es una red sin lugares con ciclos propios. En redes L/T puras, la red puede ser tambien definida por la tupleta triple N = (P, T,C), donde C es llamada la matriz de incidencia, C[p, t] = W(p, t) −W(t, p).

Una marca m de una red L/T N es un vector IN^*|P|, asignando un numero finito de marcas m[p] (llamadas marcas) a cada lugar p ∈ P. Las marcas son representadas por puntos negros dentro de los lugares. El soporte de una marca, ∥m∥, es un conjunto de lugares que son marcados en m, i.e. ||m|| = {p ∈ P | m[p] ≠0}. Definimos una red L/T marcada (incluso un sistema de red L/T) como una dupleta (N,m0), donde N es una red L/T, y m0 es una marca para N, tambien llamda marca inicial. N se dice que es la esctuctura del sistema donde m0 representa el estado del sistema.

Dejemos que (N,m0) sea una red L/T marcada. Una transición t ∈ T esa habilitada (incluso disparable) si p ∈ •t . m0[p] ≥ W(p, t), que es denotada por m0[t]. El disparador de una transción habilitada t ∈ T cambia el estado del sistema a (N,m1), donde p ∈ P . m1 [p] = m₀[p] + C[p, t], y es denotado por m0[t)m1. Una secuencia de disparo σ desde (N,m0) es una secuencia de transiciones no vacía σ = t₁ t₂ ... t_k tal que m₀[t1⟩m1[t2) ...mk−1[tk). El disparado de σ es denotado por m0[σ)t_k. Nosotros llamamos al vector de conteo de disparado σ de σ al mapeo de Parikh σ → IN^*|T| (i.e. σ[t] es igual al numero de veces que t aparece en σ). El soporte de σ es denotado por ||σ||.

Una marca m es alcanzable desde (N,m0) si existe una secuencia de disparo σ tal que m₀[σ)m. El conjunto de alcanzabilidad RS(N,m0) es un conjunto de marcas alcanzables, i.e. RS(N,m₀) = {m | ∃ σ . m0[σ)m}.

La ecuación de estado de red de una red L/T marcada (N,m0) es una ecuación definida como m = m0+C·σ, donde σ≥\ 0. Cada marca alcanzable guarda la ecuación de estado de la red, pero puede que exista soluciones para la ecuación las cuales no son marcas alcanzables. Por lo que nosotros llamaremos m una marca potencialmente alcanzable. El conjunto de alcanzabilidad potencial PRS(N,m0) es definido como PRS(N,m0) = {m | ∃ σ ∈ IN∗|T|. m = m0+C ·σ,σ≥\ 0}.

Una transción t ∈ T está viva si para cada marca alcanzable m ∈ RS(N,m0), ∃m′ ∈ RS(N,m) tal que m′[t). El sistema (N,m0) está vivo sii cada transción está viva. De otro modo, (N,m₀) está muerto. Una transición t ∈ T está muerta si no hay marcas alcanzables m ∈ RS(N,m₀) tal que m[t). El sistema (N,m₀) está en un bloqueo mutuo total sii cada transición está muerta, i.e. ninguna transición es disparable. Un estado hogar mk es una marca tal que es alcanzable desde cada marca alcanzable, i.e. 'm ∈ RS(N,m₀) . mk ∈ RS(N,m). El sistema de red (N,m₀) es reversible si m₀ es un estado hogar.

Un semiflujo-p (semiflujo-t) es un vector Y ∈ IN∗|P|, Y ̸= 0 (X ∈ IN∗|T|, X ̸= 0), que es un anulador izquierdo (derecho) de la matriz de incidencia, Y · C = 0 (C ·X = 0). El soporte de un semiflujo-p (semiflujo-t) es denotado ||Y|| (||X||), y sus lugares (transciones) se dicen que son cubiertos por Y (X). La red L/T N es conservativa (consistente) sii cada lugar (transción) es cubierto por un semiflujo-p (semiflujo-t). Un semiflujo-p m´ınimo (semiflujo-t m´ınimo) es un semiflujo-p (semiflujo-t) tal que el m.c.d. de sus componentes no nulos es uno y su soporte ||Y|| (||X||) no es un super conjunto estricto del soporte de otro semiflujo-p (semiflujo-t).

Un camino π de una red L/T N es una secuencia de nodos π = x₁ x₂ ... x_n tal que los componentes impares son lugares y los componentes pares transiciones, o viceversa, y para cada par (x₁, x_xi+1), W(x₁, x_xi+1) ≠ 0. Un camino elemental es un camino tal que i, j ∈ [1, n] . x_i ≠ x_j , excepto para x₁ = x_n (lo cual es permitido). Un circuito general es un camino tal que x₁ = x_n. Un circuito elemetal (o simplemente circuito) es a la vez un camino elemental y un circuito general.