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

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.

Les Cargill <lcargill99@comcast.com> writes:
> Not... necessarily. If the complexity means it's never
> truly finished, then yes.

I thought the saying was that software is never truly finished until the
last user is dead ;-).

> Well, I think we should all strive for that regardless. IMO, it doesn't
> cost more to do things in a rigorous and careful way. I'd point you
> to the writings of Bruce Powell-Douglas.

I've started to look at some, thanks.  He writes mostly about critical
real-time systems, a niche area which is of course of special interest
to c.a.e. (and to me).  I can accept that some of those programs must
have zero bugs, and accomplishing that requires special, ultra-rigorous
methods and tools.  But, I'd also say, that puts an upper limit on the
complexity of the things that the software can attempt to do.

Other types of software must deal more directly with the real world,
which requires accomodating the unbounded complexity of the real world,
which in turn puts more complexity into the software than a pure formal
approach can handle.  That may prevent the software from getting the
last epsilon of reliability, but that's ok, the real world isn't 100%
reliable either.

Joe Armstrong likes to say that any non-distributed system is inherently
unreliable, because the power cord is a single point of failure.  Most
of the programs that most of us write run on computers with a single
power cord, so they can also withstand software practices that wouldn't
suffice for critical realtime systems, but that can handle more types of
real-world requirements.

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.

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 :)

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?

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.

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

Tom Gardner wrote on 1/7/2018 6:32 PM:
> On 07/01/18 21:41, Paul Rubin 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.
>
> You appear to have a very limited definition of what constitutes
> an FSM. "Business code" often /is/ an FSM, even if it doesn't use
> some specific implementation techniques.

*EVERYTHING* on a computer is a FSM as a computer is a FSM.  What's your point?

-- 

Rick C

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

On 10/01/18 15:33, rickman wrote:
> Tom Gardner wrote on 1/7/2018 6:32 PM:
>> On 07/01/18 21:41, Paul Rubin 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.
>>
>> You appear to have a very limited definition of what constitutes
>> an FSM. "Business code" often /is/ an FSM, even if it doesn't use
>> some specific implementation techniques.
>
> *EVERYTHING* on a computer is a FSM as a computer is a FSM.  What's your point?

Read the context in which I made the statement, especially
the comments by Mr Rubin.

Paul Rubin wrote on 1/7/2018 1:53 PM:
> rickman <gnuarm.deletethisbit@gmail.com> writes:
>> There is *no* infinity is finite state machines.  Not input sequence
>> lengths or input sequence combinations.
>
> There are infinitely many sequences of inputs.

Which is irrelevant.  There are also infinitely long times, again irrelevant.


> Of course since it's an
> FSM, you end up getting repeated states.  For example, consider the
> event sequence [A,B].  Then consider [A,A,B].  Then [A,A,A,B].  Then
> [A,A,A,A,B], etc.  There are infinitely many such sequences.  Obviously
> after a while they will start repeating states, and you can analyze that
> example since every transition except the last one is on event A.

I don't follow your logic.  I don't care about the extent of the input 
sequence.  The machine only responds to the combination of the current input 
and current state.  The previous inputs at any given time are not relevant 
just as subsequent inputs are not relevant at this time.  All appropriate 
analysis can be done by considering a finite sequence that exercises the 
finite limits of the machine.

Any infinite sequence will result in repetition of tests that have already 
been performed.


> The problem happens when there's multiple transitions from each state,
> so you have to consider all the combinations [A,C], [B,C], [A,A,C],
> [A,B,C], [B,A,C], [B,B,C], etc.  The number of such combinations is
> exponential in the number of states.  And the state space itself can be
> exponentially large.  E.g. if a straightforward code implementation of
> something involves a 3-bit retry counter, you need 8 states to handle
> all the possible counts, maybe ok.  But if it's a 64-bit packet size
> counter, the number of states required is ridiculous.

I again refer you to the earlier statements regarding the relevance of 
current input and current state.


>> I can count all possible combinations of inputs and states which is
>> why it is a *finite* state machine.
>
> We're talking about what you can do in practice on a real computer, not
> whether something is mathematically finite.  Can you count to 1000?
> Sure.  To a million?  Maybe.  To a googol (1e100)?  I don't think so,
> even though a googol is finite.

Irrelevant.


>> Hmmm... clearly you don't understand the nature of the infinite.
>> Integers *are* infinite.
>
> I am always willing to learn.  I'd be interested in seeing an example of
> an infinite integer.

"An infinite integer"?  The range of integers are infinite.

-- 

Rick C

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