Redes petri

1. Adaptado por: GIOVANNI ANDRÉS TOVAR CLAVIJO Sistemas Operativos REDES PETRI

2. REDES PETRI Una Red de Petri es una representación matemática de un sistema distribuido discreto. Las redes de Petri fueron definidas en los años 1960 por Carl Adam Petri. Son una generalización de la teoría de autómatas que permite expresar eventos concurrentes. Una red de Petri es un grafo dirigido bipartito, con un estado inicial, llamado marcación inicial. Los dos componentes principales de la red de Petri son los sitios (también conocidos como estados) y las transiciones. Las redes de Petri se utilizan para modelar el comportamiento dinámico de sistemas discretos. Se componen de dos tipos de objetos: Las plazas (lugares) que permiten representar los estados del sistema mediante la utilización de marcas. Las transiciones que representan el conjunto de acciones a realizar cuando se cumplen unas determinadas precondiciones en el sistema.

3. Mediante una red de Petri puede modelarse un sistema de evolución en paralelo compuesto de varios procesos que cooperan para la realización de un objetivo común. En general, la presencia de marcas en una plaza se interpreta como la presencia de recursos. El franqueo de una transición (la acción a ejecutar) se realiza cuando se cumplen unas determinadas precondiciones, indicadas por las marcas en las plazas (hay una cantidad suficiente de recursos), y la transición (ejecución de la acción) genera unas postcondiciones que modifican las marcas de otras plazas (se liberan los recursos) y así se permite el franqueo de transiciones posteriores.

4. REPRESENTACIÓN DE REDES PETRI En la representación de una red de Petri, se omiten los arcos valorados con 0, y el 1 en los arcos valorados con 1. Las plazas se representan mediante círculos, las transiciones mediante rectángulos horizontales o líneas horizontales, y las marcas mediante puntos en el interior de las plazas. Ejemplo: Representación como grafo de la red de Petri, R1.

5. Implementación de la teoría de Redes Petri Áreas de aplicación : Análisis de datos Diseño de software Fiabilidad Flujo de trabajo Programación concurrente Se emplean en las metodologías formales* de desarrollo de software. Las metodologías formales se basan en el empleo de técnicas, lenguajes y herramientas definidos matemáticamente para cumplir objetivos tales como facilitar el análisis y construcción de sistemas confiables independientemente de su complejidad, delatando posibles inconsistencias o ambigüedades que de otra forma podrían pasar inadvertidas. * Es cualquier serie de técnicas que trate la construcción y/o el análisis de modelos matemáticos que contribuyen a la automatización del desarrollo de sistemas informáticos.

6. Metodologías Formales Ventajas : Se comprende mejor el sistema. La comunicación con el cliente mejora ya que se dispone de una descripción clara y no ambigua de los requisitos del usuario. El sistema se describe de manera más precisa. El sistema se asegura matemáticamente que es correcto según las especificaciones. Mayor calidad software respecto al cumplimiento de las especificaciones. Mayor productividad .

7. Metodologías Formales Desventajas : El desarrollo de herramientas que apoyen la aplicación de métodos formales es complejo. Los investigadores por lo general no conocen la realidad industrial. Es escasa la colaboración entre la industria y el mundo académico, que en ocasiones se muestra demasiado dogmático* Se considera que la aplicación de métodos formales encarece los productos y ralentiza su desarrollo. *Que no admite contradicción en sus opiniones

8. REDES PETRI Una gran dificultad al especificar sistemas en: Tiempo real es la temporización Problemas de sincronización Condiciones de carrera Deadlock (punto muerto) Es una técnica poderosa para especificar sistemas que tienen problemas potenciales con interrelaciones (concurrencias). Una Red Petri consiste en cuatro partes: Un conjunto de lugares P

9. Un conjunto de transiciones T Un función de entrada I Una función de salida O • Conjunto de lugares P –{p1, p2, p3, p4} •Conjunto de transición T –{t1, t2} •Funciones de entrada: –I(t1) = {p2, p4} –I(t2) = {p2} •Funciones de salida: –O(t1)= {p1} –O(t2)= {p3, p3}

10. Formalmente, una Red Petri es una 4-tupla C= (P, T, I, O) P = {p1, p2, …, pn } es un conjunto finitos de lugares, n ≥ 0 T = {t1, t2, …, tm } es un conjunto finito de transiciones, m ≥0, con P y T disjuntos I: T P∞ es la función de entrada, un mapeo de transiciones a bolsas de lugares O: T P∞ es la función de salida, un mapeo de transiciones a bolsas de lugares Una bolsa es una generalización de un conjunto que permite múltiples instancias de elementos (como en el ejemplo anterior) Una marca en una red Petri es una asignación de tokens (ficha) a esa red Petri

11. EJEMPLO: REDES PETRI Cuatro tokens : uno en p1, dos en p2,ninguno en p3 y uno en p4. Representado por el vector (1,2,0,1) Una transición se habilita si cada uno de sus lugares de entrada tiene tantos tokens en ella como arcos hay de ese lugar a la transición.

12. • La transición t1 está habilitada (lista para activarse) – Si t1 se activa, se elimina un token de p2 y otro de p4 y un nuevo token se ubica en p1. • Se activa entonces la transición t2 • Importante: – El número de tokens no se conserva Las redes Petri son indeterminadas* Al activarse t1

13. El vector resultante es (2,1,0,0) * Se aplica a un sistema de ecuaciones en el que el número de variables es superior al de ecuaciones independientes y que, por lo tanto, admite infinitas soluciones. Ahora sólo t2 se activa El vector resultante es (2,0,2,0)

14. Formalmente, una marca M en una red de Petri C = (P, T, I, O) es una función del conjunto de lugares P a los enteros no negativos M: Pᴨ{0, 1, 2, …}. Una red de Petri marcada es entonces una 5-tpla (P, T, I, O, M) Arcos inhibidores Un arco inhibidor se marca con un pequeño círculo En general, una transición se activa si hay al menos un token en cada arco de entrada normal y no hay tokens en los arcos de entrada inhibidores.

15. Enlaces relacionados Documentos, libros y tutoriales que introduce los conceptos básicos de redes de Petri: http://www.informatik.uni-hamburg.de/TGI/PetriNets/introductions/aalst/ Típicas preguntas que ocurre alrededor de las Redes de Petri: http://www.informatik.uni-hamburg.de/TGI/PetriNets/faq/ Tutoriales interactivos Redes Petri: http://www.informatik.uni-hamburg.de/TGI/PetriNets/introductions/aalst/ Aplicaciones prácticas de las Redes Petri: http://www.informatik.uni-hamburg.de/TGI/PetriNets/applications/ Normalización . Estándar ISO para el nivel de Redes de Petri http://www.informatik.uni-hamburg.de/TGI/PetriNets/standardisation/ Petri Nets World : http://www.informatik.uni-hamburg.de/TGI/PetriNets/