Aleph-Zero
Revista de Educación y Divulgación de la Ciencia, Tecnología e Innovación

Divulgadores

Modelado De Sistemas En Tiempo Real Utilizando Redes De Petri

Medel Juárez José de Jesús 1, Guevara López Pedro 2, Suárez Quezada Víctor Manuel 3 Contacto 1, Contacto 2, Contacto 3 1, 2, 3 Centro de Investigación en Ciencia Aplicada y Tecnología Avanzada – IPN 1 Centro de Investigación en Computación - IPN 2 Dirección de Recursos Humanos – IPN Av. Juan de Dios Batíz s/n casi esq. Miguel Othón de Mendizabal, Unidad Profesional "Adolfo López Mateos" Col. Nueva Industrial Vallejo, Mexico D.F. C.P. 07738

INTRODUCCIÓN
Existen sistemas que deben entregar información con restricciones de tiempos que hacen cálculos y dan respuestas con tiempos acotados por el mundo físico con el que interactúan. Con frecuencia se ignora la existencia de esta clase de sistemas, a pesar de que están presentes en nuestra vida cotidiana. Están en los aviones, trenes (el Metro de la Ciudad de México) y en automóviles, en la lavadora, la televisión y los teléfonos celulares. Son un elemento imprescindible para garantizar la generación, transmisión y distribución de la energía eléctrica, y para asegurar la calidad y la seguridad de incontables procesos industriales.

Estos sistemas de cómputo son los Sistemas de Tiempo Real (STR). Su estudio formal inicia a finales de los años sesenta con James Martin y su libro “Design of real-time computer systems”, continuando con un enfoque diferente en 1973 con Liu y Layland con el artículo titulado: “Scheduling algorithms for multiprogramming in hard real-time environment”.
Las Redes de Petri (RP) fueron definidas en los años 1966 por Carl Adam Petri con el informe técnico “Communication with automata”. Son una generalización de la teoría de autómatas que permite expresar eventos concurrentes. Las RP son una herramienta para el estudio de los sistemas; se reconocen como una metodología establecida en la literatura de la robótica para modelar los sistemas de manufactura flexibles. Las RP, por sus características dinámicas, manejo del tiempo y uso de procesos concurrentes son usadas por muchos investigadores e ingenieros para modelar y diseñar STR. En este artículo de da un breve acercamiento a esta teoría y se dan algunos ejemplos básicos.
SISTEMAS EN TIEMPO REAL (STR)
 
Un STR es aquel sistema que interactúa activamente con un entorno con dinámica conocida en relación con sus entradas, salidas y restricciones temporales, para darle un correcto funcionamiento, de acuerdo a algún criterio previamente definido.
Un STR cumple tres condiciones básicas (ver la figura 1):
·  Contacto con el mundo físico.
·  Emisión de respuestas correctas.
·  Cumplimiento de restricciones temporales.

Figura 1. Sistema en Tiempo Real
Entre las cualidades que los STR deben tener se encuentran: puntualidad en la emisión de sus respuestas, soporte para carga pico cuando el sistema requiere procesar mucha información, predictibilidad para conocer su comportamiento futuro, tolerancia a fallos para que el sistema no se desestabilice y se interrumpa su servicio, accesibilidad para mantenimiento, capacidad mapeo de números reales a enteros y viceversa, soporte de tareas paralelas o cuasiparalelas (concurrencia), manejo de prioridades e interacción con interfaces de hardware.
El contacto con el mundo físico es a través de sensores que recogen información y actuadores que envían a la computadora la información procesada para la manipulación del sistema físico (ver la figura 2).

Figura 2. Diagrama de bloques de un STR.
Los STR se pueden clasificarse de acuerdo a sus restricciones temporales en: críticos, no críticos e inflexibles. En los primeros siempre y para todo caso deben cumplirse sus restricciones temporales, como en los sistemas de vuelo; en los segundos el cumplimiento debe ser estadístico, debe cumplirse la media de las restricciones temporales, por ejemplo en los sistemas de captura de audio; en el tercer caso, si una sola restricción no se cumple, el sistema simplemente no sirve, como en los cajeros automáticos.

REDES DE PETRI (RP)  
Una Red de Petri (RP) es una representación matemática de un sistema distribuido discreto. Mediante una red de Petri puede modelizarse un sistema de evolución en paralelo compuesto de varios procesos que cooperan para la realización de un objetivo común.
Una RP esta compuesta por lugares, transiciones y arcos; con los cuales se define su estructura. Los lugares se utilizan para describir las posibles localizaciones de los estados del sistema (nombrando las condiciones o situaciones). Las transiciones se utilizan para describir los eventos que pueden modificar el estado del sistema. Los arcos especifican la relación entre los estados locales y los eventos en dos maneras: indican el estado local en el cual el evento puede ocurrir, y las transformaciones locales del estado inducidas por el evento. Los símbolos que residen en lugares son los marcadores y son explícitamente los que nos describen los estados del sistema.
Las RP se componen de cuatro partes:
 Un conjunto de nodos,
 Un conjunto de transiciones,
 Una función de entrada y
 Una función de salida.
Las funciones de entrada y salida relacionan a los nodos y a las transiciones. La función de entrada mapea de una transición tj a los nodos de entrada. La estructura de una RP es definida por los nodos, las transiciones, la función de entrada y la función de salida.
EJEMPLO 1. El zorro feliz
En la figura 3, se muestra el resultado parcial del comportamiento poblacional de zorros y conejos, donde cada zorro hambriento debe comer 3 conejos para satisfacer su apetito. Podemos observar que la transición t tiene 2 lugares de entrada y 1 para los zorros hambrientos y otra para los conejos, y uno de salida (¡para el zorro feliz!).

MODELADO DE SISTEMAS EN TIEMPO REAL CON REDES DE PETRI
Las RP proporcionan los elementos necesarios con restricciones de tiempo para la representación de los STR. Siendo preciso representar de manera no ambigua los siguientes aspectos:
 Eventos, tanto internos como externos, a los que debe responder el sistema,
 Los patrones temporales que rigen a estos eventos, por su periodicidad o aperiodicidad,
 Las acciones activadas por sus características temporales,
 Las interacciones entre las distintas acciones, que pueden consistir en sincronizaciones, comunicaciones, relaciones de precedencia u otras.
En el modelo de RP temporizado, requiere considerar el tipo de transiciones que el STR contiene:
 CODEt. Cada una de estas transiciones junto con sus lugares de entrada representa una actividad desarrollada por el sistema (código ejecución). Este código comenzara a ejecutarse en el momento en que la transición sea sensibilizada, es decir, todos sus lugares de entrada están marcados,
 TIMEt. Son transiciones asociadas a alguna actividad temporal, como un time out o la activación periódica de un proceso,
 SYCOt. Son el resto de transiciones, y no tienen significado temporal explicito asociado. Su disparo será inmediato, lo que supone un intervalo temporal implícito, usadas para modelar sincronizaciones y tareas de control.
En los STR la parte operativa del sistema recae sobre las transiciones CODE, mientras que el de la parte de control y de supervisión temporal depende de transiciones SYCO, TIME.
Estos tres tipos de transiciones son la base de lo que se llama unidades de ejecución, o componentes básicos que representan acciones elementales en el STR. Como consecuencia de la anterior clasificación, se distinguen tres unidades de ejecución:
 CODEe: Formada por una transición CODEt y sus lugares de entrada, que modelará la ejecución de un cierto código en el sistema: esta unidad comenzará a ejecutarse cuando se sensibilice su transición, estará en ejecución mientras sus lugares de entrada permanezcan marcados, y terminará en un instante determinado por su intervalo temporal, o si es ocupada se le dice que es abortada,
 TIMEe: Integrada por una transición TIMEt y sus lugares de entrada, que corresponderá a la posible ocurrencia de un evento temporal; la unidad se ejecutará cuando transcurra la cantidad de tiempo especificada por su intervalo temporal, siempre que la transición permanezca ocupada de forma continua durante esa cantidad de tiempo,
 SYCOe: Formada por una transición SYCOt que representa acciones de control o sincronización; se ejecutará inmediatamente en el momento en que se detecte su ocupación.
El resto de elementos, tales como lugares de la red serán utilizados para modelar recursos, datos, condiciones, etc., de acuerdo al modelo del sistema descrito por la RP. Cada lugar puede tener como máximo, una transición CODEt de salida, si bien puede contar simultáneamente con varias TIMEe y varias SYCO. De este modo se evita que puedan existir conflictos entre transiciones CODEt (lo que modela que un sistema está ejecutando simultáneamente dos códigos distintos).

PLANIFICACIÓN DE TAREAS EN LOS STR
Cuando se tiene un STR implantado sobre un Sistema Operativo en Tiempo Real (como QNX, LynxOS, RT-Linux o Blue Cat) en una computadora con más tareas que procesadores, es necesario decidir qué unidad de ejecución será ejecutada cuado varias puedan serlo concurrentemente y no se disponga de un procesador para cada una. Este problema se conoce como planificación ("scheduling") de procesos y recursos. Ha sido profusamente tratado en la literatura especializada en temas de programación de STR, dando lugar a múltiples clasificaciones, como la que distingue entre planificador estático y dinámico dependiendo de si las decisiones de planificación se toman antes o durante la ejecución de los procesos. Como último paso en el desarrollo se encuentra la implementación a través de '"software" de una RP como un algoritmo que simula reglas de evolución del modelo del STR. Conviene matizar esta descripción para distinguir el término del de simulación.

POLÍTICA DE RESOLUCIÓN DE CONFLICTOS
Para realizar esta política, se requiere el establecer una secuencia de acciones dentro de la política de ejecución: En primer lugar se atenderá al disparo de transiciones SYCOt. Si no existiese ninguna transición SYCO sensibilizada, se comenzará a considerar el disparo de las transiciones CODEt y TIMEt de modo que la que antes termine será disparada (tiempo de sensibilización menor). Si varias acabasen al mismo tiempo, se atenderá el disparo de la TIMEt más prioritaria y la CODEt será la última en ser considerada.
EJEMPLO 2. Sistema de control de una mina
El sistema a considerar es de extracción de agua de una mina (se proporciona un esquema simplificado de la situación en la figura 4). Los sensores de nivel de agua se gestionan a través de interrupciones, mientras que los demás son leídos directamente.
Las especificaciones funcionales del sistema se pueden dividir en dos componentes: de monitoreo y de control. El sistema de control de la bomba debe supervisar el nivel de agua en el pozo, cuando ésta alcance el nivel de alarma superior la bomba es encendida, drenando el pozo hasta que el agua alcance el nivel mínimo. Entonces la bomba es apagada. La bomba sólo debe funcionar si el nivel de metano y de monóxido de carbono en el aire de la mina es inferior a un cierto nivel. El entorno debe ser monitoreado para medir el nivel de metano en el aire: hay un nivel a partir del cual no es seguro extraer mineral ni operar con la bomba de agua.


Con el propósito de simplificar el funcionamiento del sistema de control, se ha realizado algunas modificaciones: a) no se ha considerado ni el operador de la consola ni el registro de datos del sistema, y b) se han eliminado el sensor de flujo de agua y de aire, quedando descrito el sistema por una RP en la figura 5.


Rp temporizada modelando el sistema de control de la bomba de extracción de agua de la mina.

Al considerar la lectura de los sensores en el sistema de control de manera temporal, se cuenta con la descripción en la figura 6.


Figura 6. Sistema de control de una mina. RP temporizada modelando la lectura de los sensores del sistema.
Solo se consideraron para este ejemplo el estudio, la descripción del sistema así como sus requisitos temporales. De tal forma que el período de monitoreo es de 60 segundos para el sensor de CO; en el caso del sensor de metano será de 5 segundos; de tal forma que los detectores de nivel de agua son dirigidos por eventos, y que el sistema debe responder a ellos en 20 segundos. El plazo de apagado en presencia de un nivel de metano superior al umbral máximo de 1 segundo. El plazo de información al operador es de 1 segundo, ante niveles de metano y/o monóxido de carbono superiores a los permitidos. La RP temporizada que modela el sistema respecto del controlador de la bomba, se muestra en la figura 5. La bomba en funcionamiento normal, puede estar encendida (ON) o apagada (OFF): puede permanecer deshabilitada si el nivel de metano es muy alto, debiendo volver al estado anterior si el nivel desciende por debajo del umbral de seguridad. Por ello el controlador puede ser visto como una máquina de estados finita con tres estados: a) ON, OFF (si no hay alarma de gas.b) no arrancar por gas (la bomba está OFF y no debe arrancar por alarma de metano) y, c) parada por gas (la bomba debería estar ON, pero la alarma de metano hizo que se apagara). La figura 6., muestra las actividades periódicas del sistema tales como el muestreo de los niveles de metano y monóxido de carbono. La activación periódica de las actividades es modelada con una transición TIMEt en un ciclo y un intervalo de disparo de límites iguales al período de muestreo. Para proteger al software de los fallos eventuales del dispositivo de muestreo, se ha protegido el acceso a éstos mediante un timeout: si el dispositivo no responde, la lectura es suspendida y el operador es informado. En la figura 6., se muestra el modelo del sensor de nivel de agua, a través de interrupciones. Ante la imposibilidad de vincular el disparo de una transición con la ocurrencia de una interrupción, se asocia un predicado a la transición. El valor del predicado será modificado por el manejador de interrupción, de modo que cuando ésta se produzca, el disparo de la transición será inmediato. Con vistas a la implementación del sistema, ni las variables que conforman el predicado, ni la forma en la que éstas varían, serán modeladas, pero si expresadas en la RP.
CONCLUSIONES
Se han repasado las distintas etapas del ciclo de vida de un STR, enfocándolas desde la óptica de la utilización de las RP. La simplicidad y gran número de situaciones que pueden ser modeladas por las RP con Tiempo han sido el argumento suficiente para elegirlas como formalismo a utilizar, pese a que es preciso completarlas mediante la asociación de predicados y prioridades a las transiciones. Así, mediante la construcción de un modelo temporizado, la semántica del sistema queda especificada sin ninguna ambigüedad.
Se ha mostrado como las RP pueden ser utilizadas para modelar a los STR. Se pueden modelar procesos periódicos, timeouts, sincronizaciones, eventos (tanto internos como externos), etc., comprobando que todas estas situaciones son cubiertas por las RP temporizada. Tras ello es posible abordar el análisis de las propiedades del STR en las RP temporizadas.
Puede decirse que las RP son válidas para su uso durante todo el ciclo de vida del STR a modelar. Su utilización conlleva varias ventajas: a) formalismo fácil de entender debido a su naturaleza gráfica, b) permite la verificación y validación de la corrección del sistema, c) las técnicas de análisis de las RP incrementarán la flexibilidad y exactitud en el diseño, pues ya no será necesario imponer restricciones al sistema para poder analizar su comportamiento ni para verificar el cumplimiento de sus restricciones temporales.
REFERENCIAS BIBLIOGRÁFICAS
 Buttazo G. “Hard Real-Time Computing Systems”, Scuola Superiore S Anna 1997.
 C. Ramachandani. Analysis of Asynchronous Concwrent Systems by Ttmed Petri Net. Massachussets Inst. of Tecnology, 2002.
·  J.L. Peterson, “Petri Nets Theory and The Modeling of Systems'', Prentice-Hall, USA,NJ, 1981.
 Liu C., Layland J. “Scheduling algorithms for multiprogramming in hard real-time environment”. Journal of the ACM, Vol. 20, No. 4, pp. 273-250, 1982.
 M.A. Marsan “Modelling Mith Generalized Stochastic Petri Nets” John Wiley, 1996.
 Guevara L. P y J. J. Medel J., Introducción a los Sistemas de Tiempo Real. Editorial Politécnico, registro de Derechos de Autor 03-2003-012912240400-01, México. 2003.
 Cruz D. Guevara L. P y J. J. Medel J., Temas Selectos de Sistemas en Tiempo Real. Editorial Politécnico, en imprenta, México. 2007.
 Peters, J.F.; Skowron, A.; Suraj, Z.; Pedrycz, W.; Ramanna, S., "Approximate Real-Time Decision Making: Concepts and Rough Fuzzy Petri Net Models", International Journal of Intelligent Systems, 1998 vol. 14, no. 4, pp.4-37.
 Petri Carl Adam. “Communication with automata” Technical Report RADC-TR-65-377 Rome Air Dev. Center, New York, NY. Tech. Rep. RADC-TR-65-377. 1966
 R. Mascarenhas, D. Kurumuri, U. Buy, R. Canyon. “Modeling and Analysis of Virtual Reality Systems with Time PetriNets”. Proceedings of the Intl. Conference on Software Engineering, 1998.
·  T. Murata, “Petri Nets: Properties, analisys and applications'', Proc. IEEE, Apr. 1989. pp. 541-579.
 Timothy V. Fossum. “A real-time object-oriented petri net implementation based on scheme”. International Workshop on Discrete Event Systems, 1996, pp. 320-325.
 Wang and Y. Deng, “Incremental modeling and verification of flexible manufacturing systems”, Journal of Intelligent Manufacturing, 1998.
subir

Contacto

Consejo Nacional para el Entendimiento Público de la Ciencia
Centenario del natalicio del Ing. Guillermo González Camarena