21 de octubre de 2012

Redes Petri: Sistema Concurrente

Verificación y Validación de Software
Entrada 8

La entrega para esta semana consistió en lo siguiente:
  • Investigar sobre las redes Petri.
  • Inventar un pequeño sistema concurrente.
  • Modelar un sistema con una red Petri y correrlo en Python.

¿Qué es una red de Petri?


Las redes de Petri son una herramienta gráfica para modelar sistemas formales que pueden ser descritos en términos de pasos en una actividad: como los procedimientos legales, procesos industriales, recetas y algoritmos. Los diseñadores industriales pueden usarlos, ya que son lo suficientemente generales como para la mayoría de los problemas y proporcionan un modelo para la programación. [1]

Una red de Petri es una representación matemática o gráfica de un sistema a eventos discretos en el cual se puede describir la topología de un sistema distribuido, paralelo o concurrente. La red de Petri esencial fue definida en la década de los años 1960 por Carl Adam Petri. Son una generalización de la teoría de autómatas que permite expresar un sistema a eventos concurrentes. [2]

Una red de Petri está formada por lugares, transiciones, arcos dirigidos y marcas o fichas que ocupan posiciones dentro de los lugares. [3]

Las reglas son:
  • Los arcos conectan un lugar a una transición así como una transición a un lugar.
  • No puede haber arcos entre lugares ni entre transiciones.
  • Los lugares contienen un número finito o infinito contable de marcas.
  • Las transiciones se disparan, es decir consumen marcas de una posición de inicio y producen marcas en una posición de llegada.
  • Una transición está habilitada si tiene marcas en todas sus posiciones de entrada.

Modelar un sistema


El sistema que decidí modelar fue el de las máquinas que hay en las gasolineras, en mi caso hice una versión simple, ya que el sistema completo requiere de más estados y transiciones que las que yo usé.

Lo que tome en cuenta para el sistema fue lo siguiente:
  • La máquina se encuentra en reposo hasta que es accionada.
  • El personal indica cual es la cantidad de gasolina a expedir.
  • Se selecciona el tipo de gasolina, que puede ser la premium o magna.
  • La máquina verifica si hay disponible el tipo deseado.
  • Si no hay disponibilidad, muestra un mensaje de agotado.
  • Si hay disponibilidad, empieza el llenado.
  • Al final vuelve al estado de espera nuevamente.

El siguiente es un dibujo creado previo a modelar el sistema en python, y muestra una idea general de como fluye el sistema.


Modelar la Red Petri con Python


Para modelar el sistema en python, fue necesario hacer uso de la librería python-snakes, que es posible descargar desde el siguiente sitio.


Snakes es una librería de python que nos proporciona todo lo necesario para definir y ejecutar muchos tipos de redes Petri. Su objetivo es tener al alcance una herramienta para crear prototipos rápidamente para nuevas ideas.

Unos de los puntos a resaltar de esta librería es la extensión de plugins, que permite ampliar funciones básicas y trabajar con clases especializadas en redes Petri. Por ejemplo, están los plugins usados para dibujar las redes de Petri en sus diferentes formas y exportarlos como imágenes.

El modelo de la imagen mostrada anteriormente fue escrito con las funciones que python-snakes proporciona, y el código fue el siguiente.


Este código al final crea las diferentes representaciones posibles de la red Petri, aquí deje solo dos de las cinco generadas, que son las que en este caso muestran de una forma más organizada la red.


La siguiente parece más ordenada y es más parecida al modelo del sistema que cree con la herramienta de dibujo.


Recursos consultados:
[1] - Petri Nets
[2] y [3] - Definición de Redes Petri
Python Snakes - Google Code
Python Snakes - API
Franck Pommereau's Blog

1 comentario:

Nota: solo los miembros de este blog pueden publicar comentarios.