FotS

… and why you should use it.

A State Machine is a mathematical concept whereby a system is driven by stimuli and its state alters by reacting to them. The condition of the stimuli indicates the state of the system at any point in time.

In computing, state machine methodology is employed to get away from having a traditionally tightly interlocked system in favour of one that is only active when a stimulus is received; Changing its “state” depending on those stimuli. Stimuli could be I/O pins, a specific string or more often, flags. Such a system tends to be loose-coupled to its tasks and thus easier to program for multiple actions, each being self contained often as the body code inside an IF test in the main thread.

As an example, consider the following:

Do

If This Then
  DoThisProcess
EndIf

If That Then
  DoThatProcess
EndIf

...etc

Loop

The Main Thread spends all it's time zipping around simply and rapidly checking flags and only taking a self-contained action when it has to. If the code is simple enough and only used in one place, then it should exist inside the If/EndIf block, otherwise write the code in a Sub program and call that from the If block.

With micro-controllers you don't often have an Operating System to handle the CPU when it is idle - you control the CPU at a very low level. In modern computer languages, the “main loop” would be a dormant state and an event handler would wake your program when the state of the stimuli changed (you don't have to give the CPU something to do while it is waiting for a state change). This makes all of the resources (while the CPU isn't busy) available to the system for other tasks.

State machine techniques are a major step towards event-driven programming on systems that don't normally have it. It can provide an almost multi-tasking appearance in micro-controllers as sections of code execute asynchronously to others, signaling and interlocking with other processes by setting or clearing flags - a process called “semaphore”. The process of semaphore by tweaking flags goes back to the earliest CPUs, when an action would be taken as a result of one process signaling a specific state which resulted in another process doing something about it. All CPUs support semaphores, if only with a zero or carry flag in the status register. This is a good way to signal from a one section of code to another.

State-machine code makes for easily readable and modifiable programs as each action becomes an atomic section of code with a clearly identifiable trigger. You don't have to worry about disrupting other sections of code so long as any process handles its input values and provides the expected output values. Flags can be set by any section of code, triggering activity from anywhere in your code.

Anyone who has spent just an hour inside a CPU at machine-code level will be familiar with the concept of flags. A flag in this context is a small amount of memory (usually just a single bit) that gets a value put in to signify some condition. Oddly, this concept is not well supported in high level languages, but is very useful. Often, programmers are forced to use a variable to remember a state - enormosly wasteful of resources, but I guess if you have memory to spare it is no big deal.

Personally, it really grinds my gears to use a whole variable (4 or more bytes) to remember if I have to do something - a simple binary option. MMBasic has no “bit” data-type as do some languages. Visual Basic supports “Boolean” but still stores each in a single byte of memory so still wasteful. GCBasic; a compiled basic for micro-controllers, embraces this better - maintaining a number of system variables (bytes) and the declared bits (flags) are allocated to each bit of the variable - as many as you need and it keeps track of it all… very nice.

In an effort to address this on MMBasic, I wrote bit manipulation routines (elsewhere on this wiki) and over the years I have revisited it and honed it to a stage where I think it is probably as good (fast) as I can get it. It uses a single integer variable called “flags” and three Subs/Functions manipulate individual bits. It works well, they are quite fast and it looks nice in your code. I had to have a stern chat with myself to avoid Z80-like names for each… We are using Basic after all, despite the minuscule speed-boost and shortening the flags name to “F”… eeeasy boy! As they are they are around 300uS so we'll take that.

Flags really play into state-machine methodology - a common method, using those techniques to compartmentalize the code into sections which run only on a stimulus - perhaps a flag being set, a character arriving at an input port, a timer or simply a keypress. It's a good idea to divide your code into functional blocks like this - it makes understanding, documenting and debugging so much easier.

For the following illustration, we are not trying to re-invent any wheels but rather look at a method of executing chunks of code according to stimuli and take the best approach. We'll assume that there is no priority to each task (we'll come to that).

For simplicity of understanding, let's assume that we have an array of flag bits.

All state-machine method code is triggered by a stimulus (state), in our case the setting of a flag - the flag changes state and something happens. Our main thread is simply a loop, checking and servicing the flags; calling the relevant piece of code when necessary - notice how each section clears its own flag to prevent false triggering. In this very-simple example, each section of code can be considered “blocking” in that no other code can run until it is finished - our system of flags does provide for “no missed calls” (provided it is only one) and it is has the advantage that all sections of code get time on the CPU, regardless.

Main:
	Do
		If FlagTest(1) Then
			FlagRes 1
			... task code					
		EndIf
		If FlagTest(2) Then
			FlagRes 2
			... task code
		EndIf
...
		If FlagTest(5) Then
			FlagRes 5
			... task code
		EndIf
	Loop

This is easy enough to understand and we can see sections run in the order they are placed - or do they? At first glance it might seem that priority to code can be assigned by thoughtful positioning, but consider as each section simply falls through to the next; if section 3 finishes, the next to execute (providing the flag is set) will be section 4, then 5 and so on. But if section 1 had it's flag set, it must wait until the execution of sections 4 and 5 are done. Because of this, we can reasonably say; there is no priority and prompt execution of any particular task depends on luck or a quiet system. In reality, it is probably fine for most cases so long as each section of code runs promptly and any waiting code is not critical.

Let's take our code and tweak it to add priority to each task.

So-called “Real Time” code (and this goes for Real-Time OSs too) execute high priority tasks before lower ones (for the sake of this article, we'll assume 1 is higher priority than 2 etc.). In like-manner to simple time-slicing, the processor is usually only executing one piece of code at a time. Prioritization can degrade the multi-tasking appearance of simultaneous running because no task is guaranteed CPU time so long as higher-priority tasks are waiting. Each waiting task is serviced in the order of its priority and low-priority tasks can be interrupted (by an RTOS or your own code making checks - see below) in favour of higher priority tasks. It can be seen that low priority tasks could conceivably never get CPU time on a busy system. RTOSs mitigate this with timers and interrupt counters and the like, and all tasks get some time on the CPU - but this is a bit beyond what we are discussing here.

In each section below, before it starts about its business, a task checks to see if there are higher priority flags set and cedes control accordingly (via the nested Do/Loop).

* The following code could be made slightly faster and less involved with the use of a GoTo, but I can feel the crowd getting restless with the mere mention of it… personally I have no truck with considerate use of GoTo, but there you go… progress and all that…

Main:
	Do
		Do
'Re-entry point
			If FlagTest(1) Then
				'No check - highest priority task
				FlagRes 1
				... task code
			EndIf
			If FlagTest(2) Then
				If Flags And (2^1-1) Then Exit Do
				FlagRes 2
				Do While (stuff_to_do)
					If Flags And (2^1-1) Then FlagSet 2:Exit Do'regular "in task" checks
					... task code
				Loop
			EndIf
...
			If FlagTest(5) Then
				If Flags And (2^4-1) Then Exit Do
				FlagRes 5
				... task code
			EndIf
		Loop
	Loop

Each section now checks that there are no higher priority tasks waiting before it executes. If there are, flow exits the inner Do/Loop and is directed to the re-entry point (where priority is highest) by the outer one, thus ensuring CPU time for waiting tasks according to their priority.

This is done by building a bit mask for every task higher than itself then ANDing it with the flag bits, looking for for a non-zero result. For example, let's look at the test in task 5:

2^4=16, -1 is 15 - binary 1111 (flags one thru four) 

If the result is non-zero then one or more of tasks 1 to 4 is waiting.

Long-running application code should make regular checks to see if it should let go of control (see task 2). If you want to switch from a task like this, it must:

• Make frequent checks for higher-priority flags.
• Set its own flag again before leaving so it gets CPU time when next offered.
• Be “re-entrant” i.e. able to carry-on its business where it left off.

Notice how Task 2 fulfills these requirements.

Earlier I said that under certain conditions, you could just go with the simple first example, but I would encourage you to use the second - the additional overhead is small and if you ever need priority it is baked in to your code, if not then it won't hurt anyway. That's future proofing that is.