redes de petri


Hoy hemos empezado a dar el tercer módulo de la asignatura de programación concurrente. Tras ver en días anteriores los fundamentos de la programación concurrente en cuanto a problemáticas que pueden surgir y mecanismos para evitarlos, hoy nos hemos puesto a estudiar los formalismos matemáticos que se pueden utilizar para estudiar sistemas concurrentes de tamaño moderado. Para sistemas muy generales o de gran tamaño la única opción de la que se dispone es la de la simulación.

De entre los formalismos que existen: álgebra de procesos y redes de petri, hemos tratado estas últimas con cierto detalle. El módulo que hemos comenzado consta de los siguientes temas:

Una red e petri es un grafo dirigido (i.e directed graph) con dos tipos de nodos: transiciones y plazas (i.e transitions (T) and places (P)) Entre dos nodos de distinto tipo están los arcos dirigidos (i.e arcs (A)), los cuales pueden ser más de uno, en cuyo caso se dibuja un arco que se dice tiene peso N, donde N es el número de arcos (siempre que vayan en la misma dirección) Los nodos plaza que tienen uno o más arcos dirigidos a un nodo transición (p,t) se llaman antecedentes o entradas (i.e inputs, I(p,t)) de dichos nodos. Los nodos plaza a los cuales se dirigen los arcos que parten del nodo transición se dicen sus consecuentes o salidas (outputs, O(t,p))

Los nodos plaza pueden contener cero o más “tokens”. El marcado de una red de petri es un vector con el número de tokens en cada nodo plaza en un momento dado (estado) Un nodo transición se dice que está activo (i.e enabled) cuando todos sus nodos plaza antecedentes tienen como mínimo el mismo número de tokens que de arcos se dirigen hacia dicho nodo de transición. Entonces se puede disparar la transición lo cual implica que los tokens de los nodos plaza antecedentes son “consumidos” (restados I(p,t)) y trasladados a los nodos consecuentes (sumados O(t,p)) La marca de la red de petri (su estado) cambia con cada transición. En un momento dado, solamente se permite una transición. En caso de estar habilitadas varias transiciones, la selección de cuál entre todas las transiciones habilitadas es la próxima en dispararse es arbitraria y se supone que se decide en un nivel de abstracción inferior.

Las redes de petri con algunas modificaciones estructurales y la introducción del concepto de tiempo son una herramienta muy efectiva para modelar procesos concurrentes. Las transiciones representan los procesos del programa, las plazas representan las condiciones necesarias para que un proceso se ejecute, los arcos dirigidos relacionan condiciones y procesos, y la presencia de tokens en las plazas indica que se verifica la condición que representa la plaza.

Se puede formalizar matemáticamente una red de petri con una n-tupla formada por el conjunto de los nodos plaza (P), el conjunto de los nodos transición (T) y las funciones de incidencia previa (I(p,t)) y posterior (O(t,p))

A partir de ahí se pueden definir otros conceptos como el vector de marcado M de dimensión n (número de plazas) en el que cada uno de los elementos tiene un valor de la función que asigna a cada nodo plaza del conjunto P un número natural que corresponde al número de tokens que aloja. Este vector representa el estado de la red de petri. Otros parámetros interesantes son los estados (inmediatamente) alcanzables y el conjunto de todos los estados alcanzables desde un estado/marca M.

La evolución del proceso de marcado de una red de petri resulta de su ejecución, es decir, por el disparo sucesivo en diferentes órdenes de las transiciones habilitadas en cada momento y se puede representar como un árbol de estados o vectores de marcado (árbol de alcanzabilidad) Ese árbol puede ser infinito y se acorta acabando el árbol cuando se repiten los estados o cuando se producen estados recurrentes con acumulación de tokens en una determinada plaza, que se representan como vectores con una letra w en el lugar en el que se acumulan los tokens.

Una representación más compacta es un diagrama de estados con nodos en los que se ponen los nodos plaza de la red de petri que contienen al menos un token y con arcos en los que se indica la transición que se dispara. Son unos grafos de estados llamados token machines.

Finalmente se puede obtener también una representación matricial de las redes de petri (que es directamente codificable) definiendo una matriz de incidencia C como la diferencia entre una matriz de incidencia posterior C+ formada por los aji tal que O(tj,pi) y una matriz de incidencia previa C- con aji tal que I(pi,tj) La matriz C representa en cada fila j el cambio de tokens (testigos) que se producen en los nodos plaza de la red cuando la transición tj se dispara una vez.

Esta notación matricial (P,T,C+,C-) nos permite representar los conceptos de forma numérica. Una transición es un vector ej de dimensión m (número de transiciones) con valor 1 para el componente i=j y cero en el resto. Una transición tj está habilitada si M ≥ ej • C-. Y tras el disparo el nuevo estado es M’ = M + ej • C. Los vectores de disparo (serie de transiciones) son m-tuplas donde cada componente i representa el número de veces que se dispara la transición ti. El significado de la serie de transiciones depende de lo que se esté modelando. Debe representar una serie válida dentro del modelo.

Un comentario en “redes de petri

  1. He pensado que tiene que haber software open source que permita trabajar con redes de petri. Esta curiosidad me ha surgido cuando la profesora nos ha dicho que en el grupo CTR no hay software desarrollado para trabajar redes de petri y que solamente conocen software propietario, que además es muy caro. Me gustaría encontrar algo con lo que experimentar y coger más conceptos de forma intuitiva.

    Así que me he puesto a buscar por la red. Y he encontrado cosas verdaderamente interesantes:

    pipe2: Platform Independent Petri net Editor 2, A tool for creating and analysing Petri nets (ver paper sobre la herramienta)

    Yttrium: Math.NET Project Yttrium Demo Package: Petri Net.

    Wikipedia (informal) list of petri net tools

    Petri Net world

    He descubierto también que existe un lenguaje de marcas llamado PNML (petri net markup language) para representar redes de petri que ha generado muchos trabajos a su alrededor:

    PNML – Reference site

    Oasis cover page

    Standard PNNML Framework

    Parece que una de las aplicaciones de las redes de petri es la definición de procesos de workflow en procesos de negocio (workflow engines), que están de actualidad en los llamados motores de negocio (BPM) que permiten definir en software mediante reglas los procesos de negocio que se quieren automatizar en una empresa:

    kbee.workflow

    BPM platform built in Java and integrated to the Eclipse platform. Designed to be simple, versatile and focused on the developer. It includes a Petri Nets graphical process designer integrated to Eclipse and a query language similar to OQL. Main components:

    * kbee Workflow Server
    * kbee Process Designer: Graphic design of procedures using Petri Nets.
    * kbee OLAP Server: for OLAP cubes in the processes
    * kbee.WQL (Workflow Query Language): OQL like query language on the workflow engine

    Bossa

    Bossa is a workflow engine written in Java. The engine is very fast and lightweight, uses a very expressive Petri net notation to define workflows, does not require a RDBMS and is very simple to use and to integrate with java applications.

Responder

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

Logo de WordPress.com

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

Imagen de Twitter

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

Foto de Facebook

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

Google+ photo

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

Conectando a %s