Input-driven vs event-driven state machines in embedded software

There is a lot of confusion about state machines in embedded software. Some example of this is the recent discussion in this forum: "FSM - Mealy vs Mo ore".

It seems to me that the real question to ask is not Mealy vs Moore, but "in put-driven" vs "event-driven" state machines.

"Input-driven" state machines seem to be far more popular, and most example s published in various magazines, books, and online pertain to "input-drive n" (a.k.a. "polled") state machines.

For example, here is an article "Embedded State Machine Implementation", wh ich was quite popular:

formatting link

From this article you can see that the state machines described there are N OT driven by events. Instead, the state machine code is called "as fast as possible", or periodically" from while(1) "superloop" to poll for the event s. In the code, you can easily recognize such input-driven state machines b y the if() statements that check the inputs in each state and only after di scovering the right combination of inputs, they execute actions.

In the diagrams, you can easily recognize input-driven state machines by th e fact that state transitions are NOT labeled by events, but rather by guar d conditions. The brackets around those guard conditions, which are require d by the UML state machine notation, are often missing, but you typically c an recognize that the labels are conditions, especially when you see logic operators, like and/or.

The main problems with "input-driven" (polled) state machines are that they might miss changes in the inputs (if sampling is too slow) or recognize th e changes in different order, depending on the timing (race conditions). Th ey are also wasteful, as they need to run "all the time". Finally, it is ha rd to apply hierarchical event processing, because there are no explicit ev ents.

This is all in contrast to truly "event-driven" state machines, which are d efined in the UML (State Machine package). These state machines are driven by events, which are generated externally to the state machine and then (ty pically) queued to be processed. This separates event generation from the s tate machine logic.

Reply to
StateMachineCOM
Loading thread data ...

The other point to be made is that such event-driven FSMs are equivalent to hardware /asynchronous/ FSMs in that there is no clock in any meaningful sense of the word.

The major disadvantage of hardware async FSMs, and the reason they are used as little as possible, is that to get from the current state to the next state, the state vector can transition through other intermediate states.

During design it can be verified (with difficulty) that those intermediate states are transient and do not affect the FSMs outputs - but provided only a single input changes at any time. If two or more inputs can change simultaneously, then such analysis is intractable.

Software event-driven FSMs don't suffer from that problem since the FSM serialises event processing. One event is taken from the input queue and processed to completion before moving on to the next event.

The remaining asynchonous behaviour is contained within the mechanism which put the events in the queue; that is relatively simple and tractable to analysis.

Reply to
Tom Gardner

me example of this is the recent discussion in this forum: "FSM - Mealy vs Moore".

I don't see a lot of confusion other than the issue being discussed previou sly.

input-driven" vs "event-driven" state machines.

les published in various magazines, books, and online pertain to "input-dri ven" (a.k.a. "polled") state machines.

which was quite popular:

NOT driven by events. Instead, the state machine code is called "as fast a s possible", or periodically" from while(1) "superloop" to poll for the eve nts. In the code, you can easily recognize such input-driven state machines by the if() statements that check the inputs in each state and only after discovering the right combination of inputs, they execute actions.

In this case, I think your distinction is a bit odd. I don't see where the purpose of the article had anything to do with input vs. event driven code . The code written is not intended to be an example of a particular "style " in this regard. The terms input driven and event driven never appear in the article. This code is just to illustrate the purpose of the article wh ich is to discuss the process of state machine implementation, much of whic h has to do with finding the *actual* requirements rather than what is pres ented to a design team.

the fact that state transitions are NOT labeled by events, but rather by gu ard conditions. The brackets around those guard conditions, which are requi red by the UML state machine notation, are often missing, but you typically can recognize that the labels are conditions, especially when you see logi c operators, like and/or.

ey might miss changes in the inputs (if sampling is too slow) or recognize the changes in different order, depending on the timing (race conditions). They are also wasteful, as they need to run "all the time". Finally, it is hard to apply hierarchical event processing, because there are no explicit events.

defined in the UML (State Machine package). These state machines are drive n by events, which are generated externally to the state machine and then ( typically) queued to be processed. This separates event generation from the state machine logic.

Why do you think we don't understand the issues and distinction between inp ut and event driven code? I didn't see anything that confused the two othe r than the fact that one poster pretty much insisted software state machine s had to be event driven. That might be true in a larger system where a pr ocessor is doing many tasks. The vast majority of computer systems are sma ll embedded devices that have many more MIPS available than are required to sample inputs.

I guess I'm asking what point you are trying to make?

--
  Rick C. 

  - Get 1,000 miles of free Supercharging 
 Click to see the full signature
Reply to
Rick C

Some

mples

ven"

,

re NOT

vents.

by the

y the

ard

red by

n

they

the

They

ard to

ts.

re

iven

m the

I don't think your argument holds water. The issues of async FSMs in hardw are has to do with the nature of hardware. Logic requires time to process which creates delay in the various logic paths. With multiple paths the re sult on the output will depend on the delays through the different paths wh ich results in what is called a "race" condition. Software FSMs simply don 't have this problem unless they are coded in multiple processes which can be run in various sequences and even interrupted while a competing "path" e xecutes. I've never seen anyone construct such a labyrinthine FSM and I do n't expect to ever see one.

Also, the nature of coding the functionality of the FSM in a single procedu re or process is that it is equivalent to being clocked. Invoking the code for the FSM is equivalent to "clocking" the "registers" which in this case are any of the variables that persist between invocations.

So your entire post is based on the fallacy of the equivalence between even t driven software and asynchronous logic.

--
  Rick C. 

  + Get 1,000 miles of free Supercharging 
 Click to see the full signature
Reply to
Rick C

They exist - and are commercially vital.

That's how all the various bits of the global telecoms system are *specified* and *implemented*.

I've also seen them in LAN protocols, thankfully lost in the mists of time in favour of simpler Ethernet-derived LANs.

To most people "clock" implies repeating at regular intervals. In many FSM specifications and implementations there is nothing whatsoever that is repeats regularly.

I'm not surprised you don't understand. On this and other subjects it is extremely difficult to get you to acknowledge that there are important things that are outside your experience.

Reply to
Tom Gardner

.

ealy

ut

n",

are

ast

the

nd

by

by

re

u

en

t

ce

e".

here

are

and

ion

nt to

ul

used

xt

es.

iate

only

M

nd

which

o

paths

t
s

ses

eting

FSM

Nope, that is a collection of smaller FSMs that operate and are designed in dependently. In particular, you suggest designing this way is a huge probl em because of dealing with "race" conditions as are found in software. The reality is you don't have race conditions in software systems if they are designed correctly. If you don't design correctly you end up with real pro blems.

cedure

e for

are

The only reason clocks are "regular" is because the intent is to run as fas t as possible without encountering the "race" conditions of combinational l ogic. So the clock period is set to something longer than the worst case d elay. The functional properties of the clock have little to do with the re gularity. They have to do with keeping all the clocked elements in sync... again to avoid the race conditions.

There are any number of systems designed with irregular clocks to minimize EMI/RFI.

event

It's not that I don't understand, the issue is that you fail to accept a re asoned explanation when given to you.

--
  Rick C. 

  -- Get 1,000 miles of free Supercharging 
 Click to see the full signature
Reply to
Rick C

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.