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

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

C++ threads versus PThreads for embedded Linux on ARM micro

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

Contents

  C++ threads versus PThreads for embedded Linux on ARM micro "gp.kiwi@gmail.com" <graeme.prentice@gmail.com> - 2018-07-20 04:01 -0700
    Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-07-20 20:19 +0200
      Re: C++ threads versus PThreads for embedded Linux on ARM micro graeme.prentice@gmail.com - 2018-07-20 15:54 -0700
        Re: C++ threads versus PThreads for embedded Linux on ARM micro Paul Rubin <no.email@nospam.invalid> - 2018-07-20 18:27 -0700
          Re: C++ threads versus PThreads for embedded Linux on ARM micro graeme.prentice@gmail.com - 2018-07-20 23:58 -0700
            Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-07-21 14:32 +0200
              Re: C++ threads versus PThreads for embedded Linux on ARM micro mac <acolvin@efunct.com> - 2018-07-26 19:37 +0000
            Re: C++ threads versus PThreads for embedded Linux on ARM micro Tauno Voipio <tauno.voipio@notused.fi.invalid> - 2018-07-21 21:48 +0300
            Re: C++ threads versus PThreads for embedded Linux on ARM micro Rob Gaddi <rgaddi@highlandtechnology.invalid> - 2018-07-23 09:58 -0700
    Re: C++ threads versus PThreads for embedded Linux on ARM micro Les Cargill <lcargill99@comcast.com> - 2018-07-22 13:15 -0500
    Re: C++ threads versus PThreads for embedded Linux on ARM micro StateMachineCOM <statemachineguru@gmail.com> - 2018-07-27 08:51 -0700
      Re: C++ threads versus PThreads for embedded Linux on ARM micro "gp.kiwi@gmail.com" <graeme.prentice@gmail.com> - 2018-07-27 14:53 -0700
        Re: C++ threads versus PThreads for embedded Linux on ARM micro Paul Rubin <no.email@nospam.invalid> - 2018-07-27 15:23 -0700
        Re: C++ threads versus PThreads for embedded Linux on ARM micro StateMachineCOM <statemachineguru@gmail.com> - 2018-07-30 09:08 -0700
        Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-07-31 09:21 +0200
      Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-07-31 09:13 +0200
        Re: C++ threads versus PThreads for embedded Linux on ARM micro StateMachineCOM <statemachineguru@gmail.com> - 2018-07-31 15:16 -0700
          Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-01 07:53 +0200
          Re: C++ threads versus PThreads for embedded Linux on ARM micro pozz <pozzugno@gmail.com> - 2018-08-01 15:49 +0200
          Re: C++ threads versus PThreads for embedded Linux on ARM micro upsidedown@downunder.com - 2018-08-01 21:47 +0300
            Re: C++ threads versus PThreads for embedded Linux on ARM micro StateMachineCOM <statemachineguru@gmail.com> - 2018-08-01 12:11 -0700
              Re: C++ threads versus PThreads for embedded Linux on ARM micro Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-08-01 20:23 +0100
              Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-02 12:24 +0200
                Re: C++ threads versus PThreads for embedded Linux on ARM micro upsidedown@downunder.com - 2018-08-02 16:14 +0300
                  Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-02 16:43 +0200
                    Re: C++ threads versus PThreads for embedded Linux on ARM micro StateMachineCOM <statemachineguru@gmail.com> - 2018-08-02 09:12 -0700
                      Re: C++ threads versus PThreads for embedded Linux on ARM micro Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-08-02 18:13 +0100
                      Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-02 23:05 +0200
                        Re: C++ threads versus PThreads for embedded Linux on ARM micro StateMachineCOM <statemachineguru@gmail.com> - 2018-08-02 14:22 -0700
                          Re: C++ threads versus PThreads for embedded Linux on ARM micro Niklas Holsti <niklas.holsti@tidorum.invalid> - 2018-08-03 10:14 +0300
                          Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-03 10:22 +0200
                      Re: C++ threads versus PThreads for embedded Linux on ARM micro Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-08-02 23:48 +0100
                    Re: C++ threads versus PThreads for embedded Linux on ARM micro upsidedown@downunder.com - 2018-08-02 19:56 +0300
                      Re: C++ threads versus PThreads for embedded Linux on ARM micro Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-08-02 18:14 +0100
                        Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-02 23:12 +0200
                          Re: C++ threads versus PThreads for embedded Linux on ARM micro Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-08-02 23:52 +0100
                            Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-03 10:28 +0200
                              Re: C++ threads versus PThreads for embedded Linux on ARM micro Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-08-03 11:21 +0100
                                Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-03 13:51 +0200
                          Re: C++ threads versus PThreads for embedded Linux on ARM micro upsidedown@downunder.com - 2018-08-03 09:11 +0300
                        Re: C++ threads versus PThreads for embedded Linux on ARM micro George Neuner <gneuner2@comcast.net> - 2018-08-04 03:00 -0400
                  Re: C++ threads versus PThreads for embedded Linux on ARM micro Robert Wessel <robertwessel2@yahoo.com> - 2018-08-02 12:23 -0500
                    Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-02 23:13 +0200
                      Re: C++ threads versus PThreads for embedded Linux on ARM micro George Neuner <gneuner2@comcast.net> - 2018-08-04 03:08 -0400
                Re: C++ threads versus PThreads for embedded Linux on ARM micro Robert Wessel <robertwessel2@yahoo.com> - 2018-08-02 12:23 -0500
                Re: C++ threads versus PThreads for embedded Linux on ARM micro George Neuner <gneuner2@comcast.net> - 2018-08-02 14:15 -0400
                  Re: C++ threads versus PThreads for embedded Linux on ARM micro Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-08-02 19:21 +0100
                    Re: C++ threads versus PThreads for embedded Linux on ARM micro David Brown <david.brown@hesbynett.no> - 2018-08-02 23:18 +0200
                      Re: C++ threads versus PThreads for embedded Linux on ARM micro Tom Gardner <spamjunk@blueyonder.co.uk> - 2018-08-03 00:02 +0100
            Re: C++ threads versus PThreads for embedded Linux on ARM micro StateMachineCOM <statemachineguru@gmail.com> - 2018-08-01 12:28 -0700

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

#27905

On Wednesday, August 1, 2018 at 2:46:08 PM UTC-4, upsid...@downunder.com wrote:
> It seems Cummings has reinvented the wheel :-). Those principles were used already in the 1970's to implement real time systems under RSX-11 on PDP-11. Later on these principles were also used on real time systems under RMX-80 for 8080 and similar kernels.

I recommended Cummings's article only because most of the participants of this discussion seem to be firmly in the "sequential programming with sharing and blocking" camp. For this traditional way of thinking, the full immersion into the reactive programming principles might be too big of a shock. Cummings arrives at these principles by trial-and-error, intuition, and experience. He also does not call the concepts by strange names like "active object (actor) pattern" or "reactive programming".

But, yes, absolutely. The various pieces of reactive programming are being re-invented all the time. For example, even in this discussion, people recommended using heavyweight processes instead of lightweight threads. This recommendation is valuable, because it addresses two of the best practices: true encapsulation for concurrency and message-driven communication and synchronization. Heavyweight processes run in separate address spaces, which makes sharing of resources hard and the only ways of communication are pipes or sockets.

But the main point is that we don't need to re-invent this wheel anymore. The best practices of concurrent programming have been well known for decades (e.g., the "Real-Time Object Oriented Modeling (ROOM)" book was published in 1994). The most amazing thing is that the principles are so little known and are still being questioned and dismissed.

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

#27906

On 01/08/18 20:11, StateMachineCOM wrote:

> But the main point is that we don't need to re-invent this wheel anymore. The
> best practices of concurrent programming have been well known for decades
> (e.g., the "Real-Time Object Oriented Modeling (ROOM)" book was published in
> 1994). The most amazing thing is that the principles are so little known and
> are still being questioned and dismissed.

Yes, and many people had independently come to the same conclusion
much earlier than that!

There was once an observation that C/C++ papers/publications
tended to refer only to other C/C++ papers/publications, whereas
those for other languages tended to refer to many different
languages/environments. An implication is that there is a
tendency for C/C++ practitioners to reinvent wheels.

I certainly noticed the phenomenon when I read Gosling's Java
whitepaper. He repeatedly said X has been proven in M,N, and
Y has been proven in P, and X and Y work together harmoniously.

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

#27908

On 01/08/18 21:11, StateMachineCOM wrote:
> On Wednesday, August 1, 2018 at 2:46:08 PM UTC-4,
> upsid...@downunder.com wrote:
>> It seems Cummings has reinvented the wheel :-). Those principles
>> were used already in the 1970's to implement real time systems
>> under RSX-11 on PDP-11. Later on these principles were also used on
>> real time systems under RMX-80 for 8080 and similar kernels.
> 
> I recommended Cummings's article only because most of the
> participants of this discussion seem to be firmly in the "sequential
> programming with sharing and blocking" camp. 

I can't speak for anyone else in this discussion, but I am in the
"Sequential programming with sharing and blocking is /one/ way to handle
things, but not the only way.  Indeed, there /is/ no single right way" camp.

> For this traditional way
> of thinking, the full immersion into the reactive programming
> principles might be too big of a shock. Cummings arrives at these
> principles by trial-and-error, intuition, and experience. He also
> does not call the concepts by strange names like "active object
> (actor) pattern" or "reactive programming".

He also gets something /seriously/ wrong.  His model of "a typical
thread" on page 4 is completely incorrect - and his whole argument
breaks down because of that.

/Some/ threads are event driven services - they wait for messages coming
in, process them, and then go back to waiting for another message.  This
is basically a cooperative multi-tasking system - the sort of thing we
had to use before multi-threading and multi-tasking OS's were suitable
for small embedded systems.  (It's also what we had in Windows for long
/after/ every other "big" OS was multi-tasking.)

Threads like that can be a very useful structure, and can be very
efficient ways to model certain types of problem.  They are excellent
for handling user interaction, and are thus very popular for the main
thread in gui programs on desktops.  They are also marvellous as pretty
much the only thread (baring perhaps timers and interrupts) on many
embedded systems - in particular, you know that when the thread is in
the "Process message 1" part, it can't be in the "Process message 2"
part, and thus you can avoid a great deal of locking or other
synchronisation.

But a key point is that a thread like that should avoid (or at least
minimise) any blocking or locking, and usually it should avoid any code
that takes a long time to run (possibly by breaking it up, using a state
machine).


Other threads can have completely different structures.  In particular,
they /can/ have blocking operations because it is fine for them to block
- the blocking operations are part of the normal flow of the sequential
processes that are clear in the code and easy to track.  That might mean
you have more threads than you would otherwise need, and a corresponding
loss in overall system efficiency, but that is the price you pay for
better modularisation and clearer code flow.  And you can have a range
of different types of synchronisation - using whatever makes the best
balance between efficiency, clear coding, and provably correct
synchronisation (i.e., you can be absolutely sure you have no deadlocks,
livelocks, etc.).


The "problem" described on pages 5-6 of the article stem from two errors
by the author.  One is to mix up the structures and responsibilities of
the threads - he has thread A being an event-driven service thread that
uses significant blocking in part of its processing.  The second problem
is that he has no clear picture of the control flow and the interaction
between threads, resulting in circular dependencies.  If you want an
efficient (and, for hard real time, correct) multi-threaded system you
have to know what your threads are, how they communicate, who waits for
what, and what deadlines you have - and arrange things so that you don't
have unnecessary waits.

The variety of incorrect "solutions" then given are clearly problematic,
as he says - but he misses the obvious one which is to restructure the
threading and communication.  For example, a better solution might be to
introduce a new thread C whose job is to handle the work currently done
in thread A in response to message 1.  Thread A's handling of message 1
thus becomes "trigger thread C", and all the work - including blocking
if that is the most convenient solution - is done in thread C.  Thread A
can go back to handling events.  But for some reason, the author (and
many other authors on such topics, IME) does not think of adding another
thread.

He also discusses the idea of the call to thread B being essentially
non-blocking, and with B sending its response as a message back to A.
But for some reason he says that should be a different message queue
that A would block on, giving the same problem but with a far more
complex structure - I can't see why anyone would suggest that as a
possible solution.  The response from B should either go into the main
event queue for A (perhaps this queue would need to be prioritised), or
(if the OS has the support) it could go in a separate queue with A
waiting for /either/ queue, maybe with a priority mechanism.

He is right in noting the dangers of using callbacks as a solution, as
they are logically in the domain of one thread but executed in the
context of another thread.  The answer here is that callbacks need to be
short, deterministic, thread-safe and do as little as possible.  Still,
many of the potential problems he sees are due to poorly structured
threading and coding.  For example, he says:

"Additional challenges can arise if, for example, Thread A is in the
middle of processing a large collection of data when the callback
executes, and if the response from B includes an update to a portion of
that collection of data."

Proper structuring of responsibilities and encapsulation of the data and
code acting on it would mean that is not allowed - or that it can be
done in such a simple atomic way that there is no problem.


Really, most or all of the problems he sees could be solved by saying
"/Design/ your multi-threaded system carefully, and don't be afraid of
splitting tasks into new threads" rather coding first and thinking
later, programming by trial and error, and using hacks instead of
re-structuring as needed.


His solution to restructure all threads to wait on multiple queues is
certainly one possibility, and can be the "best" for some problems.  But
it is not without its significant costs in complexity, especially if you
assume it is the /only/ way to structure your threads.  He helpfully
gives some examples of these.  But then he says "Confronting such
complications is what often motivates people to take shortcuts. In-line
blocking, for example...".  No, confronting such complications is what
should motivate people to realise this is not "one size fits all", and
there are better ways to handle the problem than shoe-horning everything
into your favourite fad model.

Exchanging your toolbox full of hammers for a toolbox full of
screwdrivers does not make for good software development.

> 
> But, yes, absolutely. The various pieces of reactive programming are
> being re-invented all the time. For example, even in this discussion,
> people recommended using heavyweight processes instead of lightweight
> threads. This recommendation is valuable, because it addresses two of
> the best practices: true encapsulation for concurrency and
> message-driven communication and synchronization. Heavyweight
> processes run in separate address spaces, which makes sharing of
> resources hard and the only ways of communication are pipes or
> sockets.

Pipes and sockets are most certainly /not/ the only way of communicating
between processes - there are about a dozen other methods, depending on
details of the OS.  But certainly the stricter separation between
processes, compared to threads, means you use more heavyweight
synchronisation and communication mechanisms, you are less likely to
"cheat", and you are more likely to have a clear modularisation and
separation of tasks.  The cost, of course, is more overheads and lower
efficiency on a small system.

> 
> But the main point is that we don't need to re-invent this wheel
> anymore. The best practices of concurrent programming have been well
> known for decades (e.g., the "Real-Time Object Oriented Modeling
> (ROOM)" book was published in 1994). The most amazing thing is that
> the principles are so little known and are still being questioned and
> dismissed.
> 

The most amazing thing to me is that so many people think they know the
"best" method.

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

#27909

On Thu, 02 Aug 2018 12:24:49 +0200, David Brown
<david.brown@hesbynett.no> wrote:

>On 01/08/18 21:11, StateMachineCOM wrote:
>> On Wednesday, August 1, 2018 at 2:46:08 PM UTC-4,
>> upsid...@downunder.com wrote:
>>> It seems Cummings has reinvented the wheel :-). Those principles
>>> were used already in the 1970's to implement real time systems
>>> under RSX-11 on PDP-11. Later on these principles were also used on
>>> real time systems under RMX-80 for 8080 and similar kernels.
>> 
>> I recommended Cummings's article only because most of the
>> participants of this discussion seem to be firmly in the "sequential
>> programming with sharing and blocking" camp. 
>
>I can't speak for anyone else in this discussion, but I am in the
>"Sequential programming with sharing and blocking is /one/ way to handle
>things, but not the only way.  Indeed, there /is/ no single right way" camp.
>
>> For this traditional way
>> of thinking, the full immersion into the reactive programming
>> principles might be too big of a shock. Cummings arrives at these
>> principles by trial-and-error, intuition, and experience. He also
>> does not call the concepts by strange names like "active object
>> (actor) pattern" or "reactive programming".
>
>He also gets something /seriously/ wrong.  His model of "a typical
>thread" on page 4 is completely incorrect - and his whole argument
>breaks down because of that.

The method just describes how real time (i.e. with upper limit for
execution time) is usually done. Most (often over 99 %) of the time
each thread/task/process is in the wait state waiting for an event,
(such as message queue, event flag etc. depending of implementation).
When an external event, such as serial line or clock interrupt occurs,
some task is activated, possibly sending messages etc. to other task.
When done, each task returns to the wait state. Usually there are only
one runnable task at a time. If more tasks become runnable at the same
time, they are executed in priority order. Very nice and clean.

>
>/Some/ threads are event driven services - they wait for messages coming
>in, process them, and then go back to waiting for another message.  This
>is basically a cooperative multi-tasking system - the sort of thing we
>had to use before multi-threading and multi-tasking OS's were suitable
>for small embedded systems.  (It's also what we had in Windows for long
>/after/ every other "big" OS was multi-tasking.)

Windows NT 3.5 and later on was a full blown priority based
multitasking system with close resemblance to RSX-11 and VMS.

Processor capabilities is no excuse for not having priority based
multitasking. In the 1970/80's  practically every company using 8
bitters had their own RT kernels. The Intel RMX-80 for 8080/85 might
be familiar to some in this NG.
  
>
>Threads like that can be a very useful structure, and can be very
>efficient ways to model certain types of problem.  They are excellent
>for handling user interaction, and are thus very popular for the main
>thread in gui programs on desktops.  

I  usually put the (l)user interface in the null task (lowest priority
task), so whatever the user does, it doesn't affect the really
important parts of the system.

>They are also marvellous as pretty
>much the only thread (baring perhaps timers and interrupts) on many
>embedded systems - in particular, you know that when the thread is in
>the "Process message 1" part, it can't be in the "Process message 2"
>part, and thus you can avoid a great deal of locking or other
>synchronisation.
>
>But a key point is that a thread like that should avoid (or at least
>minimise) any blocking or locking, and usually it should avoid any code
>that takes a long time to run (possibly by breaking it up, using a state
>machine).

Think about the various cases as interrupt service routines. Compare
this with a multiline serial card with a single interrupt. You first
determine which subsystem caused the interrupt and handle it
accordingly. Of cause, the ISR should be then handled quickly as
should the various message processing. The return from interrupt is
then comparable to go to the loop wait state.

>
>
>Other threads can have completely different structures.  In particular,
>they /can/ have blocking operations because it is fine for them to block
>- the blocking operations are part of the normal flow of the sequential
>processes that are clear in the code and easy to track.  

If you need complicated sequential processing, such as in the (l)user
interface, put it into the null task.

>That might mean
>you have more threads than you would otherwise need, and a corresponding
>loss in overall system efficiency, but that is the price you pay for
>better modularisation and clearer code flow.  And you can have a range
>of different types of synchronisation - using whatever makes the best
>balance between efficiency, clear coding, and provably correct
>synchronisation (i.e., you can be absolutely sure you have no deadlocks,
>livelocks, etc.).
>
>
>The "problem" described on pages 5-6 of the article stem from two errors
>by the author.  

Yes, this is "self inflicted headache" (hangover) :-=

>One is to mix up the structures and responsibilities of
>the threads - he has thread A being an event-driven service thread that
>uses significant blocking in part of its processing.  The second problem
>is that he has no clear picture of the control flow and the interaction
>between threads, resulting in circular dependencies.  If you want an
>efficient (and, for hard real time, correct) multi-threaded system you
>have to know what your threads are, how they communicate, who waits for
>what, and what deadlines you have - and arrange things so that you don't
>have unnecessary waits.
>
>The variety of incorrect "solutions" then given are clearly problematic,
>as he says - but he misses the obvious one which is to restructure the
>threading and communication.  For example, a better solution might be to
>introduce a new thread C whose job is to handle the work currently done
>in thread A in response to message 1.  Thread A's handling of message 1
>thus becomes "trigger thread C", and all the work - including blocking
>if that is the most convenient solution - is done in thread C.  Thread A
>can go back to handling events.  But for some reason, the author (and
>many other authors on such topics, IME) does not think of adding another
>thread.
>
>He also discusses the idea of the call to thread B being essentially
>non-blocking, and with B sending its response as a message back to A.
>But for some reason he says that should be a different message queue

I also wondered why.

>
>that A would block on, giving the same problem but with a far more
>complex structure - I can't see why anyone would suggest that as a
>possible solution.  The response from B should either go into the main
>event queue for A (perhaps this queue would need to be prioritised), or
>(if the OS has the support) it could go in a separate queue with A
>waiting for /either/ queue, maybe with a priority mechanism.

What is the point of having a queue priority, if there is already a
state machine for Msg1 processing ?

>
>He is right in noting the dangers of using callbacks as a solution, as
>they are logically in the domain of one thread but executed in the
>context of another thread. 

Callback from some system service makes sense (i.e. translated
interrupts), but I have seldom seen callbacks from one application to
an other.

> The answer here is that callbacks need to be
>short, deterministic, thread-safe and do as little as possible.  Still,
>many of the potential problems he sees are due to poorly structured
>threading and coding.  For example, he says:
>
>"Additional challenges can arise if, for example, Thread A is in the
>middle of processing a large collection of data when the callback
>executes, and if the response from B includes an update to a portion of
>that collection of data."
>
>Proper structuring of responsibilities and encapsulation of the data and
>code acting on it would mean that is not allowed - or that it can be
>done in such a simple atomic way that there is no problem.
>
>
>Really, most or all of the problems he sees could be solved by saying
>"/Design/ your multi-threaded system carefully, and don't be afraid of
>splitting tasks into new threads" rather coding first and thinking
>later, programming by trial and error, and using hacks instead of
>re-structuring as needed.

I use to limit the number of different tasks to 10, so that I can keep
track of them with my fingers. Using more than that, would also
require me to use my toes and my colleges might not appreciate, if I
took off my socks  :-)

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

#27910

On 02/08/18 15:14, upsidedown@downunder.com wrote:
> On Thu, 02 Aug 2018 12:24:49 +0200, David Brown
> <david.brown@hesbynett.no> wrote:
> 
>> On 01/08/18 21:11, StateMachineCOM wrote:
>>> On Wednesday, August 1, 2018 at 2:46:08 PM UTC-4,
>>> upsid...@downunder.com wrote:
>>>> It seems Cummings has reinvented the wheel :-). Those principles
>>>> were used already in the 1970's to implement real time systems
>>>> under RSX-11 on PDP-11. Later on these principles were also used on
>>>> real time systems under RMX-80 for 8080 and similar kernels.
>>>
>>> I recommended Cummings's article only because most of the
>>> participants of this discussion seem to be firmly in the "sequential
>>> programming with sharing and blocking" camp. 
>>
>> I can't speak for anyone else in this discussion, but I am in the
>> "Sequential programming with sharing and blocking is /one/ way to handle
>> things, but not the only way.  Indeed, there /is/ no single right way" camp.
>>
>>> For this traditional way
>>> of thinking, the full immersion into the reactive programming
>>> principles might be too big of a shock. Cummings arrives at these
>>> principles by trial-and-error, intuition, and experience. He also
>>> does not call the concepts by strange names like "active object
>>> (actor) pattern" or "reactive programming".
>>
>> He also gets something /seriously/ wrong.  His model of "a typical
>> thread" on page 4 is completely incorrect - and his whole argument
>> breaks down because of that.
> 
> The method just describes how real time (i.e. with upper limit for
> execution time) is usually done. Most (often over 99 %) of the time
> each thread/task/process is in the wait state waiting for an event,
> (such as message queue, event flag etc. depending of implementation).

Most of the time, threads (other than an idle or background thread) will
be waiting, yes.  But it is completely wrong to suggest that they will
necessarily be waiting at the outside of the thread function as
suggested by his structure.

> When an external event, such as serial line or clock interrupt occurs,
> some task is activated, possibly sending messages etc. to other task.
> When done, each task returns to the wait state. Usually there are only
> one runnable task at a time. If more tasks become runnable at the same
> time, they are executed in priority order. Very nice and clean.

Yes, I understand how threading works.  I also understand that it is
/not/ a requirement that waiting threads are sitting in their outer loop
waiting for a new message - they can make blocking calls at any point in
their execution.  What the author calls a "typical thread" is only one
possible thread structure, and is certainly not a typical one.


> 
>>
>> /Some/ threads are event driven services - they wait for messages coming
>> in, process them, and then go back to waiting for another message.  This
>> is basically a cooperative multi-tasking system - the sort of thing we
>> had to use before multi-threading and multi-tasking OS's were suitable
>> for small embedded systems.  (It's also what we had in Windows for long
>> /after/ every other "big" OS was multi-tasking.)
> 
> Windows NT 3.5 and later on was a full blown priority based
> multitasking system with close resemblance to RSX-11 and VMS.

I know.  But in the days of Win 3.x, most "big" OS's were multi-tasking
- Windows (and, perhaps, MacOS - I am not as familiar with that) was the
exception.  Other systems were running *nix variants, VMS, or other
multi-tasking OS's.  Windows did not catch up until NT.

> 
> Processor capabilities is no excuse for not having priority based
> multitasking. In the 1970/80's  practically every company using 8
> bitters had their own RT kernels. The Intel RMX-80 for 8080/85 might
> be familiar to some in this NG.

I disagree.  Multi-tasking OS's require a certain overhead of ram and
processing power.  If you only really need to do one thing, or if the
requirements can be stacked in a simple linear form (background task,
with layers of clearly prioritised interrupts on top) then such systems
are much more efficient use of resources.  And a cooperative
multi-tasking system fills the middle ground between features and
efficiency, if it is good enough for the requirements.

Certainly you /can/ make a multitasking RTOS for even the smallest of
processors.  That does not make it a sensible choice.

>   
>>
>> Threads like that can be a very useful structure, and can be very
>> efficient ways to model certain types of problem.  They are excellent
>> for handling user interaction, and are thus very popular for the main
>> thread in gui programs on desktops.  
> 
> I  usually put the (l)user interface in the null task (lowest priority
> task), so whatever the user does, it doesn't affect the really
> important parts of the system.

That is often a good idea!

> 
>> They are also marvellous as pretty
>> much the only thread (baring perhaps timers and interrupts) on many
>> embedded systems - in particular, you know that when the thread is in
>> the "Process message 1" part, it can't be in the "Process message 2"
>> part, and thus you can avoid a great deal of locking or other
>> synchronisation.
>>
>> But a key point is that a thread like that should avoid (or at least
>> minimise) any blocking or locking, and usually it should avoid any code
>> that takes a long time to run (possibly by breaking it up, using a state
>> machine).
> 
> Think about the various cases as interrupt service routines. Compare
> this with a multiline serial card with a single interrupt. You first
> determine which subsystem caused the interrupt and handle it
> accordingly. Of cause, the ISR should be then handled quickly as
> should the various message processing. The return from interrupt is
> then comparable to go to the loop wait state.
> 

Yes, that is clear - and like the ISR, such event-driven threads should
process the messages quickly or hand them off to other threads when
long-running work is needed.  These other threads, however, do /not/
have to be structured as event-driven with message queues as their point
of entry.

>>
>>
>> Other threads can have completely different structures.  In particular,
>> they /can/ have blocking operations because it is fine for them to block
>> - the blocking operations are part of the normal flow of the sequential
>> processes that are clear in the code and easy to track.  
> 
> If you need complicated sequential processing, such as in the (l)user
> interface, put it into the null task.
> 
>> That might mean
>> you have more threads than you would otherwise need, and a corresponding
>> loss in overall system efficiency, but that is the price you pay for
>> better modularisation and clearer code flow.  And you can have a range
>> of different types of synchronisation - using whatever makes the best
>> balance between efficiency, clear coding, and provably correct
>> synchronisation (i.e., you can be absolutely sure you have no deadlocks,
>> livelocks, etc.).
>>
>>
>> The "problem" described on pages 5-6 of the article stem from two errors
>> by the author.  
> 
> Yes, this is "self inflicted headache" (hangover) :-=
> 
>> One is to mix up the structures and responsibilities of
>> the threads - he has thread A being an event-driven service thread that
>> uses significant blocking in part of its processing.  The second problem
>> is that he has no clear picture of the control flow and the interaction
>> between threads, resulting in circular dependencies.  If you want an
>> efficient (and, for hard real time, correct) multi-threaded system you
>> have to know what your threads are, how they communicate, who waits for
>> what, and what deadlines you have - and arrange things so that you don't
>> have unnecessary waits.
>>
>> The variety of incorrect "solutions" then given are clearly problematic,
>> as he says - but he misses the obvious one which is to restructure the
>> threading and communication.  For example, a better solution might be to
>> introduce a new thread C whose job is to handle the work currently done
>> in thread A in response to message 1.  Thread A's handling of message 1
>> thus becomes "trigger thread C", and all the work - including blocking
>> if that is the most convenient solution - is done in thread C.  Thread A
>> can go back to handling events.  But for some reason, the author (and
>> many other authors on such topics, IME) does not think of adding another
>> thread.
>>
>> He also discusses the idea of the call to thread B being essentially
>> non-blocking, and with B sending its response as a message back to A.
>> But for some reason he says that should be a different message queue
> 
> I also wondered why.
> 
>>
>> that A would block on, giving the same problem but with a far more
>> complex structure - I can't see why anyone would suggest that as a
>> possible solution.  The response from B should either go into the main
>> event queue for A (perhaps this queue would need to be prioritised), or
>> (if the OS has the support) it could go in a separate queue with A
>> waiting for /either/ queue, maybe with a priority mechanism.
> 
> What is the point of having a queue priority, if there is already a
> state machine for Msg1 processing ?
> 

You may want the reply from B to be handled quickly, at higher priority
than ordinary messages coming in to A.  If so, you would either have a
second queue that has a higher priority (but wait on both), or use a
priority queue as your main event queue into A.  Having a single
priority queue is the most flexible as long as all your messages will
work with it.

>>
>> He is right in noting the dangers of using callbacks as a solution, as
>> they are logically in the domain of one thread but executed in the
>> context of another thread. 
> 
> Callback from some system service makes sense (i.e. translated
> interrupts), but I have seldom seen callbacks from one application to
> an other.

No one talked about callbacks between "applications" (do you mean
"processes" here?).

> 
>> The answer here is that callbacks need to be
>> short, deterministic, thread-safe and do as little as possible.  Still,
>> many of the potential problems he sees are due to poorly structured
>> threading and coding.  For example, he says:
>>
>> "Additional challenges can arise if, for example, Thread A is in the
>> middle of processing a large collection of data when the callback
>> executes, and if the response from B includes an update to a portion of
>> that collection of data."
>>
>> Proper structuring of responsibilities and encapsulation of the data and
>> code acting on it would mean that is not allowed - or that it can be
>> done in such a simple atomic way that there is no problem.
>>
>>
>> Really, most or all of the problems he sees could be solved by saying
>> "/Design/ your multi-threaded system carefully, and don't be afraid of
>> splitting tasks into new threads" rather coding first and thinking
>> later, programming by trial and error, and using hacks instead of
>> re-structuring as needed.
> 
> I use to limit the number of different tasks to 10, so that I can keep
> track of them with my fingers. Using more than that, would also
> require me to use my toes and my colleges might not appreciate, if I
> took off my socks  :-)
> 

There is a lot of sense in limiting a system - it should be as simple as
possible, but no simpler.  An artificial limit is not helpful, however,
and encourages the kind of restricted "solutions" suggested by the
author of that paper.  If adding a new thread simplifies the structure
of your program, then use it - even if you have to take your socks off.

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

#27911

On Thursday, August 2, 2018 at 6:24:52 AM UTC-4, David Brown wrote:
> Other threads can have completely different structures.  In particular, they /can/ have blocking operations because it is fine for them to block - the blocking operations are part of the normal flow of the sequential processes that are clear in the code and easy to track.

There is no denying that sequential solution to a sequential problem is the simplest and most efficient. For example (which I provide here for the benefit of the whole NG), if you have a thread that must handle a sequence of events ABC, you might hard-code the sequence in the following pseudo-code:

wait_for_semaphore_signaling_evt_A();
process_evt_A();
wait_for_queue_signaling_evt_B();
process_evt_B();
wait_for_evt_flag_signaling_evt_C();
process_evt_c();.

But the problem is that *most* of real-life problems are NOT sequential. So, in the example above, later in the development cycle it might become clear that the thread also needs to handle a (perhaps rare) sequence of events ABBA. At this point, the thread has to be completely re-designed, perhaps in the following way:

wait_for_semaphore_signaling_evt_A();
process_evt_A();
wait_for_queue_signaling_evt_B();
process_evt_B();
wait_for_queue_signaling_evt_BC();
switch (evt_type)
    case B: process_evt_B(); break;
    case C: process_evt_C(); break;
}

At this point, the thread structure becomes a "hybrid" of sequential and "event-driven". Specifically, B can be followed by another B or C, which requires a more generic OS mechanism to wait for both B and C *simultaneously* (which most likely is a queue rather than event-flag). Moreover, downstream of the generic wait for both B and C, the code needs to check which one actually arrived (hence the 'switch').

The main point is that people (including Dr. Cummings) have observed that sequential code almost always degenerates that way, so they propose a simple, generic thread structure that is *flexible* to accommodate any event sequence, which is the event-loop structure. Cummings' article stops at this, but of course real-life threads must "remember" certain event sequences, because the behavior depends on it. For example, if you build a vending machine, events A, B, and C might represent "product selection", "payment", "product dispense". The sequence is obviously important and other sequences should not be allowed (e.g., AC -- selection and dispensing, but without payment). Here is where state machines come in, but this discussion is perhaps for another time.

> The "problem" described on pages 5-6 of the (Cummings') article stem from two errors by the author.  One is to mix up the structures and responsibilities of the threads...

This is misunderstanding of the main premise of the article. Having found a generic thread structure (event-loop), Cummings (implicitly) assumes that this, and only this, generic structure is allowed. He then moves on to explaining how to use the thread structure correctly and how NOT to use it incorrectly. The event-driven thread structure is so superior to sequential code that he doesn't even consider that someone might still revert to the "old". It is a bit like a programmer once exposed to structured programming will typically not consider going back to GOTOs.

> This is basically a cooperative multi-tasking system - the sort of thing we had to use before multi-threading and multi-tasking OS's were suitable for small embedded systems.  (It's also what we had in Windows for long /after/ every other "big" OS was multi-tasking.)

This might be another misconception, which might be coming from the historical baggage surrounding event-driven systems. The generic thread structure recommended in Cummings' article *combines* preemptive multitasking with event-driven thread structure. Threads don't need to "cooperate" to yield the CPU to each other. Instead, any longer processing in a low-priority thread can be preempted (many times if need by) by higher-priority threads. This is determined by the preemptive kernel and its scheduling policy, without any explicit coding on the application developer part.
 

> The most amazing thing to me is that so many people think they
> know the "best" method.

Indeed, if you stick with the "sequential programming based on shared-state concurrency and blocking", there is no "best" method. You need to devise the structure of each and every thread from scratch, carefully choosing your blocking mechanisms (semaphore vs. queue vs. event-flags vs. select, etc.). You then need to worry about race conditions and carefully apply mutual exclusion. The blocking threads tend to be unresponsive, so to evolve the system you need to keep adding new threads to be able to handle new event sequences. This proliferation of threads leads to more sharing, because now two threads that wanted to be one need to share large data structures.

Alternatively, you can choose to work at a *higher level of abstraction*, with encapsulated event-driven threads (active objects). The threads wait generically on event-queue at the top of the loop and don't block otherwise. This allows the threads to remain *responsive*, so adding new events is easy. This also means that such threads can handle much more functionality than sequential threads. This reduces the need for sharing ("share nothing" principle). And finally, this thread structure offers high-enough level of abstraction and the *right* abstraction to apply event-driven state machines, graphical modeling, code generation, and other such modern programming techniques.

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

#27913

On 02/08/18 17:12, StateMachineCOM wrote:
> On Thursday, August 2, 2018 at 6:24:52 AM UTC-4, David Brown wrote:
>> Other threads can have completely different structures.  In particular, they /can/ have blocking operations because it is fine for them to block - the blocking operations are part of the normal flow of the sequential processes that are clear in the code and easy to track.
> 
> There is no denying that sequential solution to a sequential problem is the simplest and most efficient. For example (which I provide here for the benefit of the whole NG), if you have a thread that must handle a sequence of events ABC, you might hard-code the sequence in the following pseudo-code:
> 
> wait_for_semaphore_signaling_evt_A();
> process_evt_A();
> wait_for_queue_signaling_evt_B();
> process_evt_B();
> wait_for_evt_flag_signaling_evt_C();
> process_evt_c();.
> 
> But the problem is that *most* of real-life problems are NOT sequential. So, in the example above, later in the development cycle it might become clear that the thread also needs to handle a (perhaps rare) sequence of events ABBA. At this point, the thread has to be completely re-designed, perhaps in the following way:
> 
> wait_for_semaphore_signaling_evt_A();
> process_evt_A();
> wait_for_queue_signaling_evt_B();
> process_evt_B();
> wait_for_queue_signaling_evt_BC();
> switch (evt_type)
>      case B: process_evt_B(); break;
>      case C: process_evt_C(); break;
> }
> 

And at that point the standard technique and design pattern is to
code it as an FSM driven from a message queue or FIFO.

Personally I dislike if/switch statements, since in practice they
always mutate like cancer to become deeply nested and unmaintainable.

Instead there are standard FSM design patterns for that, e.g.
a 2D array of pointers to the process() functions with one dimension
being the FSM state and the other being the event type.

I also like the State represented as a class, and the events as
virtual functions. That allows complex behaviour to be represented
simply, where a common super-state is represented as a common
superclass.

Those design patterns have stood me well for all sorts of soft and
hard realtime systems over the decades.


> At this point, the thread structure becomes a "hybrid" of sequential and "event-driven". Specifically, B can be followed by another B or C, which requires a more generic OS mechanism to wait for both B and C *simultaneously* (which most likely is a queue rather than event-flag). Moreover, downstream of the generic wait for both B and C, the code needs to check which one actually arrived (hence the 'switch').
> 
> The main point is that people (including Dr. Cummings) have observed that sequential code almost always degenerates that way, so they propose a simple, generic thread structure that is *flexible* to accommodate any event sequence, which is the event-loop structure. Cummings' article stops at this, but of course real-life threads must "remember" certain event sequences, because the behavior depends on it. For example, if you build a vending machine, events A, B, and C might represent "product selection", "payment", "product dispense". The sequence is obviously important and other sequences should not be allowed (e.g., AC -- selection and dispensing, but without payment). Here is where state machines come in, but this discussion is perhaps for another time.
> 
>> The "problem" described on pages 5-6 of the (Cummings') article stem from two errors by the author.  One is to mix up the structures and responsibilities of the threads...
> 
> This is misunderstanding of the main premise of the article. Having found a generic thread structure (event-loop), Cummings (implicitly) assumes that this, and only this, generic structure is allowed. He then moves on to explaining how to use the thread structure correctly and how NOT to use it incorrectly. The event-driven thread structure is so superior to sequential code that he doesn't even consider that someone might still revert to the "old". It is a bit like a programmer once exposed to structured programming will typically not consider going back to GOTOs.
> 
>> This is basically a cooperative multi-tasking system - the sort of thing we had to use before multi-threading and multi-tasking OS's were suitable for small embedded systems.  (It's also what we had in Windows for long /after/ every other "big" OS was multi-tasking.)
> 
> This might be another misconception, which might be coming from the historical baggage surrounding event-driven systems. The generic thread structure recommended in Cummings' article *combines* preemptive multitasking with event-driven thread structure. Threads don't need to "cooperate" to yield the CPU to each other. Instead, any longer processing in a low-priority thread can be preempted (many times if need by) by higher-priority threads. This is determined by the preemptive kernel and its scheduling policy, without any explicit coding on the application developer part.
>   
> 
>> The most amazing thing to me is that so many people think they
>> know the "best" method.
> 
> Indeed, if you stick with the "sequential programming based on shared-state concurrency and blocking", there is no "best" method. You need to devise the structure of each and every thread from scratch, carefully choosing your blocking mechanisms (semaphore vs. queue vs. event-flags vs. select, etc.). You then need to worry about race conditions and carefully apply mutual exclusion. The blocking threads tend to be unresponsive, so to evolve the system you need to keep adding new threads to be able to handle new event sequences. This proliferation of threads leads to more sharing, because now two threads that wanted to be one need to share large data structures.
> 
> Alternatively, you can choose to work at a *higher level of abstraction*, with encapsulated event-driven threads (active objects). The threads wait generically on event-queue at the top of the loop and don't block otherwise. This allows the threads to remain *responsive*, so adding new events is easy. This also means that such threads can handle much more functionality than sequential threads. This reduces the need for sharing ("share nothing" principle). And finally, this thread structure offers high-enough level of abstraction and the *right* abstraction to apply event-driven state machines, graphical modeling, code generation, and other such modern programming techniques.
> 

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

#27919

(Please get a real newsreader and a real newsserver, instead of using 
Google Groups for posting.  GG screws up Usenet formatting and line 
endings, so the result is that when replying to you, other people have 
to choose between messed up text quotation, or messed up code quotation. 
  You'll also find it far better for Usenet access.)

On 02/08/18 18:12, StateMachineCOM wrote:
> On Thursday, August 2, 2018 at 6:24:52 AM UTC-4, David Brown wrote:
>> Other threads can have completely different structures.  In
>> particular, they /can/ have blocking operations because it is fine
>> for them to block - the blocking operations are part of the normal
>> flow of the sequential processes that are clear in the code and
>> easy to track.
> 
> There is no denying that sequential solution to a sequential problem
> is the simplest and most efficient. For example (which I provide here
> for the benefit of the whole NG), if you have a thread that must
> handle a sequence of events ABC, you might hard-code the sequence in
> the following pseudo-code:
> 
> wait_for_semaphore_signaling_evt_A(); process_evt_A(); 
> wait_for_queue_signaling_evt_B(); process_evt_B(); 
> wait_for_evt_flag_signaling_evt_C(); process_evt_c();.
> 
> But the problem is that *most* of real-life problems are NOT
> sequential.

So use sequential-style coding for sequential problems, and use other 
styles in other situations.

> So, in the example above, later in the development cycle
> it might become clear that the thread also needs to handle a (perhaps
> rare) sequence of events ABBA. At this point, the thread has to be
> completely re-designed, perhaps in the following way:
> 
> wait_for_semaphore_signaling_evt_A(); process_evt_A(); 
> wait_for_queue_signaling_evt_B(); process_evt_B(); 
> wait_for_queue_signaling_evt_BC(); switch (evt_type) case B:
> process_evt_B(); break; case C: process_evt_C(); break; }
> 
> At this point, the thread structure becomes a "hybrid" of sequential
> and "event-driven".

If the logic is hybrid, then use a hybrid code structure.

The idea that there is only one correct way of writing your code is 
simply /wrong/.

> Specifically, B can be followed by another B or
> C, which requires a more generic OS mechanism to wait for both B and
> C *simultaneously* (which most likely is a queue rather than
> event-flag). 

Lots of RTOS's have support for waiting for multiple objects.  Failing 
that, it is not hard to solve such challenges in other ways.  You don't 
have to use a queue, and you don't have to re-structure everything 
around the possibility that one part of your code might have to wait for 
two different things.

> Moreover, downstream of the generic wait for both B and
> C, the code needs to check which one actually arrived (hence the
> 'switch').
> 
> The main point is that people (including Dr. Cummings) have observed
> that sequential code almost always degenerates that way, so they
> propose a simple, generic thread structure that is *flexible* to
> accommodate any event sequence, which is the event-loop structure.
> Cummings' article stops at this, but of course real-life threads must
> "remember" certain event sequences, because the behavior depends on
> it. For example, if you build a vending machine, events A, B, and C
> might represent "product selection", "payment", "product dispense".
> The sequence is obviously important and other sequences should not be
> allowed (e.g., AC -- selection and dispensing, but without payment).
> Here is where state machines come in, but this discussion is perhaps
> for another time.

The standard "vending machine" solution is done in a /completely/ 
different manner - it is the running example in the classic book 
"Communicating Sequential Processes" which has a far neater, clearer and 
more efficient handling of multiple threads than that paper.  The book 
is available freely online - I would recommend it.

> 
>> The "problem" described on pages 5-6 of the (Cummings') article
>> stem from two errors by the author.  One is to mix up the
>> structures and responsibilities of the threads...
> 
> This is misunderstanding of the main premise of the article. Having
> found a generic thread structure (event-loop), Cummings (implicitly)
> assumes that this, and only this, generic structure is allowed. 

Why?  There is no justification for such an assumption - implicitly or 
not.  He has picked a single thread structure and somehow decided that's 
the only one to use, and further that there should only be two threads 
in his system no matter how he changes the tasks at hand.  All the 
problems he gets are due to his poor choice of structure and 
stubbornness in sticking to it.

It's not that I misunderstand the premise of the article - it's simply 
that I think it is a pointless premise.  It would be like deciding that 
I will program in C, but all my loops will be "do {...} while ()" loops 
- and then complaining that simple counting loops look ugly.

> He
> then moves on to explaining how to use the thread structure correctly
> and how NOT to use it incorrectly.

No, he goes on to talk about how to get something working - ugly, 
unclear and separate from the logical flow of the task at hand, but 
working - despite the self-imposed limitations.

> The event-driven thread structure
> is so superior to sequential code that he doesn't even consider that
> someone might still revert to the "old".

When I first looked at the paper, I thought maybe he had a point.  More 
thought, and the discussion here, has convinced me that he does not. 
No, event-driven thread structures are /not/ superior.  They do have 
their uses and there are cases where they work well - fortunately I knew 
that before looking at the paper, because his efforts to force their 
usage inappropriately could easily convince people that they are always 
a poor choice.

> It is a bit like a
> programmer once exposed to structured programming will typically not
> consider going back to GOTOs.

Think a little bit harder, and you will see that it is the event-driven 
model that is ending up as GOTOs.  It is not even managing a good 
old-fashioned GOSUB from BASIC years - you have to use global state 
variables to keep track of where you have been and where you are going.

> 
>> This is basically a cooperative multi-tasking system - the sort of
>> thing we had to use before multi-threading and multi-tasking OS's
>> were suitable for small embedded systems.  (It's also what we had
>> in Windows for long /after/ every other "big" OS was
>> multi-tasking.)
> 
> This might be another misconception, which might be coming from the
> historical baggage surrounding event-driven systems.

I know what event-driven systems are.

> The generic
> thread structure recommended in Cummings' article *combines*
> preemptive multitasking with event-driven thread structure. Threads
> don't need to "cooperate" to yield the CPU to each other. 

I realise that.  But it is much the same structure as for pre-emptive 
multi-tasking.

> Instead,
> any longer processing in a low-priority thread can be preempted (many
> times if need by) by higher-priority threads. This is determined by
> the preemptive kernel and its scheduling policy, without any explicit
> coding on the application developer part.
> 
> 
>> The most amazing thing to me is that so many people think they know
>> the "best" method.
> 
> Indeed, if you stick with the "sequential programming based on
> shared-state concurrency and blocking", there is no "best" method.

No, if you do proper development you understand there is no "best" 
method.  Sometimes event-driven threads /are/ the best choice, or part 
of the best choice - but they are most certainly not /always/ the best 
choice.  Please understand what I am saying here - I have nothing 
against event-driven threads used in the right place.  I have everything 
against using them in the wrong place, or thinking that they are always 
the right choice.

> You need to devise the structure of each and every thread from
> scratch, carefully choosing your blocking mechanisms (semaphore vs.
> queue vs. event-flags vs. select, etc.). 

Yes.

> You then need to worry about
> race conditions and carefully apply mutual exclusion. 

Yes.

You need to /design/ your code - you need to plan it, you need to be 
willing to change it to handle different requirements if that becomes 
necessary.

You need to separate your code into clearly defined parts, and 
understand their interactions.

This is /always/ the case.  You can't just say "This guy said in a paper 
that event-driven threads were magic.  So we'll just use them instead of 
thinking".

> The blocking
> threads tend to be unresponsive,

Nonsense.  If your threads are not as responsive as you need, you will 
have to fix the design (or perhaps it can't be handled by the hardware 
you have).  That applies whatever kind of blocking your threads have.

> so to evolve the system you need to
> keep adding new threads to be able to handle new event sequences.
> This proliferation of threads leads to more sharing, because now two
> threads that wanted to be one need to share large data structures.

You are inventing problems faster than that paper's author did.

> 
> Alternatively, you can choose to work at a *higher level of
> abstraction*, with encapsulated event-driven threads (active
> objects). The threads wait generically on event-queue at the top of
> the loop and don't block otherwise. This allows the threads to remain
> *responsive*, so adding new events is easy. This also means that such
> threads can handle much more functionality than sequential threads.
> This reduces the need for sharing ("share nothing" principle). And
> finally, this thread structure offers high-enough level of
> abstraction and the *right* abstraction to apply event-driven state
> machines, graphical modeling, code generation, and other such modern
> programming techniques.
> 

Nonsense.  If you think your magic thread structures have eliminated 
sharing and synchronisation, or the need to think carefully about your 
design, you have misunderstood everything about multi-threaded coding. 
Using different structures, or different synchronisation primitives, 
does not change /anything/ about the fundamentals of what data passes 
around, what synchronisation is needed, and what parts need to wait for 
which other parts.  It changes the details, and the choices can make a 
big difference on how clear and simple the code is, how efficient it is, 
and how much effort it takes to write, read and maintain the code. 
Event-driven threads are the best choice in some cases, and the worst 
choice in others as your mess of state variables means your logic is 
spread out all over the place instead of a clear, neat code flow.

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

#27923

@David Brown: As they say: "you can lead a horse to water, but you can't make it drink". I rest my case.

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

#27928

On 18-08-03 00:22 , StateMachineCOM wrote:
> @David Brown: As they say: "you can lead a horse to water, but you
> can't make it drink". I rest my case.

At least this one juror decides in favour of David B.

All programs are state machines, but the "state" can be represented in 
various ways: as data ("reified") or as control flow ("sequential", 
"blocking"). Which is better depends on the problem to be solved; 
usually I end up with a mixture.

Sometimes system constraints force one to use more data-state than is 
optimal, and the code becomes an awful mess. I have in mind my last 
project but one, where the SW controls several devices over a 
MIL-STD-1553 bus, with a cyclic, frame-based schedule, running several 
sporadically activated concurrent activites, each of which usually 
requires several carefully timed bus commands and responses, spread over 
several bus cycles.

The nicest design would dedicate one thread to each such activity; after 
sending a command, the thread would wait (block) for the response, and 
would know, from its position in the algorithm, what to do with the 
response and what command to send next. But system constraints prohibit 
this number of threads, and thread switches, so all the state of the 
activities is reified into multiple state machines, activated once on 
every bus cycle, with switch/case statements that change the global 
state, increment counters, detect end of loops, retry failed commands, 
and so on and on. Yuck.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

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

#27929

On 02/08/18 23:22, StateMachineCOM wrote:
> @David Brown: As they say: "you can lead a horse to water, but you can't make it drink". I rest my case.
> 

That applies equally in the other direction, of course.

The discussion has been interesting, but I really don't think either you
or the paper's author have done yourself justice here.

I have not seen any clear arguments from you about /why/ you think
event-driven threads with state machines are so much better - "proof by
repeated assertion" does not wash.  I have not seen any counters to my
alternative suggestions, nor any solid reasoning why strict event-driven
threads with state machines are somehow easier than more flexible
solutions.  And I certainly have not seen any good argument for why
using /one/ tool should be so much better than having that tool as an
option amongst several.

I am of the opinion that having more options lets you pick better
designs.  (I actually think that in a great many cases where people use
RTOS's, they would be better with a simpler non-OS design.  I am not a
believer in "everything should be RTOS".)  But despite my clear opinions
here, I think I could have come up with more and better arguments in
your favour than you did.


Still, as I say, it has been an interesting discussion in many ways, and
it is good to see this sort of thing in the newsgroup.  It has been too
quite for too long.

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

#27924

On 02/08/18 17:12, StateMachineCOM wrote:
> At this point, the thread structure becomes a "hybrid" of sequential and "event-driven". Specifically, B can be followed by another B or C, which requires a more generic OS mechanism to wait for both B and C*simultaneously*  (which most likely is a queue rather than event-flag). Moreover, downstream of the generic wait for both B and C, the code needs to check which one actually arrived (hence the 'switch').

Of course some processors have that capability in their hardware, e.g.
select {
   // suspend until one of these events occurs and then
   // resume with 10ns latency
   message from channel A:
     do_this ();
     break;
   message from channel B:
     do_that();
     break;
   timeout:
     scram_reactor();
     break;
   input on port C:
     read it and record time it arrived
     break;
   output completed on port D:
     do next output on port D at 12.96us after last output on port D
     break;
}


(RTOS? What RTOS?)

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

#27912

On Thu, 02 Aug 2018 16:43:29 +0200, David Brown
<david.brown@hesbynett.no> wrote:

>> Processor capabilities is no excuse for not having priority based
>> multitasking. In the 1970/80's  practically every company using 8
>> bitters had their own RT kernels. The Intel RMX-80 for 8080/85 might
>> be familiar to some in this NG.
>
>I disagree.  Multi-tasking OS's require a certain overhead of ram and
>processing power.  If you only really need to do one thing, or if the
>requirements can be stacked in a simple linear form (background task,
>with layers of clearly prioritised interrupts on top) then such systems
>are much more efficient use of resources.  And a cooperative
>multi-tasking system fills the middle ground between features and
>efficiency, if it is good enough for the requirements.

The overhead doesn't have to be big. Of course, in a pre-emptive
systems, there must be a private stack for each thread. In addition to
that, very little overhead is required. I once worked with a small
kernel for 6809, which in addition to the stacks, there were 3 bytes
bookkeeping (thread status and saved stack pointer) for each thread.


>Certainly you /can/ make a multitasking RTOS for even the smallest of
>processors.  That does not make it a sensible choice.

All you need is the ability to have stacks in RAM and in addition
instructions for loading and storing the stack pointer from/to memory.

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

#27914

On 02/08/18 17:56, upsidedown@downunder.com wrote:
> All you need is the ability to have stacks in RAM and in addition
> instructions for loading and storing the stack pointer from/to memory.

Unfortunately that is difficult to implement in C, so youngsters
don't think of it.

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

#27920

On 02/08/18 19:14, Tom Gardner wrote:
> On 02/08/18 17:56, upsidedown@downunder.com wrote:
>> All you need is the ability to have stacks in RAM and in addition
>> instructions for loading and storing the stack pointer from/to memory.
> 
> Unfortunately that is difficult to implement in C, so youngsters
> don't think of it.
> 

This particular youngster grew up on small microcontrollers programmed 
in assembly.  "All you need is the RAM" is not helpful when you have 512 
bytes in total, and the stack pointer is limited to accessing the first 
128 bytes of that.  I have worked on microcontrollers where the context 
switches involved in handling an interrupt could easily take 50 µs or 
more - a proper RTOS would be far too high overhead.

Of course you can have more minimal OS's with very limited features (all 
the way down to "protothreads"), and perhaps cooperative multi-tasking 
rather than pre-emptive.  But then you are not going to have threads 
with multiple message queues like the ones under discussion.

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

#27925

On 02/08/18 22:12, David Brown wrote:
> On 02/08/18 19:14, Tom Gardner wrote:
>> On 02/08/18 17:56, upsidedown@downunder.com wrote:
>>> All you need is the ability to have stacks in RAM and in addition
>>> instructions for loading and storing the stack pointer from/to memory.
>>
>> Unfortunately that is difficult to implement in C, so youngsters
>> don't think of it.
>>
> 
> This particular youngster grew up on small microcontrollers programmed in 
> assembly.  

Ditto; neither of us are spring chickens.

The first computer I designed, while still an undergrad, had
128 bytes of memoy. I still have that ic :)

> "All you need is the RAM" is not helpful when you have 512 bytes in 
> total, and the stack pointer is limited to accessing the first 128 bytes of 
> that.  I have worked on microcontrollers where the context switches involved in 
> handling an interrupt could easily take 50 µs or more - a proper RTOS would be 
> far too high overhead.
> 
> Of course you can have more minimal OS's with very limited features (all the way 
> down to "protothreads"), and perhaps cooperative multi-tasking rather than 
> pre-emptive.  But then you are not going to have threads with multiple message 
> queues like the ones under discussion.

Protothreads always strike me as being a kludge that is "justified"
by the limitations of the software tools rather than the hardware
limitations.

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

#27930

On 03/08/18 00:52, Tom Gardner wrote:
> On 02/08/18 22:12, David Brown wrote:
>> On 02/08/18 19:14, Tom Gardner wrote:
>>> On 02/08/18 17:56, upsidedown@downunder.com wrote:
>>>> All you need is the ability to have stacks in RAM and in addition
>>>> instructions for loading and storing the stack pointer from/to memory.
>>>
>>> Unfortunately that is difficult to implement in C, so youngsters
>>> don't think of it.
>>>
>>
>> This particular youngster grew up on small microcontrollers programmed
>> in assembly.  
> 
> Ditto; neither of us are spring chickens.
> 
> The first computer I designed, while still an undergrad, had
> 128 bytes of memoy. I still have that ic :)

I have never designed a chip - though in my teens I once designed key
parts of a simple 4-bit cpu with a small instruction set.  I drew it all
out in two input NAND gates, on graph paper - including the single-cycle
multiplier.

> 
>> "All you need is the RAM" is not helpful when you have 512 bytes in
>> total, and the stack pointer is limited to accessing the first 128
>> bytes of that.  I have worked on microcontrollers where the context
>> switches involved in handling an interrupt could easily take 50 µs or
>> more - a proper RTOS would be far too high overhead.
>>
>> Of course you can have more minimal OS's with very limited features
>> (all the way down to "protothreads"), and perhaps cooperative
>> multi-tasking rather than pre-emptive.  But then you are not going to
>> have threads with multiple message queues like the ones under discussion.
> 
> Protothreads always strike me as being a kludge that is "justified"
> by the limitations of the software tools rather than the hardware
> limitations.

They are a way to get convenient coding structures from very little
software or hardware.  I haven't had a use for them myself, but I
suppose some people use them.

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

#27931

On 03/08/18 09:28, David Brown wrote:
> On 03/08/18 00:52, Tom Gardner wrote:
>> On 02/08/18 22:12, David Brown wrote:
>>> On 02/08/18 19:14, Tom Gardner wrote:
>>>> On 02/08/18 17:56, upsidedown@downunder.com wrote:
>>>>> All you need is the ability to have stacks in RAM and in addition
>>>>> instructions for loading and storing the stack pointer from/to memory.
>>>>
>>>> Unfortunately that is difficult to implement in C, so youngsters
>>>> don't think of it.
>>>>
>>>
>>> This particular youngster grew up on small microcontrollers programmed
>>> in assembly.
>>
>> Ditto; neither of us are spring chickens.
>>
>> The first computer I designed, while still an undergrad, had
>> 128 bytes of memoy. I still have that ic :)
> 
> I have never designed a chip - though in my teens I once designed key
> parts of a simple 4-bit cpu with a small instruction set.  I drew it all
> out in two input NAND gates, on graph paper - including the single-cycle
> multiplier.

Mine was 6800 based. Just about everything was "suboptimal" - except
that it worked and I learned a heck of a lot.

I later designed a single-purpose machine using 2900 bit-slices,
but it was never implemented.

> 
>>
>>> "All you need is the RAM" is not helpful when you have 512 bytes in
>>> total, and the stack pointer is limited to accessing the first 128
>>> bytes of that.  I have worked on microcontrollers where the context
>>> switches involved in handling an interrupt could easily take 50 µs or
>>> more - a proper RTOS would be far too high overhead.
>>>
>>> Of course you can have more minimal OS's with very limited features
>>> (all the way down to "protothreads"), and perhaps cooperative
>>> multi-tasking rather than pre-emptive.  But then you are not going to
>>> have threads with multiple message queues like the ones under discussion.
>>
>> Protothreads always strike me as being a kludge that is "justified"
>> by the limitations of the software tools rather than the hardware
>> limitations.
> 
> They are a way to get convenient coding structures from very little
> software or hardware.  I haven't had a use for them myself, but I
> suppose some people use them.

That's my (lack of) experience, but the requirement that all
context switches are in the top level code (i.e. not a function)
doesn't strike me as convenient. I know why it is "necessary",
but that doesn't change the inconvenience.

Back in 1982 I was using cooperative multitasking with C threads
on a Z80 (or PDP11 or whatever was convenient), with a little
bit of assembler to save/restore the stacks and other context.
That always seemed pretty natural - provided I used message
passing (with timeouts) for large-scale flow control.

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

#27932

On 03/08/18 12:21, Tom Gardner wrote:
> On 03/08/18 09:28, David Brown wrote:
>> On 03/08/18 00:52, Tom Gardner wrote:
>>> On 02/08/18 22:12, David Brown wrote:
>>>> On 02/08/18 19:14, Tom Gardner wrote:
>>>>> On 02/08/18 17:56, upsidedown@downunder.com wrote:
>>>>>> All you need is the ability to have stacks in RAM and in addition
>>>>>> instructions for loading and storing the stack pointer from/to
>>>>>> memory.
>>>>>
>>>>> Unfortunately that is difficult to implement in C, so youngsters
>>>>> don't think of it.
>>>>>
>>>>
>>>> This particular youngster grew up on small microcontrollers programmed
>>>> in assembly.
>>>
>>> Ditto; neither of us are spring chickens.
>>>
>>> The first computer I designed, while still an undergrad, had
>>> 128 bytes of memoy. I still have that ic :)
>>
>> I have never designed a chip - though in my teens I once designed key
>> parts of a simple 4-bit cpu with a small instruction set.  I drew it all
>> out in two input NAND gates, on graph paper - including the single-cycle
>> multiplier.
> 
> Mine was 6800 based. Just about everything was "suboptimal" - except
> that it worked and I learned a heck of a lot.
> 
> I later designed a single-purpose machine using 2900 bit-slices,
> but it was never implemented.
> 
>>
>>>
>>>> "All you need is the RAM" is not helpful when you have 512 bytes in
>>>> total, and the stack pointer is limited to accessing the first 128
>>>> bytes of that.  I have worked on microcontrollers where the context
>>>> switches involved in handling an interrupt could easily take 50 µs or
>>>> more - a proper RTOS would be far too high overhead.
>>>>
>>>> Of course you can have more minimal OS's with very limited features
>>>> (all the way down to "protothreads"), and perhaps cooperative
>>>> multi-tasking rather than pre-emptive.  But then you are not going to
>>>> have threads with multiple message queues like the ones under
>>>> discussion.
>>>
>>> Protothreads always strike me as being a kludge that is "justified"
>>> by the limitations of the software tools rather than the hardware
>>> limitations.
>>
>> They are a way to get convenient coding structures from very little
>> software or hardware.  I haven't had a use for them myself, but I
>> suppose some people use them.
> 
> That's my (lack of) experience, but the requirement that all
> context switches are in the top level code (i.e. not a function)
> doesn't strike me as convenient. I know why it is "necessary",
> but that doesn't change the inconvenience.

I agree entirely - that is one of the main things that puts me off about
them.  But others may find the benefits are worth it.

> 
> Back in 1982 I was using cooperative multitasking with C threads
> on a Z80 (or PDP11 or whatever was convenient), with a little
> bit of assembler to save/restore the stacks and other context.
> That always seemed pretty natural - provided I used message
> passing (with timeouts) for large-scale flow control.

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

#27927

On Thu, 2 Aug 2018 23:12:02 +0200, David Brown
<david.brown@hesbynett.no> wrote:

>On 02/08/18 19:14, Tom Gardner wrote:
>> On 02/08/18 17:56, upsidedown@downunder.com wrote:
>>> All you need is the ability to have stacks in RAM and in addition
>>> instructions for loading and storing the stack pointer from/to memory.
>> 
>> Unfortunately that is difficult to implement in C, so youngsters
>> don't think of it.
>> 
>
>This particular youngster grew up on small microcontrollers programmed 
>in assembly.  "All you need is the RAM" is not helpful when you have 512 
>bytes in total, and the stack pointer is limited to accessing the first 
>128 bytes of that.  

With 2-4 tasks, that is at least 32 bytes of stack per task. This
needs to fit the task subroutine return addresses and space for saving
task context (such as program counter, index reguster(s) and
accumulator(s)) and additionally local variables used by the ISR.
Should be doable, since subroutine parameters can be passed through
the remaining 384 bytes.

>I have worked on microcontrollers where the context 
>switches involved in handling an interrupt could easily take 50 µs or 
>more - a proper RTOS would be far too high overhead.
>
>Of course you can have more minimal OS's with very limited features (all 
>the way down to "protothreads"), and perhaps cooperative multi-tasking 
>rather than pre-emptive.  But then you are not going to have threads 
>with multiple message queues like the ones under discussion.

A simple RTOS just needs a fixed table for each task in priority order
in which each element contains the task state and saved stack pointer.

When e.g. the ISR wants to activate a specific task, it simply sets
the target task state to READY. After that, scan the task table and
find first task in READY state, load the saved stack  pointer and
execute a return from interrupt from the new stack to restore that
task context.

Routines for e.g. sending and receiving messages between tasks is just
syntactic sugar :-).

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

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

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

csiph-web