Clase de red de Petri para usos de recursos binarios ordenados

Binary Ordered Resources Petri Net Class

Carlos A. Rovetto1

[email protected],

Tomás J. Concepción2

[email protected],

Elia. E. Cano3

[email protected]

1,2,3Depto. de Ciencias de la Computación
Universidad Tecnológica de Panamá

Resumen–La prevención/evitación de los bloqueos mutuos es un dominio de investigación activo que exige aplicar diversas políticas de control para hacer frente a este problema. En este artículo presentamos una nueva subclase de Red de Petri especializada llamada Clase de red de Petri para usos de recursos binarios ordenados (BORPN) y sus principales propiedades estructurales. En esencia esta nueva clase está construida a partir de diversas máquinas de estados que comparten recursos unitarios en forma compleja, lo que permite el modelado de bifurcaciones y procesos de unión. La estructura reducida de esta nueva clase de red de Petri así como su marcado de los recursos proporciona ventajas que permiten el análisis de todo el comportamiento del sistema, siendo una tarea prohibitiva para grandes sistemas como los algoritmos de encaminamiento.

Palabras claves– Bloqueo mutuo, clase BORPN, redes de Petri, sifones, Sistemas de Asignación de Recursos.

Abstract–Prevention/avoidance of deadlocks is an active research domain that requires to implement diverse control policies to address this problem. In this paper we present a new specialized Petri Net subclass called Binary ordered resources petri net (BORPN) and its main structural properties. Essentially it is an ordinary class constructed from various state machines that share unitary resources in a complex form, which allows branching and joining processes. Its reduced structure of this new class gives advantages that allow analysis of the entire system behavior, being a prohibitive task for large systems because of the complexity and routing algorithms.

Keywords– Deadlock, BORPN class, Petri nets, siphons, Resource Allocation Systems.

1. Introducción

El concepto de vivacidad está estrechamente relacionado con la ausencia de bloqueos mutuos en los sistemas. Un bloqueo mutuo se produce si un estado del sistema se vuelve infinitamente inalcanzable por una solicitud de recursos sin respuesta. La propiedad de vivacidad establece que el sistema debe alcanzar todos los estados para los que fue diseñado, por tal motivo, esta propiedad sirve para caracterizar la ausencia de bloqueos mutuos. Debido a esta razón, siempre es deseable la presencia de esta propiedad en los 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 alcanzarán todos los estados deseados utilizando los recursos solicitados por un tiempo determinado. La perspectiva de Sistemas de Asignación de Recursos (RAS) será utilizada para modelar los sistemas a través de las Redes de Petri, por lo tanto, los recursos se utilizan en forma conservadora, es decir que no se crean ni se destruyen. Como se sabe, una red de Petri es una técnica formal, gráfica y ejecutable para la especificación y análisis de sistemas dinámicos de eventos discretos concurrentes. En este trabajo, garantizaremos la ausencia de bloqueos del sistema a través de la búsqueda de la propiedad de vivacidad que se obtiene del análisis del modelo de la Red de Petri del sistema bajo estudio. Es conocido que 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 está limitado por la tecnología debido a que es un modelo matemático con una representación gráfica utilizando un grafo bipartito. Normalmente, la manera de sintetizar y analizar sistemas concurrentes utilizando Redes de Petri es a través de las subclases con fortalezas para abordar problemas específicos. Por lo tanto, vamos a definir una nueva subclase de las redes de Petri llamada Clase de Red de Petri para Usos de Recursos Binarios Ordenados (BORPN) que se apoya en clases previamente existentes, las cuales han sido utilizadas para abordar problemas similares como la S₄PR [1] [2] y las clases de Redes de Petri ES³PR [3].

Es bien conocido que una estructura reducida nos permite mejorar los algoritmos para analizar el modelo de Red de Petri, por lo tanto conciliar las habilidades que reducen el modelo de Red de Petri, mientras se evitan extensos cálculos es un deseo siempre presente en la literatura. Una estrategia similar se menciona en los enfoques [4] [5] en donde se utilizaban cálculos booleanos para evitar operaciones complejas. Intuitivamente, los Diagramas de Decisiones Binarias Ordinarias (OBDD) se han utilizado como estructuras de datos reducidas 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 enfrenta el problema de bloqueo mutuo en muchos sistemas distribuidos, como por ejemplo, en los algoritmos de encaminamiento de tipo wormhole o en los vehículos guiados automáticamente. Su estructura refuerza los algoritmos durante el proceso de análisis porque evita el gasto de memoria en grandes operaciones de cálculo para detectar objetos estructurales como sifones.

Como muestra la muy conocida propiedad de Commoner, algunos objetos estructurales como los sifones están estrechamente relacionados con las propiedades de comportamiento básicas 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 del modelo de la Red de Petri nos permite demostrar algunas propiedades a través de los sifones para asegurar la vivacidad del modelo, sin embargo este cálculo utiliza mucha memoria e incluso en algunos casos es imposible realizarlo debido al problema de la explosión de estados. Varios métodos permiten reducir el número exponencial de cálculos como ecuaciones lineales o desigualdades, simetrías, diseño modular, etc.

Un nuevo enfoque se presenta en [8] que trabaja con objetos de nivel más alto, evitando el desperdicio de memoria en los pasos intermedios. El método está basado en la teoría de grafos y en la manipulación de los subgrafos fuertemente conectados máximos que existen en el grafo [9]. Este artículo está organizado de la siguiente forma. Sección 2 incluye la definición de clase BORPN y sus propiedades básicas. La sección 3 se dedica al análisis de la propiedad de vivacidad en esta clase de red de Petri. También se presenta en esta sección un ejemplo de encaminamiento básico modelado con esta clase de red. La sección 4 presenta las conclusiones y finalmente el apéndice se incluye definiciones básicas y notaciones de las Redes de Petri lugar transición.

2. Definición de la clase y propiedades

2.1 Clase red de Petri para usos de recursos binarios ordenados

Durante esta sección vamos a introducir la clase de Red de Petri 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 será utilizada para el análisis de las propiedades de buen comportamiento del modelo como la vivacidad. Estas características como su estructura reducida provienen de la restricción impuesta a las transiciones de la clase BORPN, 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 encaminamiento 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:

Definición 1. (La clase de red de Petri de recursos binarios ordenados). Digamos que IN={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:

1) P=P₀P_SP_R es una partición tal que:

a) P=₀U_i∈InP_Si,P_Si≠∅ y P_Si=∅, para toda i≠j .

b)P₀=⋃_i∈IN{P_0i}

c) P_R={r₁,r₂,…,r_n}, n>0.

2) T=T_aU T_r es una partición tal que:

a) T_a=⋃_i∈INT_ai≠∅ T_a∈ P_R,para cada i,j∈I_NT_ai⋂T_aj=∅, para toda i ≠j

b)T_r=⋃_i∈INT_ri,T_ri≠∅,T_a∈P_r●, para cada i,j∈I_N T_ri⋂T_rj=∅, para toda i ≠j

3) Para todo recurso r, r∈I_N, la subred N_i generada por P_si⋃{P_0i}⋃T_ai⋃T_ri es una máquina de estado fuertemente conectada, tal que cada ciclo contiene p_oi e induce un T–Semiflujo mínimo

4) Para cada r∈P_R existe un P–Semiflujo mínimo, Y_r∈{0,1}, tal que {r}=||Y_r||⋂P_R,Y_r[r]=1 P₀⋂||Y_r||≠0

5) P_s=⋃_r∈Pr(||Yr||\{r}).

Todo el modelo de red de Petri BORPN está compuesto por diversas redes fuertemente conectadas denotadas por N_i donde i ∈ℕ⁺. Una red de Petri libre de bucles existe sii ∀t∈T|●t∩t●=∅. En la Figura 2 cada máquina de estado (SM) corresponde a una subred que juntas forman una sola red de Petri de la clase BORPN. Debido a que los problemas de bloqueo mutuo están relacionados a estados inalcanzables producidos por diversos procesos que de forma simultánea retienen y solicitan recursos generando un bucle que no permite ninguna evolución de los procesos. Como se muestra en la definición 1, del Apartado 1, los lugares P son particionados en tres grupos representados por: a) los lugares proceso Ps, b) los lugares de reposo P_R representando los mensajes en espera, c) y los recursos P. Los lugares recursos representan la disponibilidad de los recursos, que debido a perspectiva RAS estos no pueden ser creados o destruidos por los procesos. La estructura de la clase BORPN impone que cada ciclo contiene los lugares reposos . Si un proceso comienza adquiere una marca del lugar reposo y al terminar el proceso la marca del lugar reposo debe retornar. Es decir, 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 tienen un comportamiento particular siguiendo nuestro enfoque de los recursos RAS. 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 esta razón, somos capaces de modelar procesos que representa el transporte de objetos (mensajes, items, etc) a través de redes o centros de distribución en un almacén. La Definición 1 del Apartado 2 está relacionada con las transiciones que están particionadas en dos conjuntos disjuntos. Transiciones Ta y Tr que significan adquirir y liberar respectivamente, por consiguiente ∀{t_i,t_j}, ∈T tanto que |●t_i∩P_R|=1 ó t_j^●∩ =1 donde i≠j . Sin embargo, esta restricción no 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 es viva, por lo que induce una propiedad invariante en la conservación de las marcas en los lugares. Para una BORPN esta propiedad se establece en la definición 1, del apartado 3, donde para todos los i ∈ IN, la subredN_i generada por=〈P_0i∪P_Si,T_ai∪T_ri,C_i〉 donde i∈ℕ⁺ es una máquina de estado fuertemente conectada, tal que cada ciclo contiene un lugar p. Cada ciclo que contiene el lugar reposo cierra un circuito que induce un T– Semiflujo en ese camino. Finalmente en la Definición 1, de 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∈P_R existe un mínimo P–Semiflujo donde Yr ∈{0, 1}|^P| . Los lugares de proceso unidos con el recurso son conocidos como lugares portadores ℋ. 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 P. El conjunto de lugares de recursos. El conjunto de lugares portadores ℋ de r es el soporte del P–Semiflujo mínimo sin el recurso ℋ=‖Yr‖\{r} donde r∈P_R.

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 Ps el conjunto de lugares procesos. Una transición t∈T está habilitada en el marcado o (deshabilitado en el marcado) resumido npe (npe sii ∀p ∈ ^●t∩Ps> el marcado M de p como M (p) ≥ PRE(p,t) (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 >P>R el conjunto de lugares de recursos y >P>s el conjunto de lugares procesos. Una transición >t∈ T está habilitada en el marcado o (deshabilitado en el marcado) resumido mre (mre) sii ∀p ∈ ^●t∩ Ps el marcado M de p como M (r) ≥ PRE(r,t) (M (r)< PRE(r,t).

Para transiciones que liberan recursos Tr es suficiente el marcado mpe 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á 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 T–Semiflujo es como sigue: ∀p ∈ Ps ∩ ℋr|^●p ∩ r^● ≠ ∅ ∧ p^● ∩ ^●r≠ ∅ donde r∈ P_R Debido a la estructura de la clase BORPN algunos lugares nunca se encontrarán en una situación de bloqueo mutuo. A estos lugares se les denomina lugares–sin–bloqueo–mutuo.

Definición 5. Consideremos que N es una BORPN, siendo Pr el conjunto de lugares de recursos y Ps el conjunto de lugares procesos. Un lugar pi ∈ Ps llamado lugares–sin–bloqueo–mutuo sii pi^● ∩ ^●Pr ≠ ∅.

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.

2.2 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 P–Semiflujo 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_k,…,t_k tal que {t₁,t₂,…,t_k} desde p₁ hasta p_k donde t_i ∈p^● ∩ P_S y t_i ∈^●P_i+1∩P_S, para 1≤i≤k y {i,k}∈N+

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 =〈P_i ,T_i ,C_i 〉, i∈ℕ_+|N| sea una BORPN y P_R el conjunto de recursos. La zona de un recurso es el conjunto de lugares portadores de r∈P que intercepta la red como Z_i,j^R =ℋ∩N_i, donde i∈ℕ_+|N| y j ∈ℕ_+|p| .

El subíndice i representa la clase BORPN y si existe más de una zona el subíndice 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.

El corolario 1. (Zona de un recurso en procesos lineales). Consideremos que sea una BORPN con solo procesos lineales, donde P es el conjunto de lugares de recurso. Consideremos que ,Z_i,j^r={p₁…p_k}, tal que k ∈ℕ+|^p| la zona de un recurso r en la red N_i para j=1 . El lugar p_x∈‖Yr‖,∀x=1…k, donde (p_x●)^●∩‖Yr‖=Px+1. Por lo que ∄s tal que p₁∈Z, y p_k∈ Z.

En una máquina de estado fuertemente conectada podrían existir procesos no–lineales, por lo que en esta red la zona de un recurso debe ser generalizada para considerar diferentes adquisiciones 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 S_R , en donde R significa liberando. El corolario 2 describe la estructura para una zona en procesos no–lineales.

Corolario 2. (Zona de un recurso en procesos no lineales). Consideremos que sea una BORPN con procesos no lineales, donde P es el conjunto de lugares de recurso y {r,s}∈P_R. Consideremos Z, =(S_A∪\ S_R), donde _●S_A⊆r●,S ●⊆r●. De esta manera, ∀ p_i∈S_A,∃p_j∈S_R tal que (p_i ●)●∩‖Yr‖=p_j,∀i≠j . Por lo que, ∄p_x∈, ∩S_R y ∄p∈, ∩S_R,∀x≠k.

La zonificación de los recursos produciría una superposición sobre las zonas de los recursos. Cuando exista una superposición entre diferentes zonas de recursos se denominará como equipos de recursos. El concepto del equipo viene del punto de vista donde un proceso adquiere/libera diversos recursos en orden estricto. Todos ellos están trabajando juntos durante el progreso del proceso como un equipo. Por otra parte, los equipos son una caracterización de este orden y serán 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 sea una BORPN, siendo P el conjunto de recurso.

Un equipo de recursos es un conjunto de lugares donde ∀r_i ,r_j ∈P_R, satisfaciendo que 1) ∃P_x⊆‖Y_ri‖∩‖Y_rj‖∩N_i ≠∅ y ●●P_X∩P_r≠P_X●●∩P_R. 2) ∃p_i∈‖Y_ri‖∩ (P_x∪_Yrj )≠∅. 3) ∃p_j∈∩‖Y_ri‖∩N‖Y_i (Psub>i∪‖Ysub>ri‖)≠∅.

El conjunto P_x⊆ P_s∩N_i existe debido a la intersección entre dos recursos en el modelo de red de Petri, no obstante debe ser un conjunto único. La segunda condición previene la existencia de más de un conjunto en las zonas de los recursos de entrada y salida. Finalmente, para prevenir subconjuntos entre los recursos implicados, debe existir un conjunto de lugares particulares. Debe existir un lugar que no pertenece al P–Semiflujo del otro recurso implicado. Si las condiciones previas son cumplidas, existirá una superposición entre todos los recursos implicados y es llamado un equipo de recursos. Una red de Petri donde todos los recursos pertenecen a un equipo de recursos es una clase BORPN y adicionalmente es necesario que todos los lugares de un proceso pertenezcan a cualquier P–Semiflujo de los recursos del equipo. Finalmente, para cada transición donde el recurso del equipo es adquirido, existe un único camino, en la máquina de estado fuertemente conectada, para alcanzar cada transición donde el recurso del equipo es liberado.

Definición 9. (Las propiedades de un recurso de la clase BORPN). Una red de Petri es una clase BORPN si todos los recursos pertenecen a un Equipo y ∀p_i∈P_s tal que p_i∩‖Yr‖=∅, ∀r∈P_R. A continuación se muestran algunas características de la clase BORPN que se mencionan como restricciones:

1) El lugar reposo colapsa los estados inicial y final

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

3) Los recursos no pueden ser creados ni destruidos.

4) Los recursos son compartidos entre los caminos.

5) Los lugares recursos tienen solo una marca.

6) Un estado puede usar recursos simultáneamente.

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

8) Las transiciones adquirirían o liberarían los recursos pero nunca ambos eventos a la vez. El comportamiento de muchos sistemas puede ser descrito en términos de los estados del sistema, debido a que estos estados y sus cambios tienen un significado físico. Basado en esto podemos decir que una marcación inicial representa la ausencia de actividad en el sistema y el comienzo de los procesos. La clase BORPN es conservativa con los recursos debido al P–Semiflujo, todas las marcaciones alcanzables representarán estados posibles del sistema desde una marcación inicial aceptable. Las marcas en lugares representan la máxima cantidad de procesos esperando en la misma red de Petri o máquina de estados. Las marcas en lugares modelan la disponibilidad de recursos, por consiguiente una marca es suficiente para representarlo. El lugar proceso carece de marcas en el marcado inicial porque representa la ausencia de actividad en el sistema.

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

1) ∀i∈I_N,[p_0i].

2)∀p∈P_S,[p]=0.

3)∀r∈P_R,[r]=1.

Usualmente, para poder aplicar la política de control de prevención de bloqueos mutuos es necesario considerar la marcación inicial para el modelo de red de Petri. En nuestra política de control de evitación de bloqueos mutuos no se modifica el modelo de la red de Petri, por lo que la marcación inicial permanece sin cambios. Para aplicar nuestra política de control de prevención de bloqueo mutuos es necesario agregar recursos virtuales para hacer el modelo de la red de Petri libre de bloqueos mutuos los cuales mantendrán la misma marcación inicial que los recursos previos. De igual forma, si se llega a agregar nuevos lugares de procesos, estos permanecen vacíos en la marcación inicial. Nuestra política de control de bloqueo mutuo no adiciona nuevos procesos al modelo de red de Petri, por lo que ningún lugar reposo será agregado.

3. 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 pierden sus marcas, permanecerán vacíos para siempre. Por lo que, todas las transiciones de salida de los lugares del sifón vacío estarán deshabilitadas para siempre debido a que por lo menos un lugar de entrada (perteneciente al sifón) estará vacío para siempre. Los sifones vacíos representan una generalización de las esperas circulares, debido a que 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 la red de Petri libre de bloqueos mutuos. En otra aproximación, se evita que los sifones pierdan marcas utilizando funciones lógicas que garantizan la propiedad de vivacidad en el modelo de la red de Petri. La clase BORPN tiene diversidad propiedades relacionadas con la estructura de los sifones y sus recursos implicados, por lo que se puede introducir el concepto de clase de red estructuralmente segura debido a la marcación binaria de los lugares procesos y los lugares recursos. La estructura de la clase BORPN garantiza que todos los estados en la red son alcanzables.

Definición 11. Un sistema de red de Petri es llamado clase Red Estructuralmente Segura sii para cada lugar p∈P_R∪P, existe un P–Semiflujo ∈ℕ^+|pr∪ps|tal que p∈‖Y‖ y m0.≤1.

Los siguientes resultados afirman que todos los vectores de marcado ℛ(N,m0)\{P_0i}|i∈ℕ^+|N| excepto de los lugares reposo pertenecen al conjunto {0, 1}. El lugar reposo satisface las condiciones necesarias para ser un lugar implícito porque todas sus transiciones de entrada tienen también otro lugar de entrada. Debido a esta característica el marcado de los lugares reposo podría ser generado desde el marcado de otros lugares. Para estas redes es posible el razonamiento a través de cálculos booleanos donde la manipulación de la marcación podría ser realizada utilizando la herramienta de los Diagramas de Decisión Binaria Ordinaria (OBBDs). Una estrategia es reducir el número de elementos que tienen que ser tratados simultáneamente lo cual produce una red bien definida, sin embargo la discusión de este método va más allá del alcance de este artículo.

Lema 1. Consideremos que 〈N,m0〉, =〈P0∪Ps∪PR,T,C, sea una red de Petri BORPN. Consideremos que m sea una marca muerta, tal que m∈ℛS(N,m0) y τ⊆T en el conjunto de transiciones muertas que pertenecen a m. El conjunto τ cumple que |τ|>1.

Demostración. Probaremos el resultado por contradicción. Supongamos que |t|=1 y existe una transición t∈t que está muerta en un marcado m∈ℛS(N,m0). Como es una marcación muerta implica que t∈●S_A|●S_A∈r● como establece el corolario 2, para esta nosotros tenemos el estado mre y mpe.

De mpe podemos disparar transiciones t mantenidas ∀ p∈S|m[p]≠0 y m0 podría ser alcanzado. Pero como |τ| = 1 y sabiendo que el sistema está bien definido (por lo establecido en la definición 1) cualquier T–Semiflujo mínimo conteniendo podría ser disparada desde m que es una contradicción con estando muerto en m. Esto contradice la hipótesis que |t|= 1 y podemos concluir que |t|>1

3.1 Teorema de vivacidad

La 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 una caracterización muy importante que apoya los siguientes resultados teóricos. El teorema 1 resume este resultado.

Teorema 1. a red N stá viva sii no existe un sifón vacío D donde |D ∩P_R>|≥ 2 existe mpe p ∈ D mre, r∈D.

Demostración. Probaremos el resultado por contradicción.

⇒ Si |D∩P_R>|≥2 entonces ∃r₁=p' y r₂ ∈ D donde r₁= p y r₂=p';p,p'∈ N_i como r pertence a la zona de recurso Z_i,j^r=Hr∩Ni,i∈N+|N|por definición 7 y dado que existe mpe podemos verificar que ∃p' '|p''=r1 y ∃p' '|p'''=r2 donde p'',p'''∈ N_j(existe tal p' 'y t' a p''' por construcción)pero como Yr[r]=1 por definición 1,Amre,r ∈ D por lo que D está vacío y la red N no está viva.

⇒ Si mpe,p∈D;mre,r∈D|D∩P_R|≥2 entonces existe r, podemos disparar las transiciones r• para todas los procesos activos que satisfacen la condición •p=r• pero como 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∈ℋ'r en la red N. Como Yr[r]=1 entonces alcanzaremos un mre , y mpe para |D∩P_R|≥2 y podemos concluir que es un sifón vacío.

3.2 Modelado de un algoritmo de encaminamiento

En esta subsección se mostrará un ejemplo de un sistema de transporte modelado a través de redes de Petri como una herramienta de síntesis y modelado. La figura 2.a muestra un sistema de transporte de objetos (objetos físicos o virtuales) compuestos de tres nodos o estaciones y dos canales duplex denominados >C>A y >C>B. Se puede deducir que si los nodos o estaciones de los extremos (1 y 3) desean enviar simultáneamente objetos, se puede generar un bloqueo mutuo en el nodo central. Es preciso mencionar que nosotros asumimos que el Nodo o Estación 2 está deshabilitado para enviar o recibir mensajes, pero habilitado para reenviar los mensajes a los Nodos o Estaciones restantes.

Figura 2. Modelado de un sistema de transporte a través de una clase BORPN.

La figura 2.b muestra una red de Petri con dos máquinas de estado SM1 y SM2, donde, la máquina SM1 modela el flujo de objeto desde el Nodo o Estación 1 hacia el Nodo o Estación 3. La 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= p+p. 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 garantiza la propiedad de vivacidad como la red de Petri muestra en el bloqueo.

4. 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 caracterización estructural para esta clase fue presentada a la vez que se ha demostrado el teorema de vivacidad. Aplicando análisis estructural sobre el modelo de red de Petri [9] somos capaces de caracterizar la propiedad de vivacidad a través de una estructura llamada sifón. El dominio de aplicación de esta nueva clase de red está orientada al análisis de algoritmos de encaminamiento en que recursos (canales) son asignados de forma unitaria a los procesos (mensajes) que parten de un origen a un destino predeterminado y siguiendo diversas rutas en una red de interconexión. Durante este recorrido emergen problemas de bloqueos debido al uso de compartido de los canales. Diversas aproximaciones pudieron ser usadas para enfrentar problemas de bloqueo mutuo [1], sin embargo una política de prevención utilizando canales virtuales es la opción más adecuada para los algoritmos de encaminamiento [12].

5. Agradecimiento

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

6. Referencias

[1] F. Tricas, “Analysis, prevention and avoidance of deadlocks in sequential resource allocation systems,” Ph.D. dissertation, Zaragoza. España. Departamento de Ingeniería Eléctrica e Informática, Universidad de Zaragoza. Mayo, 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 deadlock-freeness 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és, 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 S4PR nets,” Discrete Event Dynamic Systems, vol. 22, no. 4, pp. 403–428, 2012.

[10] T. Murata, “Petri nets: Properties, analysis and applications,” Proceed-ings of the IEEE, vol. 77, no. 4, pp. 541–580, April 1989.

[11] E. G. Coffman, M. Elphick, and A. Shoshani, “System deadlocks,” ACM Computing Surveys (CSUR), 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ón (red L/T), es una tupla N=〈P,T,W〉, donde W es una función total W: (P× T)∪(T×P)⟶ℕ+, 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 representadas como un grafo bipartito directo, donde los lugares (transiciones) son gráficamente denotados por círculos (rectángulos): 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) si u≠0 (v≠0).

El preset (postset) o conjunto de nodos de entradas (salidas) x={y ∈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∈ }).

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ón total (P×T)∪ (T×P)→{0, 1}) la red es llamada ordinaria. Una máquina de estado es una red ordinaria tal que para cada transición t∈T,|●t|=|t ●|=1.

Sea = 〈P,T,W〉 una red L/T. Su (red inversa)N^r=〈P,T,W〉 es la misma red con sus arco invertidos, i.e. W^r(p,t)=W^r(t,p) y W^r(t,p)=W^r(p,t) .

Un lugar con ciclo propio p ∈P es un lugar tal que p ∈p••. Una red L/T pura (también 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 también definida por la tupla 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 ℕ∗|P|, asignando un número finito de marcas m[p] (llamadas marcas ) a cada lugar ∈. 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 tupla 〈N,m0〉, donde N es una red L/T, y m0 es una marca para N, también llamada marca inicial.

Sea 〈N,m0〉 una red L/T marcada. Una transición t ∈ T esa habilitada (disparable) si ∀p∈t ● .m[p]≥W (p,t), que es denotada por m0[t ⟩. El disparador de una trans ición habilitada t∈T cambia el estado del sistema a 〈,m〉 , donde ∀p∈P. m1[p]=m0[p]+C [p,t], y es denotado por m[t ⟩m. Una secuencia de disparo σ desde 〈N,m0〉 es una secuencia de transiciones no vacía σ=t1 t2...tk tal que m [t1 ⟩m[t⟩…m[t⟩. El disparado de σ es denotado por m[σ⟩t. Llamamos vector de conteo de disparado σ al mapeo de Parikh σ→ℕ∗|| (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 〈,m〉 si y solo si existe una secuencia de disparo σ tal que m[σ⟩m. El conjunto de alcanzabilidad RS〈,m〉 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 〈,m〉 es una ecuación definida como m=m+C·, σ donde σ≱0. Cada marca alcanzable guarda la ecuación de estado de la red, pero puede que existan 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〈,m〉 es definido como PRS 〈,m〉= {m |∃σ∈ℕ∗|T|⋅m=m0+C·σ,σ≱0 } .

Una transición t∈T está viva si y solo si para cada marca alcanzable m∈RS(N,m0) , ∀m'∈RS(N,m) tal que m'[t ⟩. El sistema 〈N,m〉 está vivo si y solo si cada transición está viva. De otro modo, 〈N,m〉 está muerto. Una transición t∈T está muerta si y solo si no hay marcas alcanzables mk∈RS(N,m0) tal que m[t ⟩. El sistema 〈N,m0〉 está en un bloqueo mutuo total si y solo si cada transición está muerta, i.e. ninguna transición es disparable. Un estado hogar m 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 y solo si m es un estado hogar.

Un p-semiflujo (t-semiflujo) es un vector Y∈ℕ ∗|p|,Y≠0 (X∈ℕ∗||,X≠0), que es un anulador izquierdo (derecho) de la matriz de incidencia, Y·C=0 (C·X=0). El soporte de un p-semiflujo (t-semiflujo) es denotado ‖Y‖ (‖X‖), y sus lugares (transiciones) se dicen que son cubiertos por Y (X). La red L/T N es conservativa (consistente) si y solo si cada lugar (transición) es cubierto por un p-semiflujo (t-semiflujo). Un p-semiflujo mínimo (t-semiflujo mínimo) es un psemiflujo (t-semiflujo) tal que el m.c.d. de sus componentes no nulos es uno y su soporte ‖Y‖ (‖X‖) no es un superconjunto estricto del soporte de otro psemiflujo (t-semiflujo).

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