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 ThisFlag Then
  DoThisProcess
EndIf

If ThatFlag 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 integer or float (8 or 4 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 - possibly… At first glance it might seem that priority to code can be assessed by thoughtful arrangement of position, 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 (or not). From 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.

RealTime code (and this goes for Real-Time OSs too) executes high priority tasks before lower ones. In like-manner to simple time-slicing, a CPU is usually only executing one piece of code at a time, but those that need it most (i.e. they have high-priority) get it. This can degrade the multi-tasking appearance of simultaneous running because tasks can steal time from others, but it does make sure that important tasks aren't kept waiting. In real-time code, a task can spend as long as it needs on the CPU, so long as no higher-priority task is waiting. Each waiting task is serviced in the order of its priority and low-priority tasks will be interrupted in favour of higher priority tasks. It can be seen that low priority tasks could conceivably never get CPU time on a busy system. Application code i.e. your program, generally has to make regular checks to see if it should let go of control (and we'll come to that too).

Below, in each section, before it starts about its business, a task checks to see if there are higher priority flags set and cedes control accordingly (via the double-nested Do/Loop). Let's take our code from above but tweak it so the order in which the sections are arranged will give real priority. We are restricted in what we can achieve with switching-out then ensuring we come back to the same place, so we only check when we are in a comfortable place. If you want to be able to switch from your task, you will need to make frequent checks on the flags and make a task “re-entrant” - perhaps by breaking its job into pieces controlled by status. In our code here - once you jump out of a task it can only start again at the beginning (because its flag was left uncleared).

The following code could be made slightly faster and less involved with 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 jumps out of the inner Do/Loop and is directed to the re-entry point (where priority is highest), thus ensuring CPU time for waiting tasks according to their priority. This is done by building a bit mask for every task less 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 of the AND with the flags is non-zero there is a higher priority task waiting i.e. a lower task number than 5 (bit 5). This check can be repeated inside the task if convenient. There is a conundrum though: A task must not clear its flag before leaving (in favour of another task) as it may not have completed its work. BUT, a task must still clear its flag early on if it expects to be re-trigger-able, e.g. task 3 can be flagged to run again while task 3 is running. This could be addressed by a task setting its own flag if it is about to cede control. Notice how Task 2 performs the same checks inside its “loop” - but it sets its own flag before leaving so it will get immediately serviced (to finish its work) once it gets CPU time again. This level of checking is only required for long-running tasks.

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.