[TUT][SOFT] Simple State Machines for Embedded Systems pt 1

Go To Last Post
11 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This is very much work in progress and will be edited over the next few days to expand certain sections.

In this tutorial I'm going to show how simple state machines can be used to simplify your software. In particular I'm going to be talking about time-triggered state machines.

Embedded systems are designed to run forever and when starting out people often write things like this...

void main (void)
{
  while (1)
  {
    read_inputs();
    do_something();
    write_outputs();
    do_something_else();
  }
}

But in real-world embedded systems we often need to wait until a switch closes before we do something or we need to set an IO pin high or low for a specific period of time. So how do we achieve this?

Let's start by considering a simple example where we need to set an IO pin high for a period of time before setting it low again.

In pseudocode we'd write something like this...

void pulse_pin(void)
{
  //set an io pin high for 20 milliseconds
  set_port_high(io_pin);
  delay_ms(20);
  set_port_low(io_pin);
}

void main (void)
{
  while (1)
  {
    do_something();
    pulse_pin();
    do_something_else();
  }
}

However, this is a very inefficient way to do things for two main reasons...

1) In the 20ms that you delay, an AVR running at 16MHz will waste 320,000 CPU cycle when it could be doing something useful
2) In that 20ms, unless you are using interrupts, all other processor activity will stop.

So how could we improve this using a State Machine?

To start with, we need a way of establishing a regular system tick using a timer interrupt. There are plenty of tutorials on using timers and interrupts so I'm not going to cover that in detail but we simply need a regular timer to set a global flag when it occurs.

We need to choose our multitasking framework 'tick' rate.

For many embedded systems that interact with us in the real world 10msecs is a good value as a common system 'tick' value. It's fast enough that buttons and display appear to react immediately but not so fast that the processor runs out of time to do things. However, it also means that the resolution of any output pulse will be 10msec. If you need output pulse with a different resolution then you will need a different tick rate but if you find yourself needing a tick rate of less than 1msec then you probably ought to be looking at different ways to produce your pulses.

Let's rewrite our code to something like this...

//define global flag
uint8_t timer_flag = 0;

void timer_isr (void)
{
  //runs every 10ms
  //reload timer
  //set flag
  timer_flag = 1;

}

void pulse_pin(void)
{
  //declare our local state variable
  //it must be static so that the value is available every time we call the routine
  //it also needs initialising to a known state at reset
  static uint8_t state = 0;

  switch (state)
  {
  case 0:
    //runs on first call and when instructed to
    set_port_high(io_pin);
    //will run from 'case 1:' next time the routine is called
    state++;
    break;
  case 1:
    //runs 10ms later
    //will run from 'case 2:' next time the routine is called
    state++;
    break;
  case 2:
    //runs another 10ms later
    set_port_low(io_pin)
    //next time the routine runs we want to start all over again
    state = 0;
    break;
  default:
    //trap error condition
    state = 0;
  }	
}

void main (void)
{
  while (1)
  {
    do_something();
    if (timer_flag)
    {
      //this will run every time the timer interrupts
      pulse_pin();
      //clear the flag until next interrupt
      timer_flag = 0;
    }
    do_something_else();
  }
}

The advantage of a simple state machine like this is that it takes very little time to run leaving us plenty of time to do other things.

How about a more complex example?

In a previous tutorial Kartman shows us how to write a simple co-operative task dispatcher which allows us to schedule tasks to run at regular intervals...

http://www.avrfreaks.net/index.p...

One of the golden rules when using such a co-operative system is that no task must ever 'block'. That is to say that no tasks should ever enter a state when it halts the execution of other tasks. In other words, no task should ever wait on an external event or have a long time delay within it.

Coupled with the ability to run tasks at chosen intervals our state machines start to become a very powerful tool.

Let's take a simple traffic light used to regulate flow on a straight road. The specification is...

Red light for 30 seconds
Red and Amber for 5 seconds
Green light for 60 seconds
Amber light for 7 seconds

The simple code would be...

void main (void)
{
  while (1)
  {
    set_lights(RED);
    delay_secs(30);
    set_lights(RED_AMBER);
    delay_secs(5);
    set_lights(GREEN);
    delay_secs(60);
    set_lights(AMBER);
    delay_secs(7);
  }
}

But let's use a state machine and our multi-tasking framework.

Here we should immediately notice that we can use a task rate of 1 second. We also note that we need different delays for different stages of the sequence.

So we'll use our framework to call traffic_light_task() every second.

void traffic_light_task(void)
{
  //this is called once per second

  //to make things clear we will use an enum to declare our states.
  enum lights_states(SET_RED, WAIT_RED_AMBER, SET_RED_AMBER, WAIT_GREEN, SET_GREEN, WAIT_AMBER, SET_AMBER, WAIT_RED);

  //declare our local state variable
  //it must be static so that the value is available every time we call the routine
  //it also needs initialising to a known state at reset
  static uint8_t state = SET_RED;

  //declare our local timer variable
  //it must be static so that the value is available every time we call the routine
  //it also needs initialising to a known state at reset
  static uint8_t timer = 30;	

  switch (state)
  {
  case SET_RED:
    //set lights to correct state
    set_lights(RED);
    //set timer for next change
    timer = 30;
    //go to next state
    state = WAIT_RED_AMBER;
    break;
  case WAIT_RED_AMBER:
    //decrement the timer
    timer--;
    //if this is the last waiting state change to next state
    if (timer == 1)
    {
      state = SET_RED_AMBER;
    }
    break;
  case SET_RED_AMBER:
    set_lights(RED_AMBER);
    timer = 5;
    state = WAIT_GREEN;
    break;
  case WAIT_GREEN:
    timer--;
    if (timer == 1)
    {
      state = SET_GREEN;
    }
    break;
  case SET_GREEN:
    set_lights(GREEN);
    timer = 60;
    state = WAIT_AMBER;
    break;
  case WAIT_AMBER:
    timer--;
    if (timer == 1)
    {
      state = SET_AMBER;
    }
    break;
  case SET_AMBER:
    set_lights(RED);
    timer = 7;
    state = WAIT_RED;
    break;	
  case WAIT_RED:
    timer--;
    if (timer == 1)
    {
      state = SET_RED_AMBER;
    }
    break;
  default:
    //trap error condition
    state = RED;
    timer = 30;
  }	
}

Again, this code takes very little time to run allowing plenty of CPU cycles for other tasks.

In the next part I'm going to cover how multiple state machines can be used to implement simple to use and simple to understand menu systems. But I'll have to write it first.

'This forum helps those who help themselves.'

 

pragmatic  adjective dealing with things sensibly and realistically in a way that is based on practical rather than theoretical consideration.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

*reserved for updates*

'This forum helps those who help themselves.'

 

pragmatic  adjective dealing with things sensibly and realistically in a way that is based on practical rather than theoretical consideration.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

*reserved for updates*

'This forum helps those who help themselves.'

 

pragmatic  adjective dealing with things sensibly and realistically in a way that is based on practical rather than theoretical consideration.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

*reserved for updates*

'This forum helps those who help themselves.'

 

pragmatic  adjective dealing with things sensibly and realistically in a way that is based on practical rather than theoretical consideration.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Brian Fairchild wrote:

Again, this code takes very little time to run allowing plenty of CPU cycles for other tasks.

what does the micro controller do if you're using interrupts and there's nothing in between to do?

Like the traffic light example, between the traffic light interrupts, if there's no other code to run, what does the micro-controller do? do the wheels keep spinning or...?

new to mirco electronics

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
what does the micro controller do if you're using interrupts and there's nothing in between to do?
Sit in a loop that does nothing (or you could put it to sleep).

Regards,
Steve A.

The Board helps those that help themselves.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Koshchi wrote:
Quote:
what does the micro controller do if you're using interrupts and there's nothing in between to do?
Sit in a loop that does nothing (or you could put it to sleep).

and there's that power saver mode where the frequency is automatically reduced...can it go into that mode as well..?

new to mirco electronics

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

and there's that power saver mode where the frequency is automatically reduced...can it go into that mode as well..?


If you want to save the most power (wouldn't you always?) then why would you leave the clock running at all if it's just idling in a loop? Surely you pick the deepest sleep mode available that you can still wake from. Set that mode, SLEEP and provide an interrupt to do the waking when needed.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Good work Brian!
The main problem that many users is that "they don't know how to, what they perceive " to break up the code" Where to make the start. I always suggest that they do a state (or bubble) diagram on a piece of paper before they even touch a key board.
The start to that, is to draw a circle. That will be your first state & conveniently could/should be your INITIAL state.
Now draw exit paths to other circles. These paths will represent a change in inputs to a sustems.
For example a single digital input has two exit paths.
Two inputs will have four exit paths. 3->8, 4->16, 5>32etc.
Some of the exit paths may point back to the current state Ie. no change.
Some combinations of inputs may never occur, but realizing that there are 2^N exit paths forces you to consider the possibility that it just might happen when you least expect it.
Timers timing will cause exit paths.
Receiving an ASCII character can cause exit paths. How many? Well potentially another 2^7.

State diagrams allow you to identify all the various states that you need to implement.

Charles Darwin, Lord Kelvin & Murphy are always lurking about!
Lee -.-
Riddle me this...How did the serpent move around before the fall?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
In the next part I'm going to cover how multiple state machines can be used to implement simple to use and simple to understand menu systems. But I'll have to write it first.

Great! Thanks a lot Brian.
I'm waiting for continue this thread.

"One's value is inherent; money is not inherent"

 

Chuck, you are in my heart!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

LDEVRIES wrote:
I always suggest that they do a state (or bubble) diagram on a piece of paper before they even touch a key board.

Look at http://www.state-machine.com/. There is very usefull book of state-machines in this site.

Ilya