Dimiter_Popoff wrote:> On 29.6.2016 г. 19:36, Les Cargill wrote: >> Dimiter_Popoff wrote: >>> On 28.6.2016 г. 17:40, Tim Wescott wrote: >>>> On Tue, 28 Jun 2016 06:20:43 +0300, Dimiter_Popoff wrote: >>>> >>>>> On 28.6.2016 г. 05:54, Simon Clubley wrote: >>>>>> >>>>> > ..... >>>>>> I still think that's a polling loop because you are reaching out to >>>>>> the >>>>>> sensor and asking it for it's current value. >>>>> >>>>> "Polling" in programming means "as opposed to interrupt handling". >>>>> How is this opposed to "interrupt handling". >>>>> >>>>> What you suggest to be polling is simply a loop of calls to >>>>> subroutines. >>>>> A "call loop" is what describes it - although it does not matter a lot >>>>> what word is used as long as it is not an already widely accepted one >>>>> like "polling" which you want to redefine. Nothing wrong with that of >>>>> course - as long as you don't have to communicate with other people >>>>> using your redefined term. >>>>> >>>>> So much talk about so little :-). Although Tim's topic idea worked, >>>>> produced quite a discussion. >>>> >>>> Well, I was hoping for a name of a design pattern, and I'm still not >>>> happy about my choices. So from that perspective it's a wash. >>>> >>>> "Super loop" seems closest, but it seems to more capture the notion of >>>> _always_ executing A, B, C, rather than executing only those bits that >>>> are ready. >>>> >>> >>> I encounter the "super loop" term for the first time here, but why not. >>> Although I see nothing "super" about it, to me this is still an endless >>> loop of calls to subroutines either of which may opt to do something >>> or to just return if it has nothing to do. >>> But like I said earlier I have almost never used this approach, it >>> smells of oversimplifying - thus costing more than a decent scheduler >>> does. Implement loops, state machines etc. as you like within tasks >>> but having a true - preemptive allowing cooperative operation- scheduler >>> costs very little in both machine resources and effort to put together >>> so I see no point in trying to avoid it. >>> >> >> Other than for ISRs, you really don't *need* preemption. > > ... > > I tend to agree with that - excepting the case of a larger system with > a user running this and that on it (in fact you still don't "need" it > there but it can be very useful, like saving you a reboot sometimes > by allowing you to kill the hogger etc.). >I've just had great luck not writing hoggers in the first place. Sometimes this puts you in the position of decomposing the problem in funny ways.> Like I said in another post here yesterday: > > > Of course, if you've got a bunch of fast tasks and even one slow one > > (reciting the Gettysburg address to a human, for instance) then a > > preemptive scheduler gets very attractive. > > > > I see the preemptive feature mostly as a backup plan, basically if the > reciter is say reciting through an UART at 9600 bps the output driver > would be exiting the task cooperatively long before being preempted > (say after filling an output FIFO of some 256 bytes or something). > But if the system is dynamic - e.g. a fullblown OS with a user in > front of it doing this and that - then preemption may well have to > kick in. >Might be convenient, but I rather doubt it's fully necessary. It's more necessary when you have to support multiple users. The Gettysburg address goes out one byte, packet or phenome at a time.> Dimiter > > >-- Les Cargill
Common name for a "Task Loop"
Started by ●June 24, 2016
Reply by ●June 30, 20162016-06-30
Reply by ●June 30, 20162016-06-30
On 01.7.2016 г. 01:07, Les Cargill wrote:> Dimiter_Popoff wrote: >> On 29.6.2016 г. 19:36, Les Cargill wrote: >>> Dimiter_Popoff wrote: >>>> On 28.6.2016 г. 17:40, Tim Wescott wrote: >>>>> On Tue, 28 Jun 2016 06:20:43 +0300, Dimiter_Popoff wrote: >>>>> >>>>>> On 28.6.2016 г. 05:54, Simon Clubley wrote: >>>>>>> >>>>>> > ..... >>>>>>> I still think that's a polling loop because you are reaching out to >>>>>>> the >>>>>>> sensor and asking it for it's current value. >>>>>> >>>>>> "Polling" in programming means "as opposed to interrupt handling". >>>>>> How is this opposed to "interrupt handling". >>>>>> >>>>>> What you suggest to be polling is simply a loop of calls to >>>>>> subroutines. >>>>>> A "call loop" is what describes it - although it does not matter a >>>>>> lot >>>>>> what word is used as long as it is not an already widely accepted one >>>>>> like "polling" which you want to redefine. Nothing wrong with that of >>>>>> course - as long as you don't have to communicate with other people >>>>>> using your redefined term. >>>>>> >>>>>> So much talk about so little :-). Although Tim's topic idea worked, >>>>>> produced quite a discussion. >>>>> >>>>> Well, I was hoping for a name of a design pattern, and I'm still not >>>>> happy about my choices. So from that perspective it's a wash. >>>>> >>>>> "Super loop" seems closest, but it seems to more capture the notion of >>>>> _always_ executing A, B, C, rather than executing only those bits that >>>>> are ready. >>>>> >>>> >>>> I encounter the "super loop" term for the first time here, but why not. >>>> Although I see nothing "super" about it, to me this is still an endless >>>> loop of calls to subroutines either of which may opt to do something >>>> or to just return if it has nothing to do. >>>> But like I said earlier I have almost never used this approach, it >>>> smells of oversimplifying - thus costing more than a decent scheduler >>>> does. Implement loops, state machines etc. as you like within tasks >>>> but having a true - preemptive allowing cooperative operation- >>>> scheduler >>>> costs very little in both machine resources and effort to put together >>>> so I see no point in trying to avoid it. >>>> >>> >>> Other than for ISRs, you really don't *need* preemption. >> > ... >> >> I tend to agree with that - excepting the case of a larger system with >> a user running this and that on it (in fact you still don't "need" it >> there but it can be very useful, like saving you a reboot sometimes >> by allowing you to kill the hogger etc.). >> > > > I've just had great luck not writing hoggers in the first place. > Sometimes this puts you in the position of decomposing the problem > in funny ways.Well this is not down to luck of course. I have not written any hoggers either - except willingly, like the "hog" command for DPS I mentioned earlier. Does a "bra *", sometimes I use it to see how this or that behaves under severe system load. Dimiter
Reply by ●July 1, 20162016-07-01
On 2016-06-28, Don Y <blockedofcourse@foo.invalid> wrote:> > Now, imagine I make the "FSM interfaces" interface to a *model* of > a FSM! There's no IO involved. No "sensors". Just "data" driven > by an "isolated" algorithm that is pretending to be a piece of > hardware. > > Is this still "polling"? Or, something else -- because it is not interfacing > with "sensors"? Even sensors who can be accessed unconditionally in the > same way that the outputs of a simulator could? > > I.e., I could rewrite the Fibonacci example as a task interfacing to > a "Fibonacci simulator". *Or*, a hardware device that was a "Fibonacci > generator"! It's the same application -- that can be implemented > with virtually identical code (see my FSM example, above). Yet, > you arbitrarily call it different things? >I'd say that's just a normal compute bound application. The difference between your examples and what started this thread is that the main loop in Tim's examples are about responding to external hardware events whereas yours are purely internal software constructs. Simon. -- Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP Microsoft: Bringing you 1980s technology to a 21st century world
Reply by ●July 2, 20162016-07-02
On Thu, 30 Jun 2016 02:33:24 -0700, Don Y <blockedofcourse@foo.invalid> wrote:>On 6/29/2016 11:02 PM, upsidedown@downunder.com wrote: > >>> Ah, but that's the problem! You now need stacks for each task >>> (each large enough to satisfy the task's worst case stack penetration >>> *plus* any stack required by ISRs -- as they can occur during any >>> task's "time slot"). >>> >>> You can save JUST the SP for each task and use that to "recover" >>> the stack and CPU registers (saved on the stack during the context >>> switch). >>> >>> But, you will alwyas be tempted to yield() (or equivalent) at some >>> arbitrary depth on the stack. I.e., you can have a dozen stack >>> frames nested FOR THIS TASK and decide to yield() -- now, all of those >>> stack frames must be preserved as part of the task's state (because >>> you picked a "less than ideal place" to yield the processor to the >>> "next" task) >> >> In preemptive systems you usually talk about a task becoming not ready >> e.g. waiting for some event. Some systems execute a Software Interrupt >> type instruction stacking the registers as a real interrupt would do. >> The stack pointer is saved into the kernel data structure. >> >> There are no nested saved register sets, there is just _one_ saved >> register set at the top of the stack. >> >> When the task finally becomes ready to run, the scheduler reloads the >> task stack pointer and then performs a Return From Interrupt, which >> pops the registers and continues with the instruction following the >> Software Interrupt instruction. >> >> So there are at most one saved register set in the task specific stack >> and it is located at the top of the stack. > >And the other tasks have NO stacks? And no "processor state" stored?After working for several decades with preemptive kernels, I thought it is self-evident that a preemptive system requires task specific stacks !!> >Note the "stack frames" that I mentioned, above, refer to the nesting of >*function calls* (or subroutine invocations) within each specific task. >I.e., you have no way of knowing how "deep" each task's stack happens to >be when the task is preempted or voluntarily yields control of the >processor.This is not relevant to the context saving discussion. You can do a quite good static stack usage analysis based on static code analysis. In many systems recursive calls are forbidden exactly for that reason.>At that point, ALL of the task's state must be preserved: its CPU registers >and its "live" stack.Self-evident.
Reply by ●July 2, 20162016-07-02
Op 02-Jul-16 om 1:27 PM schreef upsidedown@downunder.com:> On Thu, 30 Jun 2016 02:33:24 -0700, Don Y > <blockedofcourse@foo.invalid> wrote: > >> On 6/29/2016 11:02 PM, upsidedown@downunder.com wrote: >> >>>> Ah, but that's the problem! You now need stacks for each task >>>> (each large enough to satisfy the task's worst case stack penetration >>>> *plus* any stack required by ISRs -- as they can occur during any >>>> task's "time slot"). >>>> >>>> You can save JUST the SP for each task and use that to "recover" >>>> the stack and CPU registers (saved on the stack during the context >>>> switch). >>>> >>>> But, you will alwyas be tempted to yield() (or equivalent) at some >>>> arbitrary depth on the stack. I.e., you can have a dozen stack >>>> frames nested FOR THIS TASK and decide to yield() -- now, all of those >>>> stack frames must be preserved as part of the task's state (because >>>> you picked a "less than ideal place" to yield the processor to the >>>> "next" task) >>> >>> In preemptive systems you usually talk about a task becoming not ready >>> e.g. waiting for some event. Some systems execute a Software Interrupt >>> type instruction stacking the registers as a real interrupt would do. >>> The stack pointer is saved into the kernel data structure. >>> >>> There are no nested saved register sets, there is just _one_ saved >>> register set at the top of the stack. >>> >>> When the task finally becomes ready to run, the scheduler reloads the >>> task stack pointer and then performs a Return From Interrupt, which >>> pops the registers and continues with the instruction following the >>> Software Interrupt instruction. >>> >>> So there are at most one saved register set in the task specific stack >>> and it is located at the top of the stack. >> >> And the other tasks have NO stacks? And no "processor state" stored? > > After working for several decades with preemptive kernels, I thought > it is self-evident that a preemptive system requires task specific > stacks !! > >> >> Note the "stack frames" that I mentioned, above, refer to the nesting of >> *function calls* (or subroutine invocations) within each specific task. >> I.e., you have no way of knowing how "deep" each task's stack happens to >> be when the task is preempted or voluntarily yields control of the >> processor. > > This is not relevant to the context saving discussion. > > You can do a quite good static stack usage analysis based on static > code analysis. In many systems recursive calls are forbidden exactly > for that reason.Do you have experience (or know) any tools that do this? Wouter "Objects? No Thanks!" van Ooijen
Reply by ●July 2, 20162016-07-02
On 7/2/2016 4:27 AM, upsidedown@downunder.com wrote:> On Thu, 30 Jun 2016 02:33:24 -0700, Don Y>>>> But, you will alwyas be tempted to yield() (or equivalent) at some >>>> arbitrary depth on the stack. I.e., you can have a dozen stack >>>> frames nested FOR THIS TASK and decide to yield() -- now, all of those >>>> stack frames must be preserved as part of the task's state (because >>>> you picked a "less than ideal place" to yield the processor to the >>>> "next" task) >>> >>> In preemptive systems you usually talk about a task becoming not ready >>> e.g. waiting for some event. Some systems execute a Software Interrupt >>> type instruction stacking the registers as a real interrupt would do. >>> The stack pointer is saved into the kernel data structure. >>> >>> There are no nested saved register sets, there is just _one_ saved >>> register set at the top of the stack. >>> >>> When the task finally becomes ready to run, the scheduler reloads the >>> task stack pointer and then performs a Return From Interrupt, which >>> pops the registers and continues with the instruction following the >>> Software Interrupt instruction. >>> >>> So there are at most one saved register set in the task specific stack >>> and it is located at the top of the stack. >> >> And the other tasks have NO stacks? And no "processor state" stored? > > After working for several decades with preemptive kernels, I thought > it is self-evident that a preemptive system requires task specific > stacks !!Now, walk back up-thread to my comment to Dimiter: Imagine having a few HUNDRED bytes of RAM, *total* in your system. How much of this do you "divert" to implementing a formal scheduler? How much do you devote to preserving the state(s) of independant tasks?>> Note the "stack frames" that I mentioned, above, refer to the nesting of >> *function calls* (or subroutine invocations) within each specific task. >> I.e., you have no way of knowing how "deep" each task's stack happens to >> be when the task is preempted or voluntarily yields control of the >> processor. > > This is not relevant to the context saving discussion.Again, walk back up-thread and please find try to see *if* I claimed it to be part of the context switch. You're missing the appeal of NOT including any "stacked task state" in the PRESERVED TASK STATE; namely, that the amount of RAM that you dedicate to stack usage -- ALL stacks -- in the design is the maximum of all tasks' stack penetration plus the ISR penetration. You never have more than one stack "live" in the system! "If, instead, you ensure all context switches occur when there is NOTHING on the 'task-specific stack', then all tasks can SHARE a stack (because you've ensured that the stack will be empty BEFORE you allow a reschedule() event).> You can do a quite good static stack usage analysis based on static > code analysis. In many systems recursive calls are forbidden exactly > for that reason. > >> At that point, ALL of the task's state must be preserved: its CPU registers >> and its "live" stack. > > Self-evident.But not necessary to work in a multitasking environment! Even with a HLL (though operating with NOTHING preserved on the stack in a HLL environment imposes lots of constraints -- with which the compiler WON'T help!): task() { some_variable_declarations; <---- disallowed ... some_function(); ... taskX(); <---- disallowed ... yield(); <---- allowed ... } some_function() { ... yield(); <------ disallowed ... } OTOH, there's nothing wrong with: task() { ... global = value; <---- allowed ... another_function(); <---- allowed ... yield(); <---- allowed ... } another_function() { some_variable_declarations; ... some_other_function(); ... another_function(); // recursive ... } This latter form is quite "comfortable", after some experience. (Replace C with your language of choice)
Reply by ●July 2, 20162016-07-02
On 16-07-02 15:50 , Wouter van Ooijen wrote:> Op 02-Jul-16 om 1:27 PM schreef upsidedown@downunder.com: >> On Thu, 30 Jun 2016 02:33:24 -0700, Don Y >> <blockedofcourse@foo.invalid> wrote: >> >>> On 6/29/2016 11:02 PM, upsidedown@downunder.com wrote: >>> >>>>> Ah, but that's the problem! You now need stacks for each task >>>>> (each large enough to satisfy the task's worst case stack penetration >>>>> *plus* any stack required by ISRs -- as they can occur during any >>>>> task's "time slot"). >>>>> >>>>> You can save JUST the SP for each task and use that to "recover" >>>>> the stack and CPU registers (saved on the stack during the context >>>>> switch). >>>>> >>>>> But, you will alwyas be tempted to yield() (or equivalent) at some >>>>> arbitrary depth on the stack. I.e., you can have a dozen stack >>>>> frames nested FOR THIS TASK and decide to yield() -- now, all of those >>>>> stack frames must be preserved as part of the task's state (because >>>>> you picked a "less than ideal place" to yield the processor to the >>>>> "next" task) >>>> >>>> In preemptive systems you usually talk about a task becoming not ready >>>> e.g. waiting for some event. Some systems execute a Software Interrupt >>>> type instruction stacking the registers as a real interrupt would do. >>>> The stack pointer is saved into the kernel data structure. >>>> >>>> There are no nested saved register sets, there is just _one_ saved >>>> register set at the top of the stack. >>>> >>>> When the task finally becomes ready to run, the scheduler reloads the >>>> task stack pointer and then performs a Return From Interrupt, which >>>> pops the registers and continues with the instruction following the >>>> Software Interrupt instruction. >>>> >>>> So there are at most one saved register set in the task specific stack >>>> and it is located at the top of the stack. >>> >>> And the other tasks have NO stacks? And no "processor state" stored? >> >> After working for several decades with preemptive kernels, I thought >> it is self-evident that a preemptive system requires task specific >> stacks !! >> >>> >>> Note the "stack frames" that I mentioned, above, refer to the nesting of >>> *function calls* (or subroutine invocations) within each specific task. >>> I.e., you have no way of knowing how "deep" each task's stack happens to >>> be when the task is preempted or voluntarily yields control of the >>> processor. >> >> This is not relevant to the context saving discussion. >> >> You can do a quite good static stack usage analysis based on static >> code analysis. In many systems recursive calls are forbidden exactly >> for that reason. > > Do you have experience (or know) any tools that do this?Google "static stack usage analysis" for links. Compilers from IAR Systems can do it, at least for some targets. AdaCore provide the "gnatstack" tool which can also do it, in conjunction with AdaCore's compilers. StackAnalyzer (www.absint.com) and Bound-T (www.bound-t.com) can do it. GCC option "-fstack-usage" gives per-function stack usage. For the AVR target, a Perl script can be used to add those up along call-paths to get per-thread stack usage (http://dlbeer.co.nz/oss/avstack.html). I have experience with Bound-T (well, I'm the developer) and some with IAR compilers. As long as all calls and stack-space allocations are static the tools work well; when either calls or stack allocations become dynamic (e.g. virtual function calls) you run into problems, but at least the commercial tools have means to work around those problems. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ .
Reply by ●July 2, 20162016-07-02
On Sat, 02 Jul 2016 07:36:34 -0700, Don Y <blockedofcourse@foo.invalid> wrote:>On 7/2/2016 4:27 AM, upsidedown@downunder.com wrote: >> On Thu, 30 Jun 2016 02:33:24 -0700, Don Y > >>>>> But, you will alwyas be tempted to yield() (or equivalent) at some >>>>> arbitrary depth on the stack. I.e., you can have a dozen stack >>>>> frames nested FOR THIS TASK and decide to yield() -- now, all of those >>>>> stack frames must be preserved as part of the task's state (because >>>>> you picked a "less than ideal place" to yield the processor to the >>>>> "next" task) >>>> >>>> In preemptive systems you usually talk about a task becoming not ready >>>> e.g. waiting for some event. Some systems execute a Software Interrupt >>>> type instruction stacking the registers as a real interrupt would do. >>>> The stack pointer is saved into the kernel data structure. >>>> >>>> There are no nested saved register sets, there is just _one_ saved >>>> register set at the top of the stack. >>>> >>>> When the task finally becomes ready to run, the scheduler reloads the >>>> task stack pointer and then performs a Return From Interrupt, which >>>> pops the registers and continues with the instruction following the >>>> Software Interrupt instruction. >>>> >>>> So there are at most one saved register set in the task specific stack >>>> and it is located at the top of the stack. >>> >>> And the other tasks have NO stacks? And no "processor state" stored? >> >> After working for several decades with preemptive kernels, I thought >> it is self-evident that a preemptive system requires task specific >> stacks !! > >Now, walk back up-thread to my comment to Dimiter: > > Imagine having a few HUNDRED bytes of RAM, *total* in your system. > How much of this do you "divert" to implementing a formal scheduler? > How much do you devote to preserving the state(s) of independant tasks?On some small systems I have worked with, I have initially allocated 64 bytes stack space for each task or something more, if the manual static analysis would demand. Also filling each task with a known pattern and checking after a week how much has actually been used and reduced the stack allocation accordingly. In one case the kernel data structure was just 3 bytes for each task, two bytes to store the stack pointer for each task and one byte to contain the task state, such as not ready, ready and running.Slightly more RAM efficient would be to use 8 or 16 task states (runnable or not) into 1 or 2 bytes. With 64 bytes/task, you could fit 3 tasks into 200 bytes and six into 400 bytes of RAM.
Reply by ●July 2, 20162016-07-02
On 7/2/2016 11:44 AM, upsidedown@downunder.com wrote:> With 64 bytes/task, you could fit 3 tasks into 200 bytes and six into > 400 bytes of RAM.With 3 tasks, you probably couldn't implement a municipal traffic light controller! (don't forget the globals and ISR's) (Yes, you could *do* it -- as one big spaghetti loop) - Run the normal light cycle (go/caution/stop) - Sense vehicles waiting in the turn lanes to conditionally qualify those by injecting the "turn arrow" controls - Sense traffic proceeding through the intersection and waiting at cross streets (to adjust the timing of the cycles) - Communicate with the other processes (so if oncoming is allowing left turns, YOU should probably do so as well -- or not!) - Sense a demand for a "walk" signal - Control the walk/countdown/don't walk signals - Monitor for on-coming emergency vehicles - Indicate recognition of said vehicles and adjust traffic cycles accordingly. - Communicate with municipal controlling algorithms/time-of-day scheduling. - Allow on-site overrides. - Support run-time diagnostics (fallback modes) And, we're not even worrying about red-light cameras or general surveillance cameras! 1980's era (arcade) video games would treat each object on the screen as a task. So, 50 - 100 objects all acting independantly without concern for their "neighbors" (unless their neighbor was something that they could kill or be killed by). I run 5 tasks to decode a barcode (without "consuming" it) My "fallback" speech synthesizers each require more than a dozen tasks. Etc. I.e., I *like* decomposing projects into more manageable pieces -- get it right the first time!
Reply by ●July 3, 20162016-07-03
On 03.7.2016 г. 00:36, Don Y wrote:> On 7/2/2016 11:44 AM, upsidedown@downunder.com wrote: >> With 64 bytes/task, you could fit 3 tasks into 200 bytes and six into >> 400 bytes of RAM. > > With 3 tasks, you probably couldn't implement a municipal traffic light > controller! (don't forget the globals and ISR's)Don, even splitting things in two tasks can be quite helpful. Say one handling the I/O and the other the rest. Having a multitask scheduler does not mean you don't use loops. You do of course - practically always. You just don't have to care about what the scheduler gives you in every subroutine you write - just call the "task exit for rescheduling" call when your code has to wait. If you don't have the scheduler you will have to care about this every step of the way, make sure you know where your current stack pointer is (subroutine calls; then a subroutine which exits cannot be just called from any nesting level etc. etc.). If we really have to count the bytes of RAM - let us say we turn the clock 25 years back - we can statically assign as much stack as needed to each task. We may find out that splitting in 3 tasks can at times _save_ memory above a certain complexity... I thought we'd be done with counting for days every byte by now, last "small" MCU I used was a coldfire in tqfp100 with 16k RAM and a sort of 68000 running at 80 MHz.... I just copied and slightly adapted the initial (68340 from 1994) DPS scheduler and trap handler, cost me virtually nothing. http://tgi-sci.com/dsv/swgboard.gif http://tgi-sci.com/dsv/swg800.gif http://tgi-sci.com/misc/PICT6999.avi http://tgi-sci.com/tgi/auxhv.htm No picture of the last, this MCU replaced a huge computer board in an 8 channel Ortec alpha counting system so they could use two netmca-s to simultaneously select any two vacuum chhambers to count, measure the vacuum and plenty of other internals, the analog part was intact). And such an MCU costs well below $10 at Mouser or the likes for a single piece.... Dimiter ------------------------------------------------------ Dimiter Popoff, TGI http://www.tgi-sci.com ------------------------------------------------------ http://www.flickr.com/photos/didi_tgi/
