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

On 06/01/18 22:37, Les Cargill wrote:
> Tom Gardner wrote:
>> On 06/01/18 03:29, Les Cargill wrote:
>>> Tom Gardner wrote:
>>>> 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.
>>
>> Unfortunately you can't test FSMs "properly", for my
>> definition of "properly" :) That's based on the
>> unfashionable and inconvenient concept that "you
>> can't test quality into a product".
>>
>
> Wait; you *can* do proofs on FSMs.

In theory yes, in practice combinatorial explosion
is a problem. I well remember (c 1990) a neighbouring
group being very pleased they had been able to prove
some FSMs lock free.

We showed them the FSMs from the networking protocol
for the LANs we were developing; they gulped and went
silent :) I strongly suspect the same would have been
true for the telecom protocols I used 20 years later.


> "Quality" is
> sufficiently nebulous and subjective to be a
> not-a-thing.
>
>> For the systems I've designed, there's a lot to
>> be gained by keeping a compressed log of "state
>> trajectory" around until not needed.
>
>
> Yep yep....
>
>> That plus
>> accurate timestamping of events to/from external
>> systems has enabled me to quickly and unambiguously
>> deflect blame away from my stuff and onto other
>> companies. The lawyers were never even called :)
>>
>
> Exactly. Precisely even that.

It is really pleasant to be able to smile sweetly
at rabid XP/Agile/YAGNI dogmatists, and say "see, we
/did/ need that" :)

(For the avoidance of doubt, XP/Agile can be very
valuable techniques when tastefully deployed
alongside other techniques)

On 07/01/18 00:06, rickman wrote:
> Tom Gardner wrote on 1/6/2018 4:17 AM:
>> On 06/01/18 03:29, Les Cargill wrote:
>>> Tom Gardner wrote:
>>>> 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.
>>
>> Unfortunately you can't test FSMs "properly", for my definition of
>> "properly" :) That's based on the unfashionable and inconvenient concept
>> that "you can't test quality into a product".
>
> FSM is one of the things where this isn't true.  You can set up a unit test
> that exhaustively tests all possible combinations of inputs and states to
> verify the machine matches the specification.

Not for many of the FSMs I've had to deal with. I've
watched some people making that claim look at such FSMs,
gulp, and become very quiet.

On 06/01/18 23:57, rickman wrote:
> Tom Gardner wrote on 1/5/2018 4:12 AM:
>> 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.
>
> Bad code can be written by any method.

And some methods help writing good code, and
some hinder writing good code.

What's your next motherhood and apple pie statement?

Tom Gardner <spamjunk@blueyonder.co.uk> writes:
> In theory yes, in practice combinatorial explosion is a problem. I
> well remember (c 1990) a neighbouring group being very pleased they
> had been able to prove some FSMs lock free.

It's still not trivial but things have improved a lot since the 1990s
(https://techpolicy.acm.org/?p=572):

  A drawback of the Model Checking approach, known as the state-explosion
  problem, seemed to limit its applicability to small designs of mainly
  academic interest. Randal Bryant, Edmund Clarke, Allen Emerson and
  Kenneth McMillan invented Symbolic Model Checking, which greatly
  extended the size and complexity of systems that could be verified. It
  also led to the widespread adoption of Model Checking by the computer
  hardware industry. For this invention, Bryant, Clarke, Emerson, and
  McMillan received the 1998 Paris Kanellakis Award for Theory and
  Practice from ACM. In 1999, they also received the Allen Newell Award
  for Research Excellence from Carnegie Mellon University. Sifakis,
  together with Thomas A. Henzinger and Sergio Yovine, extended the Model
  Checking approach to address verification of real time systems. In 2001,
  Sifakis received the Centre National de la Recherche Scientifique Silver
  Medal.

On 06/01/18 22:49, Les Cargill wrote:
> upsidedown@downunder.com wrote:
>> However, I do _not_ think that the xCore would be very handy for ad hoc
>> parallel processing, even with XMOS programming environment (which is quite
>> versatile).
>>
>
> It seems like total overkill for SCADA in general.

Only in the sense that all fast processors, HLLs and
dev environments are overkill. Usually the determining
factors are cost and industrial inertia.

(When I returned to hardware/embedded after a gap
of 20 years, I was horrified at how little had
changed).


> I don't know if it means
> you can have GPP solutions that compete with ASICs ( I seriously doubt it )
> but the economics of ASICs have gone mad anyway :)

xCore has hard realtime "FPGA-like" i/o port structures, e.g.
  - per i/o port clocks down to a 4ns resolution (250MHz)
  - SERDES
  - timers for each i/o port
  - read inputs at a specific future clock cycle
  - capture time at which an input occurred
  - specify time at which the next output will occur
  - i/o "events" and messages latency of 10ns

The xC language and processor architecture also allow
hard realtime guarantees to be made by the IDE without
executing code. The IDE examines the (optimised) object
code emitted by the LLVM compiler, and calculates the
min/max timings from the call-flow graph.

IMNSHO they do eat into FPGA territory in ways that
other processors and languages simply cannot: /hard/
realtime /guarantees/, low latency, and multiprocessing.

They will not, of course, replace FPGAs. Nonetheless
in some cases they are a very viable alternative.
Given the impressive investments from many external
companies over the past decade, others agree :)

People that have a deep personal interest in FPGAs
will likely resist that, of course :)

On 07/01/18 01:31, Paul Rubin wrote:
> Tom Gardner <spamjunk@blueyonder.co.uk> writes:
>> In theory yes, in practice combinatorial explosion is a problem. I
>> well remember (c 1990) a neighbouring group being very pleased they
>> had been able to prove some FSMs lock free.
>
> It's still not trivial but things have improved a lot since the 1990s
> (https://techpolicy.acm.org/?p=572):
>
>   A drawback of the Model Checking approach, known as the state-explosion
>   problem, seemed to limit its applicability to small designs of mainly
>   academic interest. Randal Bryant, Edmund Clarke, Allen Emerson and
>   Kenneth McMillan invented Symbolic Model Checking, which greatly
>   extended the size and complexity of systems that could be verified. It
>   also led to the widespread adoption of Model Checking by the computer
>   hardware industry. For this invention, Bryant, Clarke, Emerson, and
>   McMillan received the 1998 Paris Kanellakis Award for Theory and
>   Practice from ACM. In 1999, they also received the Allen Newell Award
>   for Research Excellence from Carnegie Mellon University. Sifakis,
>   together with Thomas A. Henzinger and Sergio Yovine, extended the Model
>   Checking approach to address verification of real time systems. In 2001,
>   Sifakis received the Centre National de la Recherche Scientifique Silver
>   Medal.

Well I certainly hope that's the case, but he
formal methods crowd has a tendency to underestimate
the complexity of practical FSM!

Hence I'd like to see some independent assessment
on some _existing_ real-world protocols/FSMs. Failing
that, how do their techniques perform when developing
_new_ protocols/FSMs? If they are generally a help,
then that would be great!

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

Paul Rubin wrote on 1/6/2018 7:58 PM:
> rickman <gnuarm.deletethisbit@gmail.com> writes:
>> FSM is one of the things where this isn't true.  You can set up a unit
>> test that exhaustively tests all possible combinations of inputs and
>> states to verify the machine matches the specification.
>
> You can't exhaustively test all the combinations because there's an
> infinite set of possible input event sequences.  Your spec might
> require, say, that no possible sequence of events can move the FSM from
> state A to state B without passing through state C in between.  At the
> higher level, that could mean that you can't fire the missiles without
> releasing the safety.

Of course that can be proven.  Why do you think it can't?  If a set of 
inputs returns you to a state you have already tested, you don't need to 
continue testing any further.  The definition of a FSM says its universe 
consists of inputs and states.  Test every state for every input and verify 
it goes to the appropriate state.

In your example you only need to test state A for every possible input to 
verify it doesn't go to state B.  Or if there are other states, you simply 
need to verify there are two sets of states, those that let you get to state 
B and those that let you get to state C.  Show that state A is in the latter 
and you are done.  You don't need to consider infinitely long sequences 
because it is a FINITE state machine.

-- 

Rick C

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

Tom Gardner wrote on 1/6/2018 8:17 PM:
> On 06/01/18 23:57, rickman wrote:
>> Tom Gardner wrote on 1/5/2018 4:12 AM:
>>> 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.
>>
>> Bad code can be written by any method.
>
> And some methods help writing good code, and
> some hinder writing good code.
>
> What's your next motherhood and apple pie statement?

What is your next pointless anecdote?  There are many examples of work going 
well and work going poorly.  What is the point of any one example?  A method 
is only as good as those using it.

-- 

Rick C

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

Tom Gardner <spamjunk@blueyonder.co.uk> writes:
> Hence I'd like to see some independent assessment on some _existing_
> real-world protocols/FSMs.

I don't know where to find any of those.  Got any suggestions?

> Failing that, how do their techniques perform when developing _new_
> protocols/FSMs? If they are generally a help, then that would be
> great!

I'd be interested to know what you think of ImProve.  The link I gave
earlier:

  https://github.com/tomahawkins/improve/wiki/ImProve

I'd look at the "verification primer" section to get an idea of what it
does.  Don't worry about understanding the syntax etc, which takes some
getting used to.

The basic approach is to control the state space explosion using a SAT
solver.  Those have gotten very powerful in recent years.  They might
get even more powerful with reinforcement learning techniques soon.