Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch.embedded > #27461 > unrolled thread

Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)?

Back to article view | Back to comp.arch.embedded

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Mike Perkins <spam@spam.com> - 2017-12-10 14:56 +0000
    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2017-12-16 11:58 -0600
      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Ed Prochak <edprochak@gmail.com> - 2017-12-19 08:19 -0800
        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm@gmail.com> - 2017-12-19 11:51 -0500
          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Ed Prochak <edprochak@gmail.com> - 2018-01-02 14:58 -0800
          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-03 06:07 -0600
            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-03 12:59 -0500
              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-03 17:59 -0600
                Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-04 03:33 -0500
                  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-04 14:31 -0500
                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Rob Gaddi <rgaddi@highlandtechnology.invalid> - 2018-01-04 11:56 -0800
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-04 21:46 -0600
                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-04 16:46 -0800
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-04 21:47 -0600
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 18:55 -0500
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 00:54 +0000
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 13:41 -0800
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 23:32 +0000
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-10 10:33 -0500
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-10 16:29 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? upsidedown@downunder.com - 2018-01-08 08:11 +0200
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 23:05 -0800
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? upsidedown@downunder.com - 2018-01-08 10:06 +0200
                                Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? David Brown <david.brown@hesbynett.no> - 2018-01-08 10:27 +0100
                                  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-08 09:56 -0800
                                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 18:39 +0000
                                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-08 12:20 -0800
                                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 22:11 +0000
                                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? David Brown <david.brown@hesbynett.no> - 2018-01-08 22:26 +0100
                                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 22:23 +0000
                                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-08 14:44 -0800
                                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 23:06 +0000
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-08 10:02 +0000
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-08 17:34 -0600
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 22:29 -0500
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 00:46 -0800
                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-04 21:44 -0600
                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-05 09:12 +0000
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2018-01-05 21:40 -0500
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-05 21:29 -0600
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-06 09:10 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-06 16:35 -0600
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:04 +0000
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-06 09:17 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Les Cargill <lcargill99@comcast.com> - 2018-01-06 16:37 -0600
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:11 +0000
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-06 17:31 -0800
                                Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:52 +0000
                                  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 00:39 -0800
                                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 09:55 +0000
                                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 10:43 -0800
                                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 19:35 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 19:06 -0500
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-06 16:58 -0800
                              Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 22:37 -0500
                                Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 00:58 -0800
                                  Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-07 09:32 -0500
                                    Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Paul Rubin <no.email@nospam.invalid> - 2018-01-07 10:53 -0800
                                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-10 11:40 -0500
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:14 +0000
                      Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 18:57 -0500
                        Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 01:17 +0000
                          Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? rickman <gnuarm.deletethisbit@gmail.com> - 2018-01-06 22:40 -0500
                            Re: When exactly do you choose to use a RTOS (instead of a non-OS approach)? Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-01-07 09:59 +0000

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#27551

On Sun, 07 Jan 2018 13:41:55 -0800, Paul Rubin
<no.email@nospam.invalid> wrote:

>Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>> But for many embedded systems, FSMs are (or IMNSHO ought to be!) a key
>> component in structuring and expressing the design. Canonical examples
>> are ATMs, car cruise control, comms/networking protocols etc.
>
>I don't see a requirement for FSM's in any of those.  ATM's (I assume
>you mean cash dispensers) just seem like they'd run normal business
>code.  Cruise control sounds like a normal PID-like controller.  I've
>written tons of comms code without FSM's.  On the other hand, maybe your
>comm protocol involves checksums or error correcting codes.  Doing those
>with FSMs would be straightforward in theory but ridiculous in practice.

Why would it be ridiculous to process the protocol frame with a state
machine ? How do you process the frame in the ISR without a state
machine ?

Especially in systems with user/kernel modes, processing the protocol
frame in user mode byte by byte requires a large number of
user/kernel/user mode changes for each byte, causing a lot of
overhead.

By completely processing the protocol frame in ISR state machine,
there will be only one user/kernel/user mode change for a full
protocol frame.

[toc] | [prev] | [next] | [standalone]

#27552

upsidedown@downunder.com writes:
> Why would it be ridiculous to process the protocol frame with a state
> machine ?

You'd need a ridiculous number of states to validate the checksum.

[toc] | [prev] | [next] | [standalone]

#27553

On Sun, 07 Jan 2018 23:05:07 -0800, Paul Rubin
<no.email@nospam.invalid> wrote:

>upsidedown@downunder.com writes:
>> Why would it be ridiculous to process the protocol frame with a state
>> machine ?
>
>You'd need a ridiculous number of states to validate the checksum.

Is 16 million states a ridiculous number ?

It fits nicely into 24 bits (3 bytes) state variable. 

It is easier to visualize the situation by dividing these 24 bits into
three separate byte variables, one is the actual state (such as
Read_header, Read_data, Read_checksum, Done), the second byte is the
remaining byte count and the third byte is the is partial checksum.

Stay in Read_data state as long as remaining byte count is greater
than zero. For each byte received, store character into result buffer,
add character to partial checksum and decrement the remaining byte
count and if it drops to zero, change main state to Read_checksum.

When checksum byte arrives, check if it is the same as the
(same/inverted/negated) partial checksum and set the main state to
Done.

This also works for CRC calculations as well as delimited data without
byte count. In principle the remaining bytes is then superfluous, but
it is good to have it to check for too long message frames.

It might be a good idea to pack these three bytes into a 32 bit DWord,
if it is visible outside the state machine to have atomic updates
visible to the external world.

[toc] | [prev] | [next] | [standalone]

#27554

On 08/01/18 09:06, upsidedown@downunder.com wrote:
> On Sun, 07 Jan 2018 23:05:07 -0800, Paul Rubin
> <no.email@nospam.invalid> wrote:
> 
>> upsidedown@downunder.com writes:
>>> Why would it be ridiculous to process the protocol frame with a state
>>> machine ?
>>
>> You'd need a ridiculous number of states to validate the checksum.
> 
> Is 16 million states a ridiculous number ?
> 

It is ridiculous for people who think of state machines as a table of
current state, event, action and next state (whether by case statement,
table with function pointers, or whatever).  It is /not/ ridiculous for
people who think of state machines more generally and are happy to
handle a whole set of states (like all values for your current checksum)
in common code.

[toc] | [prev] | [next] | [standalone]

#27556

David Brown <david.brown@hesbynett.no> writes:
> It is /not/ ridiculous for people who think of state machines more
> generally and are happy to handle a whole set of states (like all
> values for your current checksum) in common code.

The term "state machine" stops having any meaning, once generalized to
include basically every possible program that doesn't allocate
potentially unbounded amounts of dynamic memory during operation.
I do believe we were discussing them in terms of state tables.

[toc] | [prev] | [next] | [standalone]

#27557

On 08/01/18 17:56, Paul Rubin wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> It is /not/ ridiculous for people who think of state machines more
>> generally and are happy to handle a whole set of states (like all
>> values for your current checksum) in common code.
>
> The term "state machine" stops having any meaning, once generalized to
> include basically every possible program that doesn't allocate
> potentially unbounded amounts of dynamic memory during operation.
> I do believe we were discussing them in terms of state tables.

To me and given the history of this subthread, coming
from you that seems a bizarre and incomprehensible response.

I really don't understand what position you are trying
to advocate.

[toc] | [prev] | [next] | [standalone]

#27558

Tom Gardner <spamjunk@blueyonder.co.uk> writes:
> I really don't understand what position you are trying
> to advocate.

There are many problems like communications protocols that people in
this thread have advocated solving with state machines, using a concept
of state machines in which all the states and transitions are written
out explicitly.  My position is that while it might be *possible* to do
those things with state machines, other methods are often preferable.

[toc] | [prev] | [next] | [standalone]

#27561

On 08/01/18 20:20, Paul Rubin wrote:
> Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>> I really don't understand what position you are trying
>> to advocate.
>
> There are many problems like communications protocols that people in
> this thread have advocated solving with state machines, using a concept
> of state machines in which all the states and transitions are written
> out explicitly.  My position is that while it might be *possible* to do
> those things with state machines, other methods are often preferable.

Ah. A strawman argument.

No more needs to be said.

[toc] | [prev] | [next] | [standalone]

#27559

On 08/01/18 18:56, Paul Rubin wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> It is /not/ ridiculous for people who think of state machines more
>> generally and are happy to handle a whole set of states (like all
>> values for your current checksum) in common code.
> 
> The term "state machine" stops having any meaning, once generalized to
> include basically every possible program that doesn't allocate
> potentially unbounded amounts of dynamic memory during operation.
> I do believe we were discussing them in terms of state tables.
> 

/I/ believe the arguments going on in this thread are based on people 
having different but very fixed ideas about what a "finite state 
machine" actually /is/.  Different people use the term in different ways 
- there is no single correct definition.  Some people think of them in 
terms of pure theory - you have a finite number of states, you have a 
finite number of events, and an event causes the machine to move from 
one state to another (usually in a purely deterministic way).  Other 
people think of them in terms of implementation - whatever their 
particular favourite method might be (switch statements, tables with 
function pointers, etc.).  With such a viewpoint, it is common to have 
some ill-defined limit of "practical size".

Once you realise that these (and many other) ways to define a "state 
machine" are valid, people in this thread can stop arguing and insulting 
each other and realise that you actually agree on many things.  (Of 
course, that might spoil the fun!)

For my own viewpoint, I usually consider code to represent a "state 
machine" if there is one or more "state" variables of an enumerated 
type.  These state variables will not hold the full state of the system 
- there are usually other variables too.  So a state machine for a 
protocol handler might have states for "idle", "getting header", 
"getting data", "getting checksum" and additional state information such 
as a counter of the bytes so far and a running checksum.  Trying to 
store all the state in a table would be impractical - but it is still a 
finite state machine by the flexible definitions I use.

[toc] | [prev] | [next] | [standalone]

#27562

On 08/01/18 21:26, David Brown wrote:
> On 08/01/18 18:56, Paul Rubin wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> It is /not/ ridiculous for people who think of state machines more
>>> generally and are happy to handle a whole set of states (like all values
>>> for your current checksum) in common code.
>>
>> The term "state machine" stops having any meaning, once generalized to
>> include basically every possible program that doesn't allocate potentially
>> unbounded amounts of dynamic memory during operation. I do believe we were
>> discussing them in terms of state tables.
>>
>
> /I/ believe the arguments going on in this thread are based on people having
> different but very fixed ideas about what a "finite state machine" actually
> /is/.  Different people use the term in different ways - there is no single
> correct definition.  Some people think of them in terms of pure theory - you
> have a finite number of states, you have a finite number of events, and an
> event causes the machine to move from one state to another (usually in a
> purely deterministic way).  Other people think of them in terms of
> implementation - whatever their particular favourite method might be (switch
> statements, tables with function pointers, etc.).  With such a viewpoint, it
> is common to have some ill-defined limit of "practical size".
>
> Once you realise that these (and many other) ways to define a "state
> machine" are valid, people in this thread can stop arguing and insulting each
> other and realise that you actually agree on many things.  (Of course, that
> might spoil the fun!)
>
> For my own viewpoint, I usually consider code to represent a "state machine"
> if there is one or more "state" variables of an enumerated type.  These
> state variables will not hold the full state of the system - there are
> usually other variables too.  So a state machine for a protocol handler might
> have states for "idle", "getting header", "getting data", "getting checksum"
> and additional state information such as a counter of the bytes so far and a
> running checksum. Trying to store all the state in a table would be
> impractical - but it is still a finite state machine by the flexible
> definitions I use.

Yes.

That is the way in which I, you, and probably everybody except
Mr Rubin, is using the term the term FSM in an embedded context.

I have come across young maintenance programmers working on
comms protocols and business rules that did not recognise the
comms protocols and programs /were/ FSMs. To them an FSM was
something they vaguely remembered from university as being
something to do with parsing in compilers.

I would not have thought someone using a usenet group on
embedded systems could be classified as "young maintenance
programmer".

Now a computer is, in a very deep sense, nothing more than a
large FSM. However, attempting to design and implement non-trivial
systems _solely_ at that level is a concept that had never
occurred to me, except possibly when we have all had too much
to drink in the pub :)

[toc] | [prev] | [next] | [standalone]

#27563

Tom Gardner <spamjunk@blueyonder.co.uk> writes:
> That is the way in which I, you, and probably everybody except
> Mr Rubin, is using the term the term FSM in an embedded context.

Excuse me, one of the claimed advantages of the FSM approach was that
you could validate an FSM implementation by enumerating all of the
states and making sure each transition does the right thing.

If you widen the idea of an FSM until you can have 100s of bits of state
variables and still call it an FSM, that approach becomes impractical.
You're back at the verification methods used for arbitrary programming.
In that case, I don't see what's so great about calling something an FSM
rather than just ordinary code.

> Now a computer is, in a very deep sense, nothing more than a large
> FSM. However, attempting to design and implement non-trivial systems
> _solely_ at that level is a concept that had never occurred to me,

Sure, I find that idea crazy too, but that's what I think was being
presented here.  Otherwise, what is the difference between an FSM-based
implementation, and a non-FSM one?

[toc] | [prev] | [next] | [standalone]

#27564

On 08/01/18 22:44, Paul Rubin wrote:
> Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>> That is the way in which I, you, and probably everybody except
>> Mr Rubin, is using the term the term FSM in an embedded context.
>
> Excuse me, one of the claimed advantages of the FSM approach was that
> you could validate an FSM implementation by enumerating all of the
> states and making sure each transition does the right thing.

You can indeed. Nobody except you conceived that might
mean _all_ aspects of a design specification and
implementation were coded as an explicit FSM.


> If you widen the idea of an FSM until you can have 100s of bits of state
> variables and still call it an FSM, that approach becomes impractical.
> You're back at the verification methods used for arbitrary programming.
> In that case, I don't see what's so great about calling something an FSM
> rather than just ordinary code.

The number of bits is unimportant. What is important
is to use good taste in implementing a design in such
a way that there is a visible correspondence between
the specification and the implementation.

And for many purposes an FSM is the most natural way
to express and then specify important aspects of an
embedded (or other!) system. Hence it is also the most
natural way to implement those parts of the design.


>> Now a computer is, in a very deep sense, nothing more than a large
>> FSM. However, attempting to design and implement non-trivial systems
>> _solely_ at that level is a concept that had never occurred to me,
>
> Sure, I find that idea crazy too, but that's what I think was being
> presented here.  Otherwise, what is the difference between an FSM-based
> implementation, and a non-FSM one?

No, that wasn't being advocated.

[toc] | [prev] | [next] | [standalone]

#27555

On 08/01/18 07:05, Paul Rubin wrote:
> upsidedown@downunder.com writes:
>> Why would it be ridiculous to process the protocol frame with a state
>> machine ?
>
> You'd need a ridiculous number of states to validate the checksum.

That's as stupid and unhelpful as suggesting that a
TCP sequence counter should be implemented as an FSM!

It is unbalanced to insist on using a single implementation
technique for all designs.

It is sane (and good practice) to select the implementation
technique that most clearly expresses the design.

"Doctor, doctor, my head hurts when I bang it against
the number of states"
"Well don't do that then"

[toc] | [prev] | [next] | [standalone]

#27565

upsidedown@downunder.com wrote:
> On Sun, 07 Jan 2018 13:41:55 -0800, Paul Rubin
> <no.email@nospam.invalid> wrote:
> 
>> Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>>> But for many embedded systems, FSMs are (or IMNSHO ought to be!) a key
>>> component in structuring and expressing the design. Canonical examples
>>> are ATMs, car cruise control, comms/networking protocols etc.
>>
>> I don't see a requirement for FSM's in any of those.  ATM's (I assume
>> you mean cash dispensers) just seem like they'd run normal business
>> code.  Cruise control sounds like a normal PID-like controller.  I've
>> written tons of comms code without FSM's.  On the other hand, maybe your
>> comm protocol involves checksums or error correcting codes.  Doing those
>> with FSMs would be straightforward in theory but ridiculous in practice.
> 
> Why would it be ridiculous to process the protocol frame with a state
> machine ? How do you process the frame in the ISR without a state
> machine ?
> 
> Especially in systems with user/kernel modes, processing the protocol
> frame in user mode byte by byte requires a large number of
> user/kernel/user mode changes for each byte, causing a lot of
> overhead.
> 

It varies.

If you take the VxWorks driver course, they have a "three-layer"
solution where the lowest layer ( ISRs ) is minimal, the middle layer is
a kernel-mode ( or user mode ) task and the upper layer is
just plain-old userspace code. But the middle layer is still a task.

In that, the "middle layer" manages the protocol FSM. I'm afraid
I don't remember much detail  beyond that.

> By completely processing the protocol frame in ISR state machine,
> there will be only one user/kernel/user mode change for a full
> protocol frame.
> 

I think the concern then would be the sheer size of the driver and
whether or not the ISR coudl turn interrupts back on or not ( probably 
can, usually ).

-- 
Les Cargill

[toc] | [prev] | [next] | [standalone]

#27534

Paul Rubin wrote on 1/4/2018 7:46 PM:
> rickman <gnuarm.deletethisbit@gmail.com> writes:
>> Why is this structure hard to understand?
>
> It's just that the decomposition into state transitions obscures what
> the program is supposed to do at a higher level.  As an extreme example,
> consider compiling a regular expression into a DFSM and look how opaque
> the DFSM is by comparison to the original regex.

I completely missed the reference to "DFSM" rather than just FSM.  After 
looking up the definitions, I don't understand the need for the distinction. 
  I can't think of any program or correctly constructed digital logic design 
that would not produce a non-deterministic FSM.

What is the point in such a distinction?

-- 

Rick C

Viewed the eclipse at Wintercrest Farms,
on the centerline of totality since 1998

[toc] | [prev] | [next] | [standalone]

#27538

rickman <gnuarm.deletethisbit@gmail.com> writes:
> I can't think of any program or correctly constructed digital logic
> design that would not produce a non-deterministic FSM.

NSFM's (actually usually called NFA, non-deterministic finite automata)
are common in software.  Each NFA state potentially has multiple
outgoing edges labelled with the same symbol, and you "run" the NFA by
exploring edges and backtracking when needed.  Regexes are
straightforward to convert to NFA.  Then you can convert the NFA to a
DFA by making a separate DFA state for each subset of NFA states that
the NFA could possibly be in.  This is explained in the "dragon book"
(https://en.wikipedia.org/wiki/Dragon_Book) and other places.

> What is the point in such a distinction?

The NFA size is linear in the regex size, but it can potentially use
exponential time because of the backtracking (it usually doesn't).  The
DFA is fast but the number of states can potentially be exponential in
the regex size (it usually isn't).  Also, compiling the NFA to a DFA
takes time.  So it's a trade-off.  DFA conversion is more likely to be
worthwhile if you're scanning for the pattern a lot of times.

[toc] | [prev] | [next] | [standalone]

#27495

rickman wrote:
> rickman wrote on 1/4/2018 3:33 AM:
>> Les Cargill wrote on 1/3/2018 6:59 PM:
>>> rickman wrote:
>>>> Les Cargill wrote on 1/3/2018 7:07 AM:
>>>>> rickman wrote:
>>>>>> Ed Prochak wrote on 12/19/2017 11:19 AM:
>>>>>>> On Saturday, December 16, 2017 at 12:56:31 PM UTC-5, Les Cargill 
>>>>>>> wrote:
>>>>>>>> Mike Perkins wrote:
>>>>>>>>> On 09/12/2017 16:05, pozz wrote:
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I use it where I have a number of 'tasks' which then interact 
>>>>>>>>> with each
>>>>>>>>> other.
>>>>>>>>>
>>>>>>>>> If your system is a pure state machine then there is no need 
>>>>>>>>> for an
>>>>>>>>> RTOS.
>>>>>>>>>
>>>>>>>>
>>>>>>>> Indeed. Indeed.
>>>>>>>
>>>>>>> If it is just one state machine. Then yes, indeed.
>>>>>>> ed
>>>>>>
>>>>>> It can always be one state machine.  The only issue is how complex 
>>>>>> the
>>>>>> combined state machine is.
>>>>>>
>>>>>
>>>>> It's always a case of "how long should a man's legs be?" Lincoln
>>>>> is alleged to have said "long enough to touch the ground."
>>>>>
>>>>>> Actually the issue is not how many state machines you have.  It is 
>>>>>> the
>>>>>> timing requirements of the various state machines.  If your timing 
>>>>>> is lax,
>>>>>> sequential operation of multiple machines is easy.  But this often 
>>>>>> becomes
>>>>>> a huge discussion with everyone talking past each other.
>>>>>>
>>>>>
>>>>> They should use state machines to keep track then :)
>>>>>
>>>>> If your system can be decomposed as roughly events cross
>>>>> state, you have a snowball's chance of "understanding" it.
>>>>
>>>> Sorry, I don't know what this means "roughly events cross state".
>>>>
>>>>
>>>
>>> You are in state A. Event 42 occurs. Lookup.... ah, here -
>>> if we get event 42 whilst in state A, we move to state B
>>> and send message m.
>>
>> So what makes that so hard to understand?
> 
> To be more explicit, I think every FSM I've ever coded was along the 
> lines of a case statement on the state with IF conditions on all the 
> interesting inputs.  I find this structure to be self documenting if the 
> signal names are chosen well.
> 
> Why is this structure hard to understand?
> 

I agree with you - but I have been told by others that it is hard to
understand.

-- 
Les Cargill

[toc] | [prev] | [next] | [standalone]

#27498

On 04/01/18 19:31, rickman wrote:
> rickman wrote on 1/4/2018 3:33 AM:
>> Les Cargill wrote on 1/3/2018 6:59 PM:
>>> rickman wrote:
>>>> Les Cargill wrote on 1/3/2018 7:07 AM:
>>>>> rickman wrote:
>>>>>> Ed Prochak wrote on 12/19/2017 11:19 AM:
>>>>>>> On Saturday, December 16, 2017 at 12:56:31 PM UTC-5, Les Cargill wrote:
>>>>>>>> Mike Perkins wrote:
>>>>>>>>> On 09/12/2017 16:05, pozz wrote:
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I use it where I have a number of 'tasks' which then interact with each
>>>>>>>>> other.
>>>>>>>>>
>>>>>>>>> If your system is a pure state machine then there is no need for an
>>>>>>>>> RTOS.
>>>>>>>>>
>>>>>>>>
>>>>>>>> Indeed. Indeed.
>>>>>>>
>>>>>>> If it is just one state machine. Then yes, indeed.
>>>>>>> ed
>>>>>>
>>>>>> It can always be one state machine.  The only issue is how complex the
>>>>>> combined state machine is.
>>>>>>
>>>>>
>>>>> It's always a case of "how long should a man's legs be?" Lincoln
>>>>> is alleged to have said "long enough to touch the ground."
>>>>>
>>>>>> Actually the issue is not how many state machines you have.  It is the
>>>>>> timing requirements of the various state machines.  If your timing is lax,
>>>>>> sequential operation of multiple machines is easy.  But this often becomes
>>>>>> a huge discussion with everyone talking past each other.
>>>>>>
>>>>>
>>>>> They should use state machines to keep track then :)
>>>>>
>>>>> If your system can be decomposed as roughly events cross
>>>>> state, you have a snowball's chance of "understanding" it.
>>>>
>>>> Sorry, I don't know what this means "roughly events cross state".
>>>>
>>>>
>>>
>>> You are in state A. Event 42 occurs. Lookup.... ah, here -
>>> if we get event 42 whilst in state A, we move to state B
>>> and send message m.
>>
>> So what makes that so hard to understand?
>
> To be more explicit, I think every FSM I've ever coded was along the lines of a
> case statement on the state with IF conditions on all the interesting inputs.  I
> find this structure to be self documenting if the signal names are chosen well.
>
> Why is this structure hard to understand?

I've seen a commercial case where that type of structure was
mutated by people under pressure to:
  - have a single state machine for all different customers
  - make the minimum change
  - do it fast
  - where the original designers had left
  - a custom domain specific language, ugh

The result was an unholy unmaintainable mess, with
if-then-elses nested up to 10 (ten!) deep.

Completely insane, of course.

My preference is for a dispatch table based on event+state,
since that forces you to consider all possibilities. The
dispatch table can be either a 2D array of function pointers,
or inherent in an OOP inheritance hierarchy where the
hierarchy is a direct mirror of the state hierarchy.

[toc] | [prev] | [next] | [standalone]

#27507

On 01/05/2018 04:12 AM, Tom Gardner wrote:
> On 04/01/18 19:31, rickman wrote:
>> rickman wrote on 1/4/2018 3:33 AM:
>>> Les Cargill wrote on 1/3/2018 6:59 PM:
>>>> rickman wrote:
>>>>> Les Cargill wrote on 1/3/2018 7:07 AM:
>>>>>> rickman wrote:
>>>>>>> Ed Prochak wrote on 12/19/2017 11:19 AM:
>>>>>>>> On Saturday, December 16, 2017 at 12:56:31 PM UTC-5,
>>>>>>>> Les Cargill wrote:
>>>>>>>>> Mike Perkins wrote:
>>>>>>>>>> On 09/12/2017 16:05, pozz wrote:
>>>>>>>>>>> 
>>>>>>>>>> 
>>>>>>>>>> I use it where I have a number of 'tasks' which
>>>>>>>>>> then interact with each other.
>>>>>>>>>> 
>>>>>>>>>> If your system is a pure state machine then there
>>>>>>>>>> is no need for an RTOS.
>>>>>>>>>> 
>>>>>>>>> 
>>>>>>>>> Indeed. Indeed.
>>>>>>>> 
>>>>>>>> If it is just one state machine. Then yes, indeed. ed
>>>>>>> 
>>>>>>> It can always be one state machine.  The only issue is
>>>>>>> how complex the combined state machine is.
>>>>>>> 
>>>>>> 
>>>>>> It's always a case of "how long should a man's legs be?"
>>>>>> Lincoln is alleged to have said "long enough to touch the
>>>>>> ground."
>>>>>> 
>>>>>>> Actually the issue is not how many state machines you
>>>>>>> have.  It is the timing requirements of the various state
>>>>>>> machines.  If your timing is lax, sequential operation of
>>>>>>> multiple machines is easy.  But this often becomes a huge
>>>>>>> discussion with everyone talking past each other.
>>>>>>> 
>>>>>> 
>>>>>> They should use state machines to keep track then :)
>>>>>> 
>>>>>> If your system can be decomposed as roughly events cross 
>>>>>> state, you have a snowball's chance of "understanding" it.
>>>>> 
>>>>> Sorry, I don't know what this means "roughly events cross
>>>>> state".
>>>>> 
>>>>> 
>>>> 
>>>> You are in state A. Event 42 occurs. Lookup.... ah, here - if
>>>> we get event 42 whilst in state A, we move to state B and send
>>>> message m.
>>> 
>>> So what makes that so hard to understand?
>> 
>> To be more explicit, I think every FSM I've ever coded was along
>> the lines of a case statement on the state with IF conditions on
>> all the interesting inputs.  I find this structure to be self
>> documenting if the signal names are chosen well.
>> 
>> Why is this structure hard to understand?
> 
> I've seen a commercial case where that type of structure was mutated
> by people under pressure to: - have a single state machine for all
> different customers - make the minimum change - do it fast - where
> the original designers had left - a custom domain specific language,
> ugh
> 
> The result was an unholy unmaintainable mess, with if-then-elses
> nested up to 10 (ten!) deep.
> 
> Completely insane, of course.
> 
Yup.
The whole point of state machine design is to avoid that sort of
logic-driven horror.

> My preference is for a dispatch table based on event+state, since
> that forces you to consider all possibilities. The dispatch table can
> be either a 2D array of function pointers, or inherent in an OOP
> inheritance hierarchy where the hierarchy is a direct mirror of the
> state hierarchy.

Cheers

Phil Hobbs

-- 
Dr Philip C D Hobbs
Principal Consultant
ElectroOptical Innovations LLC / Hobbs ElectroOptics
Optics, Electro-optics, Photonics, Analog Electronics
Briarcliff Manor NY 10510

http://electrooptical.net
http://hobbs-eo.com

[toc] | [prev] | [next] | [standalone]

#27508

Tom Gardner wrote:
> On 04/01/18 19:31, rickman wrote:
>> rickman wrote on 1/4/2018 3:33 AM:
>>> Les Cargill wrote on 1/3/2018 6:59 PM:
>>>> rickman wrote:
>>>>> Les Cargill wrote on 1/3/2018 7:07 AM:
>>>>>> rickman wrote:
>>>>>>> Ed Prochak wrote on 12/19/2017 11:19 AM:
>>>>>>>> On Saturday, December 16, 2017 at 12:56:31 PM UTC-5, Les Cargill 
>>>>>>>> wrote:
>>>>>>>>> Mike Perkins wrote:
>>>>>>>>>> On 09/12/2017 16:05, pozz wrote:
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I use it where I have a number of 'tasks' which then interact 
>>>>>>>>>> with each
>>>>>>>>>> other.
>>>>>>>>>>
>>>>>>>>>> If your system is a pure state machine then there is no need 
>>>>>>>>>> for an
>>>>>>>>>> RTOS.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Indeed. Indeed.
>>>>>>>>
>>>>>>>> If it is just one state machine. Then yes, indeed.
>>>>>>>> ed
>>>>>>>
>>>>>>> It can always be one state machine.  The only issue is how 
>>>>>>> complex the
>>>>>>> combined state machine is.
>>>>>>>
>>>>>>
>>>>>> It's always a case of "how long should a man's legs be?" Lincoln
>>>>>> is alleged to have said "long enough to touch the ground."
>>>>>>
>>>>>>> Actually the issue is not how many state machines you have.  It 
>>>>>>> is the
>>>>>>> timing requirements of the various state machines.  If your 
>>>>>>> timing is lax,
>>>>>>> sequential operation of multiple machines is easy.  But this 
>>>>>>> often becomes
>>>>>>> a huge discussion with everyone talking past each other.
>>>>>>>
>>>>>>
>>>>>> They should use state machines to keep track then :)
>>>>>>
>>>>>> If your system can be decomposed as roughly events cross
>>>>>> state, you have a snowball's chance of "understanding" it.
>>>>>
>>>>> Sorry, I don't know what this means "roughly events cross state".
>>>>>
>>>>>
>>>>
>>>> You are in state A. Event 42 occurs. Lookup.... ah, here -
>>>> if we get event 42 whilst in state A, we move to state B
>>>> and send message m.
>>>
>>> So what makes that so hard to understand?
>>
>> To be more explicit, I think every FSM I've ever coded was along the 
>> lines of a
>> case statement on the state with IF conditions on all the interesting 
>> inputs.  I
>> find this structure to be self documenting if the signal names are 
>> chosen well.
>>
>> Why is this structure hard to understand?
> 
> I've seen a commercial case where that type of structure was
> mutated by people under pressure to:
>   - have a single state machine for all different customers
>   - make the minimum change
>   - do it fast
>   - where the original designers had left
>   - a custom domain specific language, ugh
> 
> The result was an unholy unmaintainable mess, with
> if-then-elses nested up to 10 (ten!) deep.
> 

Eh, doing it totally, totally wrong. With all due respect - you really
need a configuration system managed well within the code itself, and
customer specializations are but different settings.

On one product, the "model number' was nothing more than a name
that pointed to a hard table of defaults for the configuration,
and further config changes were possible. If the support
people requested it, we'd grow a model number when they got too painful.

That being said - OO and configuration go together like chalk and cheese
:)

> Completely insane, of course.
> 


Well, yeah. You can make anything disgusting
if you work hard enough :)

> My preference is for a dispatch table based on event+state,
> since that forces you to consider all possibilities. 

Yup yup. And you can generate a test vector for it with combinators.
Then testing essentially becomes compressing the output - tedious, but
... rewarding.

If the tested FSM is properly tested, then all remaining
defects are 1) either tweak/tone of unrealistic expectations or
2) hardware bugs.

> The
> dispatch table can be either a 2D array of function pointers,
> or inherent in an OOP inheritance hierarchy where the
> hierarchy is a direct mirror of the state hierarchy.


There's something to be said for the 2d approach. It's
more canonical ( and more normal ) for one.

-- 
Les Cargill

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | comp.arch.embedded

csiph-web