Using Simple Finite State Machines - Fsm(C++)

A Simple Dynamically-Programmed Fsm

This example illustrates the use of an Fsm `dynamic programming' feature.

Consider a traffic light that alters its program according to the time of day. Between 6AM and midnight it executes the normal green-yellow-red cycle. Between midnight and 6AM it flashes the yellow light. Input to the traffic light comes from two sources: (1) a time-of-day clock set to interrupt at 6AM and again at midnight and (2) a timer which sends an interrupt once each second. Assume the normal cycle consists of 30 seconds of green followed by 3 seconds of yellow followed by 30 seconds of red, and that the flashing cycle consists of one second of yellow followed by one second of darkness.

One possible solution would be to define two Fsm programs, one for each cycle; the control program would simply switch machines at midnight and again at 6AM. However if this program were running on a small microcomputer with limited memory, we might not be able to spare the storage required for two machines. We will instead define a single machine containing two programs; the twice-daily interrupt handler will toggle between programs by calling function go() to force an explicit state change to the initial state of the alternate program.

As usual, we start by drawing the state transition diagrams for the machines (Figure 4):

Traffic Light State Transition Diagram

As usual, we introduce names for the states and the inputs:

       enum Inputs{tick,change};
       enum States{green,yellow,red,flash_on,flash_off};

Action routines are next defined for the 1-second timer interrupts; these routines simply increment a counter and force a color change when thirty seconds have elapsed:

       int mark_red_time(Fsm& f,unsigned){
           static int red_time = 0;
           return 1;
       Similar for mark_green_time and mark_yellow_time

Note that when a 30-second limit is attained in any of the above action routines, the routine recursively calls fire(). (Don't forget that action routines are themselves called by fire()).

When writing code like this, it is important to understand the precise semantics of fire(). fire() calls an action routine in the current state. It changes the machine state upon return from the action routine. If an action routine modifies the machine (by calling go(), fire(), abort(), or reset()), however, the state change that would normally occur upon return from the action routine will not take place. For the traffic light program, this means that when mark_red_time() returns to fire(tick) after calling fire(change), the normal transition back to the red state will not occur: it has been superseded by the transition to the green state.

Next, we furnish the action routines that turn lights on and off:

       int make_red(Fsm& f,unsigned input){
           turn off all lights
           turn on red light
       Similar for make_green, make_yellow, and turn_off

Finally, we write handlers for each interrupt:

       void interval_timer_interrupt_handler(){
           disable all interrupts;
           enable all interrupts    }
       void time_of_day_interrupt_handler(){
           disable all interrupts        if(t.state()!=flashing){
           enable all interrupts    }

Note how time_of_day_interrupt_handler() uses explicit transfer of control to toggle between programs.

Finally, we define a default action routine that will be called in the event the system becomes hopelessly confused, which would be indicated by an illegal input. It performs the least harmful action, namely, switching back to the normal cycle and disabling interrupts from the time-of-day clock:

       int panic(Fsm& f,unsigned){
           disable interrupts from time-of-day clock

The main program has no control loop because it is interrupt-driven. We need only program the machine, enable interrupts, and ``busy wait:''

           Fsm t(6,green,panic);  // "t" for "traffic light"
           enable interrupts        while(1);  // Busy wait

Next topic: Preconditions
Previous topic: Translator State Transition Diagram

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005