Forums

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

Started by StateMachineCOM August 22, 2019
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 Moore".

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

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

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

https://m.eet.com/media/1174905/f-gomez.pdf

From this article you can see that the state machines described there are NOT driven by events. Instead, the state machine code is called "as fast as possible", or periodically" from while(1) "superloop" to poll for the events. 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 the diagrams, you can easily recognize input-driven state machines by the fact that state transitions are NOT labeled by events, but rather by guard conditions. The brackets around those guard conditions, which are required by the UML state machine notation, are often missing, but you typically can 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 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.

This is all in contrast to truly "event-driven" state machines, which are defined in the UML (State Machine package). These state machines are driven 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.
On 22/08/19 18:03, StateMachineCOM wrote:
> 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 > Moore". > > It seems to me that the real question to ask is not Mealy vs Moore, but > "input-driven" vs "event-driven" state machines. > > "Input-driven" state machines seem to be far more popular, and most examples > published in various magazines, books, and online pertain to "input-driven" > (a.k.a. "polled") state machines. > > For example, here is an article "Embedded State Machine Implementation", > which was quite popular: > > https://m.eet.com/media/1174905/f-gomez.pdf > > From this article you can see that the state machines described there are NOT > driven by events. Instead, the state machine code is called "as fast as > possible", or periodically" from while(1) "superloop" to poll for the events. > 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 the diagrams, you can easily recognize input-driven state machines by the > fact that state transitions are NOT labeled by events, but rather by guard > conditions. The brackets around those guard conditions, which are required by > the UML state machine notation, are often missing, but you typically can > 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 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. > > This is all in contrast to truly "event-driven" state machines, which are > defined in the UML (State Machine package). These state machines are driven > 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.
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.
On Thursday, August 22, 2019 at 1:03:44 PM UTC-4, StateMachineCOM wrote:
> 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 Moore".
I don't see a lot of confusion other than the issue being discussed previously.
> It seems to me that the real question to ask is not Mealy vs Moore, but "input-driven" vs "event-driven" state machines. > > "Input-driven" state machines seem to be far more popular, and most examples published in various magazines, books, and online pertain to "input-driven" (a.k.a. "polled") state machines. > > For example, here is an article "Embedded State Machine Implementation", which was quite popular: > > https://m.eet.com/media/1174905/f-gomez.pdf > > From this article you can see that the state machines described there are NOT driven by events. Instead, the state machine code is called "as fast as possible", or periodically" from while(1) "superloop" to poll for the events. 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 which is to discuss the process of state machine implementation, much of which has to do with finding the *actual* requirements rather than what is presented to a design team.
> In the diagrams, you can easily recognize input-driven state machines by the fact that state transitions are NOT labeled by events, but rather by guard conditions. The brackets around those guard conditions, which are required by the UML state machine notation, are often missing, but you typically can 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 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. > > This is all in contrast to truly "event-driven" state machines, which are defined in the UML (State Machine package). These state machines are driven 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 input and event driven code? I didn't see anything that confused the two other than the fact that one poster pretty much insisted software state machines had to be event driven. That might be true in a larger system where a processor is doing many tasks. The vast majority of computer systems are small 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 - Tesla referral code - https://ts.la/richard11209
On Thursday, August 22, 2019 at 2:22:18 PM UTC-4, Tom Gardner wrote:
> On 22/08/19 18:03, StateMachineCOM wrote: > > 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 > > Moore". > > > > It seems to me that the real question to ask is not Mealy vs Moore, but > > "input-driven" vs "event-driven" state machines. > > > > "Input-driven" state machines seem to be far more popular, and most examples > > published in various magazines, books, and online pertain to "input-driven" > > (a.k.a. "polled") state machines. > > > > For example, here is an article "Embedded State Machine Implementation", > > which was quite popular: > > > > https://m.eet.com/media/1174905/f-gomez.pdf > > > > From this article you can see that the state machines described there are NOT > > driven by events. Instead, the state machine code is called "as fast as > > possible", or periodically" from while(1) "superloop" to poll for the events. > > 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 the diagrams, you can easily recognize input-driven state machines by the > > fact that state transitions are NOT labeled by events, but rather by guard > > conditions. The brackets around those guard conditions, which are required by > > the UML state machine notation, are often missing, but you typically can > > 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 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. > > > > This is all in contrast to truly "event-driven" state machines, which are > > defined in the UML (State Machine package). These state machines are driven > > 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. > > 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.
I don't think your argument holds water. The issues of async FSMs in hardware 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 result on the output will depend on the delays through the different paths which 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" executes. I've never seen anyone construct such a labyrinthine FSM and I don't expect to ever see one. Also, the nature of coding the functionality of the FSM in a single procedure 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 event driven software and asynchronous logic. -- Rick C. + Get 1,000 miles of free Supercharging + Tesla referral code - https://ts.la/richard11209
On 23/08/19 16:53, Rick C wrote:
> On Thursday, August 22, 2019 at 2:22:18 PM UTC-4, Tom Gardner wrote: >> On 22/08/19 18:03, StateMachineCOM wrote: >>> 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 Moore". >>> >>> It seems to me that the real question to ask is not Mealy vs Moore, but >>> "input-driven" vs "event-driven" state machines. >>> >>> "Input-driven" state machines seem to be far more popular, and most >>> examples published in various magazines, books, and online pertain to >>> "input-driven" (a.k.a. "polled") state machines. >>> >>> For example, here is an article "Embedded State Machine Implementation", >>> which was quite popular: >>> >>> https://m.eet.com/media/1174905/f-gomez.pdf >>> >>> From this article you can see that the state machines described there are >>> NOT driven by events. Instead, the state machine code is called "as fast >>> as possible", or periodically" from while(1) "superloop" to poll for the >>> events. 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 the diagrams, you can easily recognize input-driven state machines by >>> the fact that state transitions are NOT labeled by events, but rather by >>> guard conditions. The brackets around those guard conditions, which are >>> required by the UML state machine notation, are often missing, but you >>> typically can 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 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. >>> >>> This is all in contrast to truly "event-driven" state machines, which >>> are defined in the UML (State Machine package). These state machines are >>> driven 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. >> >> 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. > > I don't think your argument holds water. The issues of async FSMs in > hardware 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 result on the output will depend on the delays through the different > paths which 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" executes. I've never seen anyone construct such a labyrinthine FSM > and I don't expect to ever see one.
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.
> Also, the nature of coding the functionality of the FSM in a single procedure > 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.
To most people "clock" implies repeating at regular intervals. In many FSM specifications and implementations there is nothing whatsoever that is repeats regularly.
> So your entire post is based on the fallacy of the equivalence between event > driven software and asynchronous logic.
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.
On Friday, August 23, 2019 at 1:46:08 PM UTC-4, Tom Gardner wrote:
> On 23/08/19 16:53, Rick C wrote: > > On Thursday, August 22, 2019 at 2:22:18 PM UTC-4, Tom Gardner wrote: > >> On 22/08/19 18:03, StateMachineCOM wrote: > >>> 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 Moore". > >>> > >>> It seems to me that the real question to ask is not Mealy vs Moore, but > >>> "input-driven" vs "event-driven" state machines. > >>> > >>> "Input-driven" state machines seem to be far more popular, and most > >>> examples published in various magazines, books, and online pertain to > >>> "input-driven" (a.k.a. "polled") state machines. > >>> > >>> For example, here is an article "Embedded State Machine Implementation", > >>> which was quite popular: > >>> > >>> https://m.eet.com/media/1174905/f-gomez.pdf > >>> > >>> From this article you can see that the state machines described there are > >>> NOT driven by events. Instead, the state machine code is called "as fast > >>> as possible", or periodically" from while(1) "superloop" to poll for the > >>> events. 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 the diagrams, you can easily recognize input-driven state machines by > >>> the fact that state transitions are NOT labeled by events, but rather by > >>> guard conditions. The brackets around those guard conditions, which are > >>> required by the UML state machine notation, are often missing, but you > >>> typically can 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 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. > >>> > >>> This is all in contrast to truly "event-driven" state machines, which > >>> are defined in the UML (State Machine package). These state machines are > >>> driven 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. > >> > >> 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. > > > > I don't think your argument holds water. The issues of async FSMs in > > hardware 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 result on the output will depend on the delays through the different > > paths which 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" executes. I've never seen anyone construct such a labyrinthine FSM > > and I don't expect to ever see one. > > They exist - and are commercially vital. > > That's how all the various bits of the global telecoms > system are *specified* and *implemented*.
Nope, that is a collection of smaller FSMs that operate and are designed independently. In particular, you suggest designing this way is a huge problem 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 problems.
> I've also seen them in LAN protocols, thankfully lost in the > mists of time in favour of simpler Ethernet-derived LANs. > > > > Also, the nature of coding the functionality of the FSM in a single procedure > > 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. > > To most people "clock" implies repeating at regular > intervals. In many FSM specifications and implementations > there is nothing whatsoever that is repeats regularly.
The only reason clocks are "regular" is because the intent is to run as fast as possible without encountering the "race" conditions of combinational logic. So the clock period is set to something longer than the worst case delay. The functional properties of the clock have little to do with the regularity. 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.
> > So your entire post is based on the fallacy of the equivalence between event > > driven software and asynchronous logic. > > 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.
It's not that I don't understand, the issue is that you fail to accept a reasoned explanation when given to you. -- Rick C. -- Get 1,000 miles of free Supercharging -- Tesla referral code - https://ts.la/richard11209
On 23/08/19 19:03, Rick C wrote:
> On Friday, August 23, 2019 at 1:46:08 PM UTC-4, Tom Gardner wrote: >> On 23/08/19 16:53, Rick C wrote: >>> On Thursday, August 22, 2019 at 2:22:18 PM UTC-4, Tom Gardner wrote: >>>> On 22/08/19 18:03, StateMachineCOM wrote: >>>>> 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 Moore". >>>>> >>>>> It seems to me that the real question to ask is not Mealy vs Moore, >>>>> but "input-driven" vs "event-driven" state machines. >>>>> >>>>> "Input-driven" state machines seem to be far more popular, and most >>>>> examples published in various magazines, books, and online pertain >>>>> to "input-driven" (a.k.a. "polled") state machines. >>>>> >>>>> For example, here is an article "Embedded State Machine >>>>> Implementation", which was quite popular: >>>>> >>>>> https://m.eet.com/media/1174905/f-gomez.pdf >>>>> >>>>> From this article you can see that the state machines described there >>>>> are NOT driven by events. Instead, the state machine code is called >>>>> "as fast as possible", or periodically" from while(1) "superloop" to >>>>> poll for the events. 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 the diagrams, you can easily recognize input-driven state machines >>>>> by the fact that state transitions are NOT labeled by events, but >>>>> rather by guard conditions. The brackets around those guard >>>>> conditions, which are required by the UML state machine notation, are >>>>> often missing, but you typically can 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 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. >>>>> >>>>> This is all in contrast to truly "event-driven" state machines, >>>>> which are defined in the UML (State Machine package). These state >>>>> machines are driven 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. >>>> >>>> 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. >>> >>> I don't think your argument holds water. The issues of async FSMs in >>> hardware 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 result on the output will depend on the delays through the >>> different paths which 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" executes. I've never seen anyone >>> construct such a labyrinthine FSM and I don't expect to ever see one. >> >> They exist - and are commercially vital. >> >> That's how all the various bits of the global telecoms system are >> *specified* and *implemented*. > > Nope, that is a collection of smaller FSMs that operate and are designed > independently.
You appear to have speedread what I wrote, and not comprehended the significance of the word "bits" in my statement. Clearly you have zero experience in modern telecoms systems.
> In particular, you suggest designing this way is a huge > problem 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 > problems.
Nonsense. Strawman arguments.
>> I've also seen them in LAN protocols, thankfully lost in the mists of time >> in favour of simpler Ethernet-derived LANs. >> >> >>> Also, the nature of coding the functionality of the FSM in a single >>> procedure 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. >> >> To most people "clock" implies repeating at regular intervals. In many FSM >> specifications and implementations there is nothing whatsoever that is >> repeats regularly. > > The only reason clocks are "regular" is because the intent is to run as fast > as possible without encountering the "race" conditions of combinational > logic.
False. It is to avoid the unpredictable behaviour that occurs when two or more inputs change simultaneously in an async FSM. If you have difficulty comprehending that, then please explain why many clocked systems are run far more slowly that the maximum possible rate.
> So the clock period is set to something longer than the worst case > delay. The functional properties of the clock have little to do with the > regularity. They have to do with keeping all the clocked elements in sync... > again to avoid the race conditions.
False.
> There are any number of systems designed with irregular clocks to minimize > EMI/RFI.
Don't be a twat. You know perfectly well that's irrelevant flack.
>>> So your entire post is based on the fallacy of the equivalence between >>> event driven software and asynchronous logic. >> >> 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. > > It's not that I don't understand, the issue is that you fail to accept a > reasoned explanation when given to you.
Whereas you don't even see a reasoned argument unless it fits within your limited weltanschauung.
On Friday, August 23, 2019 at 6:33:14 PM UTC-4, Tom Gardner wrote:
> On 23/08/19 19:03, Rick C wrote: > > On Friday, August 23, 2019 at 1:46:08 PM UTC-4, Tom Gardner wrote: > >> On 23/08/19 16:53, Rick C wrote: > >>> On Thursday, August 22, 2019 at 2:22:18 PM UTC-4, Tom Gardner wrote: > >>>> On 22/08/19 18:03, StateMachineCOM wrote: > >>>>> 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 Moore". > >>>>> > >>>>> It seems to me that the real question to ask is not Mealy vs Moore, > >>>>> but "input-driven" vs "event-driven" state machines. > >>>>> > >>>>> "Input-driven" state machines seem to be far more popular, and most > >>>>> examples published in various magazines, books, and online pertain > >>>>> to "input-driven" (a.k.a. "polled") state machines. > >>>>> > >>>>> For example, here is an article "Embedded State Machine > >>>>> Implementation", which was quite popular: > >>>>> > >>>>> https://m.eet.com/media/1174905/f-gomez.pdf > >>>>> > >>>>> From this article you can see that the state machines described there > >>>>> are NOT driven by events. Instead, the state machine code is called > >>>>> "as fast as possible", or periodically" from while(1) "superloop" to > >>>>> poll for the events. 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 the diagrams, you can easily recognize input-driven state machines > >>>>> by the fact that state transitions are NOT labeled by events, but > >>>>> rather by guard conditions. The brackets around those guard > >>>>> conditions, which are required by the UML state machine notation, are > >>>>> often missing, but you typically can 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 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. > >>>>> > >>>>> This is all in contrast to truly "event-driven" state machines, > >>>>> which are defined in the UML (State Machine package). These state > >>>>> machines are driven 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. > >>>> > >>>> 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. > >>> > >>> I don't think your argument holds water. The issues of async FSMs in > >>> hardware 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 result on the output will depend on the delays through the > >>> different paths which 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" executes. I've never seen anyone > >>> construct such a labyrinthine FSM and I don't expect to ever see one. > >> > >> They exist - and are commercially vital. > >> > >> That's how all the various bits of the global telecoms system are > >> *specified* and *implemented*. > > > > Nope, that is a collection of smaller FSMs that operate and are designed > > independently. > > You appear to have speedread what I wrote, and not comprehended > the significance of the word "bits" in my statement. > > Clearly you have zero experience in modern telecoms systems.
I never get the impression that you actually wish to discuss a matter. Rather you seem to want to pull in any arbitrary and obscure detail you can and then try to build a case around it that proves some wider point. If you have something to say, then say it. I'm not going to follow you around while you try to make a case out of something you won't even talk about.
> > In particular, you suggest designing this way is a huge > > problem 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 > > problems. > > Nonsense. Strawman arguments.
Lol! This is what YOU are talking about. YOU are the one trying to compare hardware async design to software. Hardware async is complex because of the race conditions that have to be mitigated. These do not exist in software unless you have a desire to write inordinately complex software.
> >> I've also seen them in LAN protocols, thankfully lost in the mists of time > >> in favour of simpler Ethernet-derived LANs. > >> > >> > >>> Also, the nature of coding the functionality of the FSM in a single > >>> procedure 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. > >> > >> To most people "clock" implies repeating at regular intervals. In many FSM > >> specifications and implementations there is nothing whatsoever that is > >> repeats regularly. > > > > The only reason clocks are "regular" is because the intent is to run as fast > > as possible without encountering the "race" conditions of combinational > > logic. > > False. It is to avoid the unpredictable behaviour that occurs > when two or more inputs change simultaneously in an async FSM.
Whoa! Now you are talking about something entirely different. All registered logic is synchronous and solves the issues of async logic which you incorrectly mischaracterize as having to do with dealing with multiple inputs changing simultaneously. In fact this has NOTHING to do with that issue since it doesn't resolve it. I have repeated this numerous times and anyone else can clearly see that multiple inputs can change at the same time in synchronous or asynchronous sequential logic. In both cases the implications must be designed for.
> If you have difficulty comprehending that, then please explain > why many clocked systems are run far more slowly that the > maximum possible rate.
Uh, because that's all the faster that needed to run them. The fact that you asked this question shows you didn't read and/or understand anything I said about the issue. Please read it again and this time try to understand what I wrote rather than just looking for points you can flame about.
> > So the clock period is set to something longer than the worst case > > delay. The functional properties of the clock have little to do with the > > regularity. They have to do with keeping all the clocked elements in sync... > > again to avoid the race conditions. > > False.
Now I see why you don't understand. You get as far as seeing I'm not agreeing with you and the FALSE alarm goes off and thinking shuts down. Clocks are used to gate the inputs to a register to the outputs. There is no requirement for a clock to be regular. In fact, clocks are not always regular. Sometimes a clock is very sporadic being gated on and off. In some logic a non-clock signal is used as a clock in order to cross clock domains. So that clock is very irregular only occurring when data is present. But I think I know how you will respond to this... FALSE!
> > There are any number of systems designed with irregular clocks to minimize > > EMI/RFI. > > Don't be a twat. You know perfectly well that's irrelevant flack.
Then tell me what you mean by "regular".
> >>> So your entire post is based on the fallacy of the equivalence between > >>> event driven software and asynchronous logic. > >> > >> 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. > > > > It's not that I don't understand, the issue is that you fail to accept a > > reasoned explanation when given to you. > > Whereas you don't even see a reasoned argument unless it fits > within your limited weltanschauung.
Not really. It just has to be factually correct. Are we about done with this? You seem to not be able to understand the arguments I make and continue to cite irrelevant examples of your own. Is there any point to continuing? I'm happy to discuss FSM design. This conversation seems to have devolved into an argument of picayune details. -- Rick C. -+ Get 1,000 miles of free Supercharging -+ Tesla referral code - https://ts.la/richard11209
Gents, its all explained here: https://tinyurl.com/d26z5b6
On Saturday, August 24, 2019 at 8:11:08 PM UTC-4, Dave Nadler wrote:
> Gents, its all explained here: https://tinyurl.com/d26z5b6
What? Are you saying angels are finite state automata? -- Rick C. +- Get 1,000 miles of free Supercharging +- Tesla referral code - https://ts.la/richard11209