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

Groups > comp.arch.embedded > #29073

Re: From cooperative to preemptive scheduler: a real example

Show all headers | View raw

Il 07/01/2020 15:51, Don Y ha scritto:
> On 1/7/2020 2:11 AM, pozz wrote:
>> Il 07/01/2020 03:37, Don Y ha scritto:
>>> On 1/6/2020 6:08 PM, pozz wrote:
>>>
>>> [ 8< ]
>>>
>>>> My impression is that a very simple code is cluttered with 
>>>> synchronization things that decrease readability and maintainability 
>>>> and increase complexity. Why? Just to use preemption?
>>>
>>> The "clutter" is introduced because your "problem" inherently involves
>>> conflict; you're allowing two competing uses for a single resource.
>>
>> Howevere the shared resource complexity is present only when 
>> preemption is used.
> 
> Because it doesn't work right in the nonpreempt case!  :>

Why do you say this? This application can work flowlessy even with 
cooperative multitasking.


>>> The use of the synchronization primitive OVERTLY acknowledges this
>>> issue/possibility -- lest (subsequent) another developer fail to
>>> recognize that the possibility exists (i.e., "latent bug").
>>>
>>>> Again my impression is that preemption is NOT GOOD and must be 
>>>> avoided if it isn't required.
>>>
>>> "Multiplication is NOT GOOD and must be avoided if it isn't required 
>>> (i.e.,
>>> if you can use repeated ADDITIONs, instead)"
>>
>> I know all approaches have pros and cons. What I was meaning is that 
>> preemption is used too often, even when it isn't really required.
> 
> Much of this has to do with coding styles.  E.g., I can't recall the 
> last time
> I wrote a single-threaded application.  My mind just doesn't see things 
> like
> that, anymore.  I *always* see parallelism in problems.
> 
> You develop a "taste' for a particular type of coding.   E.g., I have a 
> buddy
> who doesn't think twice about spawning new tasks -- only to kill them off
> a short time later, having decided that they've served their purpose.  He
> might have HUNDREDS in a little tiny system, at any given time!  OTOH, I
> tend to spawn tasks that "run forever" and "do more".
> 
> I have a colleague who approaches all projects top-down.  I find it 
> unnerving
> to watch him "think" during his design process.  By contrast, I *assess* 
> the
> problem from the top, down -- and then *implement* it from the bottom up 
> with
> a clear view of where I'm headed!
> 
> Similarly, I now deal almost exclusively with "featureful" RTOSs -- memory
> protection, multiple cores, multiple processors, network interfaces, high
> resolution timing, etc.  I'm tired of counting bytes and packing 8 booleans
> into a byte.  Processors are cheap -- my time isn't!

Yes, you're right. It's a matter of coding style. I don't have any 
experience in multi-tasking systems so I am worried about them. There's 
a learning curve for coding tasks in a preemptive environment that it 
appears to me a waste of time if I'm able to reach the same goal with a 
completeley different approach that is much more friendly to me.

Anyway I'd like to learn a little of the other approach. This is the 
reason of my posts.


> The biggest headache in preemptive designs is worrying about which 
> operations
> MUST be atomic -- and being sure to protect that aspect of their design.
> But, this is related to sharing.  If you don't share stuff, then you 
> don't have
> to worry about this problem!
> 
> And, /ad-hoc/ sharing TENDS to be "A Bad Thing".  You want to strive to 
> isolate
> "things" as much as possible.  Information hiding.  etc.  If there's no
> *compelling* reason for A to know about B, then why expose one to the 
> other?
> 
> And, if they *do* need to be aware of each other, make their interactions
> very visible and restricted to a small set of operations.

In my very simple application (display showing a message) there is a 
sharing resource that can't be avoided (at least to me). Imagine if many 
variables would be set through the serial line: a semaphore everytime 
both tasks need to access those variables!


> So, if you're already working to minimize sharing, then you're already 
> working
> to facilitate the preemptive approach.
> 
> Finally, its easier to relate to and tune a preemptive system because the
> "interrupts" (preemptions) are visible -- much moreso than all those
> "yield()s" scattered through your codebase!

Again I don't use explicit yield()s. So the worst-case superloop 
duration is the sum of worst-case durations of each task, plus 
worst-case duration of interrupts.
If tasks are coded as non-blocking (state-machine), this worst-case 
duration could be very small and real-time requirements can be respected.


>> With FreeRTOS preemption scheduler is often enabled. It seems to me 
>> many times preemption is used only to show how nice I am.
> 
> Designing BIG systems with cooperative approach can become a headache.  How
> do you ever know what sort of latency a particular task may encounter at
> a particular time?  You have to be aware of what all the other tasks are
> doing (and how willingly they are CURRENTLY relinquishing the processor)
> in order to guesstimate the time between activations of YOUR task.

Again, in my approach every task are *non-blocking*, so they take 
100us-1ms maximum at each loop. If I have 10 tasks, superloop duration 
could be estimated in 10ms maximum. If the most critical real-time 
requirement is 100ms or more, cooperative multitasking is ok.

Of course, we need to take into account interrupts, that are much 
shorter than tasks, so they can be normally ignored. Anyway they must be 
considered in preemptive scheduler too.


> What's BIG?  BIG == COMPLEX.
> 
> What's COMPLEX?  COMPLEX is anything that doesn't COMPLETELY fit in your 
> head.
> <grin>  If you can't remember all of the pertinent details to be able to
> make a decision/assessment (e.g., the above scenario), then your system is
> COMPLEX.
> 
>>>>  From what I have understood, preemption could solve real-time 
>>>> requirement.
>>>
>>> Preemption, like any capability, brings with it assets and liabilities.
>>> Imagine you were tasked with building a box that blinked lights (XMAS
>>> lights!) at different/varying rates.  The box has a dozen solid state
>>> switches that control the individual lights (or, "light strands").
>>>
>>> It would be really easy -- and intuitive -- to write:
>>>      void lights1() {
>>>         while(FOREVER) {
>>>           light(1,ON);  sleep(500ms);
>>>           light(1,OFF); sleep(279ms);
>>>         }
>>>      }
>>>
>>>      void lights2() {
>>>         while(FOREVER) {
>>>           light(2,ON);  sleep(100ms);
>>>           light(2,OFF); sleep(50ms);
>>>         }
>>>      }
>>>
>>>      void lights3() {
>>>         while(FOREVER) {
>>>           ontime = (10.0 * rand() ) / RAND_MAX;
>>>           light(3,ON);  sleep(ontime);
>>>           light(3,OFF); sleep(10.0 - ontime);
>>>         }
>>>      }
>>>
>>> etc.  No silly "yields" to get in the way.  No need for synchronization
>>> primitives, either, because nothing is SHARED!
>>
>> In the superloop cooperative approach:
>>
>> void lights1() {
>>    if (state_ON && timer_expired()) {
>>      light(1, OFF);
>>      timer_arm(500ms);
>>      state_ON = false;
>>    } else if (!state_ON && timer_expired()) {
>>      light(1, ON);
>>      timer_arm(279ms);
>>      state_ON = true;
>>    }
>>
>> This is a state-machine and I admit it's harder to write then in 
>> preemptive scheduler.
> 
> Yes.  In the preemptive approach I described, the "state" is automatically
> saved for you -- it manifests as the PRESERVED value of the Program Counter
> at the time the task was preempted.  Note that this need not be done by
> a time-slicer.  Rather, each sleep() effectively relinquishes the 
> processor...
> and resumes execution when the time period elapses.
> 
> Note that you can create a cooperative solution that similarly
> "tracks" the "state" -- by having yield() capture the program counter
> and restore it on the next activation.
> 
>>> [Contrived example but you'll find that there are many cases of
>>> tasks co-executing that are NOT sharing anything (other than the
>>> processor)]
>>>
>>> There are other classes of problems where the problem lends itself, 
>>> naturally,
>>> to "peaceful" sharing -- where you're not in conflict with another.  
>>> And,
>>> other techniques to hide the sharing mitigation in other mechanisms.
>>>
>>> Preemption lets you code AS IF you were the sole owner of the 
>>> processor...
>>> EXCEPT when you need to share something (which would imply that you are
>>> NOT the sole owner -- at least at THAT time!  :> )
>>
>> I suspect many real applications need synchronization mess (and risks 
>> if you don't know very well what the pitfalls of multitasking).
>> And in those cases I'm not sure if it's simpler to code in 
>> preemption/blocking/synchronization or in 
>> cooperative/non-blocking/state-machine.
> 
> You can actually mix them in the same design.
> 
> I, for example, often implement a cooperative multitasking system *in*
> an ISR (so the ISRs function can evolve from iteration to iteration).
> There, the yield() causes another "responsibility" of the ISR to
> begin execution while still actively IN the original interrupt.
> A separate mechanism is used to return from the interrupt in the
> last "interrupt task" executed.
> 
>>> The downside to cooperative multitasking is that *it* clutters your
>>> code -- with all those yield()s -- and requires you to keep track of
>>> how "long" you've hogged the CPU in the time since your last yield
>>> (because that time gets reflected to all subsequent task runnings).
>>  >> When I write code in a cooperative environment, I *litter* the code
>>> with yield()s to keep *reaction* times (of other tasks) short.  This
>>> then means yield() has to run like greased lightning lest it impact
>>> overall performance (because it is pure overhead!)
>>
>> If you use non-blocking state-machines, there aren't any downside to 
>> cooperative multitasking. There aren't real yield()s, they are hidden 
>> when the task function exits.
> 
> Find a coding style that you're comfortable with and with which you can
> be reasonably expected to become proficient.  Then, hone your skills
> on that approach -- peeking into other approaches, periodically, to see
> when/if they might offer you a better solution.  The "right" approach is
> the one that works for you.  *Reliably*.  (if you find yourself writing
> buggy code -- or, coding efficiency drops -- then look at where YOUR
> problems lie and see if any of them are related to the environment
> in which you've chosen to code)
> 
> The only real worry is to avoid things that are too "exotic" as they
> can make it hard for others to understand/adopt that approach.
> 
> E.g., I like to use "finite state executives" to encode user interface
> operations and communication protocols.  This lets me condense the rules
> for the interface into small tables that (*I* think) tersely encapsulate
> the essence of the operator's actions at any point in the interface.
> 
> For example, to collect a numeric value from the user, I might have
> this FSM fragment:
> 
>       STATE   ENTRY
> On  '0' THRU '9'   goto ENTRY    executing  AccumulateDigit()
> On  'BACKSPACE'    goto ENTRY    executing  ElideDigit()
> On  'CLEAR'        goto ENTRY    executing  ClearAccumulator()
> On  'ENTER'        goto VERIFY   executing  CheckValue()
> 
>       STATE   VERIFY
> On  'VALID'        goto DONE     executing  AcceptValue()
> On  'INVALID'      goto ERROR    executing  SignalError()
> 
>       STATE   ERROR
> On  'TIMEOUT'      goto ENTRY    executing  ClearErrorMessage()
> LinkTo                  ENTRY
> 
> Everything above this sentence can compile into as few as *30* bytes,
> despite its verbosity!  (LinkTo effectively treats the referenced
> state's rules as if they were also present in the table.  Here, it allows
> the operator to type any of the "normal" data entry keystrokes enumerated
> in the referenced state -- ENTRY -- and have them terminate the error
> message -- without having to wait for the TIMEOUT)
> 
> AccumulateDigit() {
>      accumulator = 10*accumulator + (input-'0')
>      DisplayAccumulator()
> }
> 
> ElideDigit() {
>      accumulator /= 10
>      DisplayAccumulator()
> }
> 
> CheckValue() {
>      signal( ((accumulator >= MIN) && (accumlator <= MAX)) ?
>              'VALID' :
>              'INVALID' )
> }
> 
> SignalError() {
>      beep()
>      DisplayString("Value out of bounds!")
>      if (Timer)
>          kill(Timer)
>      spawn(Timer)
> }
> 
> Timer() {     // nominally runs concurrently with ERROR state
>      sleep(2 sec)
>      signal(TIMEOUT)
> }
> 
> In *my* opinion, this is relatively self-explanatory.  However, it
> requires additional compile-time and run-time tools to implement.
> And, needs to be integrated with the particular O/S.
> 
> So, it's unattractive to certain clients (who want a cleaner toolchain
> or have their own O/S requirements).
> 
> [Imagine developing an entire subsystem like this -- and then discovering
> a client resists your including it (REUSING it as an ALREADY DEBUGGED
> component!) in your solution to their problem!]
> 
> Good luck!

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 02:08 +0100
  Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-06 19:37 -0700
    Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 10:11 +0100
      Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-07 07:51 -0700
        Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-07 23:51 +0100
          Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 01:39 +0200
            Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:42 +0100
              Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 18:39 +0200
          Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-08 23:12 -0700
            Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:49 +0100
          Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-08 23:12 -0700
          Re: From cooperative to preemptive scheduler: a real example Don Y <blockedofcourse@foo.invalid> - 2020-01-09 01:33 -0700
  Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-07 09:38 +0200
    Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-08 00:02 +0100
      Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 00:54 +0200
        Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-09 12:19 +0100
          Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-09 14:03 +0200
            Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-10 00:32 +0100
              Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 18:53 +0200
                Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-16 14:48 +0100
                Re: From cooperative to preemptive scheduler: a real example upsidedown@downunder.com - 2020-01-16 21:04 +0200
                Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-16 22:24 +0200
                Re: From cooperative to preemptive scheduler: a real example pozz <pozzugno@gmail.com> - 2020-01-17 02:05 +0100
                Re: From cooperative to preemptive scheduler: a real example Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-18 23:03 +0200
  Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-14 13:27 +0100
    Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-14 20:10 +0100
      Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-15 09:36 +0100
        Re: From cooperative to preemptive scheduler [Stack] Stef <stef33d@yahooI-N-V-A-L-I-D.com.invalid> - 2020-01-15 11:30 +0100
          Re: From cooperative to preemptive scheduler [Stack] pozz <pozzugno@gmail.com> - 2020-01-15 11:51 +0100
        Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-15 21:51 +0100
    Re: From cooperative to preemptive scheduler [Stack] Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 21:26 +0200
      Re: From cooperative to preemptive scheduler [Stack] Hans-Bernhard Bröker <HBBroeker@t-online.de> - 2020-01-15 22:12 +0100
        Re: From cooperative to preemptive scheduler [Stack] Niklas Holsti <niklas.holsti@tidorum.invalid> - 2020-01-15 23:30 +0200

csiph-web