El principio básico
Las máquinas de estados se utilizan a menudo para resolver ciertos tipos de problemas orientados al control, en los cuales el flujo de control pueda dibujarse como un movimiento a través de un conjunto de diferentes estados. Hay una serie de definiciones diferentes y de descripciones de tipo práctico de una máquina de estados; a un nivel teórico es como un autómata que responde a un estímulo concreto mediante un cambio de estado. Para indicar una expresión habitual específica se puede considerar por ejemplo como un autómata que reacciona a la cadena de entrada moviéndose a través de un conjunto de estados. Si se alcanza el estado buscado, la cadena de entrada equivale a la expresión habitual.
Dentro del software de control, es habitual tomar como base del modelo computacional de la máquina de estados su carácter finito y su determinismo, lo cual significa fundamentalmente que el número de estados posibles o de combinaciones de estados es finito, y que la máquina de estados sólo puede tener un estado en cada momento. Veremos más tarde que la regla de un estado en cada momento puede relajarse, pero el aspecto relevante es que el estado de la corriente es una propiedad determinística.
Si para usted es una novedad la implementación de máquinas de estado en software, éstos son los conceptos más importantes:
Estados: un estado puede considerarse una descripción abreviada de la situación actual del sistema. A modo de sencillo ejemplo, pensemos en un dispositivo periférico que pueda tener tres modos de funcionamiento alternativos del máximo nivel: on, off o standby (reposo).
Eventos: Un evento es un mensaje de entrada a la máquina de estados. El evento puede provocar que la máquina de estados cambie de estado. La presión del botón On en un televisor en modo standby es un tipo de evento que con un poco de suerte devolverá la vida al televisor, o a estado de on.
Transiciones: Una transición es una ruta dirigida de un estado a otro. La transición se designa generalmente con un nombre de evento, indicando así que la transición tendrá lugar si el evento especificado sucede cuando la máquina de estados se encuentra en el estado de inicio de la transición. El resultado final es que la máquina de estados cambia el estado al estado buscado por la transición. Para complicar las cosas – o más bien para incrementar el poder expresivo de la notación de la máquina de estados – una transición puede ‘protegerse’ mediante condiciones de vigilancia que deben cumplirse para llevar a cabo la transición.
Acciones – Una acción es una actividad a realizar por la máquina de estados en un punto determinado en el tiempo. Generalmente una acción realiza alguna tarea en el entorno, como la lectura o escritura de un dispositivo de E/S. Las acciones pueden asociarse a transiciones, o bien pueden especificarse como acciones de entrada y salida en estados específicos.
Estos conceptos son fundamentales para el planteamiento formal al diseño de máquinas de estado que encontraremos como subconjunto del lenguaje de modelado UML.
Más allá de los fundamentos básicos
Veamos ahora un ejemplo básico en un libro de texto consiste en un problema orientado a estado y tratemos de hallar una implementación apropiada en una máquina de estado. En este caso más bien se trata de dos soluciones diferentes, cada una de ellas con sus ventajas e inconvenientes, y la elección de la solución depende de la evaluación de sus pros y contras.
El problema: “Una concurrida carretera principal se cruza con una carretera local poco transitada. Se colocan detectores a lo largo de la carretera local para activar una señal C cuando haya un vehículo esperando para cruzar la carretera principal. El controlador del semáforo debería funcionar como se indica a continuación. Mientras no se detecte ningún vehículo en la carretera local, los semáforos deberían permanecer en verde en la dirección de la carretera principal. Si se detecta un vehículo en la carretera local, los semáforos de la carretera principal deberían cambiar de amarillo a rojo, permitiendo así que los semáforos de la carretera local se pongan en verde. Los semáforos de la carretera local permanecen en verde siempre que se detecte un vehículo en la carretera local y nunca durante un intervalo establecido para permitir que el tráfico fluya en la carretera principal. Si se cumplen estas condiciones, los semáforos de la carretera local cambiarán de verde a amarillo y a rojo, permitiendo así que los semáforos de la carretera principal vuelvan a verde. Incluso si hay vehículos esperando para cruzar la carretera principal, éste debería permanecer en verde durante un intervalo establecido”. 1
Este ejercicio se dirige a una perspectiva del hardware, pero con un poco de libertad artística se puede adaptar para un entorno de software. Obsérvese que el ejemplo aplica la convención de que la luz amarilla siempre aparece por sí misma (en algunos lugares del mundo se utilizan otras convenciones). Pero en realidad esto no afecta la dificultad del problema; tan sólo nos facilita el seguimiento de las posibles combinaciones de color.
El planteamiento sencillo al diseño de máquinas de estados se puede describir así:
1. Identificar eventos y acciones
2. Identificar estados
3. Agrupar por jerarquías
4. Agrupar por concurrencia
5. Añadir transiciones
6. Añadir sincronizaciones
Ésta es una receta prescriptiva, sino un planteamiento que en general será de ayuda al estructurar una solución, con independencia de las herramientas y de los métodos de implementación escogidos.
Profundicemos
Empecemos pues por examinar la descripción del problema buscando posibles eventos y acciones. ¿Qué constituye un evento en el contexto de una máquina de estados? Dicho en pocas palabras, un evento viene a ser un activador que potencialmente puede hacer que la máquina de estados cambie de estado y realice alguna acción. En el caso de los semáforos podemos encontrar una serie de eventos potenciales:
La llegada de tráfico en la carretera local es un evento que tiene un significado para el funcionamiento del semáforo.
Existen unos pocos intervalos de tiempo relacionados con la descripción:
- El tiempo mínimo durante el cual está en verde el semáforo de la carretera principal. También se puede utilizar como tiempo fijo para que el semáforo de la carretera local permanezca en verde en el
caso de que haya tráfico.
- El retardo cuando se conmuta desde y hacia el semáforo en amarillo para ambas carreteras.
Los intervalos de retardo no son eventos por sí mismos, sino que el fin de un intervalo puede verse como un evento. En la práctica esto nos deja con dos eventos, un evento con un largo intervalo para el período en verde en ambas carreteras y un evento para el corto retraso uniforme durante la transición a través de la secuencia de luces entre rojo y verde y viceversa.
Esto nos deja con tres eventos que podemos llamar EventoTráficoCarre-teraLocal, EventoLargo y EventoCorto.
Por tanto, ¿qué constituye una acción en este problema? Cambiar el color de los semáforos es una acción típica. La única pregunta es si constituye una o dos acciones el cambio de la luz en ambas carreteras. La respuesta es que en realidad es una cuestión convencional. Podemos considerarlo como dos acciones distintas, donde cada acción se encarga de una de las carreteras, o bien podemos verlo como una sola acción. Yo opto por contemplarlo como dos acciones distintas, por razones que aparecerán más tarde.
Opto por denominar a las acciones ConfigurarLuzCarreteraLocal() y Con-figurarLuzCarreteraPrincipal(); cada acción toma un parámetro de color que indica el color que se desea visualizar.
Aquí la idea es que los eventos que hemos escogido activarán cambios en ciertas situaciones en las cuales se visualizarán los colores de los semáforos.
Necesitamos también alguna forma de realizar un seguimiento de los intervalos temporales, por lo que introducimos una acción especial denominada una acción de temporizador cuya finalidad es iniciar un temporizador contador durante un intervalo especificado y realizar el seguimiento de un evento que se activará cuando el temporizador llegue a su fin. Para simplificar las cosas denominaremos a esta acción del temporizador AcciónTemp().
Para conocer mejor la lógica de control del sistema de semáforos necesitamos conocer los posibles estados y transiciones entre ellos. La primera solución empleará estas observaciones:
En cualquier momento determinado los semáforos mostrarán una de las siguientes combinaciones de colores: {VERDE, ROJO}, {AMARILLO, ROJO}, {ROJO, ROJO}, {ROJO, AMARILLO}, {ROJO, VERDE}, {ROJO, AMARILLO}. A partir de las normas de funcionamiento de un semáforo, está claro que no deberían permitirse otras combinaciones para no introducir riesgos en el tráfico que atraviesa la intersección de ambas carreteras al mismo tiempo. El primer color en cada par es el semáforo de la carretera principal.
Existe una secuencia fija en la cual se mostrarán las combinaciones de color indicadas antes: {VERDE, ROJO}, {AMARILLO, ROJO}, {ROJO, ROJO}, {ROJO, AMARILLO}, {ROJO, VERDE}, {ROJO, AMARILLO}, {ROJO, ROJO}, {AMARILLO, ROJO} y de vuelta a la primera combinación para empezar de nuevo.
No hace falta ir muy lejos para ver cada una de las etapas de la secuencia como un posible estado, dado que claramente incluye el estado del sistema en un momento determinado. Las transiciones entre estados se activarían entonces por los diferentes intervalos temporales para cada cambio de color. Suponiendo que la secuencia empiece con la luz verde para la carretera principal, entonces la secuencia completa se activa por un EventoTráficoCa-rreteraLocal.
El lector observador se habrá dado cuenta de que hay algunos duplicados en la secuencia anterior de combinaciones de color. Por ejemplo la combinación “ambos semáforos en rojo” aparece dos veces. ¿Deberíamos tratarlos como un estado o como dos? He optado por tratar todas las posiciones de la secuencia como estados separados. Esta decisión implica que las transiciones entre estados sean lo más sencillas que sea posible.
Tenemos ya los fundamentos en forma de conjunto de eventos, algunas acciones y un conjunto de estados candidatos.
La Figura 2 muestra el diseño en notación UML. Los estados propuestos se han dibujado en forma circular con transiciones cuyo nombre es el de los eventos correspondientes. Los estados también tienen acciones de entrada para cambiar el color del semáforo. Como podemos ver, sólo el estado de inicio necesita configurar ambos semáforos para asegurar un inicio correcto de la secuencia; para los otros estados sólo se necesita cambiar una de las luces respecto al estado anterior. Éste el motivo que explica la utilización de dos funciones de acciones diferentes. El estado de inicio se indica mediante la transición entre el estado inicial, y que se denota mediante un pequeño círculo en la esquina superior izquierda.
La semántica de UML utiliza el estado inicial y la transición a partir de él para apuntar hacia el estado de inicio deseado, lo cual significa que podemos expresar la inicialización del sistema directamente en el diagrama. La transición carece de evento alguno y es implícita en el arranque.
Desde una perspectiva de máquina de estados, este diseño está casi completo pero le falta el manejo de un intervalo mínimo en verde para la carretera principal. Podemos resolver esto de varias maneras, pero la siguiente solución parece bastante sencilla.
Introducir una pequeña cantidad de jerarquía en el modelo creando una máquina de estados dentro del estado VerdePrincipal_RojoLocal. Esta máquina de estados consta de dos estados más el pseudoestado inicial. Siempre que se entre en el estado de alrededor se activará también el estado NuevoVerde.
Cuando se agote un largo intervalo de tiempo que se inició al entrar en VerdePrincipal_RojoLocal dejamos que la pequeña máquina de estados cambie de estado a EventoCarreteraLo-calOK. Ahora sabemos que ha pasado el intervalo mínimo en verde para la luz verde en la carretera principal y que ahora debería ser correcto (OK) ‘pasar a verde’ en la carretera local si hay tráfico allí.
La última pieza necesaria para mantener el mínimo intervalo en verde en la carretera principal es una ‘protección’ en la transición al salir del estado VerdePrincipal_RojoLocal. Esta transición sólo debería anularse si se activa el estado EventoCarreteraLo-calOK. Esto puede expresarse mediante la denominada condición de estado positiva o la sincronización positiva en la transición. Los cambios resultantes pueden verse en la Figura 3.
Esta solución no es perfecta dado que no contempla el hecho de que el tráfico que llega por la carretera local durante el mínimo intervalo en verde de la carretera principal se queda detenido hasta que llegue otro coche una vez agotado el intervalo. Para resolverlo necesitamos registrar cualquier EventoTráficoCarre-teraLocal que suceda durante el intervalo en verde, de modo que podamos realizar la acción apropiada cuando se agote el intervalo. No estudiaremos aquí una solución completa al problema, pero si usted intenta diseñar una solución los siguientes puntos indican un posible camino a seguir:
Introducir una variable de alerta interna de la máquina de estados que se ponga a cero con cada entrada del estado en verde en la carretera principal
Introducir una ‘reacción interna’ en el estado verde de la carretera principal que vea la alerta si se recibe un EventoTráficoCarreteraLocal, quizá con NuevoVerde como estado de protección
Una ‘reacción de entrada’ en el estado EventoCarreteraLocalOK que envía una señal si la alerta se activa al entrar en el estado (una señal es un evento especial que puede enviar la propia máquina de estados)
Una transición a Amarillo que dispara la señal e inicia un corto intervalo de temporización
Hay otra maneras de tratar este problema, pero necesitan un poco más de sintaxis UML que resulta demasiado compleja como para tratarla aquí.
Las máquinas de estado de software difieren de sus homólogas de hardware en que la máquina de estados de software tiene que detectar y reaccionar a los eventos en el entorno de hardware. Esto significa que el modelo computacional de las máquinas de estados de software se basa en un ciclo detectar evento – reaccionar a evento compuesto por pasos discretos, mientras que una máquina de estados de hardware puede reaccionar ‘simultáneamente’ a una señal cambiada en una determinada patilla. (Aunque la variación real de las puertas desde luego es una actividad discreta al nivel de bit). Por ejemplo, se puede combinar un conjunto de señales de hardware en una puerta para proporcionar un evento cuando se cumpla una cierta combinación de señales en el lado de entrada. En un entorno de software o bien hay que dejar que los controladores de interrupciones y de dispositivos realicen la combinación o dejar que la máquina de estados haga la combinación. (A menos que usted controle el diseño del hardware).
Un estado diferente
Como se ha subrayado al principio, existe al menos una forma completamente diferente de resolver el mismo problema, lo cual implica modelar las máquinas de estado como dos regiones paralelas en la misma máquina de estados de alto nivel. Esto tiene la ventaja de que puede verse la solución completa como un sistema constituido por componentes separados y semi-independientes. El espacio no permite un comentario más extenso, pero puede consultarse on-line en www.iar.com/p236597/
p236597_eng.php.
La opción exacta escogida para la solución en realidad no es importante, pero en general es bueno que las cosas sean lo más sencillas que sea posible. La utilización de una herramienta de diseño gráfico como IAR visualSTATE para el diseño de máquinas de estado es una manera práctica de elevar el nivel de abstracción, ya que una buena herramienta ofrece soporte a aspectos como generación de código, test y simulación, y la comprobación de la capacidad del modelo.
Autor: Anders Holmberg, IAR Systems
Más información o presupuesto
