ANÁLISIS DE PROPIEDADES DINÁMICAS DE LÍNEAS DE PRODUCTO DE SISTEMAS CONCURRENTES DYNAMIC PROPERTIES ANALYSIS OF PRODUCT LINES FOR CONCURRENT SYSTEMS Trabajo de Fin de Grado Curso 2023–2024 Autor Javier Pastor Ramirez Director MARÍA ELENA GÓMEZ MARTÍNEZ JOSÉ IGNACIO REQUENO JARABO Doble Grado en Ingeniería Informática y Matemáticas Facultad de Informática Universidad Complutense de Madrid ANÁLISIS DE PROPIEDADES DINÁMICAS DE LÍNEAS DE PRODUCTO DE SISTEMAS CONCURRENTES DYNAMIC PROPERTIES ANALYSIS OF PRODUCT LINES FOR CONCURRENT SYSTEMS Trabajo de Fin de Grado en Ingeniería Informática Autor Javier Pastor Ramirez Director MARÍA ELENA GÓMEZ MARTÍNEZ JOSÉ IGNACIO REQUENO JARABO Convocatoria: Junio 2024 Doble Grado en Ingeniería Informática y Matemáticas Facultad de Informática Universidad Complutense de Madrid 27 de MAYO de 2023 Resumen ANÁLISIS DE PROPIEDADES DINÁMICAS DE LÍNEAS DE PRODUCTO DE SISTEMAS CONCU- RRENTES Con el desarrollo de sistemas cada vez más complejos, desde el desarrollo de herramientas software con partes comunes entre ellas hasta lineas de producción in- dustrial, nos vemos en la necesidad de utilizar herramientas como líneas de producto para poder estudiar y analizar su comportamiento gracias a la variabilidad que nos ofrecen. Las líneas de productos nos permiten estudiar de forma aislada cada una de las partes de un proceso y después estudiar la interacción de estos subprocesos entre ellos. Estos procesos suelen ser implementados mediante grafos bipartidos llamados Redes de Petri. Estos grafos tienen la característica de poder representar un sistema a eventos, más concretamente sistemas concurrentes. El objetivo de este Trabajo de Fin de Grado se centra en procedimientos para calcular propiedades dinámicas de estas redes de Petri aplicadas a lineas de producto, implementando en este caso la generación de grafos de alcanzabilidad y grafos de alcanzabilidad con tiempo, valorando posteriormente los resultados obtenidos y la utilidad de los mismos. Palabras clave Redes de Petri, Grafo de Alcanzabilidad, Propiedades Dinámicas, Lineas de Pro- ducto. v Abstract DYNAMIC PROPERTIES ANALYSIS OF PROD- UCT LINES FOR CONCURRENT SYSTEMS With the development of increasingly complex systems, ranging from the devel- opment of software tools with common parts to industrial production lines, we find the need to use tools such as product lines to study and analyze their behavior, thanks to the variability they offer. Product lines allow us to study each part of a process in isolation and then examine the interaction of these subprocesses among themselves. These processes are often implemented using graphs called Petri Nets. These graphs have the characteristic of being able to represent a system of events, more specifically concurrent systems. The objective of this Bachelor’s Thesis focuses on procedures for calculating dynamic properties of these Petri nets applied to product lines, implementing in this case the generation of reachability graphs and reachability graphs with time, subsequently evaluating the results obtained and their usefulness. Keywords Petri Nets, Reachability Graph, Dynamic Properties, Product Lines. vii Índice 1. Introducción 1 1.1. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Plan de trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Conceptos previos 5 2.1. Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1. Grafo dirigido . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2. Grafo dirigido simple . . . . . . . . . . . . . . . . . . . . . . . 6 2.2. Red de Petri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1. Red de Petri con tiempo . . . . . . . . . . . . . . . . . . . . . 9 2.3. Líneas de producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4. Líneas de Producto de Redes de Petri . . . . . . . . . . . . . . . . . . 11 2.4.1. Ventajas de las redes de Petri para el análisis de líneas de producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5. Titan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3. Grafos de Alcanzabilidad 17 3.1. Estado alcanzable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2. Grafo de alcanzabilidad de una PNPL . . . . . . . . . . . . . . . . . 17 3.3. Características del grafo de alcanzabilidad . . . . . . . . . . . . . . . 19 ix 3.4. Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4.1. Algoritmo de generación del grafo de alcanzabilidad . . . . . . 20 3.4.2. Componentes de la implementación . . . . . . . . . . . . . . . 21 3.4.3. Implementación en detalle . . . . . . . . . . . . . . . . . . . . 22 3.5. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.6. Representación gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4. Grafos de Alcanzabilidad con Tiempo 27 4.1. Decisiones de implementación . . . . . . . . . . . . . . . . . . . . . . 27 4.2. Representación gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5. Conclusiones y Trabajo Futuro 33 5.1. Objetivos alcanzados . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Introduction 35 5.3. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.4. Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.5. Work Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.6. Document Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Conclusions and Future Work 39 5.7. Achieved Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.8. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Bibliografía 41 6. Manual de Programador 43 6.1. Readme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Índice de figuras 1.1. Diagrama de Gantt. Fuente: Jira (1) . . . . . . . . . . . . . . . . . . 4 2.1. Grafo. Fuente: (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Grafo dirigido. Fuente: (3) . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3. Grafo dirigido simple. Fuente: Elaboración propia . . . . . . . . . . . 6 2.4. Red de Petri. Fuente: Elaboración propia. . . . . . . . . . . . . . . . 8 2.5. Red de Petri con tiempo. Fuente: Elaboración propia. . . . . . . . . . 10 2.6. Diagrama de características. Fuente: Elaboración propia. . . . . . . . 11 2.7. Ejemplo de configuración. Fuente: Elaboración propia. . . . . . . . . . 12 2.8. Configuración de una linea de producto. Fuente: (4) . . . . . . . . . . 12 2.9. Mutex de dos hilos. Fuente: Elaboración propia. . . . . . . . . . . . . 13 2.10. Mutex de tres hilos. Fuente: Elaboración propia. . . . . . . . . . . . . 14 2.11. Arquitectura de TITAN. Fuente: (5) . . . . . . . . . . . . . . . . . . 15 2.12. Entorno de TITAN. Fuente: (5) . . . . . . . . . . . . . . . . . . . . . 15 3.1. Grafo de alcanzabilidad de la red de Petri. Fuente: (6) . . . . . . . . . 18 3.2. Estado [p1, p5]. Fuente: (6) . . . . . . . . . . . . . . . . . . . . . . . 18 3.3. Red de Petri con grafo de alcanzabilidad no-finito. Fuente: Elabora- ción propia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4. Grafo de alcanzabilidad no-finito. Fuente: Elaboración propia. . . . . 20 3.5. Red de Petri. Fuente: Elaboración propia. . . . . . . . . . . . . . . . 25 3.6. Grafo de alcanzabilidad. Fuente: Elaboración propia. . . . . . . . . . 26 4.1. Red de Petri. Fuente: Elaboración propia. . . . . . . . . . . . . . . . 29 xi 4.2. Grafo de alcanzabilidad con tiempo (100 tiempo máximo). Fuente: Elaboración propia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3. Red de Petri mutex. Fuente: Elaboración propia. . . . . . . . . . . . . 30 4.4. Grafo de alcanzabilidad de mutex con tiempo (100 tiempo máximo). Fuente: Elaboración propia. . . . . . . . . . . . . . . . . . . . . . . . 31 5.1. Gantt Diagram. Source: Jira (1) . . . . . . . . . . . . . . . . . . . . . 37 6.1. Selección de análisis. Fuente: Elaboración propia. . . . . . . . . . . . 44 6.2. Selección de grafo de alcanzabilidad con o sin tiempo. Fuente: Elabo- ración propia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.3. Selección del límite de tiempo para el grafo de alcanzabilidad con tiempo. Fuente: Elaboración propia. . . . . . . . . . . . . . . . . . . . 45 6.4. Salida del algoritmo en formato Graphviz. Fuente: Elaboración propia. 46 Capı́tulo 1 Introducción La necesidad de modelar procesos concurrentes variables de pequeña o gran es- cala, como un mutex entre varios hilos, nos lleva a valorar varias alternativas de representación de los mismos como las redes de colas, los autómatas finitos o las redes de Petri. Elegimos este último, ya que las redes de Petri (7) se han convertido en una herramienta indispensable en multitud de campos como el análisis de datos, el diseño de software o la programación concurrente. Además, debido a que los procesos que modelamos son variables, es decir, existen múltiples configuraciones distintas del mismo procesos que crean sistemas parecidos con pequeñas diferencias, y requerimos analizarlos todos a la vez, modelamos estos procesos mediante líneas de producto. Las líneas de producto nos permiten reutilizar y aprovechar los elementos comunes de las diferentes configuraciones que tengamos de un mismo proceso, optimizando el análisis de los procesos en comparación a analizar uno a uno de forma independiente. Siguiendo el ejemplo anterior del mutex, este puede manejar dos o tres hilos por ejemplo. Nuestro objetivo es analizar el comportamiento en el tiempo de un proceso, es decir, una de sus propiedades dinámicas, en concreto la alcanzabilidad de sus estados. Describimos el estado de un proceso como la configuración del sistema en un instante dado. Es así como llegamos nuestro principal objetivo de este Trabajo de Fin de Grado, el análisis de la alcanzabilidad de estados de las líneas de producto modeladas como redes de Petri con el objetivo de diseñar algoritmos de generación de grafos de alcanzabilidad para analizar esta propiedad dinámica. La ventaja que aportan las líneas de producto es la variabilidad asociada a las mismas, podemos modelar un sistema muy complejo en su totalidad o, aislarnos y centrarnos en aspectos más pequeños del modelo. En este trabajo abordaremos todos los conceptos previos necesarios para entender el análisis de la alcanzabilidad acompañándonos de un ejemplo de conexión de una máquina a otras tres máquinas distintas. 1 2 Capítulo 1. Introducción La relevancia de esta investigación radica en la falta de estudios previos dispo- nibles sobre los grafos de alcanzabilidad aplicados específicamente a redes de Petri que modelan líneas de productos. Al abordar esta brecha de conocimiento, buscamos ofrecer una contribución significativa al campo, proporcionando una comprensión más profunda y una herramienta práctica para el análisis de sistemas de producción en este dominio. Durante este Trabajo de Fin de Grado elaboramos el desarrollo en la herramienta TITAN, un plug-in de Eclipse (8) desarrollado con el objetivo de analizar líneas de producto modeladas con redes de Petri. 1.1. Motivación La motivación de este Trabajo de Fin de Grado es proporcionar nuevas herra- mientas y recursos al análisis de los sistemas concurrentes con variabilidad que nos encontramos en el mundo real. Para realizar este análisis de los sistemas concurrentes hacemos un estudio exhaus- tivo de la alcanzabilidad, una propiedad dinámica de las redes de Petri. Además, para añadir variabilidad a los sistemas que valoramos, realizamos el estudio de la exhaustividad de las redes de Petri en el contexto las lineas de producto, un área que ha recibido una atención limitado en al literatura académica hasta el momento. Más en detalle, nos enfocaremos en el desarrollo e implementación detallada de los grafos de alcanzabilidad de las redes de Petri, explorando no solo sus ventajas y desventajas, sino también su aplicación práctica, características intrínsecas y sus diversas aplicaciones potenciales en el modelado y análisis de líneas de productos. 1.2. Objetivos El objetivo principal de este Trabajo de Fin de Grado es el desarrollo, implemen- tación y estudio de grafos de alcanzabilidad de una red de Petri que modela una línea de producto, para lograrlo lo desglosamos en los siguientes objetivos secundarios: Objetivo secundario 1. Introducir y explicar de manera exhaustiva los con- ceptos previos necesarios para comprender completamente el resto del trabajo. Esto implica no solo presentar resultados conocidos sobre grafos y redes de Pe- tri, sino también contextualizar estos conceptos dentro del ámbito específico de las líneas de productos. Lo veremos en el capítulo 2. Objetivo secundario 2. Desarrollar una implementación completa y fun- cional de los grafos de alcanzabilidad aplicados a redes de Petri, incluyendo 1.3. Plan de trabajo 3 detalles técnicos sobre algoritmos de generación, representación de datos y herramientas computacionales utilizadas. Lo estudiamos en los capítulo 2 y 3. Objetivo secundario 3. Realizar un análisis detallado de las características de estos grafos de alcanzabilidad, explorando su estructura, propiedades emer- gentes y comportamiento dinámico en diferentes escenarios. Lo vemos en los capítulos 2 y 3. Objetivo secundario 4. Investigar las aplicaciones prácticas y la utilidad de los grafos de alcanzabilidad en comparación con otras alternativas de modelado y análisis utilizadas en el contexto de líneas de productos. Esto implica evaluar su eficacia en la detección de cuellos de botella, la optimización de procesos, la predicción de posibles fallos o inconsistencias en la producción. Lo vemos en los capítulos 2 y 3. Objetivo secundario 5. Finalmente, presentar conclusiones sólidas basadas en los resultados obtenidos, destacando la relevancia y el impacto potencial de este estudio en la mejora de la eficiencia y la gestión de líneas de productos. Lo vemos en el capítulo 6. A través de la consecución de estos objetivos, se espera contribuir significativa- mente al cuerpo de conocimientos existentes en el campo de la ingeniería de sistemas, proporcionando nuevas perspectivas y herramientas para abordar los desafíos espe- cíficos asociados con el diseño y la operación de líneas de productos. 1.3. Plan de trabajo La metodología de trabajo de este Trabajo de Fin de Grado se divide en los siguientes tareas: 1. Investigación de la literatura que aborda el tema de la modelización de líneas de producto mediante redes de Petri. 2. Desarrollo, implementación y validación de algoritmos de creación de grafos de alcanzabilidad. 3. Elaboración de este manuscrito. Para ello hemos seguido una metodología Ágil (9) usando la herramienta Jira (1) para compaginar de forma concurrente las distintas tareas. Además, durante el desarrollo del proyecto hemos tenido reuniones cada una o dos semanas de una media hora de duración, para actualizar el trabajo hecho, el pendiente y posibles dudas. 4 Capítulo 1. Introducción Figura 1.1: Diagrama de Gantt. Fuente: Jira (1) 1.4. Estructura del documento Este documento se estructura en seis capítulos, comenzando en este primer ca- pítulo Introducción con la presentación de este trabajo. En el Capítulo 2 vemos todos las definiciones y resultados necesarios para comprender el resto del trabajo. En los Capítulos 3 y 4 estudiamos en detalle la implementación y presentamos ejem- plos de los mismos. Y en el Capítulo 5 veremos como se han logrado los objetivos de este trabajo. Capı́tulo 2 Conceptos previos Comenzamos viendo los conceptos básicos para abordar este Trabajo de Fin de Grado, empezando por los grafos ya que utilizaremos multitud de resultados sobre grafos y modificaremos algoritmos conocidos para la implementación de los grafos de alcanzabilidad. Más adelante veremos las redes de Petri, las líneas de productos, las líneas de producto de redes de Petri y por último Titan (4), la herramienta sobre la que realizaremos nuestra implementación. Con esto habremos finalizado todos los conceptos previos necesarios para introducir los grafos de alcanzabilidad. 2.1. Grafo Decimos que un grafo es un conjunto de nodos o vértices unidos por aristas o arcos que nos permiten representar relaciones binarias entre elementos de un conjunto. Formalmente un grafo G es un par ordenado G = (V,E) donde V es el conjunto de vértices o nodos del grafo y E es el conjunto de aristas o arcos que relacionan estos nodos (10). La Figura 2.1 muestra un ejemplo de grafo. Figura 2.1: Grafo. Fuente: (2) El interés que tienen los grafos en nuestro caso es que nos permiten estudiar los relaciones que existen entre los elementos que los representan, por ejemplo, en caso de una red de ordenadores podríamos representar los ordenadores como nodos y las conexiones entre ellos como aristas. Continuando con este mismo ejemplo, no 5 6 Capítulo 2. Conceptos previos siempre deseamos que las conexiones entre ordenadores vayan en ambos sentidos, por lo que introducimos un tipo concreto de grafo para representar estas situaciones. 2.1.1. Grafo dirigido Decimos que un grafo es un grafo dirigido si las aristas que lo componen tienen un sentido definido, es decir, las relaciones entre los elementos del conjunto no tienen porque ser simétricas. Formalmente un grafo dirigido G está formado por un par ordenado de conjuntos G = (V,E) donde V es un conjunto de vértices o nodos y E es un conjunto de vértices o aristas, estas aristas a diferencia de los grafos no dirigidos, son pares ordenados (x, y) que verifican ∀(x, y) ∈ G, x ∈ V, y ∈ V (10). Decimos en este caso que el arco e = (x, y) va del nodo x al nodo y. La Figura 2.2 muestra un ejemplo de grafo dirigido. Figura 2.2: Grafo dirigido. Fuente: (3) Continuando aún con el anterior ejemplo, no siempre queremos que una máquina este conectada consigo misma o que tenga varias conexiones distintas a otra máquina en la red, en este caso decimos que nuestro grafo es simple. 2.1.2. Grafo dirigido simple Decimos que un grafo dirigido es simple si acepta una sola arista uniendo dos vértices cualesquiera, es decir, existe una única arista que une dos vértices entre ellos. Formalmente decimos que un grafo dirigido G es simple si y solo si ∀e = (x, y) ∈ E, e ̸= a donde a ∈ E\{e} (10). La Figura 2.3 muestra un ejemplo de grafo dirigido simple. Figura 2.3: Grafo dirigido simple. Fuente: Elaboración propia 2.2. Red de Petri 7 De ahora en adelante nos centraremos en los grafos dirigidos simples, ya que son los que utilizamos para mostrar y estudiar los grafos de alcanzabilidad y el comportamiento dinámico de las redes de Petri. Pasamos ahora a estudiar las redes de Petri en detalle. Las redes de Petri son representaciones de un sistema discreto que nos permiten describir y estudiar en detalle procesos concurrentes. Como se ha comentado anteriormente tienen multitud de aplicaciones en el mundo real, desde el análisis de datos, simulación de sistemas, y diseño de software hasta planificación del flujo de trabajo. 2.2. Red de Petri Una red de Petri es una representación de un sistema de eventos que permite describir un sistema concurrente, compuesta por lugares, transiciones, arcos dirigidos y marcas o tokens. Una red de Petri es una 5-tupla R = {P, T, F,W,m0} donde P es un conjunto finito de lugares, T un conjunto finito de transiciones, F ⊆ (P ×T )∪ (T × P ) conjunto finito de arcos, W es una función que asigna un peso a los arcos, W : F → N y m0 es la distribución inicial de tokens, también llamado estado inicial (11; 7). Veamos en detalle cada uno de estos elementos. Lugares. Contienen las marcas o fichas del sistema, el conjunto de los todos ellos representa el estado del sistema en un determinado instante. Transiciones. Representan eventos del sistema que alteran la red de Petri. Pueden ser disparadas para mover marcas o fichas entre los lugares que rela- cionan. Arcos dirigidos. Relacionan transiciones con lugares o lugares con transicio- nes, nunca transiciones con transiciones o lugares con lugares. En el caso de arcos dirigidos entre lugares y transiciones, tienen un peso que es la cantidad de marcas necesarias en el lugar de inicio para poder ser disparada la transición a la que apuntan. En el caso de arcos dirigidos entre transiciones y lugares, tienen un peso que es la cantidad de marcas que se depositan en el lugar de llegada cuando es disparada la transición de la que provienen. Marcas o fichas (tokens). Pueden representar multitud de conceptos en el sistema, el ejemplo más común es recursos. Distribución inicial. Es la distribución inicial de los tokens entre los dife- rentes lugares. Después de haber visto las partes que componen las redes de Petri, veamos las restricciones asociadas a las mismas (11). Un mismo elemento de la red no puede ser un lugar y una transición a la vez, P ∩ T = Ø. 8 Capítulo 2. Conceptos previos Los arcos deben conectar un lugar con una transición, o conectar una transición con un lugar. No pueden existir arcos de transiciones a transiciones o de lugares a lugares. Los lugares pueden contener una cantidad finita o contable de marcas. Las transiciones para dispararse deben consumir marcas en las posiciones de entrada (la que apuntan a la transición) y producen marcas en las posiciones de llegada (las que salen de la transición). Una transición puede ser disparada si tiene las marcas suficientes en sus posi- ciones de entrada. Veamos un ejemplo extenso de red de Petri, en la Figura 2.4 para comprender bien su funcionamiento, utilidad y restricciones: Figura 2.4: Red de Petri. Fuente: Elaboración propia. Esta red de Petri modela un ordenador que puede conectarse a otras máquinas en la misma red. Los lugares, los círculos, son los estados en los que se encuentra este ordenador, sin conexión o conectada a una o más máquinas. Las marcas o tokens representan los recursos disponibles por el ordenador para realizar las conexiones. Las transiciones, los rectángulos, representan las acciones que toma el ordenador para cambiar su estado. Los arcos dirigidos, las aristas, son las relaciones entre los estados y las transiciones e indican con un número (el 1 se omite) los recursos necesarios, el peso del arco, en el lugar de partida para poder recorrer ese camino 2.2. Red de Petri 9 en el caso de arcos de lugares a transiciones, y en el caso de arcos de transiciones a lugares, la cantidad de recursos que generan en el lugar de llegada. Por último llamamos estado de la red de Petri a la ubicación de sus tokens en un determinado instante, lo formalizamos definiéndolo como un conjunto m de pares or- denados mp = (p, n) donde p ∈ P es un lugar de la red de Petri y n ∈ N es el número de tokens que se encuentran en ese lugar. El estado m = {mp1,mp2,mp3, ...,mpk} con k = |P | satisface que ∀p ∈ P∃!mpi = (mpi,mpi) ∈ S tal que i ∈ {1, k}∧mpi = p, es decir, por cada lugar de la red de Petri existe un y solo un par ordenado en el estado asociado con el lugar. Por facilitar la visualización solo mostraremos en los diversos gráficos que mencionan estados los lugares con al menos un token, por ejemplo, el estado de la Figura 2.4 será {[Sin_conexion, 2]} Ahora después de haber estudiado que es una red de Petri estamos en condiciones de introducir una de sus variantes, las redes de Petri con tiempo, donde los tokens cuentan con una marca temporal y las transiciones con retardos. 2.2.1. Red de Petri con tiempo Definimos una red de Petri con tiempo de forma similar a la red de Petri, es una 6- tupla Z = (P, T, F,W,m0, τ) donde P es un conjunto finito de lugares, T un conjunto finito de transiciones, F ⊆ (P × T ) ∪ (T × P ) conjunto finito de arcos y W es una función que asigna un peso a los arcos, W : F → N, m0 es el estado o localización de tokens inicial y τ es una función que asocia un retardo a las transiciones, τ : T → R+. (12) Vemos ahora en detalle las diferencias de una red de Petri a una red de Petri temporal. Los tokens tienen asociado en este caso una marca temporal o timestamp, que indica el instante en el que son depositados en el lugar que se encuentran. Este valor cambia cada vez que una transición es disparada y cambia el estado de la red. Las transiciones cuentan con un retardo, que indica el tiempo que tarda en dispararse, es decir, consumir los tokens en los lugares de entrada y depositarlos en los lugares de salida. Es a través de estos retardos con los que alteramos las marcas temporales de los tokens. Existen dos tipos de transiciones distintas a causa de este retardo añadido: • Atómicas. El retardo de las transacciones 0, alteran el estado de la red de Petri pero no modifican las marcas temporales de los tokens. • En tres fases. Cuando la transición es disparada, fase uno, remueven los tokens de los correspondientes lugares de entrada, por la duración del retardo almacenan los tokens, segunda fase, y finalmente los depo- sitan en los correspondientes lugares de llegada modificando sus marcas temporales en función del retardo de la transición, tercera fase. 10 Capítulo 2. Conceptos previos Veamos una presentación de la red de la Figura 2.4 esta vez con el delay de cada transición, representada en el dibujo con π = milisegundos. Figura 2.5: Red de Petri con tiempo. Fuente: Elaboración propia. Una vez vistas las redes de Petri nos disponemos a introducir las líneas de pro- ducto, que nos permiten introducir variabilidad en nuestros modelos. 2.3. Líneas de producto Definimos la línea de productos como una representación de un modelo que permite definir características, dependencias y restricciones de sus elementos. For- malmente una linea de productos es una tupla FM = (F, ϕ) donde F = {f1, ..., fn} es un conjunto variables proposicionales llamadas características y ϕ es una fórmu- la proposicional sobre las variables de F (4). Este suele representarse con lo que denominamos diagrama de características (FM, del inglés Feature Model), que nos informa de las configuraciones posibles finales. Explicamos la definición sobre un ejemplo en la Figura 2.6: Esta representación en árbol nos muestra las diferentes configuraciones (o Feature configurations (4)) que podemos obtener: De los nodos. • Obligatorios. Cualquier linea de producto debe contener los elemen- tos marcados como obligatorios, es nuestro caso, debe contener Conectar 2.4. Líneas de Producto de Redes de Petri 11 Figura 2.6: Diagrama de características. Fuente: Elaboración propia. máquina a la red. • Opcionales. Una línea de producto final puede contener o no contener este elemento y seguir siendo válida. En nuestro caso, tenemos Configurar parámetros_1, Configurar parámetros_2 y Reiniciar conexión. De las relaciones. • Alternativa. Debe incluirse una y solo una de las características des- cendientes de está, es nuestro caso, es la relación entre Máquina 3· y sus descendientes TCP y UDP. • Or. Debe incluirse al menos una de las características descendientes, pu- diendo incluirse más. En nuestro caso, es la relación Conectar máquina a a red con sus descendientes Máquina 1, Máquina 2, Máquina 3, y Máquina 1 y Máquina 2. Un ejemplo de configuración válida sería “Conectar máquina a la red con Máquina 1 y Máquina 2” y “Configurar parámetros_2” y una configuración inválida sería “Conectar máquina a la red con Máquina 3”, ya que no tiene ni TCP ni UDP. Nos disponemos ahora a juntar los dos conceptos más importantes vistos en esta sección, las redes de Petri y las líneas de producto, que como veremos, nos permiten extender la variabilidad de las líneas de producto a las redes de Petri que modelan nuestro sistema. 2.4. Líneas de Producto de Redes de Petri También llamadas PNPL (Petri Net Product Lines). Formalmente se define como una 3-tupla PNL = (FM,PN, ϕ) donde FM es un diagrama de características, PN una red de Petri y ϕ un mapeo de pares (x, ϕx) donde x ∈ P ∪T ∪A es un elemento de la fórmula proposicional ϕx de las características del diagrama de características (4). Gracias al diagrama de características y la especificación de las características 12 Capítulo 2. Conceptos previos Figura 2.7: Ejemplo de configuración. Fuente: Elaboración propia. en redes de Petri, podemos crear redes de Petri concretas que representan una de- terminada configuración de este diagrama de características. Veamos esta propiedad en la Figura 2.8. Figura 2.8: Configuración de una linea de producto. Fuente: (4) En el ejemplo se aprecia que hemos tomado la configuración de PartB, Parallel y Prod1, dejando fuera PartA, QuialityControl, Prod2 y Prod1&Prod2. El resultado de esta configuración es una red the petri que une los distintos elementos de una linea de producto. Una vez vistas estas redes de Petri de líneas de productos, veamos las ventajas frente a sus alternativas. 2.4. Líneas de Producto de Redes de Petri 13 2.4.1. Ventajas de las redes de Petri para el análisis de líneas de producto Las redes de Petri presentan multitud de ventajas a la hora de representar y analizar líneas de producto respecto a otros tipos de autómatas: Sencillez y legibilidad de la visualización. Las redes de Petri son muy legibles en comparación a otros tipos de autómatas para describir eventos concurrentes gracias a la distinción de lugares y transiciones. Reutilización de patrones comunes. Son conocidos los patrones de diseño de estructuras clásicas como bucles, mutex (exclusión mutua) o semáforos entre otros muchos. Lo que nos permite reutilizarlas rápidamente entre distintos proyectos o en la misma linea de producto. Vemos un ejemplo concreto en la implementación del un mutex en la Figura 2.9. Figura 2.9: Mutex de dos hilos. Fuente: Elaboración propia. Escalabilidad. Nos permiten trabajar de forma incremental y modular con mucha sencillez sin tener que realizar apenas cambios en el trabajo ya realizado, como vemos en el ejemplo Figura 2.10 en el que hemos añadido un hilo adicional que comparte una sección crítica con el mutex de la Figura 2.9. Implementación sencilla. Implementamos las redes de Petri como grafos dirigidos en los que tenemos que respetar las restricciones y la funcionalidad de los lugares, transiciones, arcos y tokens descritas anteriormente en esta sección. 14 Capítulo 2. Conceptos previos Figura 2.10: Mutex de tres hilos. Fuente: Elaboración propia. Reutilización de algoritmos. Debido a esta implementación similar a los grafos dirigidos, podemos aprovechar y reutilizar los diversos algoritmos cono- cidos para grafos dirigidos para desarrollar algoritmos aplicables a las redes de Petri como búsqueda en profundidad, conexión del grafo... Por último, habiendo visto ya todos los conceptos relacionados con las líneas de producto modeladas como redes de Petri, pasamos a hablar de la herramien- ta que utilizaremos como base para el desarrollo de nuestros algoritmos, TITAN, mencionando brevemente su arquitectura y su interfaz de usuario. 2.5. Titan Titan es una herramienta gratuita disponible en https://github.com /antonio- garmendia/titan desarrollada como un plug-in de Eclipse (8). Presentamos su ar- quitectura en la Figura 2.11. Esta herramienta permite definir redes de Petri de líneas de productos, editarlas y en concreto para el interés de este Trabajo de Fin de Grado, implementar nuevas funcionalidades para trabajar y analizar las redes de Petri resultantes de una confi- guración de características. En la Figura 2.12 donde 1 es el editor visual, 2 la vista 2.5. Titan 15 Figura 2.11: Arquitectura de TITAN. Fuente: (5) de invariantes, 3 y 4 son herramientas para filtrar la visualización. Sin embargo, tal y como vemos en la columna de la derecha de la Figura 2.11, TITAN todavía no soporta la generación de grafos de alcanzabilidad como resultado del análisis de redes de Petri con líneas de producto. Figura 2.12: Entorno de TITAN. Fuente: (5) Una vez vistos todos los conceptos previos que necesitamos estamos en disposi- ción de abordar el tema de los grafos de alcanzabilidad, que veremos en el próximo 16 Capítulo 2. Conceptos previos capítulo. Capı́tulo 3 Grafos de Alcanzabilidad En esta sección explicamos todos los conceptos relacionados con la propiedad dinámica de la alcanzabilidad de las redes de Petri, comenzando por la alcanzabilidad de un estado. Inicialmente, presentamos en este capítulo los grafos de alcanzabilidad sin tiempo. En el posterior capítulo 4 introduciremos una variante de grafos de alcanzabilidad con tiempo, idónea para analizar sistemas temporizados con un reloj global y retardos temporales. 3.1. Estado alcanzable Sea una red de Petri T , decimos que un estado m es alcanzable por la confi- guración inicial o estado inicial m0 ∈ T si existe una secuencia finita disparo de transiciones σ desde el estado inicial m0 tal que σ : m0 t1−→ m1 t2−→ ... tk−→ m donde t1, t2, ...tk son transiciones de la red de Petri T . (13) A continuación vamos a definir y explicar los grafos de alcanzabilidad de una linea de producto modelada con redes de Petri. 3.2. Grafo de alcanzabilidad de una PNPL Definimos un grafo de alcanzabilidad como un grafo dirigido G = (V,E) donde los vértices o nodos E representan los estados alcanzables m de una red de Petri R y las aristas o arcos E representan la transición disparada entre los estados, es decir, sea e = (x, y) ∈ E esto significa que disparando la transición e desde el estado x de la red de Petri alcanzamos el estado y de la red de Petri. (13) Gracias a esta definición, y como veremos en la implementación 3.4 del algorit- mo de generación del grafo de alcanzabilidad en este mismo capítulo, el grafo de alcanzabilidad contiene todos los estados alcanzables m desde el estado inicial dado 17 18 Capítulo 3. Grafos de Alcanzabilidad m0 siempre que este grafo sea finito. Estudiamos el ejemplo de la Figura 3.1 para comprender mejor el objetivo del grafo de alcanzabilidad. (a) Red de Petri (b) Grafo de alcanzabilidad Figura 3.1: Grafo de alcanzabilidad de la red de Petri. Fuente: (6) El grafo de alcanzabilidad describe con los nodos los estados de la red de Petri del ejemplo y las transiciones que se disparan para cambiar entre los diferentes estados posibles. En este caso la aparición del nombre de un lugar de la red de Petri en un estado del grafo de alcanzabilidad implica que tiene al menos un token, y si no aparece este nombre que no tiene ninguno. Por ejemplo, para ir del estado en el que la red tiene un único token el el lugar i, disparamos la transición x para acabar con un token en los estados p1 y p5. Al igual que la red de Petri (a) es el estado del nodo i del grafo de alcanzabilidad, la siguiente Figura 3.2 es el estado de la red de Petri correspondiente al nodo [p1, p5] del grafo de alcanzabilidad. Figura 3.2: Estado [p1, p5]. Fuente: (6) Vemos que en el grafo de alcanzabilidad los estados p4 y o aparecen rodeados en rojo y sin conectar, esto es porque en este caso no son estados alcanzables por la configuración inicial de esta red de Petri. Se incluyen en la imagen a pesar de no pertenecer al grafo para resaltar la ausencia de los mismos en el grafo de alcanzabi- lidad. 3.3. Características del grafo de alcanzabilidad 19 3.3. Características del grafo de alcanzabilidad Como podemos intuir por las definiciones y los ejemplos aportados hasta ahora el grafo de alcanzabilidad verifica las siguientes propiedades. Conexo. El grafo de alcanzabilidad que obtenemos de cualquier red de Petri es siempre conexo, podemos razonarlo sencillamente viendo que este grafo representa los estados alcanzables desde una cierta configuración inicial, por lo que debe existir un camino desde el vértice inicial a todos y cada uno de los otros vértices del grafo y por lo tanto el grafo ha de ser conexo. Sin embargo, esta condición no garantiza que el grafo sea porque ser fuertemente conexo. No finitud. No podemos asegurar que el grafo de alcanzabilidad de una red de Petri sea finito, sea la red de Petri finita o no. Para ilustrarlo mejor vemos un ejemplo con la red de Petri descrita en la Figura 3.3 (a) 1. Estado inicial (b) 2. x disparado (c) 3. y disparado (d) 4. x disparado Figura 3.3: Red de Petri con grafo de alcanzabilidad no-finito. Fuente: Elaboración propia. En este caso vemos que al disparar la transición x y luego la y de forma sucesi- va, vamos acumulando tokens en el lugar b a la vez que nos permite continuar disparando las transiciones x e y cuanto queramos, con lo que tendríamos un grafo de alcanzabilidad no-finito descrito en la Figura 3.3. Como vemos, este grafo es no finito, con una sucesión no-finita de estados como sigue: {[begin, j], [b. j]} x−→ {[a, j], [b. j+1]} y−→ {[begin, j], [b. j + 1]}... 20 Capítulo 3. Grafos de Alcanzabilidad Figura 3.4: Grafo de alcanzabilidad no-finito. Fuente: Elaboración propia. Completo. El grafo de alcanzabilidad recoge todos los estados alcanzables de una red de Petri dada desde un cierto estado inicial. Si un estado no aparece en este grafo, no es posible llegar a el. Veremos más adelante en la implementación 3.4 que esto en efecto se verifica. Una vez vistas las características de estos grafos, pasamos a ver la implementa- ción de los algoritmos que generan estos grafos en detalle. 3.4. Implementación Para implementar el grafo de alcanzabilidad dada una red de Petri recorremos en la red de Petri como si de un grafo se tratara respetando las diferencias corres- pondientes entre los lugares y las transiciones. Desde un estado dado recorremos en profundidad las diferentes transiciones que podrían ser disparadas hasta que, o bien hemos recorrido todos los estados posibles de la red de Petri, o bien hemos detectado que el grafo de alcanzabilidad es no-finito. Esto sucede cuando llegamos a un mismo estado (salvo por la cantidad de tokens de los lugares del estado) en la que la cantidad de tokens aumenta, sin que se modifique el comportamiento del estado. 3.4.1. Algoritmo de generación del grafo de alcanzabilidad Este algoritmo está basado en un algoritmo de exploración en profundidad de un grafo. Dada una red de Petri T , generamos un grafo de alcanzabilidad G, el procedimiento es el siguiente (13). 1. Verificamos que la red de Petri T dada contiene al menos un token en algún lugar P . 2. Identificamos y guardamos el estado inicial m0 en un vértice o nodo como raíz de nuestro grafo de alcanzabilidad G. Almacenamos el estado de una red de 3.4. Implementación 21 Petri recorriendo todos los lugares P de la red y almacenando los tokens que contienen en una lista. 3. Realizamos ahora la llamada recursiva con el estado m, la primera llamada se realiza desde la raíz m0. a) Recorremos una a una todas las transiciones de la red de Petri T consi- derando los tokens del estado proporcionado m. 1) Si la transición t no puede ser disparada la ignoramos y pasamos a la siguiente. Una vez hemos recorrido todas las transiciones del esta- do m podemos asegurar que ya hemos encontrado todos los estados alcanzables desde el estado m y finalizamos la exploración desde ese vértice. 2) Si una transición t puede ser disparada generamos un nuevo estado m′, si este estado se encuentra ya en el grafo G conectamos los estados m y m′ y continuamos recorriendo transiciones. Si este nuevo estado m′ no se encuentra en el grafo G creamos un nuevo nodo en el grafo con el estado m y volvemos a llamar a nuestra función recursiva desde el nuevo nodo m′. Por esta implementación del algoritmo podemos asegurar que todos los estados alcanzables desde el estado inicial m0 se encuentran en el grafo G, siempre que este sea finito. Debido a las similitudes de este algoritmo con el algoritmo de búsqueda en pro- fundidad de un grafo, a pesar de que nosotros generemos los nodos “sobre la mar- cha”, es inmediato asegurar la validez y las características del mismo se verifican para nuestro algoritmo (14). Pasamos ahora a ver en los dos próximos apartados aspectos de la implementa- ción y sus componentes en mucho mayor detalle. 3.4.2. Componentes de la implementación Desde el punto de vista de la ingeniería del software cabe destacar los siguientes detalles. Se ha implementado el proyecto utilizando el lenguaje de programación Java (15). Hemos usando el entorno de programación Eclipse debido a que Titan, como ya hemos mencionado antes, es un plug-in de Eclipse. Y finalmente hemos usado librerías conocidas como java.util (16) para utilizar estructuras de datos comunes como grafos, listas o mapas. 22 Capítulo 3. Grafos de Alcanzabilidad 3.4.3. Implementación en detalle En este apartado discutimos las distintas decisiones de implementación que he- mos tomado en para la implementación del algoritmo de generación del grafo de alcanzabilidad. Hemos implementado esta funcionalidad de la aplicación TITAN creado un nuevo proyecto para encapsularla del resto de la aplicación. Veremos ahora en detalle cada uno de las clases o componentes de esta imple- mentación. La funcionalidad de cada componente se implementa en su totalidad en la propia clase. Comenzamos por la implementación de la red de Petri, utilizando únicamente los parámetros necesarios para construir el grafo de alcanzabilidad. Realizamos una implementación de una red de Petri propia para manejar únicamente los atributos que necesitamos y no alterar la red de Petri que recibimos de la aplicación. Tokens (GToken). La implementación de los tokens de la red de Petri se realiza en una clase cuyo único atributo son timestamps de los tokens, vere- mos más adelante que son necesarios para la implementación de los grafos de alcanzabilidad con tiempo. Lugares (GPlace). Contamos con los atributos necesarios para construir el grafo de alcanzabilidad, el nombre, una lista de inputs, outputs y tokens de cada lugar. Todas las listas las implementamos con la clase List de java.util.List y java.util.ArrayList (16). Transiciones (GTransition). Contamos con los atributos necesarios para construir el grafo de alcanzabilidad, el nombre, una lista de inputs, outputs y el retardo de la transición, que será necesario para los grafos de alcanzabilidad de redes de Petri con tiempo. Todas las listas las implementamos con la clase List de java.util.List y java.util.ArrayList (16). Arcos (GArc). Cuentan únicamente con el nombre del arco y su peso. De esta clase heredan los dos tipos de arcos presentes en las redes de Petri. • Arco transición lugar (GTPArc). Tienen una referencia a la transi- ción de la que vienen (input) y al lugar al que van (output). • Arco lugar transición (GPTArc). Tienen una referencia al lugar del que vienen (input) y a la transición a la que van (output). Red de Petri (GPetriNet). Cuentan con una lista de lugares, transicio- nes y un reloj global, veremos la necesidad de este último en los grafos de alcanzabilidad de las redes de Petri con tiempo. Finalmente veamos la implementación pertinente al grafo de alcanzabilidad (Reacha- bilityGraph). 3.5. Aplicaciones 23 Arco (Edge). Almacenamos el nombre del arco (la transición disparada entre estados) así como los estados de donde sale y llega el arco. Estado (State). Tenemos un mapa implementado como un HashMap de string y listas de tokens donde asociamos cada lugar de la red de Petri, en un determinado instante, con una lista de los tokens que encontramos en ese lugar. En caso de que el lugar no tenga ningún token no lo almacenamos en nuestro mapa. Grafo de alcanzabilidad (ReachabilityGraph). Almacenamos el grafo de alcanzabilidad en esta clase como un HashMap de estados asociados a listas de arcos. Esta clase tiene una copia de la red de Petri proporcionada así como el estado inicial y se ocupa de generar el grafo de alcanzabilidad. La decisión de las diversas estructuras usadas parece acertada, siendo cada una de estas una forma razonable de representarlas, aunque siempre existen alternativas similares, como representar un grafo mediante una matriz de incidencia en lugar de un HashMap. Finalmente, tras ver todas las minucias de implementación podemos hablar de las aplicaciones prácticas de los grafos de alcanzabilidad. 3.5. Aplicaciones La principal aplicación de los grafos de alcanzabilidad radica en su última carac- terística, la completitud, que nos asegura que si un estado de nuestra red de Petri se encuentra en este grafo significa que es alcanzable, y por el contrario si no está en el grafo no podremos llegar a el de ninguna forma. Esta información es tremendamente útil para evaluar las características de una red de Petri y comprobar que el comportamiento de la red de Petri se ajusta al modelo y el proceso que estamos representando. Presentamos las principales aplicaciones ahora. Todos los estados de la red de Petri alcanzables son deseados. No existen estados sin sentido, como podría ser que una máquina estuviera apagada y encendida a la vez por ejemplo. Todos los estados esperados se encuentran en el grafo. Por ejemplo una máqui- na que no pudiera nunca apagarse ya que no se puede disparar esa transición. Manejo de recursos. El proceso genera recursos y los destruye tal y como debería, tanto si queremos modelar un proceso que tiene infinitos estados, en caso de obtener un grafo de alcanzabilidad no-finito, tanto como si queremos modelar un proceso con una cantidad finita o menguante de recursos. 24 Capítulo 3. Grafos de Alcanzabilidad Captura de comportamientos no deseados. Podemos detectar transiciones en- tre estados no deseadas, como por ejemplo enviar un producto sin haberse terminado de embalar. Se respetan los diferentes comportamientos del proceso. Si existe una o más alternativas desde un cierto estado, todas ellas están presentes en el grafo de alcanzabilidad. Existencia de puntos muertos. Conocidos también como deadlocks, este grafo nos permite identificar y detectar estos comportamientos no deseados. Terminación correcta. Todos los estados finales, desde no se disparan ninguna transición son los esperados. Como hemos visto, este grafo nos permite de manera concisa, resumida y efi- caz detectar multitud de problemas o confirmar la ausencia de los mismos con un procedimiento sencillo y rápido. Es una gran herramienta tanto para ver el compor- tamiento a grandes rasgos del proceso, como para centrarse en aspectos específicos del mismo. Terminamos hablando de la representación gráfica de estos grafos, junto con un ejemplo. 3.6. Representación gráfica Para los gráficos mostrados se ha utilizado la herramienta Graphvi (17), adap- tando la salida del algoritmo para representar los grafos con esta. Veamos el aspecto de un grafo de alcanzabilidad, dada la red de Petri del ejemplo de conexión con distintas máquinas. La red de Petri se muestra en la Figura 3.5. A continuación vemos el grafo de alcanzabilidad mostrado en la Figura 3.6, el cual ha sido generado para la red de Petri de la figura 3.5. Cabe destacar que por legibilidad hemos decidido darle un doble borde al es- tado raíz (home) del que parte el grafo, lo vemos en la Figura 3.5 en el nodo {[sin_conexion, 2]}. 3.6. Representación gráfica 25 Figura 3.5: Red de Petri. Fuente: Elaboración propia. 26 Capítulo 3. Grafos de Alcanzabilidad Figura 3.6: Grafo de alcanzabilidad. Fuente: Elaboración propia. Capı́tulo 4 Grafos de Alcanzabilidad con Tiempo Presentamos ahora el cálculo del grafo de alcanzabilidad de una red de Petri con tiempo, donde debemos en cuenta el retardo de los arcos y el disparo de transiciones atendiendo a funciones temporales. A efectos prácticos tanto su definición como implementación son muy similares a los grafos de alcanzabilidad sin tiempo, por lo que vemos directamente las principales diferencias entre ellos. 4.1. Decisiones de implementación En esta sección vamos a ver en detalle diferentes alternativas para calcular el grafo de alcanzabilidad y cuales de ellas hemos seleccionado: Elementos nuevos. • Reloj global. En el cálculo de nuestro grafo contamos con un reloj global que va aumentando a medida que navegamos entre los posibles estados de la red de Petri, en concreto, este reloj global se actualizará con el valor del anterior reloj global más la transición disparada en cada momento, reloj_global = reloj_global + transicion.retardo. Hemos decidido usar esta herramienta para poder tener una condición de parada paramétrica. • Timestamp en tokens. Los tokens de la red de Petri cuentan con un timestamp que indica el momento en el que fueron puestos en el lugar en el que se encuentran. Este timestamp se actualiza en cuanto disparamos una transición y los token se mueven de un lugar a otro con el valor del nuevo reloj global después de disparar la transición. En concreto los lugares almacenan tokens con una estructura FIFO (First In First Out). Si hubiera más de un token en un mismo lugar para disparar la transición, moveremos primero los tokens más antiguos de cada uno de los lugares necesarios, es decir, los de menor timestamp. 27 28 Capítulo 4. Grafos de Alcanzabilidad con Tiempo • Disparos atómicos. Una única transición puede ser disparada a la vez, y hasta que esta transición no finaliza, el reloj global alcanza su retardo, no podemos disparar otra transición. • Diferenciación de estados por timestamp. Hemos decido diferenciar estados por su timestamp, es decir, dos estados que solamente difieran en el timestamp de sus tokens, no en su lugar, se considerarán estados diferentes entre ellos. Esta decisión provoca que estos grafos de alcanza- bilidad sean potencialmente ilegibles para un ser humano, pero aportan mucha más información a un algoritmo para trabajar en ellos. Hemos valorado realizar un posible “plegamiento” del grafo después de generarlo, en el que unamos los diferentes estados obviando el timestamp asociado a sus tokens para lograr un grafo más legible y similar al grafo de alcanzabilidad sin tiempo, manteniendo a la vez parte de la información relativa al tiempo. Como decidimos que transición disparamos. En este caso hemos optado por disparar la transición, siempre que esta pueda ser disparada, con menor re- tardo, hemos optado por esta implementación por los problemas que presentan las diversas alternativas: • Disparar la transición de menor retardo. En este caso el grafo de alcanzabilidad que generemos con la misma red de Petri siempre será el mismo y es por esto que lo hemos valorado como mejor opción. Sin embargo, esta opción tiene la desventaja de la existencia de carreras que resolvemos comparando el timestamp de cada uno de los tokens en los lugares de entrada de la transición. Si el menor timestamp de estos tokens también coincide, tomamos la transición declarada antes. • Disparos aleatorizados por peso. La desventaja de esta opción es que el grafo de alcanzabilidad no será, en general, igual dada la misma red de Petri inicial. Adicionalmente tampoco encontramos un consenso para asignar el peso a que transición usamos, podríamos usar la cantidad de tokens, el retardo de la transición, la anterior transición disparada y una miríada más de criterios con todas sus posibles combinaciones. • Probabilidad de transición no disparada. En este caso la desventaja, al igual que la opción anterior, es que no siempre generaremos el mismo grafo de alcanzabilidad. Con estas consideraciones previas hemos conseguido que el grafo de alcanzabi- lidad temporal que generamos sea siempre el mismo dado una misma red de Petri inicial. Las características, la implementación y sus aplicaciones son muy similares al grafo de alcanzabilidad sin tiempo. Veamos donde más difiere de los anteriores, su representación gráfica. 4.2. Representación gráfica 29 4.2. Representación gráfica En este caso al diferenciar los estados por su reloj global y la marca temporal de sus tokens, los incluimos en su representación. El resto de sus elementos es igual o similar a la representación de los grafos de alcanzabilidad sin tiempo. Vemos un ejemplo con la red de Petri de la Figura 4.1, igual a la de la Figura 3.5, salvo por los delays de las transiciones. Y podemos apreciar que el grafo de alcanzabilidad 3.6 es muy distinto que obtenemos ahora en la Figura 4.2. Figura 4.1: Red de Petri. Fuente: Elaboración propia. Como se puede observar, cada vértice cuenta con un número al principio que es el instante en el que se consigue ese estado de la red de Petri. Además cada lugar del vértice se relaciona con el tiempo de cada uno de los tokens que tiene, no con la cantidad de ellos. Veamos otro ejemplo de gráfo de alcanzabilidad con tiempo con un mutex entre dos procesos en la Figura 4.4 de la red de Petri de la Figura 4.3. 30 Capítulo 4. Grafos de Alcanzabilidad con Tiempo Figura 4.2: Grafo de alcanzabilidad con tiempo (100 tiempo máximo). Fuente: Ela- boración propia. Figura 4.3: Red de Petri mutex. Fuente: Elaboración propia. 4.2. Representación gráfica 31 Figura 4.4: Grafo de alcanzabilidad de mutex con tiempo (100 tiempo máximo). Fuente: Elaboración propia. Capı́tulo 5 Conclusiones y Trabajo Futuro Para concluir este trabajo nos centramos en evaluar si hemos logrado los objetivos propuestos en el capitulo 1 de la introducción y posibles propuestas de cara al futuro. Pasamos a evaluar estos objetivos en primer lugar. 5.1. Objetivos alcanzados Comprobamos ahora que hemos logrado los objetivos secundarios propuestos. Objetivo secundario 1. Introducir y explicar de manera exhaustiva los con- ceptos previos necesarios. Se ha completado correctamente, ya que hemos dedi- cado el capítulo 2 Conceptos previos a abordarlo, estudiando los diferentes conceptos que se presentan y viendo ejemplos y casos concretos para asegurar su comprensión completa. Objetivo secundario 2. Desarrollar una implementación completa y funcio- nal de los grafos de alcanzabilidad aplicados a redes de Petri. En este caso también hemos logrado este objetivo, como hemos visto en los Capítulos 3 Grafos de Alcanzabilidad y 4 Grafos de Alcanzabilidad con Tiempo donde hemos desarrollado y explicado con todo lujo de detalle nuestra imple- mentación. Objetivo secundario 3. Realizar un análisis detallado de las características de estos grafos de alcanzabilidad. De forma similar al anterior objetivo, hemos visto las características de estos grafos con mucho detalle en el capítulo 3 Grafos de Alcanzabilidad. Objetivo secundario 4. Investigar las aplicaciones prácticas y la utilidad de los grafos de alcanzabilidad. De nuevo en los capítulos 3 Grafos de Alcan- zabilidad y 4 Grafos de Alcanzabilidad con Tiempo hemos explorado 33 34 Capítulo 5. Conclusiones y Trabajo Futuro las diversas aplicaciones que nos ofrecen estos grafos a la hora de evaluar un modelo. Objetivo secundario 5. Finalmente, presentar conclusiones sólidas basadas en los resultados obtenidos. Hemos logrado este último objetivo con la reali- zación de este trabajo. Acabamos de comprobar que hemos logrado todos los objetivos secundarios, por lo que podemos asegurar que hemos logrado nuestro objetivo principal, el desarrollo, implementación y estudio de grafos de alcanzabilidad de una red de Petri que modela una linea de producto. Podrían haberse mejorado ciertos aspectos de la implementación como el uso de hilos para explorar el grafo en profundidad, mejorando seguramente la rapidez del algoritmo. Así como, se podrían haber preparado grandes casos de prueba, o pruebas unitarias, para cerciorarse de que el resultado es el deseado, además de permitirnos modificar el código verificando que los requisitos de comportamiento siguen cumpliéndose. Finalmente terminamos con posibles contribuciones futuras que nazcan de este trabajo. 5.2. Trabajo futuro Por último, de cara trabajo futuro partiendo del realizado por este Trabajo de Fin de Grado podrían realizarse multitud de implementaciones distintas basándose en el algoritmo en el Capítulo 3, entre ellas destacamos las siguientes. Implementación un algoritmo con tiempo donde el disparo de una transición no impida el disparo de la misma u otras de forma simultánea o concurrente, expandiendo y explorando las alternativas que ofrecen los distintos grafos de alcanzabilidad resultantes. También podríamos considerar la incorporación de una probabilidad al disparo de las transiciones, cuando tengamos varias que puedan ser disparadas en los grafos de alcanzabilidad con tiempo. Finalmente, podría desarrollarse una “plegación” del grafo de alcanzabilidad con tiempo, uniendo estados por la cantidad de tokens que tienen para reali- zarlo más legible y comparable al grafo de alcanzabilidad sin tiempo generado por la misma red de Petri. Introduction The need to model variable concurrent processes, both on a small and large scale, such as a mutex between multiple threads, leads us to evaluate various representation alternatives such as queue networks, finite automaton, or Petri nets. We chose the latter because Petri nets (7) have become an indispensable tool in numerous fields such as data analysis, software design, and concurrent programming. Moreover, since the processes we model are variable, meaning there are multiple different configurations of the same process that create similar systems with slight differences, and we need to analyze them all at once, we model these processes using product lines. Product lines allow us to reuse and leverage the common elements of the different configurations we have for the same process, optimizing the analysis of the processes compared to analyzing each one independently. Following the previous mutex example, it can handle two or three threads, for instance. Our objective is to analyze the behavior over time of a process, specifically the reachability of its states, which is one of its dynamic properties. We describe the state of a process as the system’s configuration at a given moment. This brings us to the main objective of this Bachelor’s Thesis: analyzing the state reachability of product lines modeled as Petri nets. Our goal is to design algorithms for generating reachability graphs to analyze this dynamic property. In this work, we will cover all the necessary preliminary concepts to understand reachability analysis, accompanied by an example of connecting one machine to three different machines. The advantage of product lines is the associated variability; we can model a very complex system in its entirety or isolate and focus on smaller aspects of the model. The relevance of this research lies in the lack of previous studies available on reachability graphs specifically applied to Petri nets that model product lines. By addressing this knowledge gap, we aim to provide a significant contribution to the field, offering a deeper understanding and a practical tool for analyzing production systems in this domain. During this Bachelor’s Thesis, we developed the tool in TITAN, an Eclipse plugin 35 36 Capítulo 5. Conclusiones y Trabajo Futuro designed to analyze product lines modeled with Petri nets. 5.3. Motivation The motivation for this Bachelor’s Thesis is to provide new tools and resources for the analysis of variable concurrent systems that we encounter in the real world. To perform this analysis of concurrent systems, we conduct an exhaustive study of reachability, a dynamic property of Petri nets. Additionally, to add variability to the systems we evaluate, we study the ex- haustiveness of Petri nets in the context of product lines, an area that has received limited attention in the academic literature to date. More specifically, we will focus on the detailed development and implementation of reachability graphs of Petri nets, exploring not only their advantages and disad- vantages but also their practical application, intrinsic characteristics, and various potential applications in the modeling and analysis of product lines. 5.4. Objectives The main objective of this Bachelor’s Thesis is the development, implementation, and study of reachability graphs of a Petri net that models a product line. To achieve this, we break it down into the following secondary objectives: Secondary Objective 1. Introduce and thoroughly explain the necessary preliminary concepts to fully understand the rest of the work. This involves not only presenting known results on graphs and Petri nets but also contextualizing these concepts within the specific scope of product lines. This will be covered in Chapter 2. Secondary Objective 2. Develop a complete and functional implementa- tion of reachability graphs applied to Petri nets, including technical details on generation algorithms, data representation, and computational tools used. This will be studied in Chapters 2 and 3. Secondary Objective 3. Perform a detailed analysis of the characteristics of these reachability graphs, exploring their structure, emerging properties, and dynamic behavior in different scenarios. This will be examined in Chapters 2 and 3. Secondary Objective 4. Investigate the practical applications and useful- ness of reachability graphs compared to other modeling and analysis alterna- tives used in the context of product lines. This involves evaluating their effec- tiveness in detecting bottlenecks, optimizing processes, and predicting possible 5.5. Work Plan 37 failures or inconsistencies in production. This will be discussed in Chapters 2 and 3. Secondary Objective 5. Finally, present solid conclusions based on the results obtained, highlighting the relevance and potential impact of this study in improving the efficiency and management of product lines. This will be covered in Chapter 6. By achieving these objectives, we hope to significantly contribute to the existing body of knowledge in the field of systems engineering, providing new perspectives and tools to address the specific challenges associated with the design and operation of product lines. 5.5. Work Plan The methodology of this Bachelor’s Thesis is divided into the following points: 1. Literature review on the topic of modeling product lines using Petri nets. 2. Development, implementation, and validation of algorithms for creating reachability graphs. 3. Writing this manuscript. We have followed an Agile methodology (9) using the Jira tool (1) to concurrently manage the different tasks. Figure 5.1: Gantt Diagram. Source: Jira (1) Additionally, during the project development, we had meetings every one or two weeks, each lasting about half an hour, to update the completed work, pending tasks, and any possible doubts. 38 Capítulo 5. Conclusiones y Trabajo Futuro 5.6. Document Structure This document is structured into six chapters, beginning with this first chapter Introduction, which presents this work. In Chapter 2, we cover all the definitions and results necessary to understand the rest of the work. Chapters 3 and 4 study in detail the implementation and provide examples of these. And in Chapter 5, we discuss how the objectives of this work have been achieved. Conclusions and Future Work To conclude this work, we focus on evaluating whether we have achieved the objectives proposed in Chapter 1 of the introduction and possible future proposals. First, we evaluate these objectives. 5.7. Achieved Objectives We now verify that we have achieved the proposed secondary objectives. Secondary Objective 1. Introduce and thoroughly explain the necessary preliminary concepts. This has been successfully completed, as we dedicated Chapter 2 Preliminary Concepts to address this, studying the different pre- sented concepts and reviewing specific examples and cases to ensure a complete understanding. Secondary Objective 2. Develop a complete and functional implementa- tion of the reachability graphs applied to Petri nets. We have also achieved this objective, as seen in Chapters 3 Reachability Graphs and 4 Timed Reachability Graphs, where we developed and explained our implementa- tion in great detail. Secondary Objective 3. Perform a detailed analysis of the characteristics of these reachability graphs. Similarly to the previous objective, we have ex- amined the characteristics of these graphs in great detail in Chapter 3 Reach- ability Graphs. Secondary Objective 4. Investigate the practical applications and utility of the reachability graphs. Again, in Chapters 3 Reachability Graphs and 4 Timed Reachability Graphs, we have explored the various applications these graphs offer when evaluating a model. Secondary Objective 5. Finally, present solid conclusions based on the results obtained. We have achieved this final objective through the completion of this work. 39 40 Capítulo 5. Conclusiones y Trabajo Futuro We have verified that we have achieved all the secondary objectives, thus we can ensure that we have accomplished our main objective, the development, imple- mentation, and study of reachability graphs of a Petri net that models a product line. Certain aspects of the implementation could have been improved, such as us- ing threads to explore the graph in depth, likely improving the algorithm’s speed. Additionally, preparing extensive test cases or unit tests would ensure the desired outcome and allow us to modify the code while verifying that the behavior require- ments are still met. Finally, we conclude with possible future contributions that may arise from this work. 5.8. Future Work Lastly, regarding future work based on this Bachelor’s Thesis, various different implementations could be developed based on the algorithm in Chapter 3, among which we highlight the following: Implementing a timed algorithm where the firing of a transition does not prevent the simultaneous or concurrent firing of the same or other transitions, expanding and exploring the alternatives offered by the resulting reachability graphs. We could also consider incorporating a probability to the firing of transitions when we have multiple transitions that can be fired in timed reachability graphs. Finally, a "folding" of the timed reachability graph could be developed, merg- ing states by the number of tokens they have to make it more readable and comparable to the untimed reachability graph generated by the same Petri net. Bibliografía [1] Jira. [Online]. Available: https://www.atlassian.com/es/software/jira [2] Universidad Nacional de Colombia. Imagen grafo. [Online]. Available: https://ciencias.medellin.unal.edu.co/cursos/algebra-lineal/clases/ 8-clases/40-clase-2-parte3.html [3] Universidad de Alicante. Imagen grafo. [Onli- ne]. Available: https://blogs.ua.es/matematicadiscrecion/2010/11/30/ tipos-de-grafos-sesion-09112010-y-16112010/ [4] E. Gómez-Martínez, J. de Lara, and E. Guerra, “Extensible Structural Analysis of Petri Net Product Lines,” Trans. Petri Nets Other Model. Concurr., vol. 15, pp. 27–49, 2021. [5] E. Gómez-Martínez, E. Guerra, J. de Lara, and A. Garmendia, “Lifted struc- tural invariant analysis of Petri net product lines,” J. Log. Algebraic Methods Program., vol. 130, p. 100824, 2023. [6] Imagen red de petri. [Online]. Available: http://mlwiki.org/index.php/ Reachability_Graph [7] W. Reisig, Petri nets: an introduction. Springer Verlag, 1985. [8] Eclipse. [Online]. Available: https://eclipseide.org/ [9] agilemanifesto. [Online]. Available: https://agilemanifesto.org/ [10] K. H. Rosen, Discrete mathematics and its applications. McGraw-Hill, 2013. [11] T. Murata, Petri Nets: Properties, Analysis and Applications. Englewood Cliffs, 1989. [12] S. Haddad, Time and Timed Petri Nets. Lecture Notes, 2019. [13] M. A. Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis, MODE- LLING WITH GENERALISED STOCHASTIC PETRI NETS. Wiley, 1995. 41 https://www.atlassian.com/es/software/jira https://ciencias.medellin.unal.edu.co/cursos/algebra-lineal/clases/8-clases/40-clase-2-parte3.html https://ciencias.medellin.unal.edu.co/cursos/algebra-lineal/clases/8-clases/40-clase-2-parte3.html https://blogs.ua.es/matematicadiscrecion/2010/11/30/tipos-de-grafos-sesion-09112010-y-16112010/ https://blogs.ua.es/matematicadiscrecion/2010/11/30/tipos-de-grafos-sesion-09112010-y-16112010/ http://mlwiki.org/index.php/Reachability_Graph http://mlwiki.org/index.php/Reachability_Graph https://eclipseide.org/ https://agilemanifesto.org/ 42 BIBLIOGRAFÍA [14] G. Brassard and P. Bratley, Fundamentos de Algoritmia. Universidad de Mon- treal, 1996. [15] Java. [Online]. Available: https://docs.oracle.com/javase/8/docs/technotes/ guides/language/index.html [16] java.util. [Online]. Available: https://docs.oracle.com/javase/8/docs/api/java/ util/package-summary.html [17] Graphviz. [Online]. Available: https://graphviz.org/ https://docs.oracle.com/javase/8/docs/technotes/guides/language/index.html https://docs.oracle.com/javase/8/docs/technotes/guides/language/index.html https://docs.oracle.com/javase/8/docs/api/java/util/package-summary.html https://docs.oracle.com/javase/8/docs/api/java/util/package-summary.html https://graphviz.org/ Capı́tulo 6 Manual de Programador En este capítulo presentamos el readme del Github con instrucciones de como generar los grafos de alcanzabilidad. 6.1. Readme Download the proyect pnpl.analysis.dynamic and import it to the workspace. Launch the eclipse application from the new dynamic proyect. On the launched eclipse aplication, select the following options: You can then select between Reachability Graph and Timed Reachability Graph: On the Timed Reachability Graph there is an aditional window to select the time limit of the reachability graph: One the algorithm generates the graph it appears on the original application console in the Graphviz format: Paste the output on http://magjac.com/graphviz-visual-editor/ to see the gene- rated reachability graph. 43 44 Capítulo 6. Manual de Programador Figura 6.1: Selección de análisis. Fuente: Elaboración propia. 6.1. Readme 45 Figura 6.2: Selección de grafo de alcanzabilidad con o sin tiempo. Fuente: Elabora- ción propia. Figura 6.3: Selección del límite de tiempo para el grafo de alcanzabilidad con tiempo. Fuente: Elaboración propia. 46 Capítulo 6. Manual de Programador Figura 6.4: Salida del algoritmo en formato Graphviz. Fuente: Elaboración propia. Página de Título Índices Tabla de Contenidos Índice de figuras Índice de tablas Introducción Motivación Objetivos Plan de trabajo Estructura del documento Conceptos previos Grafo Grafo dirigido Grafo dirigido simple Red de Petri Red de Petri con tiempo Líneas de producto Líneas de Producto de Redes de Petri Ventajas de las redes de Petri para el análisis de líneas de producto Titan Grafos de Alcanzabilidad Estado alcanzable Grafo de alcanzabilidad de una PNPL Características del grafo de alcanzabilidad Implementación Algoritmo de generación del grafo de alcanzabilidad Componentes de la implementación Implementación en detalle Aplicaciones Representación gráfica Grafos de Alcanzabilidad con Tiempo Decisiones de implementación Representación gráfica Conclusiones y Trabajo Futuro Objetivos alcanzados Trabajo futuro Introduction Motivation Objectives Work Plan Document Structure Conclusions and Future Work Achieved Objectives Future Work Bibliografía Manual de Programador Readme